Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection
We formulate and study a fundamental search and detection problem, Schedule Optimization, motivated by a variety of real-world applications, ranging from monitoring content changes on the web, social networks, and user activities to detecting failure on large systems with many individual machines. We consider a large system consists of many nodes, where each node has its own rate of generating new events, or items. A monitoring application can probe a small number of nodes at each step, and our goal is to compute a probing schedule that minimizes the expected number of undiscovered items at the system, or equivalently, minimizes the expected time to discover a new item in the system. We study the Schedule Optimization problem both for deterministic and randomized memoryless algorithms. We provide lower bounds on the cost of an optimal schedule and construct close to optimal schedules with rigorous mathematical guarantees. Finally, we present an adaptive algorithm that starts with no prior information on the system and converges to the optimal memoryless algorithms by adapting to observed data.
Code (0)
등록된 구현이 없습니다.
Tasks
Event DetectionSimilar Papers 제목 키워드 기반
Optimal Linear Decay Learning Rate Schedules and Further Refinements
Learning rate schedules used in practice bear little resemblance to those recommended by theory. We close much of this theory/practice gap, and as a consequence are able to derive new problem-adaptive learning rate sched…
SchedulingAPEX: Learning Adaptive Priorities for Multi-Objective Alignment in Vision-Language Generation
Multi-objective alignment for text-to-image generation is commonly implemented via static linear scalarization, but fixed weights often fail under heterogeneous rewards, leading to optimization imbalance where models ove…
Text-to-Image GenerationKareus: Joint Reduction of Dynamic and Static Energy in Large Model Training
The computing demand of AI is growing at an unprecedented rate, but energy supply is not keeping pace. As a result, energy has become an expensive and contended resource that requires explicit management and optimization…
ProbeLLM: Automating Principled Diagnosis of LLM Failures
Understanding how and why large language models (LLMs) fail is becoming a central challenge as models rapidly evolve and static evaluations fall behind. While automated probing has been enabled by dynamic test generation…
SOPE: Stabilizing Off-Policy Evaluation for Online RL with Prior Data
Incorporating prior data into online reinforcement learning accelerates training but typically forces a difficult trade-off between high computational costs and long, multi-stage training pipelines. While fixed-length st…
Computational EfficiencyReinforcement LearningContinuous Control