# Is MSE cost for a linear regression model a convex function with one global optimum?

Here is the thing: MSE cost for a linear regression model is a convex function with one global optimum, and it can be solved efficiently using gradient descent or in closed form (SVD, normal eq. ....) . Also, we can approximate any function to any precision degree as a linear combination of Fourier bases with enough sine and/or cos terms. Now imagine we want to approximate f(x). instead of using x we use features based on Fourier bases. Then, find the coefficients of these bases using linear regression. So we can approximate any function to any degree by solving a convex function. Am I correct? What am I missing?

• Any function can be approximated by a Fourier series?
– Dave
Commented Dec 6, 2023 at 15:27

I'm lost on the Fourier part, as I'm pretty sure that then finding the minimum on the other space will be convex. However, on the first part "is a convex function with one global optimum", you are already wrong.

For example, you can build a $$X$$ such that you have a valley of solutions (aka non strictly convex function), just by duplicating a column, since any linear combination of the two identical one will be equally valid... let alone the case where you have more features than samples...

• let $y'=w^Tx$. find w such that $1/n\sum^n (w^Tx^{(i)}-y'^{(i)})$ is minimized. This, objective is convex, so has one optima (unless some in wired case). you can take derivative and obtain the solution as $(X^TX)^{-1}X^TY$ where X is the matrix of all samples and Y their corresponding targets. (you can find this in any ML book [deep learning by Goodfellow, reinforcement learning by Sutton, Hands-On Machine Learning by Aurelien, ...]). So the convex part is correct. Also, you can transfer your sample to a higher dimensional space where they can be linearly modeled. Commented Dec 6, 2023 at 13:03
• @Reza_va you are assuming that $X^TX$ is invertible, which is, as I'm trying to tell you, definitely not always the case, and not being linearly separable is not one of such cases... note that I'm not saying that the "convex part" is wrong, but that "with one global minimum" is wrong... stats.stackexchange.com/questions/69442/… Commented Dec 6, 2023 at 17:27
• @Reza_va or if you want, page for of web.stanford.edu/~mrosenfe/soc_meth_proj3/… directly from Stanford Commented Dec 6, 2023 at 17:28

According to the Fourier basis paper, which I think is what you're referencing to, you can approximate whatever periodic function as a summation of sine and cosine functions of proper frequency (i.e., the bases). You can do so, and you can put a linear model on top to learn the regression target. That model would still be linear so you can learn its parameters the usual way.

But there are two issues:

1. The Fourier bases, $$f(x)$$, are non-linear in $$x$$ so, although the MSE cost is convex, the parameter shape should be not in general due the added non-linearity. But you can still optimize it and get a good local minima.
2. The Fourier bases are still an approximation of the true (unknown) function that generates the features $$x$$, and may not work well for general (non-periodic) functions. So the more you approximate, the less accuracy you get in the overall linear model.

In general, consider that a linear model can only fit well linear functions and that if you want it to be an universal function approximator you need to be non-linear in the features, likewise using $$f(x)$$ instead of $$x$$. The fact is that you would get $$\hat f(x)$$, i.e., the approximated $$f(x)$$ instead, which should also be higher-dimensional than $$x$$. So, you're making your regression model more powerful but also more complex, and so the optimization process is not made simpler but probably even harder.

In conclusion, if you have a good $$f(x)$$ (likewise, a well pre-trained neural net, acting as feature extractor) your LR model is expected to improve compared to training directly on $$x$$, otherwise you would get similar or even worse performance.

• There is still linearity in the parameters (coefficients), so I do not agree with point $\#1$.
– Dave
Commented Dec 6, 2023 at 22:52
• Periodic/ or bounded , i.e. f defined within [-l, l] (which is usually the case in the function approximation). Cause, for a given function f, defined in the interval -l < x < l, you can always assume that outside of this interval extended f is defined by f(x + 2l) = f(x), so that extended f has period 2l, and I agree with Dave in part 1. Commented Dec 7, 2023 at 4:10
• @Dave Sure but each Fourier basis as defined in the paper, i.e., $\phi(x)_i=\cos(i\pi\cdot x)$, is still non-linear in $x$ due to the $\cos(.)$ function. Also you can have an arbitrary number of them to represent the features, e.g., $|x|=N$ and $|f(x)|=M$ where $M>N$. Commented Dec 7, 2023 at 21:20
• The linearity in $x$ is not what "linear" means in linear regression. The square loss function for the linear regression $\mathbb E[y] = \beta_0 + \beta_1 x + \beta_2 x^2$ is still convex, despite the curvature introduced by the quadratic term.
– Dave
Commented Dec 7, 2023 at 21:21