0
$\begingroup$

Sorry for asking a very simple question:Why block coordinate descent and block coordinate gradient descent are identical in quadratic case? I think question is clear it self. But if you need context please pay attention to the following:

In the paper, An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming, it is said that a well known technique for solving a problem \begin{align} min{\Psi(x) := \theta(x) + \zeta(x) } \end{align} ($\zeta(x)$ differentiable, with $x=(x_1,x_2,...,x_q)$, $x_i$ block of variables) is block coordinate descent (BCD), i.e. at iteration $t$ one may update blocks based on gauss-siedel fashion: \begin{align} x_1^{k+1} &= arg\min_{x_1} \Psi(x_1,x_2^{k},...,x_q^{k})\\ ...\\ x_i^{k+1} &= arg\min_{x_i} \Psi(x_1^{k+1},...x_i,...,x_q^{k})\\ ...\\ x_q^{k+1} &= arg\min_{x_q} \Psi(x_1^{k+1},...,x_{q-1}^{k+1},x_q) \end{align} it is in the paper, that if the above subproblems are not easily solvable, a popular approach is to use a single step of the proximal gradient (PG) method, therefore block coordinate gradient descent (BCGD) method. It is said that if $\zeta(x)$ is a quadratic function, then BCD and BCGD are identical.

My questions is why they BCD and BCGD are identical in quadratic case? and what is the exact form of BCGD for the above gauss-siedel fashion?

$\endgroup$
  • $\begingroup$ Actually, the authors write that their new accelerated block gradient descent (ABCGD) is equivalent to BCD in the quadratic case. $\endgroup$ – Brian Borchers Jan 20 '17 at 21:35
0
$\begingroup$

Fortunately, the author responded to my email. The following is my understanding of his answer.

With a semi-proximal term, gradient descent, is the following:

At iteration $t$ one may update by \begin{align} x^{k+1} &= arg\min_{x} \langle \triangledown_{x}\zeta(x^k), x-x^k\rangle+\theta(x)+\frac{1}{2}\Vert x-x^k \Vert^2_\mathcal{H}\\ \end{align} In the quadratic case, hessian of $\Psi(x)$ is constant. So if we let $\mathcal{H} =\bigtriangledown^2\Psi(x)$, then the above problem becomes equivalent to original quadratic problem. If optimized block coordinately, it is equivalent to BCD.

$\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.