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

I'm trying to use proximal gradient methods (Forward-Backwards Splitting and FISTA) to minimize a function

$f(B) = \frac{1}{2}|| XB - Y||_F^2 + \frac{\gamma}{2}||B C^T||_F^2$, where $X \in \mathbb{R}^{N \times p}, Y \in \mathbb{R}^{N \times K}, B \in \mathbb{R}^{p \times K}, C \in \mathbb{R}^{E \times K}.$

I know this can be done with gradient descent but I'd like to use proximal methods anyway for didactic purposes. Since the entire function is twice differentiable, I don't care about the actual prox operator at the moment.

Now, the basic proximal methods require computing the Lipschitz constant L. I have seen different versions of this, e.g.

$L = ||X^T X||_2^2 \;||H_w \psi||_2^2$

where $||\cdot||_2^2$ is squared spectral norm of the matrix and $H$ is Hessian of the function $f(w) =\psi(Xw)$ (http://www.di.ens.fr/~fbach/bach_jenatton_mairal_obozinski_FOT.pdf, p. 43). I've seen other formulations in other papers, which is confusing.

Is there a "canonical" way to derive a "good" Lipschitz constant for these sort of functions?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

In practice, you would not want to run a vanilla prox-gradient method that requires knowledge of the Lipschitz constant. Instead, you'd use a method that combines line-search (these notes give a nice, quick overview, along with pseudocode). More careful versions of FISTA-style and other prox-gradient methods exist, that do not require knowledge of the Lipschitz constant. Shameless plug: A trust-region proximal splitting method that my co-authors and I once developed.

share|improve this answer
    
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... –  digdug Nov 15 '12 at 5:39
    
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 :-) –  Suvrit Nov 15 '12 at 6:07
    
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. –  digdug Nov 15 '12 at 11:04
    
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. –  Suvrit Nov 15 '12 at 17:37
    
Great! Is there a reference/tutorial that explains this? –  digdug Nov 15 '12 at 22:27

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.