# Does gradient descent for linear regression selects the minimal norm solution?

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)
• too many questions in one post. can you break them down? Jan 25, 2021 at 12:48
• 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.
– rod
Jan 25, 2021 at 13:13
• If you know about the topic you can probably answer right away without effort
– rod
Jan 25, 2021 at 13:14