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"?



Sufficient conditions for gradient descent convergence
Ok, after reading your comments, and some thinking, here is one way to tackle what seems to be going on:


1. You have a nondifferentiable loss function.
2. You wish to compute a subgradient of the loss, but the subgradient is too expensive to compute
3. 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. 
> 
> 
> 


