Information-theoretic lower bounds on the oracle complexity of convex optimization

By Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, Martin J. Wainwright. 2009

225 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.

Citations in the corpus

Distributed delayed stochastic optimization (2011, neutral): “The result is sharp to constant factors [14, 1], but can be further improved using Assumption II.”
Privacy Aware Learning (2012, methodology): “Moreover, our analysis is sharper than previous analyses [1, 20], as none (to our knowledge) recover the logarithmic dependence on the dimension d, which is evidently necessary.”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, background): “Indeed, after n observations and with the proper step-sizes, averaged SGD achieves the rate of O(1/μn) in the strongly-convex case [5, 4], while it achieves only O(1/ √ n) in the nonstrongly-convex case [5], with matching lower-bounds [8, 9].”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, neutral): “Optimizing F (x) to within ✏ accuracy then implies recovering the bias of the Bernoulli random variable, which requires ⌦(1/✏2) queries based on a standard information theoretic result [2, 19].”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, background): “This stepsize schedule matches the schedule which leads to optimal rates of convergence for SGD in the case of convex, but not necessarily smooth, loss functions, as well as smooth, but not necessarily convex loss functions (see, for instance, [1] and [4]).”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, methodology): “We follow the typical reduction of estimation to testing, common in the literature on lower bounds [2, 21, 46, 56].”
On the Oracle Complexity of First-Order and Derivative-Free Algorithms for Smooth Nonconvex Minimization (2012, background): “Many results of that nature have been derived since, mostly on the convex optimization problem (see, for instance, Nesterov (2004), (2008), Nemirovski (1994), Agarwal et al. (2009)), but also for the nonconvex case (see Vavasis (1992a), (1992b), (1993), Nesterov and Polyak (2006), Gratton, Sartenaer”
Minimax Bounds on Stochastic Batched Convex Optimization (2018, methodology): “In the typical proofs of information-theoretic lower bounds (Tsybakov, 2009; Agarwal et al., 2012; Duchi, 2017), the goal is to choose the separation between distributions, ‖Pvu1:M − P ṽ u1:t,ũt+1:M ‖TV in Le Cam’s method (8), to be a constant so as to guarantee a reasonable lower bound.”
Is Interaction Necessary for Distributed Private Learning? (2017, background): “Previous bounds on oracle optimization [3, 34, 33, 37] used information-theoretic arguments that do not distinguish between adaptive and nonadaptive algorithms (in particular, the instances that arise in those proofs are easy to solve nonadaptively).”
Randomized Smoothing for Stochastic Optimization (2011, methodology): “Then for any method that outputs a point x T ∈ X after T queries of the oracle, we have the lower bound where the supremum is taken over convex f that are L 0 , 2 -Lipschitz with respect to the ℓ 2 -norm [1, Section 3.1].”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, background): “In the strong convex problem, SGD can achieve the optimal convergence speed [36], [94]–[96].”
Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization (2014, background): “This matches the lower bound of Agarwal et al. (2010) up to constant factors.”
A Simple Convergence Proof of Adam and Adagrad (2020, unknown): “, 2011) showed that Adagrad achieves an optimal rate of convergence of O(1/ √ N) for convex optimization (Agarwal et al., 2009). Later, RMSProp (Tieleman & Hinton, 2012) and Adam (Kingma & Ba, 2015) were developed for training deep neural networks, using an exponential moving average of the past squ”
Asynchronous stochastic convex optimization: the noise is in the noise and SGD don't care (2015, background): “or the decision variables x, the rate n−12 is unimprovable, as is—at least generally—the asymptotic covariance H−1ΣH−1. We also have f(xn) −f(x⋆) = OP(n−1), which is information-theoretically optimal [22, 2]. So we see that quite literally, the noise inherent to the sampling in stochastic gradient p”
On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, background): “Lower Bounds for Stochastic Optimization: Lower bounds have also been established in the stochastic convex optimization [2, 17] where each gradient- or function-value oracle query is corrupted with i.”
Local Privacy and Statistical Minimax Rates (2013, background): “We do, however, obtain matching upper bounds for the general convex case (the linear case is, in some sense, the hardest [21, 1]), leading to the intriguing open question of interactivity’s role in non-linear settings.”