Upper bound on SVM solution

Question

Given a solution $w,b,\zeta$ to primal SVM soft margin optimization, and the solution $\alpha$ to the duel problem. What is the upper bound on $||w||$?

Answer 1

Recall the SVM soft margin optimization problem:

$min :f(w,b,ξ)=(1/2)w^T w+C∑_1^mξ_i$

with the constraints:
$∀i=1..m : y_i (w^T x_i+b)≥1- ξ_i, ξ_i≥0$

Let $w^*,b^*,ξ^*$ the solution to the problem. Recall the dual problem:

$max: g(α)=(-1/2) w^T w+∑_1^m α_i ,C≥α_i≥0 $

Let $α^*$ be the solution to the dual problem. The primal objective value is equal to the dual objective value at the optimum. Therefore:

$ (1/2) (w^*)^T w^*+C∑_1^m (ξ^*)_i =(-1/2) (w^*)^T w^*+∑_1^m (α^*)_i .$

From this we can derive that $(w^*)^T w^*=-C∑_1^m (ξ^*)_i +∑_1^m (α^*)_i $

However, $C≥α_i, ξ_i≥0 $ and thus:

$‖w^* ‖^2=(w^*)^T w^*=-C∑_1^m (ξ^*)_i +∑_1^m (α^*)_i ≤-C∑1^m (ξ^*)_i +mC=C(m-∑_1^m (ξ^*)_i )≤Cm$

Therefore, $‖w^* ‖≤√Cm$