On lower complexity bounds for large-scale smooth convex optimization
On lower complexity bounds for large-scale smooth convex optimization
复制标题
大规模平滑凸优化的较低复杂度界限
DOI：
10.1016/j.jco.2014.08.003
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Nemirovski
中科院分区：
文献类型：
--
作者：
Cristóbal Guzmán;A. Nemirovski
我们给出了大规模光滑凸极小化问题黑箱预言复杂性的下界，重点是极小化高维‖⋅‖p-ball，1≤p≤∞上的光滑(Hölder连续，给定指数和常数，梯度)凸函数.我们的界被证明是紧的(直到设计维度因子中的对数)，并且可以被视为覆盖非光滑情况和欧几里德光滑情况(欧几里德球上具有Lipschitz连续梯度的凸函数的最小化)的大规模凸极小化的现有较低复杂性界的实质性扩展。作为我们结果的一个副产品，我们证明了当最小化高维‖⋅‖∞球上的光滑凸函数时，经典的条件梯度算法在基于信息的复杂性理论的意义下是近最优的。
We derive lower bounds on the black-box oracle complexity of large-scale smooth convex minimization problems, with emphasis on minimizing smooth (with Hölder continuous, with a given exponent and constant, gradient) convex functions over high-dimensional‖⋅‖ p-balls, 1≤ p≤∞. Our bounds turn out to be tight (up to logarithmic in the design dimension factors), and can be viewed as a substantial extension of the existing lower complexity bounds for large-scale convex minimization covering the nonsmooth case and the “Euclidean” smooth case (minimization of convex functions with Lipschitz continuous gradients over Euclidean balls). As a byproduct of our results, we demonstrate that the classical Conditional Gradient algorithm is near-optimal, in the sense of Information-Based Complexity Theory, when minimizing smooth convex functions over high-dimensional‖⋅‖∞-balls and their matrix analogies–spectral norm balls in the spaces of square matrices.