The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$.

The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where $D(\alpha)=\frac{1}{n}\sum_{i=1}^n-\phi_i^*(-\alpha_i)+\frac{\lambda}{2}\left \|\frac{1}{\lambda n}\sum_{i=1}^n \alpha_ix_i\right \|^2$, where $\phi_i^*$ is the convex conjugate of $\phi_i$.

I spent almost two days, but still cannot figure it out why these two are primal-dual problem. Because the primal problem has no constrains, is the dual problem means its conjugate problem? I know if the primal problem has constraints, then I can use Lagrange form to find its dual. But this problem has no constraint, I kind of don't know what to do.

Here is my solution that can be used to obtain dual of ERM without forming constrained problem as shown by Michael above.

From Fenchel conjugacy one has: $$\phi(w^Tx) = \sup_z \langle w^Tx,z \rangle - \phi^*(z)$$ from where we conclude that $$\phi(w^Tx) \geq \langle w^Tx,z \rangle - \phi^*(z)$$ Using the above trick, we can lower bound the given objective function as: $$F(w,\alpha) = \lambda r(w) -\frac{1}{n}\sum_i(w^tx_i\alpha_i + \phi^*_i(-\alpha_i) ) \leq P(w)$$ where I have taken ${any}$ regularizer $r(w)$ and $z$ replaced by $-\alpha_i$. Next, we minimize the lower bound as: \begin{aligned} D(\alpha)&=\inf_w F(w,\alpha)\\ &=\inf_w \left( \lambda r(w) -\frac{1}{n}\sum_i(w^tx_i\alpha_i + \phi^*_i(-\alpha_i) )\right)\\ &=-\sup_w \langle w,\frac{1}{n}\sum_i x_i\alpha_i \rangle -\lambda r(w)-\frac{1}{n}\sum_i\phi^*_i(-\alpha_i)\\ &=-\lambda r^*(\frac{1}{\lambda n}\sum_i x_i\alpha_i)-\frac{1}{n}\sum_i\phi^*_i(-\alpha_i) \end{aligned} where in step 3, we used the linear algebra fact $\sum_i <.,.>=<.,\sum_i .>$; inf-sup equality and in the last step, the definition of conjugate and one property of conjuagtes (conjugate of $ah(x)$ is $ah^*(y/a)$).

• Can you explain more about the inf-sup equality in the last step. what do you mean by "inf-sup equality"? I think you use Fenchel conjugacy in the last step. – E.J. Dec 6 '15 at 16:52
• see here for equality used in 3rd step. Fenchel conjugacy is used in the last step. – chandresh Dec 6 '15 at 16:56
• But what you provide is a lower bound. – E.J. Feb 12 '16 at 17:53
• Exactly. Since your primal problem is minimization problem, minimizing the lower bound makes sense. As an exercise, you can check if strong duality holds? – chandresh Feb 13 '16 at 8:24

As you rightly point out, because this doesn't have any constraints, it can't possibly have any dual variables. So the dual offered by the author is not the true dual. I'm not exactly sure where you got this from, but its author has done a poor job of explaining what they're doing.

What the author likely has done here is create some sort of equivalent problem by introducing some additional variables into the primal problem. Here's my guess: given $y\in\mathbb{R}^n$, they created this equivalent problem: $$\begin{array}{ll} \text{minimize} & \tfrac{1}{n}\sum_{i=1}^n \phi_i(y_i) + \tfrac{\lambda}{2}\|w\|^2 \\ \text{subject to} & w^Tx_i = y_i, ~ i=1,2,\dots,n \end{array}$$ I believe that $\alpha_i$ above are Lagrange multipliers for these equality constraints. I might be off by a sign change, though for equality constraints that doesn't matter much.

Why don't you try deriving the dual of this modified problem and see if that matches up with $D(\alpha)$. If so, you can go chastise the author of the claimed primal/dual pair.

• Thanks for your suggestion. Let me try to derivate it from your equivalent problem. It seems to be the correct direction. I will let you know the result. Thanks again! – E.J. Jun 17 '14 at 22:37
• If set the constraint to $w^Tx_i+y_i=0$, then the dual problem is exactly as what they give. Thanks for your hint:) – E.J. Jun 18 '14 at 0:15
• Excellent! I am glad I could help. And I am glad you could finish the job. – Michael Grant Jun 18 '14 at 3:09