Lower Bound for Randomized First Order Convex Optimization
Not on the map. Why?
Abstract (arXiv)
We provide an explicit construction and direct proof for the lower bound on the number of first order oracle accesses required for a randomized algorithm to minimize a convex Lipschitz function.
Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Sep 2017.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 2; 2023: 3; 2024: 0; 2025: 1; 2026: 1.
9 papers.
- 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
- 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
- 2023Query lower bounds for log-concave samplingcited by 12
- 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 7
- 2021The Minimax Complexity of Distributed Optimizationcited by 6
- 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
- 2023Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimizationcited by 0
- 2025Complexity Bounds for Smooth Multiobjective Optimizationcited by 0
- 2026Optimal Stochastic Bilevel Optimization with First-Order Oraclescited by 0
- 2026Optimal Stochastic Bilevel Optimization with First-Order Oracles1 Oct 2026
- 2025Complexity Bounds for Smooth Multiobjective Optimization16 Sep 2025
- 2023Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization6 Dec 2023
- 2023Query lower bounds for log-concave sampling5 Apr 2023
- 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal9 Feb 2023
- 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimization21 Sep 2022
- 2022Efficient Convex Optimization Requires Superlinear Memory29 Mar 2022
- 2021The Minimax Complexity of Distributed Optimization1 Sep 2021
- 2021Oracle Complexity in Nonsmooth Nonconvex Optimization14 Apr 2021