Sufficient conditions for gradient descent convergence 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"?
 A: 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. 

