1
$\begingroup$

I am reading Andrew Ng's SVM notes (https://see.stanford.edu/materials/aimlcs229/cs229-notes3.pdf) and am lacking the intuition for why we need the functional margin. As far as I understand we need it as the following optimization problem expressed only in terms of the geometric margin is not convex:

$max_{\gamma, w, b} = \gamma$

such that $y_{i}(w^{T}x + b) \geq \gamma $ $i = 1 \ldots m$

and $\lvert \lvert w \rvert \rvert = 1$

The constraint $\lvert \lvert w \rvert \rvert = 1$ is not convex. Suppose for the sake of understanding the importance of the functional margin that $\lvert \lvert w \rvert \rvert = 1$ is convex and we can directly optimize this problem. Could we then entirely forget about the concept of the functional margin? In other words, do we only need the notion of a functional margin, as it allows us to rewrite the above equation as a convex optimization problem?

$\endgroup$

1 Answer 1

1
$\begingroup$

Generally, the single constraint $||w||^2 = 1$ actually has zero-duality gap.

However, a simpler explanation can help for this situation. We can actually solve instead for $||w||^2 \leq 1$, which is convex. To see this, note though that if $||w||^2 < 1$ then if I multiply $\gamma$ and $w$ by some factor $\beta > 1$ that I maintain the constraint, and improve the objective. Thus, given any valid solution having $0 < ||w||^2 < 1$, I can simply multiply through by $\beta = \frac{1}{||w||^2}$ to maximize the objective, for $w$ pointing in "that direction". Thus, the constraint $||w||=1$ can actually be replaced by the convex $||w||^2 \leq 1$.

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