Online Optimization with Memory and Competitive Control
- URL: http://arxiv.org/abs/2002.05318v3
- Date: Fri, 8 Jan 2021 06:24:19 GMT
- Title: Online Optimization with Memory and Competitive Control
- Authors: Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, Adam Wierman
- Abstract summary: This paper presents competitive algorithms for a class of online optimization problems with memory.
We show a connection between online optimization with memory and online control with adversarial disturbances.
- Score: 43.974996526016305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents competitive algorithms for a novel class of online
optimization problems with memory. We consider a setting where the learner
seeks to minimize the sum of a hitting cost and a switching cost that depends
on the previous $p$ decisions. This setting generalizes Smoothed Online Convex
Optimization. The proposed approach, Optimistic Regularized Online Balanced
Descent, achieves a constant, dimension-free competitive ratio. Further, we
show a connection between online optimization with memory and online control
with adversarial disturbances. This connection, in turn, leads to a new
constant-competitive policy for a rich class of online control problems.
Related papers
- A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
We address the problem of dynamically pricing complementary items that are sequentially displayed to customers.
Coherent pricing policies for complementary items are essential because optimizing the pricing of each item individually is ineffective.
We empirically evaluate our approach using synthetic settings randomly generated from real-world data, and compare its performance in terms of constraints violation and regret.
arXiv Detail & Related papers (2024-07-08T09:55:31Z) - Best of Both Worlds in Online Control: Competitive Ratio and Policy
Regret [61.59646565655169]
We show that several recently proposed online control algorithms achieve the best of both worlds: sublinear regret vs. the best DAC policy selected in hindsight.
We conclude that sublinear regret vs. the optimal competitive policy is attainable when the linear dynamical system is unknown.
arXiv Detail & Related papers (2022-11-21T07:29:08Z) - Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
-freeness in online learning refers to the adaptivity of an algorithm with respect to the optimal decision in hindsight.
In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the optimistic updates required by parameter-freeness.
We propose a simple yet powerful algorithm for Online Linear Optimization (OLO) with switching cost, which improves the existing suboptimal regret bound [ZCP22a] to the optimal rate.
arXiv Detail & Related papers (2022-05-13T18:44:27Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
We investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO)
We show that the proposed algorithm can minimize the adaptive regret with switching cost in every interval.
arXiv Detail & Related papers (2022-05-02T08:48:22Z) - Smoothed Online Combinatorial Optimization Using Imperfect Predictions [27.201074566335222]
We study smoothed online optimization problems when an imperfect predictive model is available.
We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost.
Our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.
arXiv Detail & Related papers (2022-04-23T02:30:39Z) - Online Optimization with Feedback Delay and Nonlinear Switching Cost [16.975704972827305]
We study a variant of online optimization in which the learner receives $k$-round $textitdelayed feedback$ about hitting cost.
We show that a novel Iterative Regularized Online Balanced Descent (iROBD) algorithm has a constant, dimension-free competitive ratio that is $O(L2k)$.
arXiv Detail & Related papers (2021-10-29T21:55:01Z) - Online Learning via Offline Greedy Algorithms: Applications in Market
Design and Optimization [0.0]
We focus on offline problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors.
For such problems, we provide a general framework that efficiently transforms offline robust greedy algorithms to online ones.
We show that the resulting online algorithms have $O(sqrtT)$ (approximate) regret under the full information setting.
arXiv Detail & Related papers (2021-02-18T19:05:26Z) - Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
We study the problem of Online Convex Optimization (OCO) with memory, which allows loss functions to depend on past decisions.
In this paper, we introduce dynamic policy regret as the performance measure to design algorithms robust to non-stationary environments.
We propose a novel algorithm for OCO with memory that provably enjoys an optimal dynamic policy regret in terms of time horizon, non-stationarity measure, and memory length.
arXiv Detail & Related papers (2021-02-07T09:45:15Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.