mlsanityData to 14 Oct 2026

Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

arXiv 1407.1537 ↗First posted 6 Jul 2014cs.DS cs.LG cs.NAcited by 58

Not on the map. Why?

Abstract (arXiv)

First-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamentally rely on two types of algorithmic steps: gradient descent, which yields primal progress, and mirror descent, which yields dual progress. We observe that the performances of gradient and mirror descent are complementary, so that faster algorithms can be designed by LINEARLY COUPLING the two. We show how to reconstruct Nesterov's accelerated gradient methods using linear coupling, which gives a cleaner interpretation than Nesterov's original proofs. We also discuss the power of linear coupling by extending it to many other settings that Nesterov's methods cannot apply to.

Key facts. Cited by 58 papers in the map (data through 14 Oct 2026). First posted on arXiv 6 Jul 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 17; 2022: 11; 2023: 8; 2024: 11; 2025: 10; 2026: 1.

58 papers.

Sort:

By area:

  1. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  2. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  3. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
  4. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  5. 2022Learning from Future: A Novel Self-Training Framework for Semantic Segmentationcited by 21
  6. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  7. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  8. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  9. 2021A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipcited by 15
  10. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  11. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  12. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
38 more
  1. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  2. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  3. 2023Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithmscited by 10
  4. 2023Accelerating optimization over the space of probability measurescited by 10
  5. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  6. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  7. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  8. 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
  9. 2021Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentumcited by 7
  10. 2023Improved Rate of First Order Algorithms for Entropic Optimal Transportcited by 7
  11. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  12. 2024Stacking as Accelerated Gradient Descentcited by 5
  13. 2024Accelerated Preference Optimization for Large Language Model Alignmentcited by 5
  14. 2025CyclicReflex: Improving Reasoning Models via Cyclical Reflection Token Schedulingcited by 5
  15. 2025A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descentcited by 5
  16. 2021Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimizationcited by 4
  17. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  18. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  19. 2024Computing Optimal Regularizers for Online Linear Optimizationcited by 4
  20. 2021Understanding Riemannian Acceleration via a Proximal Extragradient Frameworkcited by 3
  21. 2022Analysis of Dual-Based PID Controllers through Convolutional Mirror Descentcited by 3
  22. 2022Optimistic Optimisation of Composite Objective with Exponentiated Updatecited by 3
  23. 2023Diffusion Sampling with Momentum for Mitigating Divergence Artifactscited by 3
  24. 2025Bant: Byzantine Antidote via Trial Function and Trust Scorescited by 3
  25. 2025Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimizationcited by 3
  26. 2025Natural Gradient VI: Guarantees for Non-Conjugate Modelscited by 3
  27. 2021Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Gamescited by 2
  28. 2023A Variational Perspective on High-Resolution ODEscited by 2
  29. 2024Accelerated regularized learning in finite N-person gamescited by 2
  30. 2025Smooth Quasar-Convex Optimization with Constraintscited by 2
  31. 2021Near Optimal Policy Optimization via REPScited by 1
  32. 2021Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphscited by 1
  33. 2024Decentralized Sum-of-Nonconvex Optimizationcited by 1
  34. 2024Level Set Teleportation: An Optimization Perspectivecited by 1
  35. 2024Faster Acceleration for Steepest Descentcited by 1
  36. 2025Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L0, L1)-Smoothnesscited by 1
  37. 2025A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applicationscited by 1
  38. 2022Accelerated Gradient Flow: Risk, Stability, and Implicit Regularizationcited by 0

50 most cited of 58 All 58 (JSON)