A Subsampling Line-Search Method with Second-Order Results
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00363766" target="_blank" >RIV/68407700:21230/22:00363766 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1287/ijoo.2022.0072" target="_blank" >https://doi.org/10.1287/ijoo.2022.0072</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1287/ijoo.2022.0072" target="_blank" >10.1287/ijoo.2022.0072</a>
Alternative languages
Result language
angličtina
Original language name
A Subsampling Line-Search Method with Second-Order Results
Original language description
In many contemporary optimization problems such as those arising in machine learning, it can be computationally challenging or even infeasible to evaluate an entire function or its derivatives. This motivates the use of stochastic algorithms that sample problem data, which can jeopardize the guarantees obtained through classical globalization techniques in optimization, such as a line search. Using subsampled function values is particularly challenging for the latter strategy, which relies upon multiple evaluations. For nonconvex data-related problems, such as training deep learning models, one aims at developing methods that converge to second-order stationary points quickly, that is, escape saddle points efficiently. This is particularly difficult to ensure when one only accesses subsampled approximations of the objective and its derivatives. In this paper, we describe a stochastic algorithm based on negative curvature and Newton-type directions that are computed for a subsampling model of the objective. A line-search technique is used to enforce suitable decrease for this model; for a sufficiently large sample, a similar amount of reduction holds for the true objective. We then present worst-case complexity guarantees for a notion of stationarity tailored to the subsampling context. Our analysis encompasses the deterministic regime and allows us to identify sampling requirements for second-order line-search paradigms. As we illustrate through real data experiments, these worst-case estimates need not be satisfied for our method to be competitive with first-order strategies in practice.
Czech name
—
Czech description
—
Classification
Type
J<sub>ost</sub> - Miscellaneous article in a specialist periodical
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
INFORMS JOURNAL ON OPTIMIZATION
ISSN
2575-1484
e-ISSN
2575-1492
Volume of the periodical
4
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
23
Pages from-to
403-425
UT code for WoS article
—
EID of the result in the Scopus database
—