Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles

• URL: http://arxiv.org/abs/2607.17607v1
• Date: Mon, 20 Jul 2026 06:53:59 GMT
• Title: Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
• Abstract summary: Non optimization can be reduced to ordinary static in online convex optimization in a black-box manner.<n>For smooth non objectives, our reduction maintains a predictable gradient tracker, while a black-box online selects a fixed $M.<n>A black-box online selects a.<n>black-box online selects a gradient tracker that determines how the tracker is transformed into a gradient.<n>A.<n>black-box online selects a fixed $M that determines how the tracker is transformed into a gradient.<n>A.<n>black-box online selects a gradient tracker that determines how the tracker is transformed into a
• Score: 15.386375612838371
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study whether stochastic nonconvex optimization can be reduced to ordinary static regret minimization in online convex optimization in a black-box manner. For smooth nonconvex objectives, our reduction maintains a predictable gradient tracker, while a black-box online learner selects a preconditioner that determines how this tracker is transformed into the update direction. The learner receives linear convex losses and is evaluated against a single fixed comparator over one undiscounted online game. For a $β$-smooth objective with range bounded by $M$ and an unbiased stochastic-gradient oracle with variance bounded by \(σ^2\), we establish $$\frac{1}{T}\sum_{t=1}^T \mathbb E\!\left[\|\nabla f(x_t)\|_2^2\right] \lesssim \frac{σ\sqrt{Mβ}}{\sqrt T} + \frac{\sqrt{Mβ}\, \mathscr R_T(\mathcal A,I_d)}{T} + \frac{Mβ}{T}.$$ Consequently, any black-box OCO algorithm with $\mathscr R_T(\mathcal A,I_d)=O(\sqrt T)$ recovers the classical $O(\frac{1}{\sqrt{T}})$ convergence rate. We further show that the same black-box framework extends beyond the smooth setting to Lipschitz nonconvex objectives without Lipschitz continuous gradients. Importantly, this extension continues to rely only on an ordinary static-regret guarantee and requires no stronger notion of online regret. When the OCO oracle admits square-root static regret, the resulting conversion achieves the optimal $O(T^{-2/7})$ convergence rate for the corresponding Goldstein stationary point. These results resolve the open problem posed by Chen and Hazan (2024). More broadly, our framework separates optimizer design into gradient prediction and online preconditioner selection, providing a principled perspective on how adaptive optimization methods such as AdaGrad and Shampoo may be understood through static regret and applied in nonconvex optimization.

Related papers

• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  We introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman.<n>Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $mathcalO(log V_T)$ regret for strongly convex functions and $mathcalO(d log V_T)$ regret for exp-concave functions.
  arXiv  Detail & Related papers  (2025-11-25T05:23:10Z)
• Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism [25.642618010943824]
  We introduce an online optimistic gradient method based on a novel doubly optimistic hint function.<n>We obtain an algorithm unified with $1.75 + sigma2 varepsilon-3.5)$, smoothly interpolating between the best-known deterministic rate and the optimal rate.
  arXiv  Detail & Related papers  (2025-10-03T16:41:24Z)
• Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD [16.019880089338383]
  We show that Clipped-SGD, for smooth and strongly convex objectives, achieves an error of $sqrtfracmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsf
  arXiv  Detail & Related papers  (2024-10-26T10:14:17Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  We define an online learning and optimization problem with discrete and irreversible decisions contributing toward a coverage target.<n>In each period, a decision-maker selects facilities to open, receives information on the success of each one, and updates a classification model to guide future decisions.<n>The goal is to minimize facility openings under a chance constraint reflecting the coverage target, in an horizon regime characterized by a large target number of facilities.
  arXiv  Detail & Related papers  (2024-06-20T23:00:25Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  Adaptive gradient methods are among the most successful neural network training algorithms.<n>These methods are known to achieve better dimensional dependence than over convex SGD-normarity.<n>In this paper we introduce new assumptions on the smoothness of the structure and the gradient noise variance.
  arXiv  Detail & Related papers  (2024-06-07T02:55:57Z)
• 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)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  We study unconstrained Online Linear Optimization with Lipschitz losses. Motivated by the pursuit of instance optimality, we propose a new algorithm. Central to these results is a continuous time approach to online learning.
  arXiv  Detail & Related papers  (2023-09-27T21:54:52Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  We show that our algorithms converge without any prior knowledge on the parameters of the problem.<n>All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function.<n>We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  We study policy optimization in an infinite horizon, $gamma$-discounted constrained Markov decision process (CMDP) Our objective is to return a policy that achieves large expected reward with a small constraint violation. We propose a generic primal-dual framework that allows us to bound the reward sub-optimality and constraint violation for arbitrary algorithms.
  arXiv  Detail & Related papers  (2022-04-11T15:08:09Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization [33.346773349614715]
  We propose a novel ProAbistic Gradient Estorimat (fract) for nonepsOmega. It is easy to implement as it is designed via a small PAGE to vanilla SGD. Not only converges much faster than SGD in training but also achieves the higher accuracy.
  arXiv  Detail & Related papers  (2020-08-25T09:11:31Z)

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.