2018/01/23 by Yingying Li, Guannan Qu, Li, Yingying +3 · 3 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1801.07780
openalex publication_date 2018/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies an online optimization problem with a finite prediction window of cost functions and additional switching costs on decisions. We propose two gradient-based online algorithms: Receding Horizon Gradient Descent (RHGD), and Receding Horizon Accelerated Gradient (RHAG). Both algorithms only require a finite number of projected gradient evaluations at each stage. We provide upper bounds on the dynamic regrets of the proposed algorithms and show that the regret upper bounds decay exponentially with the length of the prediction window. Moreover, we study the fundamental lower bound on the dynamic regret for a broad class of deterministic online algorithms. The lower bound is close to RHAG's regret upper bound, indicating that our gradient-based RHAG is a near-optimal online algorithm. Finally, we conduct numerical experiments to complement our theoretical analysis.