Fetching the paper…

Reading the bibliography…

2016

Oracle Complexity of Second-Order Methods for Finite-Sum Problems

Arjevani, Yossi, Shamir, Ohad

Original
PDF
Post on X

Understand

Finite-sum optimization problems are ubiquitous in machine learning, and are commonly solved using first-order methods which rely on gradient computations.

Recently, there has been growing interest in \emph{second-order} methods, which rely on both gradients and Hessians.
In principle, second-order methods can require much fewer iterations than first-order methods, and hold the promise for more efficient algorithms.
Although computing and manipulating Hessians is prohibitive for high-dimensional problems in general, the Hessians of individual functions in finite-sum problems can often be efficiently computed, e.g.

Oracle Complexity of Second-Order Methods for Finite-Sum Problems · Around

Built on

Problem Complexity and Method Efficiency in Optimization
A. Nemirovsky and D. Yudin · 1983
Earlier work this paper cites.
Convex optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Numerical optimization
Jorge Nocedal and Stephen Wright · 2006
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course , volume 87
Yurii Nesterov · 2013
Earlier work this paper cites.
Sub-sampled newton methods with non-uniform sampling
Original
Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher Ré, and Michael W Mahoney · 2013
Earlier work this paper cites.

Similar

A lower bound for the optimization of finite sums
Original
Alekh Agarwal and Leon Bottou · 2014
Cited alongside, same era.
Communication complexity of distributed convex learning and optimization
Yossi Arjevani and Ohad Shamir · 2015
Cited alongside, same era.
Convergence rates of sub-sampled newton methods
Murat A Erdogdu and Andrea Montanari · 2015
Cited alongside, same era.
An optimal randomized incremental gradient method
Original
Guanghui Lan · 2015
Cited alongside, same era.
Dimension-free iteration complexity of finite sum optimization problems
Yossi Arjevani and Ohad Shamir
Cited in the paper.
On the iteration complexity of oblivious first-order optimization algorithms
Yossi Arjevani and Ohad Shamir
Cited in the paper.
Sub-sampled newton methods i: globally convergent algorithms
Original
Farbod Roosta-Khorasani and Michael W Mahoney
Cited in the paper.
Sub-sampled newton methods ii: Local convergence rates
Original
Farbod Roosta-Khorasani and Michael W Mahoney
Cited in the paper.

Then

Newton sketch: A linear-time optimization algorithm with linear-quadratic convergence
Original
Mert Pilanci and Martin J Wainwright · 2015
Later among the works it cites.
Second order stochastic optimization in linear time
Original
Naman Agarwal, Brian Bullins, and Elad Hazan · 2016
Closest in time.
Exact and inexact subsampled newton methods for optimization
Original
Raghu Bollapragada, Richard Byrd, and Jorge Nocedal · 2016
Closest in time.
Tight complexity bounds for optimizing composite objectives
Original
Blake Woodworth and Nathan Srebro · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…