A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization

• URL: http://arxiv.org/abs/2402.08621v3
• Date: Wed, 13 Nov 2024 03:24:24 GMT
• Title: A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization
• Authors: Mohammad Pedramfar, Vaneet Aggarwal,
• Abstract summary: We show that any algorithm for online linear optimization with fully adaptive adversaries is an algorithm for online convex optimization. We use this to describe general metaalgorithms to convert deterministic algorithms to zeroth order algorithms with comparable regret bounds.
• Score: 33.38582292895673
• License:
• Abstract: In this paper, we analyze the problem of online convex optimization in different settings, including different feedback types (full-information/semi-bandit/bandit/etc) in either stochastic or non-stochastic setting and different notions of regret (static adversarial regret/dynamic regret/adaptive regret). This is done through a framework which allows us to systematically propose and analyze meta-algorithms for the various settings described above. We show that any algorithm for online linear optimization with fully adaptive adversaries is an algorithm for online convex optimization. We also show that any such algorithm that requires full-information feedback may be transformed to an algorithm with semi-bandit feedback with comparable regret bound. We further show that algorithms that are designed for fully adaptive adversaries using deterministic semi-bandit feedback can obtain similar bounds using only stochastic semi-bandit feedback when facing oblivious adversaries. We use this to describe general meta-algorithms to convert first order algorithms to zeroth order algorithms with comparable regret bounds. Our framework allows us to analyze online optimization in various settings, recovers several results in the literature with a simplified proof technique, and provides new results.

Related papers

• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
  This paper introduces the notion of concavity and DR-submodularity in various settings, including monotone non-linear and DR-submodularity. A general meta-algorithmm converts linear/quadratic into ones that optimize upper-linear/quadratizable functions.
  arXiv  Detail & Related papers  (2024-04-27T06:19:30Z)
• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization [28.598226670015315]
  This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial DR-submodular optimization. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $alpha$-regret bounds or have better $alpha$-regret bounds than the state of the art.
  arXiv  Detail & Related papers  (2024-03-15T07:05:44Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  First-order optimization methods tend to inherently favor certain solutions over others when minimizing an underdetermined training objective. We present a series of state-of-the-art implicit bias rates for mirror descent and steepest descent algorithms. Our accelerated rates are derived by leveraging the regret bounds of online learning algorithms within this game framework.
  arXiv  Detail & Related papers  (2023-05-27T18:16:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• 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)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  The algorithms can be interpreted as the combination of the exponentiated gradient and $p$-norm algorithm. They achieve a sequence-dependent regret upper bound, matching the best-known bounds for sparse target decision variables.
  arXiv  Detail & Related papers  (2022-08-08T11:29:55Z)
• Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting [21.584183030149084]
  A class of parameter-free online linear optimization algorithms is proposed. They harness the structure of an adversarial sequence by adapting some side information. The proposed algorithm is further refined to achieve the best performance over all adaptive algorithms.
  arXiv  Detail & Related papers  (2022-02-04T21:56:29Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.