An optimal high-order tensor method for convex optimization
From MaRDI portal
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 / k^2 ). A high-order tensor algorithm with iteration complexity of O( 1 / k^{d+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), and Shamir 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.
Recommendations
- Reachability of optimal convergence rate estimates for high-order numerical convex optimization methods
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- Local convergence of tensor methods
- Introduction to high-order optimization methods
- Implementable tensor methods in unconstrained convex optimization
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- A variational perspective on accelerated methods in optimization
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Accelerating the cubic regularization of Newton's method on convex problems
- An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- An optimal method for stochastic composite optimization
- Backtracking strategies for accelerated descent methods with smooth composite objectives
- Enlargement of monotone operators with applications to variational inequalities
- Fast first-order methods for composite convex optimization with backtracking
- Implementable tensor methods in unconstrained convex optimization
- Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems
- On High-order Model Regularization for Constrained Optimization
- On the maximal monotonicity of subdifferential mappings
- Oracle complexity of second-order methods for smooth convex optimization
- Performance of first-order methods for smooth convex minimization: a novel approach
- Relatively smooth convex optimization by first-order methods, and applications
- Universal Regularization Methods: Varying the Power, the Smoothness and the Accuracy
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
Cited in
(27)- The polyadic structure of factorable function tensors with applications to high-order minimization techniques
- An adaptive high order method for finding third-order critical points of nonconvex optimization
- A control-theoretic perspective on optimal high-order optimization
- Reachability of optimal convergence rate estimates for high-order numerical convex optimization methods
- Optimal combination of tensor optimization methods
- Affine-invariant contracting-point methods for convex optimization
- On local convergence of alternating schemes for optimization of convex problems in the tensor train format
- A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems
- Introduction to high-order optimization methods
- Tensor Methods for Unconstrained Optimization Using Second Derivatives
- Tensor Methods for Equality Constrained Optimization
- Near-optimal hyperfast second-order method for convex optimization
- Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives
- Unified acceleration of high-order algorithms under general Hölder continuity
- Inexact basic tensor methods for some classes of convex optimization problems
- Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods
- A unified adaptive tensor approximation scheme to accelerate composite convex optimization
- Contracting proximal methods for smooth convex optimization
- On inexact solution of auxiliary problems in tensor methods for convex optimization
- Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
- High-order optimization methods for fully composite problems
- A sub-sampled tensor method for nonconvex optimization
- Higher-order Newton methods with polynomial work per iteration
- A search-free \(O(1/k^{3/2})\) homotopy inexact proximal-Newton extragradient algorithm for monotone variational inequalities
- High-order methods beyond the classical complexity bounds: inexact high-order proximal-point methods
- Near-optimal tensor methods for minimizing the gradient norm of convex functions and accelerated primal–dual tensor methods
- Proximal oracles for optimization and sampling
This page was built for publication: An optimal high-order tensor method for convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5026443)
