How do I obtain the primal and dual for the estimator $\min _\beta\left[\|\beta\|^2+\sum_{i=1}^n \xi_i^2\right]$ s.t. $\xi_i=y_i-h(x_i)^\top \beta$?

Question

I am working on a statistical learning exercise that requires some knowledge of convex optimization which I am unfortunately lacking.

Consider the linear regression model $$y_i=h(x_i)^\top\beta+\epsilon_i \quad i=1,\ldots,n$$ where $\varepsilon_i$ are random errors. Consider a symmetric, positive definite kernel $K(x_i, x_j)=h(x_i)^\top h(x_j)$. The estimator $\hat{\beta}$ is the solution to $$\min _\beta\left[\|\beta\|^2+\sum_{i=1}^n \xi_i^2\right]$$ subject to the constraint $\xi_i=y_i-h\left(x_i\right)^{\top} \beta$.

I am now asked to give (i) the Lagrange primal function, (ii) the Wolfe dual function and (iii) to derive an expression for $\hat{\beta}$.

For (i), by plugging in the equality constraint and introducing Lagrangian multipliers I get $L_P=\beta^\top\beta+\sum_{i=1}^n \alpha_i(y_i-h(x_i)^\top\beta)^2$.

For (ii), I compute $$\frac{\partial L_P}{\partial \beta}=\beta+2\sum_{i=1}^n\alpha_iy_ih(x_i)-2\sum_{i=1}^n\alpha_ih(x_i)^\top\beta h(x_i)=0.$$

Now I reckon I must isolate $\beta$ in the above and plug the expression I obtain into the primal problem to obtain the dual. I am stuck here. If my derivation so far is correct, I’d appreciate a hint on how to do this. (If it is not I’d of course be glad to be made aware of any mistake.) Thanks for considering my question!

Answer 1

There's a few minor issues in the earlier parts -- I'll provide some hints.

(i) If I recall correctly this is simply the Lagrangian function (i.e., the objective of the Wolfe dual). For an equality-constrained problem of the form $$\underset{x}{\text{minimize}}\quad f(x) \\ \text{subject to} \quad g(x) = 0,$$ this would take on the form $f(x) + \alpha g(x)$, or $f(x) + \mathbf{\alpha}^\top \mathbf{g}(x)$ if you have multiple constraints as in this problem.

Substituting the definition $\zeta_i$ into the original objective directly defeats the purpose of having a constraint; while this constraint appears vacuous, sometimes adding such constraints can make the derivation of the dual go more smoothly. See if (changing $x$ to $\beta$) you can get your problem into the above form to obtain the Lagrangian primal.

(ii) You have the right idea for the dual (partial derivative of the primal w.r.t. $\beta$); I believe this is straightforward once (i) is correct. As a small detail, your answer should probably be formulated as an optimization problem (i.e., maximize something subject to first-order condition = 0) — you currently just have a first-order condition.

(iii) This is arguably the tough part if you haven't seen some linear algebra tricks before. You will get something of a similar form to the first-order condition you've provided (most terms are of the same order). It might be useful to note that, given some vectors $\mathbf{u}, \mathbf{v}$, $(\mathbf{u}^\top \mathbf{v}) \mathbf{u} = (\mathbf{u}\mathbf{u}^\top)\mathbf{v}$ (convince yourself that this holds). Substitute the variables for your problem accordingly.

As a sanity-check, you might also notice that this is simply a formulation of kernelized ridge regression -- it's not a huge deal (for the purposes of wrangling the objective) to ignore the kernel for now, and try to pattern-match with the ridge regression optimum. It is also a decent exercise to use cxvpy to simulate this problem to double-check.

In short, you seem to have the general right ideas/intuition for what you need to do for (ii), (iii), but there are some errors in the derivation for (i). Please feel free to follow-up if anything is unclear.

Answer 2

Per (i), the Lagrangian isn't defined by plugging in the equality constraints multiplied by Lagrange multipliers to the objective function.

Given an optimization problem with equality constraints $\{g_i(x) = 0 \}_{i=1}^n$, $$ \min f(x)\: s.t. \: g_i(x) = 0\:\forall i, $$ the Lagrangian would be of the form $\mathcal{L}(x,\alpha) = f(x)+\alpha^Tg(x)\qquad (*)$.

Make sure to "convert" your constraints to the form $g(x) = 0$ before you plug them into $(*)$.

Per (ii), admittedly, I wasn't familiar with the concept of Wolfe Duality up until this thread. However, the Wikipedia article linked here doesn't seem to make sense to me.

Since you have only equality constraints, the Lagrangian Dual problem would have Lagrangian multipliers unconstrained. The Lagrangian Dual and the Wolfe Dual should be equivalent. The Primal problem could be alternatively stated $$ \min_{\beta\in\mathbb{R}} \{ \max_{\alpha\in\mathbb{R}} \{||\beta||^2 + ||\xi||^2 + \sum_i \alpha_i \left( y_i - \beta^Th(x_i) -\xi_i \right) \}\} \equiv \min_{\beta\in\mathbb{R}} \{ \max_{\alpha\in\mathbb{R}} \{ \mathcal{L}(\beta,\alpha)\}. $$

The Lagrangian Dual problem: $\max_{\alpha\in\mathbb{R}} \{ \min_{\beta\in\mathbb{R}} \mathcal{L(\beta,\alpha)} \}$.

Therefore, I think the Wolfe Dual would more or less take the form: $$ \max_{\alpha\in\mathbb{R}} \{ \min_{\beta\in\mathbb{R}} \mathcal{L(\beta,\alpha)} \} \\ s.t. \\ \nabla f(\beta)+\alpha^T\nabla g(\beta) = 0. $$ Notice the $\alpha$ multipliers are unconstrained.

If it's a homework assignmentI think your professor\TA aimed at you'd simplify the $ \min_{\beta\in\mathbb{R}} \mathcal{L(\beta,\alpha)} $ term in the problem above to get a maximization problem with only the $\alpha$ parameters (dual variables) to optimize. IMHO, you should be able to express the $\beta$s in terms of $\alpha$.

Hope it helps.