Consider the optimization problem

$$\min_x \; f(x) := \sum_{i=1}^m f_i(x).$$

A subgradient method at each iteration takes a subgradeint descent step

$$ x^+ = x - \alpha g, \quad g\in \partial f(x)$$

and a stochastic gradient method takes a step with respect to one of the incremental terms

$$ x^+ = x - \alpha \nabla f_i(x), \quad i \sim Unif[1,...,m].$$

I often hear stochastic methods as "taking a subgradient step", and often see works describing subgradient methods cited for stochastic gradient results, but the two do not look equivalent to me at all. (For example, this paper by Duchi and Singer: Efficient Online and Batch Learning Using Forward Backward Splitting, is commonly cited as giving the prox-stochastic-gradient convergence result, but the paper only deals with subgradients.)

Am I missing something? Are there common conditions under which a stochastic gradient IS a subgradient? It seems like in most cases that would not be true, even with bounded variance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.