Oracle complexity of second-order methods for smooth convex optimization
From MaRDI portal
Publication:2330652
DOI10.1007/S10107-018-1293-1zbMath1430.90460arXiv1705.07260OpenAlexW2962824898MaRDI QIDQ2330652
Ron Shiff, Yossi Arjevani, Ohad Shamir
Publication date: 22 October 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.07260
Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical methods based on nonlinear programming (49M37)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Accelerating the cubic regularization of Newton's method on convex problems
- On uniformly convex functionals
- Introductory lectures on convex optimization. A basic course.
- Cubic regularization of Newton method and its global performance
- An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order Methods
- Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization
- On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
- Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors
Related Items (30)
Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods ⋮ On lower iteration complexity bounds for the convex concave saddle point problems ⋮ A simple method for convex optimization in the oracle model ⋮ Superfast second-order methods for unconstrained convex optimization ⋮ Regularized Newton Method with Global \({\boldsymbol{\mathcal{O}(1/{k}^2)}}\) Convergence ⋮ Super-Universal Regularized Newton Method ⋮ Affine-invariant contracting-point methods for convex optimization ⋮ Lower bounds for finding stationary points I ⋮ A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization ⋮ Lower bounds for finding stationary points II: first-order methods ⋮ Contracting Proximal Methods for Smooth Convex Optimization ⋮ Implementable tensor methods in unconstrained convex optimization ⋮ Unnamed Item ⋮ An accelerated regularized Chebyshev-Halley method for unconstrained optimization ⋮ Inexact tensor methods and their application to stochastic convex optimization ⋮ 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 ⋮ SketchySGD: reliable stochastic optimization via randomized curvature estimates ⋮ Perseus: a simple and optimal high-order method for variational inequalities ⋮ On the oracle complexity of smooth strongly convex minimization ⋮ Tensor Methods for Minimizing Convex Functions with Hölder Continuous Higher-Order Derivatives ⋮ Unified Acceleration of High-Order Algorithms under General Hölder Continuity ⋮ A control-theoretic perspective on optimal high-order optimization ⋮ Unnamed Item ⋮ Inexact High-Order Proximal-Point Methods with Auxiliary Search Procedure ⋮ Unnamed Item ⋮ Higher-Order Methods for Convex-Concave Min-Max Optimization and Monotone Variational Inequalities ⋮ High-Order Optimization Methods for Fully Composite Problems ⋮ An Optimal High-Order Tensor Method for Convex Optimization
This page was built for publication: Oracle complexity of second-order methods for smooth convex optimization
