On stochastic gradient and subgradient methods with adaptive steplength sequences

By Farzad Yousefian, Angelia Nedić, Uday V. Shanbhag. 2011

158 citations recorded by the source corpus.

Traditionally, stochastic approximation (SA) schemes have been popular choices for solving stochastic optimization problems. However, the performance of standard SA implementations can vary significantly based on the choice of the steplength sequence, and in general, little guidance is provided about good choices. Motivated by this gap, we present two adaptive steplength schemes for strongly convex differentiable stochastic optimization problems, equipped with convergence theory, that aim to overcome some of the reliance on user-specific parameters. The first scheme, referred to as a recursive steplength stochastic approximation (RSA) scheme, optimizes the error bounds to derive a rule that expresses the steplength at a given iteration as a simple function of the steplength at the previous iteration and certain problem parameters. The second scheme, termed as a cascading steplength stochastic approximation (CSA) scheme, maintains the steplength sequence as a piecewise-constant decreasing function with the reduction in the steplength occurring when a suitable error threshold is met. Then, we allow for nondifferentiable objectives but with bounded subgradients over a certain domain. In such a regime, we propose a local smoothing technique, based on random local perturbations of the objective function, that leads to a differentiable approximation of the function. Assuming a uniform distribution on the local randomness, we establish a Lipschitzian property for the gradient of the approximation and prove that the obtained Lipschitz bound grows at a modest rate with problem size. This facilitates the development of an adaptive steplength stochastic approximation framework, which now requires sampling in the product space of the original measure and the artificially introduced distribution.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes (2018, background): “Youseﬁan et al. (2012) analyze diﬀerent adaptive stepsizes, but only for strongly convex optimization.”
A Stochastic Quasi-Newton Method for Large-Scale Optimization (2014, methodology): “ibed in Algorithm 1. It is well known amongst the optimization and machine learning communities that the SGD method can be improved by choosing the parameter via a set of problem dependent heuristics [19, 27]. In some cases, k (rather than ) is made to vary during the course of the iteration, and co”
Randomized Smoothing for Stochastic Optimization (2011, methodology): “In this case, Youseﬁan et al. give (i)–(iii) of the following lemma [38].”
A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces (2014, result): “In the case when G is the indicator function of a non empty closed convex set and (∀n ∈ N) λn = 1, a similar result on the rate of convergence of E[‖wn−w‖] has been obtained in [53], under similar assumptions to (A1), .”