Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Are there further restrictions on $g$? Do you know the form of $g$? Is it linear? Nonlinear? It seems to me that it's difficult to develop general sufficiency conditions on an arbitrary $g$. For instance, we may say that a necessary condition might be that $g$ ought to have the same sign as $\nabla f$, but if $g$ is a nonlinear function that changes signs depending on the region, this statement may be problematic. A trivial sufficiency condition would be that $g(x) = x$. –  Gilead Mar 11 '12 at 18:16
1  
Oh, it seems that I just took $g$ to be the identity map. More generally, we can have $g(\nabla f(x)) = D\nabla f(x)$, where $D$ is a strictly positive definite matrix. That would ensure that $g(\nabla f(x))$ is a descent direction. Given that, and some minor technical assumptions, should ensure sufficiency. However, if $g$ is allowed to be a nonlinear transformation, then things can be trickier. However, maybe you have a more specific $g$ is mind? –  Suvrit Mar 11 '12 at 18:26
1  
There are certainly convergence theorems that work as long as the step direction is a descent direction for the function being minimized and the step length is selected so as to satisfy some special conditions (e.g. the Armijo conditions.) I don't think it's possible to say much more without knowing exactly what's being done to the gradient. –  Brian Borchers Mar 11 '12 at 18:29
1  
Based on Brian's comment, perhaps broad sufficiency conditions would be that $g$ (1) maps to a descent direction; and (2) satisfies Armijo conditions in the domain of interest. Those are pretty general conditions, but it's harder to get more specific without additional restrictions on $g$. –  Gilead Mar 12 '12 at 0:35
2  
Ah, there may be another difficulty here. Hinge loss functions are non-smooth, and many standard convergence proofs generally stipulate that the function of interest is at least once-differentiable everywhere. The standard gradient descent method is undefined for non-differentiable functions. One may need to look at subgradient methods or bundle methods which may have completely different convergence criteria. (I'm not familiar with those) –  Gilead Mar 12 '12 at 15:04

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
I'm confused- the original poster referred to the gradient as if this was a smooth problem. How did we jump to considering nonsmooth problems? –  Brian Borchers Mar 12 '12 at 19:44
    
@Brian, in a comment, he mentioned that the objective $f$ was a sum of hinge losses. en.wikipedia.org/wiki/Hinge_loss –  Gilead Mar 12 '12 at 22:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.