Sufficient conditions for gradient descent convergence

2012-03-11T17:34:38Z

I have an unconstrained optimisation problem with convex objective function $f(x)$. Suppose I have access only to some function of the gradient $\hat{\nabla}= g(\nabla f)$, and I take gradient steps treating $\hat{\nabla}$ as the true gradient: \begin{equation} x^{t+1} = x^{t} - \lambda \hat{\nabla} \end{equation}

What are sufficient conditions on $g$ such that this converges to the optima? In particular, are there results of the form "if $\|\hat{\nabla}-\nabla\|<\epsilon$ and some-property-of-$f$ then gradient descent treating $\hat{\nabla}$ as the gradient converges to the optima"?

Answer by suVRit for Sufficient conditions for gradient descent convergence

2012-03-12T18:27:44Z

Ok, after reading your comments, and some thinking, here is one way to tackle what seems to be going on:

You have a nondifferentiable loss function.
You wish to compute a subgradient of the loss, but the subgradient is too expensive to compute
So you compute only a small part of some subgradient.

This is, the classic setting of an inexact subgradient projection method, where essentially you are iterating as follows:

$$ x^{k+1} = \Pi_X(x^k - \alpha_k(g^k+e^k)), $$ where $g^k$ is a subgradient of your loss function and $e^k$ is an error in the subgradient computation, which can be used to model the fact that you are not using all the components of the loss function to compute a subgradient.

Depending on what you are doing, this type of method might be cast as an online, stochastic, or incremental subgradient method.

I recommend that you have a look at the recent survey, your inexact computations will probably fit the general frameworks discussed therein.

D. P. Bertsekas, "Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey", Lab. for Information and Decision Systems Report LIDS-P-2848, MIT, August 2010; this is an extended version of a chapter in the edited volume Optimization for Machine Learning, by S. Sra, S. Nowozin, and S. J. Wright, MIT Press, Cambridge, MA, 2012, pp. 85-119.

Sufficient conditions for gradient descent convergence - MathOverflow

Sufficient conditions for gradient descent convergence

Answer by suVRit for Sufficient conditions for gradient descent convergence