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.