1
$\begingroup$

I was reading up on the dual formulation of SVMs and have some questions to ask. https://github.com/epfml/ML_course/blob/master/lectures/07/lecture07a_svm.pdf

enter image description here

1) Why is it easy to optimize via coordinate ascent ? Is it because $\alpha$ is bounded between [0,1] ? If it is not because of its range of [0,1], then what about logistic regression ? Why does no one talk about coordinate descent for logistic regression ? Can alpha only be 0 or 1 ? Can it take any other values in between ?

enter image description here

2) From the diagram and also point no. 2, $\alpha_2 \subset (0,1) $. When would it be zero and when would it be 1 ? If it lies exactly on the margin then wouldn't that make $\max_{\alpha}\alpha_2[1 - y_2f_2] = 0 $ since it is correctly classified ? i.e. $f_2 = 1$

$\endgroup$
1
$\begingroup$

I think the simplest way to answer this is that it is easy to optimize via coordinate ascent because you only have box constraints (this is because you are solving for the unbiased version of SVM which doesn't have the constraint $\sum_i \alpha_i y_i = 0$). Thus, you can optimize for each $\alpha_i$ separately and not worry about any constraint violation (i.e., optimize for $\alpha_i \in [0,1]$). If you had the biased version, then for example SMO by Platt could be used which chooses a pair for which to optimize at each stage (and maintains the bias constraint throughout). $\alpha$ can be any value between 0 and 1, in particular for vectors on the margins (technically, if $\alpha_i$ is between 0 and 1, then $x_i$ must be on the margin).

You can also solve logistic regression using coordinate descent; from an optimization perspective there are additional questions around whether there are closed-form solutions to solving for a single variable at a time, or whether optimization needs to be done to solve or approximately solve. There are numerous methods which solve using for example dual coordinate descent. Here is one such method, which also discusses solving via updates to a single variable.

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