Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

Functional analysis and applied mathematics

Leonid Vital’evich Kantorovich · 1948

Earlier work this paper cites.

Problem Complexity and Method Efficiency in Optimization

Arkadi Nemirovsky and David Yudin · 1983

Earlier work this paper cites.

A method of solving a convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) O(1/k^{2})

Yurii Nesterov · 1983

Earlier work this paper cites.

Interior-point polynomial algorithms in convex programming

Yurii Nesterov and Arkadii Nemirovskii · 1994

Earlier work this paper cites.

Trust region methods

Andrew R Conn, Nicholas IM Gould, and Philippe L Toint · 2000

Earlier work this paper cites.

Convex optimization

Stephen Boyd and Lieven Vandenberghe · 2004

Earlier work this paper cites.

Introductory lectures on convex optimization: A basic course , volume 87

Yurii Nesterov · 2004

Earlier work this paper cites.

Efficient methods in convex programming – lecture notes, 2005

Arkadi Nemirovski · 2005

Cited alongside, same era.

Cubic regularization of newton method and its global performance

Yurii Nesterov and Boris T Polyak · 2006

Cited alongside, same era.

Accelerating the cubic regularization of newton’s method on convex problems

Yurii Nesterov · 2008

Cited alongside, same era.

Estimate sequence methods: extensions and approximations

Michel Baes · 2009

Cited alongside, same era.

Self-concordant analysis for logistic regression

Francis Bach · 2010

Cited alongside, same era.

On the complexity of steepest descent, newton’s and regularized newton’s methods for nonconvex unconstrained optimization problems

Coralia Cartis, Nicholas IM Gould, and Philippe L Toint · 2010

Cited alongside, same era.

Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization

Coralia Cartis, Nicholas IM Gould, and Philippe L Toint · 2012

Later among the works it cites.

An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods

Renato DC Monteiro and Benar Fux Svaiter · 2013

Later among the works it cites.

On uniformly convex functionals

Original

AA Vladimirov, Yu E Nesterov, and Yu N Chekanov · 2013

Later among the works it cites.

Successive rank-one approximations for nearly orthogonally decomposable symmetric tensors

Cun Mu, Daniel Hsu, and Donald Goldfarb · 2015

Later among the works it cites.

Optimal black-box reductions between optimization objectives

Zeyuan Allen-Zhu and Elad Hazan · 2016

Later among the works it cites.