Information-Based Complexity, Feedback and Dynamics in Convex Programming

By Maxim Raginsky, Alexander Rakhlin. 2010

91 citations recorded by the source corpus.

We study the intrinsic limitations of sequential convex optimization through the lens of feedback information theory. In the oracle model of optimization, an algorithm queries an oracle for noisy information about the unknown objective function and the goal is to (approximately) minimize every function in a given class using as few queries as possible. We show that, in order for a function to be optimized, the algorithm must be able to accumulate enough information about the objective. This, in turn, puts limits on the speed of optimization under specific assumptions on the oracle and the type of feedback. Our techniques are akin to the ones used in statistical literature to obtain minimax lower bounds on the risks of estimation procedures; the notable difference is that, unlike in the case of i.i.d. data, a sequential optimization algorithm can gather observations in a controlled manner, so that the amount of information at each step is allowed to change in time. In particular, we show that optimization algorithms often obey the law of diminishing returns: the signal-to-noise ratio drops as the optimization algorithm approaches the optimum. To underscore the generality of the tools, we use our approach to derive fundamental lower bounds for a certain active learning problem. Overall, the present work connects the intuitive notions of “information” in optimization, experimental design, estimation, and active learning to the quantitative notion of Shannon information.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

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

In Optimization & Training

Citations in the corpus

Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies (2015, background): “The black-box model for optimization was introduced in (Nemirovski and Yudin, 1983), see (Raginsky and Rakhlin, 2011) for a recent exposition.”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “r methods with higher per-iteration costs, distributed computing oers new opportunities for the success of such methods for machine learning. Alternatives with Faster Convergence As mentioned above, [1,128] establish lower complexity bounds for optimization algorithms that only access information ab”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “…of learning with expert advice, deﬁned as a game over T rounds, where each round t a loss vector (cid:96) t ∈ [0 , 1] d is chosen, and the learner (without knowing (cid:96) t ) needs to pick an action i t from a ﬁxed set { 1 , . . . , d } , after which the learner suffers loss (cid:96) t,i t .”
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]).”
Deterministic and Stochastic Primal-Dual Subgradient Algorithms for Uniformly Convex Minimization (2014, background): “, [15, 18]), they cannot be directly transposed to the non-Euclidean framework.”
Information-theoretic lower bounds on the oracle complexity of convex optimization (2009, result): “We note that special cases of the first two results in this paper appeared in the extended abstract [6], and that a similar study was independently undertaken by Raginsky and Rakhlin [7].”
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization (2010, result): “We note that special cases of the first two results in this paper appeared in the extended abstract [7], and that a related study was independently undertaken by Raginsky and Rakhlin [8].”
Primal-dual subgradient methods for minimizing uniformly convex functions (2010, background): “The worst-case complexity bounds for the problem (1) with the exact and stochastic ﬁrst order oracle are available for the case of strongly convex objective (see, e.g. [18, 1] and references therein).”
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).”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, unknown): “[RR11] Maxim Raginsky and Alexander Rakhlin.”
Fine-Tuning Language Models with Just Forward Passes (2023, background): “Zeroth-order optimization Many classical lower bounds have been derived for ZO-SGD in the strongly convex and convex settings [47, 3, 79, 32, 85, 69] as well as non-convex [101].”
On Perturbed Proximal Gradient Algorithms (2014, background): “Xn k=1 F( k) min = Lq O 1 p n : An upper bound O(lnn= p n) can be obtained by choosing a n = n = (n+ 1) 1=2. This upper bound match the lower bounds reported for rst-order noisy optimization in (Raginsky and Rakhlin, 2011, Theorem 2). 3.2. Monte Carlo approximation with increasing batch size. The ”
Accelerating Stochastic Gradient Descent (2017, background): “Lower bounds in stochastic oracle models have been considered in the literature (see Nemirovsky and Yudin (1983); Raginsky and Rakhlin (2011); Agarwal et al. (2012)), though it is not evident these oracle models and lower bounds are sharp enough to imply statements in our setting (see section 1.4…”
Query Complexity of Derivative-Free Optimization (2012, background): “Our bounds are based on simple techniques borrowed from the statistical learning literature that use natural functions and oracles in the same spirit of [11].”
Lower bounds for non-convex stochastic optimization (2019, background): “Extensions since then have allowed sharp dimension-dependent bounds via reductions to statistical estimation problems [1, 41], as well as extension to structured problems common in machine learning, such as finite sums, by restrictions on the form of the update rules [7] and high-dimensional constru”