Does loss function becomes non convex when we add polynomial features?

Question

When we use polynomial features in case of polynomial regression, logistic regression, svm , does the loss function becomes non convex ?

Answer 1

If a loss function is convex for any choice of X -> y you're trying to estimate then adding a fixed set of polynomial features won't change that. You're simply trading your initial problem with the estimation problem X' -> y, where X' has the additional features.

If you're additionally trying to estimate the parameters for the new feature(s) then it's pretty easy to get a non-convex loss in those dimensions (assuming there are parameters to choose -- if you're just talking about adding a polynomial basis then this doesn't apply).

As some measure of proof, take the example of a 1D estimation problem and choose the feature f(x) = (x-a)^3. Assume your dataset has the single point (0, 0). With a little work you can show that the loss even for linear regression over the new feature is non-convex in places with respect to the parameter a. Note that the loss IS still convex with respect to the new features -- standard linear regression always satisfies that property -- it's the fact that we used linear regression along with a choice of polynomial to build a new non-convex regressor that causes this behavior.