On stochastic proximal gradient algorithms

By Yves F. Atchadé, Gersende Fort, Eric Moulines. 2014

48 citations recorded by the source corpus.

We study a perturbed version of the proximal gradient algorithm for which the gradient is not known in closed form and should be approximated. We address the convergence and derive a non-asymptotic bound on the convergence rate for the perturbed proximal gradient, a perturbed averaged version of the proximal gradient algorithm and a perturbed version of the fast iterative shrinkage-thresholding (FISTA) of \cite{becketteboulle09}. When the approximation is achieved by using Monte Carlo methods, we derive conditions involving the Monte Carlo batch-size and the step-size of the algorithm under which convergence is guaranteed. In particular, we show that the Monte Carlo approximations of some averaged proximal gradient algorithms and a Monte Carlo approximation of FISTA achieve the same convergence rates as their deterministic counterparts. To illustrate, we apply the algorithms to high-dimensional generalized linear mixed models using $\ell_1$-penalization.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, positive): “Under Assumptions 1 and 3, the iterates of Algorithm 4 satisfy, Proof.”
On Acceleration with Noise-Corrupted Gradients (2018, methodology): “…the setting of stochastic methods, in which the gradient is only estimated from a subset of its components (Lan, 2012; Ghadimi & Lan, 2012; 2013; Atchade et al., 2014; Krichene & Bartlett, 2017; Jain et al., 2018), the setting of differentially private empirical risk minimization, in which…”
Exploiting Multi-Core Architectures for Reduced-Variance Estimation with Intractable Likelihoods (2014, methodology): “Stochastic approximation of the score function was also recently considered by Atchad´e et al. (2014) in the context of designing proximal gradient algorithms.”
A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces (2014, background): “Also, very recently, a related algorithm has been studied in [1].”
Stochastic Approximations and Perturbations in Forward-Backward Splitting for Monotone Operators (2015, unknown): “…every z ∈ F, there exist (ϑn(z))n∈N ∈ ℓ+(X ), (χn(z))n∈N ∈ ℓ1+(X ), and (ηn(z))n∈N ∈ ℓ1+(X ) such that (∀n ∈ N) E(φ(‖xn+1 − z‖) |Xn) + ϑn(z) 6 (1 + χn(z))φ(‖xn − z‖) + ηn(z) P-a.s. (3.2) Then the following hold: (i) (∀z ∈ F) [ ∑ n∈N ϑn(z) < +∞ P-a.s. ] (ii) (xn)n∈N is bounded P-a.s. (iii) There…”