Online Convex Optimization with Long Term Constraints for Predictable
Sequences
- URL: http://arxiv.org/abs/2210.16735v1
- Date: Sun, 30 Oct 2022 03:50:53 GMT
- Title: Online Convex Optimization with Long Term Constraints for Predictable
Sequences
- Authors: Deepan Muthirayan, Jianjun Yuan, and Pramod P. Khargonekar
- Abstract summary: We study a specific framework of OCO called it OCO with long term constraints.
Long term constraints are introduced as an alternative to reduce the complexity of the projection at every update step in online optimization.
We show that, with a predictor that can supply the information of the next function in the sequence, our algorithm can achieve an overall regret and constraint violation rate that is strictly less than the rate that is achievable without prediction.
- Score: 5.964436882344728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we investigate the framework of Online Convex Optimization
(OCO) for online learning. OCO offers a very powerful online learning framework
for many applications. In this context, we study a specific framework of OCO
called {\it OCO with long term constraints}. Long term constraints are
introduced typically as an alternative to reduce the complexity of the
projection at every update step in online optimization. While many algorithmic
advances have been made towards online optimization with long term constraints,
these algorithms typically assume that the sequence of cost functions over a
certain $T$ finite steps that determine the cost to the online learner are
adversarially generated. In many circumstances, the sequence of cost functions
may not be unrelated, and thus predictable from those observed till a point of
time. In this paper, we study the setting where the sequences are predictable.
We present a novel online optimization algorithm for online optimization with
long term constraints that can leverage such predictability. We show that, with
a predictor that can supply the gradient information of the next function in
the sequence, our algorithm can achieve an overall regret and constraint
violation rate that is strictly less than the rate that is achievable without
prediction.
Related papers
- Efficient Methods for Non-stationary Online Learning [67.3300478545554]
We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$.
Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
arXiv Detail & Related papers (2023-09-16T07:30:12Z) - Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
This work introduces a new notion of complexity, the generalized bracketing numbers, which marries constraints on the adversary to the size of the space.
We then instantiate our bounds in several problems of interest, including online prediction and planning of piecewise continuous functions.
arXiv Detail & Related papers (2023-02-10T18:45:52Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.
An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
arXiv Detail & Related papers (2023-02-01T08:50:48Z) - Learning-Assisted Algorithm Unrolling for Online Optimization with
Budget Constraints [27.84415856657607]
We propose a new machine learning (ML) assisted unrolling approach, called LAAU (Learning-Assisted Algorithm Unrolling)
For efficient training via backpropagation, we derive gradients of the decision pipeline over time.
We also provide the average cost bounds for two cases when training data is available offline and collected online, respectively.
arXiv Detail & Related papers (2022-12-03T20:56:29Z) - Learning-Augmented Algorithms for Online Linear and Semidefinite
Programming [9.849604820019394]
Semidefinite programming (SDP) is a unifying framework that generalizes both linear and quadratically-constrained programming.
There exist known impossibility results for approxing the optimal solution when constraints for covering SDPs arrive in an online fashion.
We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution.
arXiv Detail & Related papers (2022-09-21T19:16:29Z) - 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) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities.
Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
arXiv Detail & Related papers (2021-12-29T02:42:59Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
A natural goal when designing online learning algorithms is to bound the regret of the algorithm in terms of the temporal variation of the input sequence.
Data-dependent "pathlength" regret bounds have recently been obtained for a wide variety of online learning problems, including OCO and bandits.
arXiv Detail & Related papers (2021-10-24T22:43:15Z) - Delay-Tolerant Constrained OCO with Application to Network Resource
Allocation [44.67787270821051]
We consider online convex optimization (OCO) with multi-slot feedback delay.
An agent makes a sequence of online decisions to minimize the accumulation of time-varying convex loss functions.
We propose Delay-Tolerant Constrained-OCO, which uses a novel constraint penalty with double regularization to tackle the asynchrony between information feedback and decision updates.
arXiv Detail & Related papers (2021-05-09T19:32:33Z)
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.