Oracle Complexity of SecondOrder Methods for FiniteSum Problems
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:205213, 2017.
Abstract
Finitesum optimization problems are ubiquitous in machine learning, and are commonly solved using firstorder methods which rely on gradient computations. Recently, there has been growing interest in secondorder methods, which rely on both gradients and Hessians. In principle, secondorder methods can require much fewer iterations than firstorder methods, and hold the promise for more efficient algorithms. Although computing and manipulating Hessians is prohibitive for highdimensional problems in general, the Hessians of individual functions in finitesum problems can often be efficiently computed, e.g. because they possess a lowrank structure. Can secondorder information indeed be used to solve such problems more efficiently? In this paper, we provide evidence that the answer – perhaps surprisingly – is negative, at least in terms of worstcase guarantees. However, we also discuss what additional assumptions and algorithmic approaches might potentially circumvent this negative result.
Related Material


