A line search proximal subgradient method for nonconvex stochastic optimization

This work introduces a proximal sample-average subgradient method for minimizing the sum of an expected cost, whose integrand is potentially nonsmooth and nonconvex, and a lower semicontinuous, prox-bounded function. We target the class of upper-$C^2$ integrands obeying a nonsmooth, localized variant of the descent lemma in the decision variable, a structural assumption that simultaneously covers smooth losses with Lipschitz gradient and differences of such losses with convex functions. At each iteration the expected cost is replaced by a linearization of the sample average that is progressively refined, and the proximal-subgradient stepsize is selected by an Armijo line search enforcing a sufficient-decrease property up to stochastic errors induced by the sample-based approximation. This framework accommodates more general problem formulations than existing methods, in particular, it requires neither (weak) convexity of the regularizer nor a uniform bound on the variance of the stochastic oracle, and our analysis yields asymptotic convergence guarantees that are new even in the smooth setting. Specifically, we establish almost sure convergence of the sequence of function values and stationarity of every accumulation point of the trajectories under the relaxed requirement that the sample-size sequence be merely nondecreasing, with no prescribed growth rate.

Article

Download

View PDF