mlsanityData to 14 Oct 2026

Optimal Complexity and Certification of Bregman First-Order Methods

arXiv 1911.08510 ↗First posted 19 Nov 2019math.OC cs.NA math.NAcited by 16

Not on the map. Why?

Abstract (arXiv)

We provide a lower bound showing that the O(1/k) convergence rate of the NoLips method (a.k.a. Bregman Gradient) is optimal for the class of functions satisfying the h-smoothness assumption. This assumption, also known as relative smoothness, appeared in the recent developments around the Bregman Gradient method, where acceleration remained an open issue. On the way, we show how to constructively obtain the corresponding worst-case functions by extending the computer-assisted performance estimation framework of Drori and Teboulle (Mathematical Programming, 2014) to Bregman first-order methods, and to handle the classes of differentiable and strictly convex functions.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). First posted on arXiv 19 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

16 papers.

Sort:

  1. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  2. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  3. 2021Acceleration in Distributed Optimization under Similaritycited by 17
  4. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  5. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  6. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9
  7. 2022Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopescited by 7
  8. 2021First-Order Methods for Convex Optimizationcited by 4
  9. 2021Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimizationcited by 4
  10. 2021Adaptive first-order methods revisited: Convex optimization without Lipschitz requirementscited by 4
  11. 2025On exploration of an interior mirror descent flow for stochastic nonconvex constrained problemcited by 3
  12. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 3
4 more
  1. 2025Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleadingcited by 2
  2. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0
  3. 2026Entropy-Smooth Convex Optimization Cannot Be Acceleratedcited by 0
  4. 2026Mirror descent algorithms with logarithmic barrierscited by 0