mlsanityData to 7 Oct 2026

Tight Complexity Bounds for Optimizing Composite Objectives

arXiv 1605.08003 ↗First posted 25 May 2016math.OC cs.LG stat.MLcited by 47

Not on the map. Why?

Abstract (arXiv)

We provide tight upper and lower bounds on the complexity of minimizing the average of m convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 13; 2023: 7; 2024: 5; 2025: 2; 2026: 1.

47 papers.

Sort:

By area:

  1. 2021Machine Unlearning via Algorithmic Stabilitycited by 128
  2. 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 80
  3. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  4. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  5. 2021Personalized Federated Learning: A Unified Framework and Universal Optimization Techniquescited by 34
  6. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  7. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  8. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  9. 2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
  10. 2022Faster federated optimization under second-order similaritycited by 18
  11. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  12. 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
35 more
  1. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  2. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  3. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  4. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  5. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  6. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  7. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  8. 2024Tuning-Free Stochastic Optimizationcited by 13
  9. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  10. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  11. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  12. 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
  13. 2022DADAO: Decoupled Accelerated Decentralized Asynchronous Optimizationcited by 8
  14. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  15. 2021Stochastic Reweighted Gradient Descentcited by 7
  16. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  17. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  18. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  19. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  20. 2021Stochastic Primal-Dual Deep Unrollingcited by 4
  21. 2022Adaptive Accelerated (Extra-)Gradient Methods with Variance Reductioncited by 4
  22. 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
  23. 2023Bayesian Optimization for Function Compositions with Applications to Dynamic Pricingcited by 3
  24. 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 3
  25. 2021Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applicationscited by 2
  26. 2022Stochastic Steffensen methodcited by 2
  27. 2024Incremental Quasi-Newton Methods with Faster Superlinear Convergence Ratescited by 2
  28. 2024On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Conditioncited by 2
  29. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  30. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  31. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  32. 2021On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimizationcited by 1
  33. 2021Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimizationcited by 0
  34. 2022Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexitycited by 0
  35. 2023Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimizationcited by 0