An Optimal High-Order Tensor Method for Convex Optimization

Bo Jiang, Haoyue Wang, Shuzhong Zhang

Research output: Contribution to journalConference articlepeer-review

17 Scopus citations

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 non-smooth, 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 non-smooth part in the objective), Nesterov (1983) proposed an optimal algorithm for the first-order methods (d = 1) with iteration complexity O (1/k2). A high-order tensor algorithm with iteration complexity of O (1/kd+1) was proposed by Baes (2009) and Nesterov (2018). In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of O (1/k(3d+1)/2), which matches the lower bound for the d-th order methods as established in Nesterov (2018); Arjevani et al. (2018), and hence is optimal. Our approach is based on the Accelerated Hybrid Proximal Extragradient (A-HPE) framework proposed in Monteiro and Svaiter (2013), 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 bounded by a logarithmic factor in the precision required.

Original languageEnglish (US)
Pages (from-to)1799-1801
Number of pages3
JournalProceedings of Machine Learning Research
Volume99
StatePublished - 2019
Event32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States
Duration: Jun 25 2019Jun 28 2019

Bibliographical note

Publisher Copyright:
© 2019 B. JIANG, H. WANG & S. ZHANG.

Keywords

  • acceleration
  • convex optimization
  • iteration complexity
  • tensor method

Fingerprint

Dive into the research topics of 'An Optimal High-Order Tensor Method for Convex Optimization'. Together they form a unique fingerprint.

Cite this