mlsanityData to 7 Oct 2026

Efficiency of minimizing compositions of convex functions and smooth maps

arXiv 1605.00125 ↗First posted 30 Apr 2016math.OCcited by 59

Not on the map. Why?

Abstract (arXiv)

We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency O(varepsilon-2), akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by first-order methods, a simple combination of smoothing, the prox-linear method, and a fast-gradient scheme yields an algorithm with complexity widetildeO(varepsilon-3). The technique readily extends to minimizing an average of m composite functions, with complexity widetildeO(m/varepsilon2+√m/varepsilon3) in expectation. We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity.

Key facts. Cited by 59 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Apr 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 14; 2023: 17; 2024: 8; 2025: 7; 2026: 6.

59 papers.

Sort:

By area:

  1. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  2. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  3. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  4. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  5. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  6. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  7. 2021Bayesian Optimization of Function Networkscited by 33
  8. 2022When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guaranteecited by 29
  9. 2022Thinking inside the box: A tutorial on grey-box Bayesian optimizationcited by 26
  10. 2022Policy Optimization over General State and Action Spacescited by 21
  11. 2022Large-scale Optimization of Partial AUC in a Range of False Positive Ratescited by 15
  12. 2023A Stochastic Proximal Polyak Step Sizecited by 15
38 more
  1. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  2. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  3. 2024Weakly Convex Regularisers for Inverse Problems: Convergence of Critical Points and Primal-Dual Optimisationcited by 12
  4. 2023Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimizationcited by 11
  5. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  6. 2021Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimizationcited by 10
  7. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  8. 2024Learning with Logical Constraints but without Shortcut Satisfactioncited by 10
  9. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  10. 2023Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERMcited by 8
  11. 2025A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimizationcited by 8
  12. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  13. 2023Moreau Envelope Based Difference-of-weakly-Convex Reformulation and Algorithm for Bilevel Programscited by 7
  14. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  15. 2023Accelerated First-Order Optimization under Nonlinear Constraintscited by 5
  16. 2023A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Propertiescited by 5
  17. 2025Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraintscited by 5
  18. 2024Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensingcited by 4
  19. 2022Regret Bounds for Noise-Free Cascaded Kernelized Banditscited by 3
  20. 2023Bayesian Optimization for Function Compositions with Applications to Dynamic Pricingcited by 3
  21. 2023Soft ascent-descent as a stable and flexible alternative to floodingcited by 3
  22. 2024Stochastic Weakly Convex Optimization Beyond Lipschitz Continuitycited by 3
  23. 2024Linear convergence of proximal descent schemes on the Wasserstein spacecited by 3
  24. 2025Beyond Scores: Proximal Diffusion Modelscited by 3
  25. 2022Efficient algorithms for implementing incremental proximal-point methodscited by 2
  26. 2023Linearization Algorithms for Fully Composite Optimizationcited by 2
  27. 2023Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Setscited by 2
  28. 2023Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraintscited by 2
  29. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  30. 2026Finding a stationary point of a stochastic convex problemcited by 2
  31. 2022Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimizationcited by 1
  32. 2023A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrievalcited by 1
  33. 2023Modified Gauss-Newton Algorithms under Noisecited by 1
  34. 2024The inexact power augmented Lagrangian method for constrained nonconvex optimizationcited by 1
  35. 2026Rethinking Neural Network Learning Rates: A Stackelberg Perspectivecited by 1
  36. 2026Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularitycited by 1
  37. 2021Robust Regression via Model Based Methodscited by 0
  38. 2021Federated Learning with Superquantile Aggregation for Heterogeneous Datacited by 0

50 most cited of 59 All 59 (JSON)