# Choice of Lipschitz constant for proximal gradient optimization

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?

• you can use L=2*[maxium of eigenvalue(A'A)]
– user64303
Dec 25, 2014 at 14:29

• 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 6:07
• 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 17:37