An Optimal High-Order Tensor Method for Convex Optimization

Bo Jiang (), Haoyue Wang () and Shuzhong Zhang ()
Additional contact information
Bo Jiang: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
Haoyue Wang: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Shuzhong Zhang: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455; Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong, Shenzhen 518176, Hong Kong

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1390-1412

Abstract: This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the d th-order derivative information available, and the second function is possibly nonsmooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find—in that setting—the best possible (optimal) iteration complexity for convex optimization. Along that line, for the smooth case (without the second nonsmooth part in the objective), Nesterov proposed an optimal algorithm for the first-order methods ( d = 1 ) with iteration complexity O ( 1 / k 2 ) , whereas high-order tensor algorithms (using up to general d th-order tensor information) with iteration complexity O ( 1 / k d + 1 ) were recently established. In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of O ( 1 / k ( 3 d +1 ) / 2 ) , which matches the lower bound for the d th-order methods as previously established and hence is optimal. Our approach is based on the accelerated hybrid proximal extragradient (A-HPE) framework proposed by Monteiro and Svaiter, where a bisection procedure is installed for each A-HPE iteration. At each bisection step, a proximal tensor subproblem is approximately solved, and the total number of bisection steps per A-HPE iteration is shown to be bounded by a logarithmic factor in the precision required.

Keywords: Primary: 90C60; 90C25; 47H05; Primary: programming/nonlinear/convex; convex optimization; tensor method; acceleration; iteration complexity (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1103 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:4:p:1390-1412

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().