0
$\begingroup$

I've take multiple machine learning classes and I am always told been told say when we do regularization on the training error $\mathcal E(W) = \frac{1}{n} \sum^n_{i=1}Loss(f(x_i),y_i)$:

$$ \text{ (1) } \min_W L(W,\lambda) = \mathcal E(W) + \lambda \|W\|^2 $$

and that the above is equivalent to the constraint problem:

$$ \text{ (2) } \min_W \mathcal E(W) \text{ subject to } \|W\|^2 \leq R^2$$

and that some $\lambda$ corresponds to some radius $R$. This last claim is the one I don't fully understand why is true. The reason is the following. Usually I am told that the equivalence between the two comes from Lagrange multipliers. I think I do understand Lagrange multipliers (when constraints are equalities), in that case if we have an objective function $f(x)$ with constraint $h(x) = R$ then we just make a new constraint $g(x) = h(x) - R = 0$

$$ \min/\max f(x) \text{ subject to } g(x) = 0 $$

and solve wrt to $x$ and $\lambda$ the auxiliary equation:

$$ \mathcal L(x,\lambda) = f(x) + \lambda g(x)$$

in the following way:

$$ \nabla_{x,\lambda} L(x,\lambda) = 0 $$

and that works because that satisfies that the objective function and constraint have parallel paths (so intuitively you can't improve f if you keep walking in g so its a critical point):

$$ \nabla f(x) = -\lambda g(x)$$

however usually in Lagrange multipliers we also take the derivative with respect to $\lambda$ because that implies the constraint is satisfied. However, because $\lambda$ is of degree 1 then it disappears we take the take the derivative:

$$ \nabla_\lambda L(x, \lambda) = \nabla_\lambda (f(x,y) - \lambda g(x,y)) \iff g(x,y) = 0 $$

which satisfies the constraint but seems to be independent of any value of $\lambda$...this is the part where I get confused because usually in Tikhonov like Regularization we impose $\lambda > 0 $ which now I guess I see that the value of $\lambda$ doesn't matter because this last equation is always satisfied no matter what value it takes... but I've always been told that each different $\lambda$ corresponds to some different radius and I've never actually mathematically clearly seen why thats true. Can someone show me this? I guess intuitively its always sort of made sense because the larger $\lambda$ the more the constraint is enforced so the smaller $R$? Why can't we see an explicit relationship between the two $R$ and $\lambda$ even if its just theoretically or in paper?

Also usually in machine learning we solve (2) and find some minimum (or critical point, even in neural nets things are empirically known to be minimums because the training loss is usually extremely close to zero or zero, as low as it can go by design) so because of this we know we are in a critical point of $L$ with respect to $W$, but are we in a critical point with respect to $\lambda$? It seems that we always are at a critical point with respect to $\lambda$ no matter its value so we only need to worry about minimizing with respect to $\lambda$?

What is up with this $\lambda$ constraint and how do we know in machine learning that we are choosing it so that it actually satisfies the constraint and how does it relate to the constraint?

$\endgroup$
  • $\begingroup$ Note that the way you have formulated this problem, there would never be any value in Lagrange multipliers for any problem, since $f(x)$ and $g(x)$ are generic functions. A simple, heuristic way of thinking about this is that if the optimum $x$ is continuous in $\lambda$ in your auxiliary equation, which it will be if $f$ and $g$ are continuous, then as you increase $\lambda$, $x$ will decrease monotonically, therefore $||W||^2$ will decrease monotonically, therefore for every $\lambda$ there will be a unique minimum $R^2$ s.t. $||W||^2 \leq R^2$, etc. $\endgroup$ – jbowman Apr 20 '18 at 15:07
  • 2
    $\begingroup$ You're dealing with an inequality constraint. It's time for you to utilize the more general version of Lagrange Multipliers, i.e., Karush–Kuhn–Tucker (KKT) conditions en.wikipedia.org/wiki/… . $\endgroup$ – Mark L. Stone Apr 20 '18 at 15:37
  • 1
    $\begingroup$ This link stats.stackexchange.com/questions/94375/… might help a little too. $\endgroup$ – jbowman Apr 20 '18 at 16:09
  • 1
    $\begingroup$ If you're willing to invest a non-trivial amount of intellectual shoe leather, study "Convex Optimization", by Boyd and Vandenberghe stanford.edu/~boyd/cvxbook If you can get through that, you'll be a wiz. $\endgroup$ – Mark L. Stone Apr 20 '18 at 16:39
  • 1
    $\begingroup$ It's actually available for free download from the author's website, at the link I provided. But you can buy a hard copy if you wish. $\endgroup$ – Mark L. Stone Apr 20 '18 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.