On lower complexity bounds for large-scale smooth convex optimization

作     者：Guzman, Cristobal Nemirovski, Arkadi 

作者机构：Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《JOURNAL OF COMPLEXITY》 (复杂性杂志)

年 卷 期：2015年第31卷第1期

页      面：1-14页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CMMI-1232623] Div Of Civil, Mechanical, & Manufact Inn Directorate For Engineering Funding Source: National Science Foundation 

主　　题：Smooth convex optimization Lower complexity bounds Optimal algorithms 

摘      要：We derive lower bounds on the black-box oracle complexity of large-scale smooth convex minimization problems, with emphasis on minimizing smooth (with Holder continuous, with a given exponent and constant, gradient) convex functions over high-dimensional parallel to . parallel to(p)-balls, 1 = p = infinity. 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 parallel to . parallel to(infinity)-balls and their matrix analogies - spectral norm balls in the spaces of square matrices. (C) 2014 Elsevier Inc. All rights reserved.