4
$\begingroup$

Consider the problem

\begin{equation} \min_{x\in X, y \in Y} f(x,y) \end{equation}

Can I solve the problem by iteratively solving the following two sub problems?

\begin{equation} x_{k+1} = \arg\min_{x\in X} f(x,y_k) \end{equation}

\begin{equation} y_{k+1} = \arg\min_{ y \in Y} f(x_k,y) \end{equation}

If yes, is there any books/papers talking about this kind of approach?

Thanks

$\endgroup$
3
$\begingroup$

It's not hard to show that if $f$ is strongly convex then this approach converges and you can give an upper bound on the number of iterations needed.

If $f$ is strictly convex, but not strongly convex, this might converge very slow or even not converge at all.

If $f$ is not convex at all, you are likely to end in a local optima rather than the global one.

You might also like to take a look at the Expectation–maximization algorithm which is quite similar, but also deals with unobserved values.

Also, there are applications where $f$ is a non-convex function at all with respect to $x,y$, but it is convex w.r.t. each of them (e.g. $f(x,y)=xy$). In these problems, the iterative process you describe is many times used in practice and works quite well.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Is there any references about this method? $\endgroup$ – Lib Jun 25 '14 at 7:23
4
$\begingroup$

This is a very popular heuristic method in machine learning, known as alternating minimization. You can easily find tons of papers using it. Often the setting in which it is used is when $f(x,y)$ is convex in $x$ and $y$ separately (so each minimization step can be done via some variant of gradient descent), but not jointly convex. In this case, as RB notes, it is not apriori clear that this method converges to an optimal solution at all. A classical paper by Csiszar and Tusnady gives a general "five point criterion" for convergance to the global optimum, and proves that it holds for $f$ equal to the KL-divergence. More recently, Jain, Nethrapalli and Singhavi, and Hardt have analyzed variants of this approach for the matrix completion problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.