Information-Based Complexity, Feedback and Dynamics in Convex Programming
Information-Based Complexity, Feedback and Dynamics in Convex Programming
复制标题
凸规划中基于信息的复杂性、反馈和动态
DOI：
10.1109/tit.2011.2154375
复制
发表时间：
2010
影响因子：
2.5
通讯作者：
A. Rakhlin
中科院分区：
文献类型：
--
作者：
M. Raginsky;A. Rakhlin
从反馈信息理论的角度研究了序列凸优化的内在局限性。在oracle优化模型中，算法向oracle查询关于未知目标函数的噪声信息，目标是使用尽可能少的查询来（近似地）最小化给定类中的每个函数。我们表明，为了优化函数，算法必须能够积累关于目标的足够信息。这反过来又限制了在oracle和反馈类型的特定假设下的优化速度。我们的技术类似于统计文献中用于获得估计程序风险的最小最大下界的技术；值得注意的是，与I.I.D.数据不同的是，顺序优化算法可以以可控的方式收集观测值，从而允许每一步的信息量随时间变化。特别是，我们表明优化算法通常遵循收益递减规律：随着优化算法接近最优，信噪比下降。为了强调这些工具的通用性，我们使用我们的方法来推导某个主动学习问题的基本下界。总的来说，目前的工作将优化、实验设计、估计和主动学习中的“信息”的直观概念与香农信息的定量概念联系起来。
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.