3
$\begingroup$

I have the following optimization problem

\begin{equation} \label{logdual} \begin{array}{ll@{}ll} \text{minimize}_{\pmb\alpha \in \mathbb{R}^n} & \theta(\pmb\alpha) &\\ \text{subject to} & \pmb\alpha > 0 &\\ \end{array} \end{equation}

where $\theta(\pmb{\alpha}) = \frac{1}{2\lambda} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x_i}^T\mathbf{x_j} + \sum_i \alpha_i \log{\alpha_i} + (1-\alpha_i)\log(1 - \alpha_i)$

$\mathbf{x_1}, \mathbf{x_2}, \dots, \mathbf{x_n}$ are $n$ data points where $\mathbf{x_i} \in \mathbb{R}^d$ and $y_1, y_2, \dots, y_n$ are binary labels for each data point such that $y_i \in \{1, -1\}$

This is also happens to be the Lagrangian dual of the $\ell_2$-Logistic regression problem.

My attempt to show that this is convex was to show that the Hessian $\mathbf{H}$ of $\theta(\pmb\alpha)$ is positive definite but I am unable to do so. I tried following the approach given in Section 9 of this paper. Here they show that the following

$$ \frac{\partial^2\theta(\pmb\alpha)}{\partial \alpha_i^2} = \frac{1}{\lambda}y_i^2\mathbf{x_i}^T\mathbf{x_i} + \frac{1}{\alpha_i(1 - \alpha_i)} $$ $$ \frac{\partial^2\theta(\pmb\alpha)}{\partial \alpha_i \partial \alpha_j} = \frac{1}{\lambda}y_iy_j\mathbf{x_j}^T\mathbf{x_i} $$

and then proceed to state that the Hessian $$\mathbf{H} = \frac{1}{\lambda}\text{diag}(\mathbf{y})\mathbf{X}^T\mathbf{X} \text{diag}(\mathbf{y}) + \text{diag}\left(\frac{1}{\alpha_i(1-\alpha_i)}\right)$$

and if so then because $\mathbf{x}\mathbf{x}^T$ is positive definite then so is $\mathbf{H}$ but I am unable to follow how the author came up with the term $\mathbf{X}^T\mathbf{X}$ in $\mathbf{H}$

I have been at this for hours now and any explanation would be really helpful!

$\endgroup$
  • $\begingroup$ Hint: Avoid computing the Hessian, if you can, and use the calculus of convex functions instead! Define $\mathbf z_i = y_i \mathbf x_i$ and the corresponding matrix $\mathbf Z = (\mathbf z_i)$. Can you rewrite the first term as a quadratic function of the vector $\alpha$ and utilizing $\mathbf Z$ appropriately? Is the corresponding quadratic convex? If so, what, then what do you know about the sum of convex functions? $\endgroup$ – cardinal Dec 15 '16 at 20:05
  • 1
    $\begingroup$ One also needs the constraint $\alpha_i \leq 1$, otherwise $\log (1 - \alpha_i)$ goes imaginary. $\endgroup$ – Rodrigo de Azevedo Dec 15 '16 at 20:09
  • $\begingroup$ @cardinal I rewrote the first term as $\frac{1}{2\lambda}(\mathbf{\alpha} \mathbf{Z})^T(\mathbf{\alpha Z})$ This gives me $\frac{1}{2\lambda}\mathbf{Z}^T\mathbf{\alpha}^T\mathbf{\alpha} \mathbf{Z}$ but I am unable to draw any further conclusions from here. $\endgroup$ – Banach Tarski Dec 15 '16 at 20:16
  • $\begingroup$ @cardinal I see that $\pmb{\alpha}^T \pmb{\alpha}$ is convex but how does this become a sum of convex functions? $\endgroup$ – Banach Tarski Dec 15 '16 at 20:23
  • $\begingroup$ Banach: It's always good to double-check the basic properties of an expression you derive. If you are treating $\alpha$ as a column vector, then your resulting expression is a matrix, not a scalar (whoops!), and if you were treating it as a row vector, then the expression makes no sense at all since the dimensions do not conform (unless $n = d$, and even then the result is incorrect). $\endgroup$ – cardinal Dec 15 '16 at 20:23
3
$\begingroup$

Note that $\log (1-\alpha_i)$ imposes the inequality constraint $\alpha_i \leq 1$. Thus, $0 \leq \alpha_i \leq 1$.

Note also that, if $p \in [0,1]$, then

$$p \log (p) + (1-p) \log (1-p) \propto - \mathcal{H} (p)$$

where $\mathcal{H} (p)$ is the famous binary entropy function, which is concave. Hence,

$$\alpha_i \log (\alpha_i) + (1-\alpha_i) \log (1-\alpha_i)$$

is convex and, thus, the sum

$$\sum_{i=1}^n \left( \alpha_i \log (\alpha_i) + (1-\alpha_i) \log (1-\alpha_i) \right) = - \sum_{i=1}^n \mathcal{H} (\alpha_i)$$

is also convex. Let

$$c_{ij} := y_i y_j \mathrm x_i^{\top} \mathrm x_j$$

and let $\mathrm C$ be the $n \times n$ matrix whose $(i,j)$-th entry is $c_{ij}$. Let $\mathrm X$ be the $d \times n$ matrix whose $i$-th column is $\mathrm x_i$, and let $\mathrm y := (y_1, y_2, \dots, y_n)$. Hence,

$$\mathrm C = (\mathrm X \, \mbox{diag} (\mathrm y))^{\top} (\mathrm X \, \mbox{diag} (\mathrm y)) = \mbox{diag} (\mathrm y) \, \mathrm X^{\top} \mathrm X \, \mbox{diag} (\mathrm y) \succeq \mathrm O$$

and, thus,

$$\sum_{i=1}^n \sum_{j=1}^n c_{ij} \alpha_i \alpha_j = \langle \mathrm C, \alpha \alpha^{\top} \rangle = \alpha^{\top} \mathrm C \, \alpha$$

is also convex. We conclude that if $\lambda > 0$, then the cost function $\theta$ is convex.

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