Sufficient conditions for gradient descent convergence - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:56:25Z http://mathoverflow.net/feeds/question/90918 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90918/sufficient-conditions-for-gradient-descent-convergence Sufficient conditions for gradient descent convergence Alex Flint 2012-03-11T17:34:38Z 2012-03-12T18:27:44Z <p>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: $$x^{t+1} = x^{t} - \lambda \hat{\nabla}$$</p> <p>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\|&lt;\epsilon$ and some-property-of-$f$ then gradient descent treating $\hat{\nabla}$ as the gradient converges to the optima"?</p> http://mathoverflow.net/questions/90918/sufficient-conditions-for-gradient-descent-convergence/91006#91006 Answer by suVRit for Sufficient conditions for gradient descent convergence suVRit 2012-03-12T18:27:44Z 2012-03-12T18:27:44Z <p>Ok, after reading your comments, and some thinking, here is one way to tackle what seems to be going on:</p> <ol> <li>You have a nondifferentiable loss function.</li> <li>You wish to compute a subgradient of the loss, but the subgradient is too expensive to compute</li> <li>So you compute only a small part of some subgradient.</li> </ol> <p>This is, the classic setting of an <strong>inexact subgradient projection</strong> method, where essentially you are iterating as follows:</p> <p>$$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 <em>error</em> 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.</p> <p>Depending on what you are doing, this type of method might be cast as an <em>online</em>, <em>stochastic</em>, or <em>incremental</em> subgradient method.</p> <p>I recommend that you have a look at the recent survey, your <em>inexact</em> computations will probably fit the general frameworks discussed therein.</p> <blockquote> <p><strong>D. P. Bertsekas</strong>, "<em>Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey</em>", 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 <strong>Optimization for Machine Learning</strong>, by S. Sra, S. Nowozin, and S. J. Wright, MIT Press, Cambridge, MA, 2012, pp. 85-119. </p> </blockquote>