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||$?


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$

  • 1
    $\begingroup$ Thank you so much! $\endgroup$ – RNN Oct 27 '18 at 8:42

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.