Lower Bound for Randomized First Order Convex Optimization
By Blake E. Woodworth, Nati Srebro. 2017
29 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- H. Brendan McMahan
- Nati Srebro
- Peter Richtárik
- Jakub Konecný
- John C. Duchi
- Michael I. Jordan
- Zeyuan Allen-Zhu
- Blake E. Woodworth
In Computational Mechanics
- Nati Srebro
- H. Brendan McMahan
- Blake E. Woodworth
- John C. Duchi
- Zeyuan Allen-Zhu
- Jialei Wang
- Peter Richtárik
- Yair Carmon
In Computational Theory and Mathematics
- Nati Srebro
- Blake E. Woodworth
- H. Brendan McMahan
- John C. Duchi
- Jialei Wang
- Hubert Eichner
- Kunal Talwar
- Tomer Koren
Citations in the corpus
- Semi-Cyclic Stochastic Gradient Descent (2019, positive): “…≥ m/2) = 1, with the following functions taken from Woodworth et al. (2018), which in turn is based on the constructions in Arjevani & Shamir (2015); Woodworth & Srebro (2017); Carmon et al. (2017); Woodworth & Srebro (2017): f (w, 1) = η 8 ( – 2a〈v1, w〉 + φ(〈v4K , w〉) + 2K–1∑ k=1 φ(〈v2k – v2k+1,…”
- Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “In the case of the prox oracle, we “straighten out” the smooth construction of Woodworth and Srebro [27].”
- SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, background): “…+ n2K ∼ O ( n2∆2L2 4 log ( n2∆2L2 4p )) , from Lemma 2 of Carmon et al. (2017b) (or similarly Lemma 7 of Woodworth & Srebro (2016) and Theorem 3 of Woodworth & Srebro (2017), also refer to Lemma 12 in the end of the paper), with probability at least 1− p, after T = nK2 iterations (at the…”
- Lower bounds for finding stationary points I (2017, background): “The result of Lemma 4 is identical (to constant factors) to an important result of Woodworth and Srebro [45, Lemma 7], but we must be careful with the sequential conditioning of randomness between the iterates x (t), the random orthogonal U , and how much information the sequentially computed deriva”
- Lower bounds for non-convex stochastic optimization (2019, methodology): “We then lift our results to the class of all randomized algorithms using the method of random rotations [15, 51].”