# On Optimal Universal First-Order Methods for Minimizing Heterogeneous Sums

arXiv: https://arxiv.org/abs/2208.08549 · HTML: https://mlsanity.com/paper/2208.08549/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2022.

## Built on by (most cited first, 9 of 9)

- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [Adaptive proximal gradient methods are universal without approximation](https://mlsanity.com/paper/2402.06271/) (2024)
- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)

## Abstract (arXiv)

This work considers minimizing a sum of convex functions, each with potentially different structure ranging from nonsmooth to smooth, Lipschitz to non-Lipschitz. Nesterov's universal fast gradient method provides an optimal black-box first-order method for minimizing a single function that takes advantage of any continuity structure present without requiring prior knowledge. In this paper, we show that this landmark method (without modification) further adapts to heterogeneous sums. For example, it minimizes the sum of a nonsmooth M-Lipschitz function and an L-smooth function at a rate of  O(M2/ε2 + √L/ε)  without knowledge of M, L, or even that the objective was a sum of two terms. This rate is precisely the sum of the optimal convergence rates for each term's individual complexity class. More generally, we show that sums of varied H"older smooth functions introduce no new complexities and require at most as many iterations as is needed for minimizing each summand separately. Extensions to strongly convex and H"older growth settings as well as simple matching lower bounds are also provided.