Timeline for Sufficient conditions for gradient descent convergence
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 12, 2012 at 21:50 | vote | accept | Alex Flint | ||
| Mar 12, 2012 at 18:27 | answer | added | Suvrit | timeline score: 3 | |
| Mar 12, 2012 at 18:20 | comment | added | Suvrit | @Alex: As Gilead has pointed out, because you are dealing with a non-differentiable loss function, we are in a totally different setup: the primary reason being that an arbitrary subgradient does not yield a "descent direction", whereby, some other juggling has to be done to ensure convergence. And, given your description now I see how to prove convergence of the kind you have in mind. Because your problem is convex, this can be done. Please edit your question to ask the actual thing you have in mind, then maybe one can provide a more precise answer. | |
| Mar 12, 2012 at 15:04 | comment | added | Gilead | 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) | |
| Mar 12, 2012 at 14:38 | comment | added | Alex Flint | Thanks all. In the problem I'm working with, $f$ is a sum over a large number of hinge losses $h_i$, and $g$ is an algorithm that computes the gradient of $\hat{f} = \sum h_j$ where $j$ ranges over some but not all of the $i$'s. In fact I know lots about the structure of $g$, but at the moment this is in the form of an algorithmic description of $g$ not directly amenable to reasoning about convergence. My goal is to prove that gradient descent using $g$ converges to the optima, and I'm trying to figure out what I should prove about $g$ to show this. | |
| Mar 12, 2012 at 0:35 | comment | added | Gilead | 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$. | |
| Mar 11, 2012 at 18:29 | comment | added | Brian Borchers | 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. | |
| Mar 11, 2012 at 18:26 | comment | added | Suvrit | 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? | |
| Mar 11, 2012 at 18:16 | comment | added | Gilead | 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$. | |
| Mar 11, 2012 at 17:34 | history | asked | Alex Flint | CC BY-SA 3.0 |