mlsanityData to 14 Oct 2026

Non-convex online learning via algorithmic equivalence

arXiv 2205.15235 ↗First posted 30 May 2022cs.LG math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

We study an algorithmic equivalence technique between non-convex gradient descent and convex mirror descent. We start by looking at a harder problem of regret minimization in online non-convex optimization. We show that under certain geometric and smoothness conditions, online gradient descent applied to non-convex functions is an approximation of online mirror descent applied to convex functions under reparameterization. In continuous time, the gradient flow with this reparameterization was shown to be exactly equivalent to continuous-time mirror descent by Amid and Warmuth 2020, but theory for the analogous discrete time algorithms is left as an open problem. We prove an O(T^frac23) regret bound for non-convex online gradient descent in this setting, answering this open problem. Our analysis is based on a new and simple algorithmic equivalence method.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 18 of its 32 references that are in the map. First posted on arXiv 30 May 2022.

Builds on

18 of 32 references.

References · 18

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  6. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  7. 2017How to Escape Saddle Points Efficientlycited by 285
  8. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 284
  9. 2016Deep Learning without Poor Local Minimacited by 234
  10. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  11. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  12. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
6 more
  1. 2017Deep linear neural networks with arbitrary loss: All local minima are globalcited by 65
  2. 2019Robust Bi-Tempered Logistic Loss Based on Bregman Divergencescited by 61
  3. 2019Exponentiated Gradient Meets Gradient Descentcited by 32
  4. 2017Efficient Regret Minimization in Non-Convex Gamescited by 28
  5. 2020Mirrorless Mirror Descent: A Natural Derivation of Mirror Descentcited by 18
  6. 2021Fast Projection Onto Convex Smooth Constraintscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 1; 2025: 3; 2026: 2.

11 papers.

  1. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  2. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
  3. 2023Identifying Equivalent Training Dynamicscited by 9
  4. 2023Non-Convex Bilevel Optimization with Time-Varying Objective Functionscited by 8
  5. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  6. 2023Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problemscited by 4
  7. 2025Online Decision-Focused Learningcited by 4
  8. 2025Adversarial bandit optimization for approximately linear functionscited by 2
  9. 2026Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Lossescited by 1
  10. 2025Machine Unlearning for Streaming Forgettingcited by 0
  11. 2026Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedbackcited by 0