Information-Based Complexity, Feedback and Dynamics in Convex Programming

DOI10.1109/TIT.2011.2154375MaRDI QIDQ5272322zbMATH OpenOpenAlexFDO

Authors Maxim Raginsky, Alexander Rakhlin

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.2285

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Feedback control (93B52) Information theory (general) (94A15)

Abstract: 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 {em 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 {em 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.

Cited in

(14)

• Stochastic gradient descent with Polyak's learning rate
• Surrogate losses in passive and active learning
• Oracle lower bounds for stochastic gradient sampling algorithms
• Sub-linear convergence of a stochastic proximal iteration method in Hilbert space
• Lower error bounds for the stochastic gradient descent optimization algorithm: sharp convergence rates for slowly and fast decaying learning rates
• Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
• Information Relaxations, Duality, and Convex Stochastic Dynamic Programs
• Optimization methods for large-scale machine learning
• Accelerated stochastic algorithms for convex-concave saddle-point problems
• The exact information-based complexity of smooth convex minimization
• Computing the value of information of quadratic decision problems and its non-negativity conditions
• Lower bounds for non-convex stochastic optimization
• Statistical complexity and optimal algorithms for nonlinear ridge bandits
• Nesterov's acceleration at the limit: first-order schemes

This page was built for publication: Information-Based Complexity, Feedback and Dynamics in Convex Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272322)