3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ you can use L=2*[maxium of eigenvalue(A'A)] $\endgroup$
    – user64303
    Commented Dec 25, 2014 at 14:29

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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... $\endgroup$
    – digdug
    Commented Nov 15, 2012 at 5:39
  • $\begingroup$ 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 :-) $\endgroup$
    – Suvrit
    Commented Nov 15, 2012 at 6:07
  • $\begingroup$ 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. $\endgroup$
    – digdug
    Commented Nov 15, 2012 at 11:04
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Commented Nov 15, 2012 at 17:37
  • $\begingroup$ Great! Is there a reference/tutorial that explains this? $\endgroup$
    – digdug
    Commented Nov 15, 2012 at 22:27

You must log in to answer this question.

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