Timeline for Choice of Lipschitz constant for proximal gradient optimization
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2013 at 2:20 | comment | added | user30473 | @Suvrit, I have same query as digdug. You mentioned to consider operator-2 norm of the Hessian to get the desired Lipschitz constant. Is there any theoretical justification to it ? | |
| Nov 15, 2012 at 23:18 | comment | added | Suvrit | I would recommend reading page 51 to 58 of Nesterov's book Introductory lectures on convex optimization (it might not appear super easy to you at first sight, but bear with it; it is actually very nicely presented). In your case, basically something simple happens. For a quadratic function, the derivative is linear. So when you try to bound $\|\nabla f(X)-\nabl f(Y)\|$ you essentially end up having to bound something of the form $\|A(X-Y)\|$. Now, invoke "sub-multiplicativity" of the 2-norm (see en.wikipedia.org/wiki/Matrix_norm) to bound this by $\|A\| \|X-Y\|$, etc. | |
| Nov 15, 2012 at 22:27 | comment | added | digdug | Great! Is there a reference/tutorial that explains this? | |
| Nov 15, 2012 at 22:26 | vote | accept | digdug | ||
| Nov 15, 2012 at 17:37 | comment | added | Suvrit | Ah ok, well, your function $f(B)$ is a convex quadratic in $B$, so just use the operator-2 norm of the Hessian to get the desired Lipschitz constant. The latter thing that you mentioned with $\psi$ can be ignored for now. | |
| Nov 15, 2012 at 11:04 | comment | added | digdug | Thanks again, but my question is simply how do I compute the Lipschitz constant, at least for the above function? I cannot find a derivation in Vandenberghe's notes. | |
| Nov 15, 2012 at 6:07 | comment | added | Suvrit | If you can compute the Lipschitz constant explicitly, then you might certainly want to use it (except if you are using "early" termination, in which case using stepsizes bigger than $1/L$ for the first few iterations might not be bad!)---also, the notes that I linked to are from Vandenberghe's lectures, which are really quite nice :-) | |
| Nov 15, 2012 at 5:39 | comment | added | digdug | Thanks, but in simple cases like above where the Lipschitz constant can be derived beforehand, wouldn't that be more computationally efficient than line search? Plus I'd like to understand the basics first... | |
| Nov 15, 2012 at 5:24 | history | answered | Suvrit | CC BY-SA 3.0 |