I was told that Gradient Descent finds the weights of smallest norm.

This is what I understood in the linear regression setting:

$f_w(x)=w^\top x$ are the linear functions $ \mathbb{R}^n \rightarrow \mathbb{R} $.

$ \mathcal{D}=\{(x_i,y_i) \in \mathbb{R}^d\times\mathbb{R} \mid i=1,...,n\} $ is a dataset

Then I choose some loss function $L$, then some cost function $C_0$ such that $ C_0(w)=\frac{1}{n} \sum_i L(f_w(x_i),y_i) $

Finally, I defined a regularized cost $ C_\lambda(w)=C_0(w)+\frac{\lambda}{2n}||w||^2 $

Then there must be some sort of equivalence between (and it looks it should be some classical result):

  1. minimizing $C_\lambda(w)$ for an opportune $ \lambda \ge 0 $
  2. minimizing $C_0(w)$ with Gradient Descent

My questions:

  • Can somebody clarify a bit this fact? By providing some hypothesis (e.g. on $L$), some insight, some reference...
  • Does this apply in a similar way to the linear classification setting ($y_i\in\{-1,+1\}$)? In that case, I would expect some equivalence bewteen:
  1. maximizing $M(w)= \min_{i=1...n} y_i \langle w, x_i \rangle $ over $||w||=1$
  2. minimizing $||w||$ over $ y_i \langle w, x_i \rangle \ge 1 $
  3. maybe the previous 1. and 2. points above (those regarding regression)
  • $\begingroup$ too many questions in one post. can you break them down? $\endgroup$
    – Haitao Du
    Jan 25, 2021 at 12:48
  • $\begingroup$ Well it's 2 questions, and they're related. Even some hints or some links would be helpful.. Please also note that the first half of the post is common knowledge. $\endgroup$
    – rod
    Jan 25, 2021 at 13:13
  • $\begingroup$ If you know about the topic you can probably answer right away without effort $\endgroup$
    – rod
    Jan 25, 2021 at 13:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.