Skip to Main content Skip to Navigation
Conference papers

The perturbed prox-preconditioned spider algorithm: non-asymptotic convergence bounds

Abstract : A novel algorithm named Perturbed Prox-Preconditioned SPIDER (3P-SPIDER) is introduced. It is a stochastic variancereduced proximal-gradient type algorithm built on Stochastic Path Integral Differential EstimatoR (SPIDER), an algorithm known to achieve near-optimal first-order oracle inequality for nonconvex and nonsmooth optimization. Compared to the vanilla prox-SPIDER, 3P-SPIDER use preconditioned gradient estimators. Preconditioning can either be applied "explicitly" to a gradient estimator or be introduced "implicitly" as in applications to the EM algorithm. 3P-SPIDER also assumes that the preconditioned gradients may (possibly) be not known in closed analytical form and therefore must be approximated which adds an additional degree of perturbation. We show that 3P-SPIDER achieves a near-optimal oracle inequality O(n 1/2 /ǫ) where n is the number of observations and ǫ the target precision even when the gradient is estimated by Monte Carlo methods. We illustrate the algorithm on an application to the minimization of a penalized empirical loss.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03183775
Contributor : Gersende Fort <>
Submitted on : Sunday, March 28, 2021 - 10:32:58 PM
Last modification on : Tuesday, May 11, 2021 - 11:59:43 AM

Files

FMtheory_HAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03183775, version 1

Citation

Gersende Fort, E Moulines. The perturbed prox-preconditioned spider algorithm: non-asymptotic convergence bounds. IEEE Statistical Signal Processing Workshop, Jul 2021, Rio de Janeiro, Brazil. ⟨hal-03183775⟩

Share

Metrics

Record views

28

Files downloads

53