2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$
    – Gilead
    Mar 11, 2012 at 18:16
  • 1
    $\begingroup$ 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? $\endgroup$
    – Suvrit
    Mar 11, 2012 at 18:26
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 11, 2012 at 18:29
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Gilead
    Mar 12, 2012 at 0:35
  • 2
    $\begingroup$ 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) $\endgroup$
    – Gilead
    Mar 12, 2012 at 15:04

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Mar 12, 2012 at 19:44
  • $\begingroup$ @Brian, in a comment, he mentioned that the objective $f$ was a sum of hinge losses. en.wikipedia.org/wiki/Hinge_loss $\endgroup$
    – Gilead
    Mar 12, 2012 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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