Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization

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

278 citations recorded by the source corpus.

Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardn4516420ess of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We introduce a new notion of discrepancy between functions, and use it to reduce problems of stochastic convex optimization to statistical parameter estimation, which can be lower bounded using information-theoretic methods. Using this approach, we improve upon known results and obtain tight minimax complexity estimates for various function classes.

Subfields: Artificial Intelligence, Computational Mechanics

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

In Computational Mechanics

Citations in the corpus

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “, those based on gradient measurements—must learn information about the gradient at Ω(n2) points to get risk bounds that are independent of n (this follows from “oracle complexity” bounds showing that 1/ √ T convergence rate is optimal [39, 1]).”
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2012, background): “√ In comparison, in the non-smooth setting, there are Ω(1 / T ) and Ω(1 /T ) lower bounds for convex and strongly-convex problems, respectively Agarwal et al. (2012).”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “We now turn to consider an example from stochastic optimization, where our goal is to approximately minimize given access to m i.i.d. instantiations of Z , whose distribution is unknown.”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, background): “Note that our convergence rate is quite close to best achievable rate of O(1/t) in (centralized) strongly convex optimization with noisy gradient samples of bounded variance [1], [30].”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “) points to get risk bounds that are independent of n (this follows from " oracle complexity " bounds showing that 1/ √ T convergence rate is optimal [32] [1]).”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, background): “Towards optimality under bounded noise assumptions: The other line of thought presents algorithms with access to stochastic gradients satisfying bounded noise assumptions, aiming to match lower bounds provided in Nemirovsky and Yudin (1983); Raginsky and Rakhlin (2011); Agarwal et al. (2012).”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, background): “If the expected function F (·) is λ-strongly convex, some variants of SGD (Hazan and Kale, 2011, 2014; Rakhlin et al., 2012; Shamir and Zhang, 2013) achieve an O(1/[λT ]) rate which is known to be minimax optimal (Agarwal et al., 2012).”
A Sample Complexity Separation between Non-Convex and Convex Meta-Learning (2020, methodology): “This result extends the result of Agarwal et al. [2012, Theorem 1] to the case of distributions over functions; all equations and statements referenced in this proof are from that paper.”
Information-Based Complexity, Feedback and Dynamics in Convex Programming (2010, methodology): “Our lower bound for strongly convexfunctionsseemstobenew;inparticular,Nemirovskiand Yudin [1] only consider the noiseless case, while Agarwal et al. [ 9 ], [10] consider noisy first-order oracles, but with a different oracle model, which does not allow additive noise due to a cointossing constructio”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “…of research on the complexity of convex optimization with access to some type of oracle (e.g., Braun et al. [15], Guzm´an and Nemirovski [47], Nemirovsky and Yudin [68]) with a lot of renewed interest because of applications in machine learning (e.g., Agarwal et al. [1], Raginsky and Rakhlin [73]).”
On lower complexity bounds for large-scale smooth convex optimization (2013, background): “The standard reference on information-based complexity of various broad families of convex programs is [4]; for some recent developments, see [8, 1] and references therein.”
Minimizing finite sums with the stochastic average gradient (2013, background): “These sublinear rates are slower than the corresponding rates for the FG method, and under certain assumptions these convergence rates are optimal in a model of computation where the algorithm only accesses the function through unbiased measurements of its objective and gradient (see [1,39,40]).”
Communication-efficient algorithms for statistical optimization (2012, background): “This is striking, since doing even one pass through the data with stochastic gradient descent gives minimax optimal convergence rates (Polyak and Juditsky, 1992; Agarwal et al., 2012).”
Lower bounds for non-convex stochastic optimization (2019, background): “For convex problems, a long line of work [1, 36, 37, 50] sheds lights on these limits, and they are by now well-understood.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “Now for the stochastic setting, using a first-order oracle, for concave, Lipschitz functions, the loss is Ω( √ D/n) and for strongly concave functions, it is Ω(q2/n) (see also [Agarwal et al., 2012] for other settings such as when the solution is sparse).”