Answers.Body: <p>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 &quot;<em>is a convex function with one global optimum&quot;</em>, you are already wrong.</p>
  <p>For example, you can build a <span class="math-container">$X$</span> 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...</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-06T13:03:38.043Z
Answers.Text: 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.
Answers.UserDisplayName: Reza_va
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-06T17:27:01.560Z
Answers.Text: @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... https://stats.stackexchange.com/questions/69442/linear-regression-and-non-invertibility
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-06T17:28:12.093Z
Answers.Text: @Reza_va or if you want, page for of https://web.stanford.edu/~mrosenfe/soc_meth_proj3/matrix_OLS_NYU_notes.pdf directly from Stanford
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-06T12:33:48.170Z
Answers.LastActivityDate: 2023-12-06T12:33:48.170Z
Answers.UserDisplayName: Alberto
Answers.Body: <p>According to the <a href="https://ojs.aaai.org/index.php/AAAI/article/view/7903/7762" rel="nofollow noreferrer">Fourier basis</a> paper, which I think is what you're referencing to, you can approximate whatever <em>periodic</em> 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.</p>
  <p>But there are two issues:</p>
  <ol>
  <li>The Fourier bases, <span class="math-container">$f(x)$</span>, are non-linear in <span class="math-container">$x$</span> 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 <em>local</em> minima.</li>
  <li>The Fourier bases are still an approximation of the <em>true</em> (unknown) function that generates the features <span class="math-container">$x$</span>, 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.</li>
  </ol>
  <p>In general, consider that a linear model can only fit well linear functions and that if you want it to be an <em>universal function approximator</em> you need to be non-linear in the features, likewise using <span class="math-container">$f(x)$</span> instead of <span class="math-container">$x$</span>. The fact is that you would get <span class="math-container">$\hat f(x)$</span>, i.e., the approximated <span class="math-container">$f(x)$</span> instead, which should also be higher-dimensional than <span class="math-container">$x$</span>. 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.</p>
  <p>In conclusion, if you have a good <span class="math-container">$f(x)$</span> (likewise, a well pre-trained neural net, acting as feature extractor) your LR model is expected to improve compared to training directly on <span class="math-container">$x$</span>, otherwise you would get similar or even worse performance.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-06T22:52:20.387Z
Answers.Text: There is still linearity in the parameters (coefficients), so I do not agree with point $\#1$.
Answers.UserDisplayName: Dave
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-07T04:10:36.183Z
Answers.Text: 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.
Answers.UserDisplayName: Reza_va
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-07T21:20:29.807Z
Answers.Text: @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$.
Answers.UserDisplayName: Luca Anzalone
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-07T21:21:30.193Z
Answers.Text: 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.
Answers.UserDisplayName: Dave
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-06T22:50:43.223Z
Answers.LastActivityDate: 2023-12-06T22:50:43.223Z
Answers.UserDisplayName: Luca Anzalone
Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-12-06T15:27:49.040Z
Comments.Text: Any function can be approximated by a Fourier series?
Comments.UserDisplayName: Dave
Tags: <machine-learning><regression>
Title: Is MSE cost for a linear regression model a convex function with one global optimum?
UserDisplayName: Reza_va
ThreadText: # Is MSE cost for a linear regression model a convex function with one global optimum?
  
  (Asked by: username_0 on 2023-12-06)
  
  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?
  
  **Tags:** machine-learning, regression
  
  > **Comments:**
  > **username_1**: Any function can be approximated by a Fourier series?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-12-06. Score: 1
  
  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...
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_2**: @username_0 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... https://stats.stackexchange.com/questions/69442/linear-regression-and-non-invertibility  
  > **username_2**: @username_0 or if you want, page for of https://web.stanford.edu/~mrosenfe/soc_meth_proj3/matrix_OLS_NYU_notes.pdf directly from Stanford  
  
  ---
  
  ### Answer by username_3 on 2023-12-06. Score: 0
  
  According to the [Fourier basis](https://ojs.aaai.org/index.php/AAAI/article/view/7903/7762) 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.
  
  > **Comments:**
  > **username_1**: There is still linearity in the parameters (coefficients), so I do not agree with point $\#1$.  
  > **username_0**: 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 username_1 in part 1.  
  > **username_3**: @username_1 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$.  
  > **username_1**: 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.  
  
  ---
  
  