Online Convex Optimization with Switching Cost and Delayed Gradients

• URL: http://arxiv.org/abs/2310.11880v1
• Date: Wed, 18 Oct 2023 11:06:06 GMT
• Title: Online Convex Optimization with Switching Cost and Delayed Gradients
• Authors: Spandan Senapati, Rahul Vaze
• Abstract summary: An online algorithm can choose its action using only gradient information about the previous objective function. We show that the competitive ratio for the OCO problem with quadratic switching cost is at most $4(L + 5) + frac16(L + 5)mu$. We conclude that the optimal competitive ratio for the quadratic and linear switching costs are fundamentally different in the limited information setting.
• Score: 7.903539618132858
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the online convex optimization (OCO) problem with quadratic and linear switching cost in the limited information setting, where an online algorithm can choose its action using only gradient information about the previous objective function. For $L$-smooth and $\mu$-strongly convex objective functions, we propose an online multiple gradient descent (OMGD) algorithm and show that its competitive ratio for the OCO problem with quadratic switching cost is at most $4(L + 5) + \frac{16(L + 5)}{\mu}$. The competitive ratio upper bound for OMGD is also shown to be order-wise tight in terms of $L,\mu$. In addition, we show that the competitive ratio of any online algorithm is $\max\{\Omega(L), \Omega(\frac{L}{\sqrt{\mu}})\}$ in the limited information setting when the switching cost is quadratic. We also show that the OMGD algorithm achieves the optimal (order-wise) dynamic regret in the limited information setting. For the linear switching cost, the competitive ratio upper bound of the OMGD algorithm is shown to depend on both the path length and the squared path length of the problem instance, in addition to $L, \mu$, and is shown to be order-wise, the best competitive ratio any online algorithm can achieve. Consequently, we conclude that the optimal competitive ratio for the quadratic and linear switching costs are fundamentally different in the limited information setting.

Related papers

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  We study the smoothed online optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t in response to a quadratic hitting cost and an additional squared $ell$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management. We present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal performance.
  arXiv  Detail & Related papers  (2023-10-31T22:59:23Z)
• Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
  We study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability. We introduce competitive (robust) threshold-based algorithms for both the deterministic and deterministic variants of this problem. We then propose learning-augmented algorithms that take advantage of black-box advice to achieve significantly better average-case performance.
  arXiv  Detail & Related papers  (2023-10-31T16:34:49Z)
• 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)
• 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 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 Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  We introduce the problem of online convex optimization with continuous switching constraint. We show that, for strongly convex functions, the regret bound can be improved to $O(log T)$ for $S=Omega(log T)$, and $O(minT/exp(S)+S,T)$ for $S=O(log T)$.
  arXiv  Detail & Related papers  (2021-03-21T11:43:35Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  We investigate the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost. To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the greedy algorithm which simply minimizes the weighted sum of the hitting cost and the switching cost.
  arXiv  Detail & Related papers  (2021-02-13T14:15:55Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  We study a variant of online convex optimization where the player is permitted to switch decisions at most $S$ times in expectation throughout $T$ rounds. Similar problems have been addressed in prior work for the discrete decision set setting, and more recently in the continuous setting but only with an adaptive adversary.
  arXiv  Detail & Related papers  (2021-02-07T14:47:19Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq. We show that an $epsilon$-optimistic controller can be computed efficiently by solving at most $Obig(log (1/epsilon)big)$ Riccati equations.
  arXiv  Detail & Related papers  (2020-07-13T16:30:47Z)

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.