5
$\begingroup$

Let $f$ be a jointly convex function of 2 variables say $x,y$. I am interested in solving the optimization problem $$\min_{x,y\in\Delta} f(x,y)$$ where $\Delta$ is a $d$ dimensional simplex. An intuitive algorithm that I have come up with is a coordinate mirror descent algorithm, where in each iteration we perform two steps. In the first step I fix one variable, say $x$, and optimize w.r.t y (almost) exactly by performing many steps of mirror descent, with the entropy function. The second step is similar to the first step, but now we shall perform mirror descent w.r.t. the second variable. This algorithm is performed repeatedly until convergence.

My question is that have people studied such algorithms? I know that there is literature on coordinate descent, but I have not seen any coordinate mirror descent type of algorithms. I am particularly interested in convergence guarantees, and rates of convergence. Intuitions/counter-examples are also welcome.

I know that I can avoid mirror descent procedure, and instead perform gradient descent coordinate-wise. The reason why I want to avoid this is because mirror descent with the entropy function is a natural fit when the constraint set is a simplex, and I can devise simple exponential updates for each sub problem being solved.

P.S. Turns out that, such coordinate mirror descent algorithms, will converge provably. For further results see the following paper. http://arxiv.org/abs/1309.2249

Improve this question
$\endgroup$
4
  • $\begingroup$ Perhaps you would care to enlighten me as to what "mirror descent" is, and what "the entropy function" is?! $\endgroup$
    – Igor Rivin
    Jul 16, 2013 at 1:28
  • $\begingroup$ mirror descent is an optimization algorithm for convex functions, that utilizes distances defined by the Bregman divergence of another convex function $\phi$. In this case since our optimization problem is over simplex, a good choice of $\phi$ is $\phi(x)=\sum_{i} x_i \log (x_i)$, when $x\in \Delta$ with $\Delta$ being the simplex in $\mathbb{R}^{n}$, and $\infty$ otherwise. For more details kindly look at the paper "Mirror descent and nonlinear projected subgradient methods for convex optimization" by Amir Beck and Marc Teboulle, where they discuss minimizing a convex function over simplex. $\endgroup$
    – gmravi2003
    Jul 16, 2013 at 5:31
  • $\begingroup$ I just want to point out that the key word for your question is: 'alternating minimization' or 'coordinate descent'. This area has grown significantly: see en.wikipedia.org/wiki/Random_coordinate_descent $\endgroup$
    – Cristóbal Guzmán
    Apr 13, 2014 at 23:01
  • $\begingroup$ Thanks Cristobal. I would like to point out that the posted problem has been solved. Here is a link to the paper. arxiv.org/abs/1309.2249 $\endgroup$
    – gmravi2003
    Apr 13, 2014 at 23:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.