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

Improve this question
$\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
    Commented 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
    Commented 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$
    – Brian Borchers
    Commented 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
    Commented 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
    Commented Mar 12, 2012 at 15:04

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Brian Borchers
    Commented 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
    Commented Mar 12, 2012 at 22:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .