Incremental Without Replacement Sampling in Nonconvex Optimization

Edouard Pauwels ()
Additional contact information
Edouard Pauwels: Université de Toulouse

Journal of Optimization Theory and Applications, 2021, vol. 190, issue 1, No 12, 274-299

Abstract: Abstract Minibatch decomposition methods for empirical risk minimization are commonly analyzed in a stochastic approximation setting, also known as sampling with replacement. On the other hand, modern implementations of such techniques are incremental: they rely on sampling without replacement, for which available analysis is much scarcer. We provide convergence guaranties for the latter variant by analyzing a versatile incremental gradient scheme. For this scheme, we consider constant, decreasing or adaptive step sizes. In the smooth setting, we obtain explicit complexity estimates in terms of epoch counter. In the nonsmooth setting, we prove that the sequence is attracted by solutions of optimality conditions of the problem.

Keywords: Without replacement sampling; Incremental methods; Nonconvex optimization; First-order methods; Stochastic gradient; Adaptive methods; Backpropagation; Deep learning (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-021-01883-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:190:y:2021:i:1:d:10.1007_s10957-021-01883-2

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-021-01883-2

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().