On Lower and Upper Bounds in Smooth and Strongly Convex Optimization

By Yossi Arjevani, Shai Shalev-Shwartz, Ohad Shamir. 2016

41 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “To derive lower bounds which matches more closely the (linear) rates of convergence of common methods, Arjevani et al. (2016) introduced a new framework.”
Lower bounds for finding stationary points I (2017, background): “In the literature on lower bounds for first-order convex optimization, it is common to assume that methods only query points in the span of the gradients they observe [37, 3].”
Online Adaptive Methods, Universality and Acceleration (2018, methodology): “Alternative accelerated methods and interpretations are explored in, [3, 7, 11].”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “, Flammarion and Bach (2015); O’Neill and Wright (2017); Arjevani et al. (2016)).”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, methodology): “Arjevani et al. (2016); Arjevani and Shamir (2016) showed non-asymptotic lower bounds using a framework called p -SCLI close to matrix iteration theory.”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “Indeed, general 1-SCLI as deﬁned in Arjevani et al. (2016) are given not by one but by two mappings C , N : R d × d → R d × d and the update rule is However, they show in Arjevani et al. (2016, Thm. 5) that, for a method to converge to a stationary point of v , at least for convex problems, that is…”
Linear Lower Bounds and Conditioning of Differentiable Games (2019, methodology): “13) satisﬁes Equivalently, as Arjevani et al. (2016) argue in their section 3.1, consistency with respect to some invertible Jacobian A is equivalent to having A converge on f A , b and Note that all three examples of optimisation algorithms discussed in this subsection satisfy eq.”