8 ms·

Are polynomial features the root of all evil? (2024)

188 points by Areibman 1y ago

deleted 1y ago
[deleted]
creata 1y ago
A well-known related paper that I didn't see mentioned in the article (although Trefethen was mentioned) is "Six Myths of Polynomial Interpolation and Quadrature". https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf
ComplexSystems 1y ago
Great article! Very curious how this orthogonalization + regularization idea could be extended to other kinds of series, such as Fourier series.
- freehorse 1y ago
  The Fourier basis is already orthonormal.
- constantcrying 1y ago
  This is the Fourier projection. Just on a different basis,the mathematics are near identical, you just change the subspace.
SkyBelow 1y ago
One thought I had while looking into regression recently is to consider the model created with a given regularization coefficient not as a line on a 2 dimensional graph but as a slice of a surface on a 3 dimensions graph where the third dimension is the regularization coefficient. In my case the model was for logistic regression and it was the boundary lines of the classification, but the thought is largely the same. Viewing it as a 3d shape form by boundary lines and considering hill tops as areas where entire classification boundaries disappeared as the regularization coefficient grew large enough to eliminate them. Impractical to do on models of any size and only useful when looking at two features at a time, but a fun consideration. More on topic with the article, how well does this work with considering multiple features and the different combinations of them. Instead of sigma(n => 50) of x^n, what happens if you have sigma(n => 50) of sigma(m => 50) of (x^n)*(y^n). Well probably less than 50 in the second example, maybe it is fair to have n and m go to 7 so there are 49 total terms compared to the original 50, instead of 2500 terms if they both go to 50.
FabHK 1y ago
This article is much better, more informative, and factual than I'd have expected from the title. Note that it's part of an 8-article series. Worth a read if you're ever fitting functions.
xg15 1y ago
Great article and clever use of linkbait!
- esafak 1y ago
  And the discussion here is pretty good.
PaulHoule 1y ago
See also https://en.wikipedia.org/wiki/Chebyshev_polynomials https://en.wikipedia.org/wiki/Chebyshev_polynomials They're the kind of math which is non-obvious and a bit intricate but yet if you knew the basics of how they worked and you were bored you might sit down with pencil and paper and derive everything about them. Then you wouldn't be bored anymore.
tc4v 1y ago
good article, but I am very bother by the "standard basis"... it's called canonical in math. I don't think standard is the right name in any context.
- LegionMammal978 1y ago
  If you treat the ring of polynomials as a vector space in their coefficients, then the unit monomials 1, x, x^2, etc. form the standard basis of that vector space. Wikipedia has an example of "standard basis" in this sense [0]. [0] https://en.wikipedia.org/wiki/Standard_basis#Generalizations https://en.wikipedia.org/wiki/Standard_basis#Generalizations
petters 1y ago
This part about double decent is really good: https://alexshtf.github.io/2025/03/27/Free-Poly.html#fnref:2 https://alexshtf.github.io/2025/03/27/Free-Poly.html#fnref:2
- ForceBru 1y ago
  Right? I'm no stranger to ML, but this feels like magic, so cool! It clearly explains why normalizing features can be important (some polynomials blow up outside their range), provides a simple example of double descent and fits extremely high-degree polynomials without loss of generalization - amazing stuff!
ForceBru 1y ago
In another post (https://alexshtf.github.io/2025/03/27/Free-Poly.html https://alexshtf.github.io/2025/03/27/Free-Poly.html) the author fits a degree-10000 (ten thousand!) polynomial using the Legendre basis. The polynomial _doesn't overfit_, demonstrating double descent. "What happened to our overfitting from ML 101 textbooks? There is no regularization. No control of the degree. But “magically” our high degree polynomial is not that bad!" So... are _all_ introductions to machine learning just extremely wrong here? I feel like I've seen tens of reputable books and courses that introduce overfitting and generalization using severe overfitting and terrible generalization of high-degree polynomials in the usual basis (1,x,x^2,...). Seemingly everyone warns of the dangers of high-degree polynomials, yet here the author just says "use another basis" and proves everyone wrong? Mind blown, or is there a catch?
- jordigh 1y ago
  Well, one catch is that you're doing degree ten thousand. That alone already increases your computational costs and can run afoul of numerical error as your numbers start losing precision. You'll have to start worrying about overflow and underflow. Horner's method or another representation of your polynomial might start to become important. You'll also start to notice your CPU spiking more. In essence, this is kind of fitting more and more points until you get rid of every oscillation you don't want. The other catch, which the author mentions, is that extrapolation is still essentially impossible with polynomials. This is easy to see. The highest-degree term will dominate all the other terms by an order of magnitude once you step out of the interval of interest. Every non-constant polynomial grows without bound. Honestly, though, what the author is doing isn't much different than a Taylor approximation. If you're okay fitting any polynomial in a small neighbourhood of the data, then go whole hog and fit the best possible polynomial: a Taylor polynomial. You wouldn't usually need to go to that high degree to get what you want in a neighbourhood either.
  - wbl 1y ago
    Taylor is for points. For functions on interval you want Chebyshev interpolation and probably want to throw in some poles to do better if L1 not L2 matters.
programjames 1y ago
This is why I believe a numerical methods course should be a requirement for any AI majors.
- stuxnet79 1y ago
  I'm exactly in the category of AI majors who are not familiar with numerical methods. Can you broadly explain where the gap in AI pedagogy is and how students can fill it? The series of articles posted here are interesting and I plan to review them in more detail. But I'm concerned about what the "unknown-unknowns" are.
  - constantcrying 1y ago
    >But I'm concerned about what the "unknown-unknowns" are. Try the examples in the article with the interval 0 to 10.
    - mkl 1y ago
      That problem's a known-known for most people interested in any of this, and for anyone who's made it as far as the first picture.
      - constantcrying 1y ago
        It obviously is something the author lacks any understanding of. As it is the most obvious reason why polynomials of high degree are dangerous. If you are arguing that they aren't, of course you have to at least mention that objection and point out how to circumvent it.
  - programjames 1y ago
    Sure. The original normalizing flows used a fixed number of layers. Someone at UToronto recognized that, as the number of layers gets very deep, this is essentially an ordinary differential equation (ODE). Why? Suppose you have n residual layers that look like: x_0 = input x_{i+1} = x_i + f(x_i) x_n = output If you replace them with an infinite number of layers, and use "time" t instead of "layer" i, you get x(t+dt) = x(t) + dt f(x(t)) <=> x'(t) = f(x, t) so to find the output, you just need to solve an ODE. It gets better! The goal of normalizing flows is to "flow" your probability distribution from a normal distribution to some other (e.g. image) distribution. This is usually done by trying to maximize the probability the training images should show up, according to your model, i.e. loss(model) = product model^{-1}(training image) Notice how you need the model to be reversible, which is pretty annoying to implement in the finite-layer case, but with some pretty lenient assumptions is guaranteed to be true for an ODE. Also, when you're inverting the model, the probabilities will change according to the derivative; since you have more than one dimension, this means you need to calculate the determinant of the Jacobian for every layer, which is decently costly in the finite-layer case. There are some tricks that can bring this down to O(layer size^2) (Hutchinson++), but the ODE case is trivial to compute (just exp(trace)). So, turning the model into an ODE makes it blazing fast, and since you can use any ODE solver, you can train at different levels of precision based on the learning rate (i.e. the real log canonical threshold from singular learning theory). I haven't seen any papers that do this exactly, but it's common to use rougher approximations at the beginning of training. Probably the best example of this is the company Liquid AI. Finally, this all turns out to be very similar to diffusion models. Someone realized this, and combined the two ideas into flow-matching. ----- This is one place it's super useful to know numerical methods, but here are a couple others: 1. Weight initialization --> need to know stability analysis 2. Convolutions --> the Winograd algorithm, which is similar to ideas in the FFT and quadrature
fancyfredbot 1y ago
Wanted to add my voice to the chorus of appreciation for this article (actually a series of 8). Very informative and engaging.
ziofill 1y ago
In this case wouldn't a Fourier-type approach work better? At least there's no risk the function blows up and it possibly needs fewer parameters?
- bsder 1y ago
  Yeah, I thought the whole point of a polynomial approximation was that it is really only useful for the first couple of powers (quick and cheap) or because you have a particular process that you know a priori has a particular form (non-convergent, non-conservative, higher powered, etc.). The "particular form" is important--if you don't know that then there is no reason for choosing x^10000 over x^5 (other than computational complexity). But there is also no reason for choosing x^5 over x^10000! Maybe that function really is flat and maybe it isn't. You really just don't know. If you don't have anything too weird, Fourier is pretty much optimal in the limit--if a bit expensive to calculate. In addition, since you can "bandwidth limit" it, you can very easily control overfitting and oscillation. Even more, Fourier often reflects something about the underlying process (epicycles, for example, were correct--they were pointing at the fact that orbits were ellipses).
  - constantcrying 1y ago
    >If you don't have anything too weird, Fourier is pretty much optimal "Optimal" by what metric? Why is projecting on the Fourier basis "better" than projecting on a polynomial basis?
    - bsder 1y ago
      Pick a metric. Fourier is probably better in general. With respect to machine learning, probably the fact that Fourier is bounded and gives coherent (if completely random) results even very far from the interval of interest. However, this is like saying that an O(n log n) algorithm is better than O(n^2). Sure, it's true in the limit, by the constant terms can be quite large and O(n^2) can remain better up to remarkably useful values of n. As I pointed out, the advantage that polynomial basis generally has is that you can be accurate enough with lower powers that are much, much faster to calculate (we use matrices of linear equations precisely for that reason). Or, you can match a particular process because you know specifically that it follows some particular function (we know that road damage follows the fourth power of load--it would be counterproductive to model that with Fourier). Using high powers for polynomial basis is almost always worse than any other choice.
constantcrying 1y ago
I completely disagree with the conclusion of the article. The reason the examples worked so well is because of an arbitrary choice, which went completely uncommented. The interval was chosen as 0 to 1. This single fact was what made this feasible. Had the interval been chosen as 0 to 10. A degree 100 polynomial would have to calculate 10^100, this would have lead to drastic numerical errors. The article totally fails to give any of the totally legitimate and very important reason why high degree polynomials are dangerous. It is absurd to say that well known numerical problems do not exist because you just found one example where they did not occur.
- nobodywillobsrv 1y ago
  Yes and it fails to talk about boundary conditions or predicates or whatever.
- ForceBru 1y ago
  The article specifically points out that these polynomials only work well on specific intervals (emphasis copied from the article): "The second source of their bad reputation is misunderstanding of Weierstrass’ approximation theorem. It’s usually cited as “polynomials can approximate arbitrary continuous functions”. But that’s not entrely true. They can approximate arbitrary continuous functions in an interval. This means that when using polynomial features, the data must be normalized to lie in an interval. It can be done using min-max scaling, computing empirical quantiles, or passing the feature through a sigmoid. But we should avoid the use of polynomials on raw un-normalized features." As I understand it, one of the main ideas of this series of posts is that normalizing features to very specific intervals is important when fitting polynomials. I don't think this "went completely uncommented".
  - constantcrying 1y ago
    The quote has absolutely nothing to do with my point. The scaling to an interval in the quote is about formal mathematical reasons,in particular that polynomials do not approximate continuous functions globally. This is totally unrelated to numerics. The issue is that in particular the interval 0 to 1 has to be chosen, as otherwise the numerics totally fall apart. The message of the article is that high degree polynomials pose no danger, but that is wrong. All the examples in the article only work because of a specific choice of interval. All the major numerical issues are totally ignored, which would immediately invalid the core thesis of the article. If you calculate 10^100 in 64 bit floating point you will run into trouble. The article pretends that will not be the case.
constantcrying 1y ago
It should also be noted that this kind of fitting is extremely closely related to integration or in other words calculating the mean. By using the "right" kind of polynomial basis you can get a polynomial approximation which also tells you the mean and variance of the function under a random variable.
lambdaone 1y ago
For large polynomial degree, this seems to me to be very similar to the P-spline method with a very large number of parameters.
bcoates 1y ago
There's something I'm fundamentally missing here--if the standard basis and the Berenstain basis describe exactly the same set of polynomials of degree n, then surely the polynomial of degree n that minimizes the mean square error is singular (and independent of the basis--the error is the samples vs the approximation, the coefficients/basis are not involved) so both the standard basis and Berenstain basis solution are the same (pathological, overfitted, oscillating) curve? Like I understand how the standard basis is pathological because the higher degree powers diverge like mad so given "reasonable" components the Berenstain basis is more likely to give "reasonable" curves but if you're already maximizing I don't understand how you arrive at a different curve. What am I missing?
- pavpanchekha 1y ago
  The minimization is regularized, meaning you add a penalty term for large coefficients. The coefficients will be different for the two bases, meaning the regularization will work differently.
  - bcoates 1y ago
    Ok, yeah, doing a little googling that makes sense. I kind of feel that the article author was burying the lede by saying this was about ML optimization where apparently regularization is the norm(so to speak lol) and basis selection is the whole ball game indirectly through the way it influences convex optimization
ssegert 1y ago
See also this stackexchange answer, which makes basically the same point: https://stats.stackexchange.com/questions/560383/how-can-we-explain-the-bad-reputation-of-higher-order-polynomials/560625#560625 https://stats.stackexchange.com/questions/560383/how-can-we-... I think the posted article has some important confusions. First is the distinction between a basis and an objective. If I fit a polynomial to go through every point in my dataset, I will end up with exactly the same resulting solution, it doesn't matter what basis I use to represent it (although the basis-specific coefficients will of course differ). This is because all polynomial bases (by definition) represent the same hypothesis class, and the recipe "fit a polynomial that passes through every point" can be expressed as an optimization problem over that hypothesis class. More generally, any two bases will give exactly the same solution when optimizing for the same objective (ignoring things like floating point errors). So why do the results with Bernstein basis look better than for the standard basis? It's because they are actually optimizing a different objective function (which is explicitly written out in the stackexchange post). So in that sense the Bernstein-vs.-standard basis is really a comparison between different objective functions rather than between different bases. It so happens that the solution to the new objective function has a simple expression in terms of the Bernstein basis; but in principle I could set up and solve the objective in terms of the standard basis and obtain exactly the same result. From this perspective, the Bernstein polynomials are nothing more than a convenient computational device for expressing the solution to the objective. The OP kind of gets at this with the distinction between Fitting and Interpolation, but seems to conflate different fitting procedures with different bases. Secondly, there is actually no need for explicit regularization when fitting Bernstein polynomials (cf. the stackexchange post). The way the OP fits Bernstein polynomials is non-standard. Although one can say that the specific form of the objective function provides an important source of implicit regularization. So in conclusion I think the OP has importantly mis-attributed the source of success of the Bernstein method. It does not have to do with explicit regularization or choice of basis, and has everything to do with re-defining the objective function.

188 points by Areibman 1y ago

deleted 1y ago

[deleted]

A well-known related paper that I didn't see mentioned in the article (although Trefethen was mentioned) is "Six Myths of Polynomial Interpolation and Quadrature". https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf

ComplexSystems 1y ago

Great article! Very curious how this orthogonalization + regularization idea could be extended to other kinds of series, such as Fourier series.

freehorse 1y ago
The Fourier basis is already orthonormal.
constantcrying 1y ago
This is the Fourier projection. Just on a different basis,the mathematics are near identical, you just change the subspace.

SkyBelow 1y ago

One thought I had while looking into regression recently is to consider the model created with a given regularization coefficient not as a line on a 2 dimensional graph but as a slice of a surface on a 3 dimensions graph where the third dimension is the regularization coefficient. In my case the model was for logistic regression and it was the boundary lines of the classification, but the thought is largely the same. Viewing it as a 3d shape form by boundary lines and considering hill tops as areas where entire classification boundaries disappeared as the regularization coefficient grew large enough to eliminate them. Impractical to do on models of any size and only useful when looking at two features at a time, but a fun consideration. More on topic with the article, how well does this work with considering multiple features and the different combinations of them. Instead of sigma(n => 50) of x^n, what happens if you have sigma(n => 50) of sigma(m => 50) of (x^n)*(y^n). Well probably less than 50 in the second example, maybe it is fair to have n and m go to 7 so there are 49 total terms compared to the original 50, instead of 2500 terms if they both go to 50.

FabHK 1y ago

This article is much better, more informative, and factual than I'd have expected from the title. Note that it's part of an 8-article series. Worth a read if you're ever fitting functions.

xg15 1y ago

Great article and clever use of linkbait!

esafak 1y ago
And the discussion here is pretty good.

PaulHoule 1y ago

See also https://en.wikipedia.org/wiki/Chebyshev_polynomials https://en.wikipedia.org/wiki/Chebyshev_polynomials They're the kind of math which is non-obvious and a bit intricate but yet if you knew the basics of how they worked and you were bored you might sit down with pencil and paper and derive everything about them. Then you wouldn't be bored anymore.

tc4v 1y ago

good article, but I am very bother by the "standard basis"... it's called canonical in math. I don't think standard is the right name in any context.

LegionMammal978 1y ago
If you treat the ring of polynomials as a vector space in their coefficients, then the unit monomials 1, x, x^2, etc. form the standard basis of that vector space. Wikipedia has an example of "standard basis" in this sense [0]. [0] https://en.wikipedia.org/wiki/Standard_basis#Generalizations https://en.wikipedia.org/wiki/Standard_basis#Generalizations

petters 1y ago

This part about double decent is really good: https://alexshtf.github.io/2025/03/27/Free-Poly.html#fnref:2 https://alexshtf.github.io/2025/03/27/Free-Poly.html#fnref:2

ForceBru 1y ago
Right? I'm no stranger to ML, but this feels like magic, so cool! It clearly explains why normalizing features can be important (some polynomials blow up outside their range), provides a simple example of double descent and fits extremely high-degree polynomials without loss of generalization - amazing stuff!

ForceBru 1y ago

In another post (https://alexshtf.github.io/2025/03/27/Free-Poly.html https://alexshtf.github.io/2025/03/27/Free-Poly.html) the author fits a degree-10000 (ten thousand!) polynomial using the Legendre basis. The polynomial _doesn't overfit_, demonstrating double descent. "What happened to our overfitting from ML 101 textbooks? There is no regularization. No control of the degree. But “magically” our high degree polynomial is not that bad!" So... are _all_ introductions to machine learning just extremely wrong here? I feel like I've seen tens of reputable books and courses that introduce overfitting and generalization using severe overfitting and terrible generalization of high-degree polynomials in the usual basis (1,x,x^2,...). Seemingly everyone warns of the dangers of high-degree polynomials, yet here the author just says "use another basis" and proves everyone wrong? Mind blown, or is there a catch?

jordigh 1y ago
Well, one catch is that you're doing degree ten thousand. That alone already increases your computational costs and can run afoul of numerical error as your numbers start losing precision. You'll have to start worrying about overflow and underflow. Horner's method or another representation of your polynomial might start to become important. You'll also start to notice your CPU spiking more. In essence, this is kind of fitting more and more points until you get rid of every oscillation you don't want. The other catch, which the author mentions, is that extrapolation is still essentially impossible with polynomials. This is easy to see. The highest-degree term will dominate all the other terms by an order of magnitude once you step out of the interval of interest. Every non-constant polynomial grows without bound. Honestly, though, what the author is doing isn't much different than a Taylor approximation. If you're okay fitting any polynomial in a small neighbourhood of the data, then go whole hog and fit the best possible polynomial: a Taylor polynomial. You wouldn't usually need to go to that high degree to get what you want in a neighbourhood either.
- wbl 1y ago
  Taylor is for points. For functions on interval you want Chebyshev interpolation and probably want to throw in some poles to do better if L1 not L2 matters.

programjames 1y ago

This is why I believe a numerical methods course should be a requirement for any AI majors.

stuxnet79 1y ago
I'm exactly in the category of AI majors who are not familiar with numerical methods. Can you broadly explain where the gap in AI pedagogy is and how students can fill it? The series of articles posted here are interesting and I plan to review them in more detail. But I'm concerned about what the "unknown-unknowns" are.
- constantcrying 1y ago
  >But I'm concerned about what the "unknown-unknowns" are. Try the examples in the article with the interval 0 to 10.
  - mkl 1y ago
    That problem's a known-known for most people interested in any of this, and for anyone who's made it as far as the first picture.
    - constantcrying 1y ago
      It obviously is something the author lacks any understanding of. As it is the most obvious reason why polynomials of high degree are dangerous. If you are arguing that they aren't, of course you have to at least mention that objection and point out how to circumvent it.
- programjames 1y ago
  Sure. The original normalizing flows used a fixed number of layers. Someone at UToronto recognized that, as the number of layers gets very deep, this is essentially an ordinary differential equation (ODE). Why? Suppose you have n residual layers that look like: x_0 = input x_{i+1} = x_i + f(x_i) x_n = output If you replace them with an infinite number of layers, and use "time" t instead of "layer" i, you get x(t+dt) = x(t) + dt f(x(t)) <=> x'(t) = f(x, t) so to find the output, you just need to solve an ODE. It gets better! The goal of normalizing flows is to "flow" your probability distribution from a normal distribution to some other (e.g. image) distribution. This is usually done by trying to maximize the probability the training images should show up, according to your model, i.e. loss(model) = product model^{-1}(training image) Notice how you need the model to be reversible, which is pretty annoying to implement in the finite-layer case, but with some pretty lenient assumptions is guaranteed to be true for an ODE. Also, when you're inverting the model, the probabilities will change according to the derivative; since you have more than one dimension, this means you need to calculate the determinant of the Jacobian for every layer, which is decently costly in the finite-layer case. There are some tricks that can bring this down to O(layer size^2) (Hutchinson++), but the ODE case is trivial to compute (just exp(trace)). So, turning the model into an ODE makes it blazing fast, and since you can use any ODE solver, you can train at different levels of precision based on the learning rate (i.e. the real log canonical threshold from singular learning theory). I haven't seen any papers that do this exactly, but it's common to use rougher approximations at the beginning of training. Probably the best example of this is the company Liquid AI. Finally, this all turns out to be very similar to diffusion models. Someone realized this, and combined the two ideas into flow-matching. ----- This is one place it's super useful to know numerical methods, but here are a couple others: 1. Weight initialization --> need to know stability analysis 2. Convolutions --> the Winograd algorithm, which is similar to ideas in the FFT and quadrature

fancyfredbot 1y ago

Wanted to add my voice to the chorus of appreciation for this article (actually a series of 8). Very informative and engaging.

ziofill 1y ago

In this case wouldn't a Fourier-type approach work better? At least there's no risk the function blows up and it possibly needs fewer parameters?

bsder 1y ago
Yeah, I thought the whole point of a polynomial approximation was that it is really only useful for the first couple of powers (quick and cheap) or because you have a particular process that you know a priori has a particular form (non-convergent, non-conservative, higher powered, etc.). The "particular form" is important--if you don't know that then there is no reason for choosing x^10000 over x^5 (other than computational complexity). But there is also no reason for choosing x^5 over x^10000! Maybe that function really is flat and maybe it isn't. You really just don't know. If you don't have anything too weird, Fourier is pretty much optimal in the limit--if a bit expensive to calculate. In addition, since you can "bandwidth limit" it, you can very easily control overfitting and oscillation. Even more, Fourier often reflects something about the underlying process (epicycles, for example, were correct--they were pointing at the fact that orbits were ellipses).
- constantcrying 1y ago
  >If you don't have anything too weird, Fourier is pretty much optimal "Optimal" by what metric? Why is projecting on the Fourier basis "better" than projecting on a polynomial basis?
  - bsder 1y ago
    Pick a metric. Fourier is probably better in general. With respect to machine learning, probably the fact that Fourier is bounded and gives coherent (if completely random) results even very far from the interval of interest. However, this is like saying that an O(n log n) algorithm is better than O(n^2). Sure, it's true in the limit, by the constant terms can be quite large and O(n^2) can remain better up to remarkably useful values of n. As I pointed out, the advantage that polynomial basis generally has is that you can be accurate enough with lower powers that are much, much faster to calculate (we use matrices of linear equations precisely for that reason). Or, you can match a particular process because you know specifically that it follows some particular function (we know that road damage follows the fourth power of load--it would be counterproductive to model that with Fourier). Using high powers for polynomial basis is almost always worse than any other choice.

constantcrying 1y ago

I completely disagree with the conclusion of the article. The reason the examples worked so well is because of an arbitrary choice, which went completely uncommented. The interval was chosen as 0 to 1. This single fact was what made this feasible. Had the interval been chosen as 0 to 10. A degree 100 polynomial would have to calculate 10^100, this would have lead to drastic numerical errors. The article totally fails to give any of the totally legitimate and very important reason why high degree polynomials are dangerous. It is absurd to say that well known numerical problems do not exist because you just found one example where they did not occur.

nobodywillobsrv 1y ago
Yes and it fails to talk about boundary conditions or predicates or whatever.
ForceBru 1y ago
The article specifically points out that these polynomials only work well on specific intervals (emphasis copied from the article): "The second source of their bad reputation is misunderstanding of Weierstrass’ approximation theorem. It’s usually cited as “polynomials can approximate arbitrary continuous functions”. But that’s not entrely true. They can approximate arbitrary continuous functions in an interval. This means that when using polynomial features, the data must be normalized to lie in an interval. It can be done using min-max scaling, computing empirical quantiles, or passing the feature through a sigmoid. But we should avoid the use of polynomials on raw un-normalized features." As I understand it, one of the main ideas of this series of posts is that normalizing features to very specific intervals is important when fitting polynomials. I don't think this "went completely uncommented".
- constantcrying 1y ago
  The quote has absolutely nothing to do with my point. The scaling to an interval in the quote is about formal mathematical reasons,in particular that polynomials do not approximate continuous functions globally. This is totally unrelated to numerics. The issue is that in particular the interval 0 to 1 has to be chosen, as otherwise the numerics totally fall apart. The message of the article is that high degree polynomials pose no danger, but that is wrong. All the examples in the article only work because of a specific choice of interval. All the major numerical issues are totally ignored, which would immediately invalid the core thesis of the article. If you calculate 10^100 in 64 bit floating point you will run into trouble. The article pretends that will not be the case.

constantcrying 1y ago

It should also be noted that this kind of fitting is extremely closely related to integration or in other words calculating the mean. By using the "right" kind of polynomial basis you can get a polynomial approximation which also tells you the mean and variance of the function under a random variable.

lambdaone 1y ago

For large polynomial degree, this seems to me to be very similar to the P-spline method with a very large number of parameters.

bcoates 1y ago

There's something I'm fundamentally missing here--if the standard basis and the Berenstain basis describe exactly the same set of polynomials of degree n, then surely the polynomial of degree n that minimizes the mean square error is singular (and independent of the basis--the error is the samples vs the approximation, the coefficients/basis are not involved) so both the standard basis and Berenstain basis solution are the same (pathological, overfitted, oscillating) curve? Like I understand how the standard basis is pathological because the higher degree powers diverge like mad so given "reasonable" components the Berenstain basis is more likely to give "reasonable" curves but if you're already maximizing I don't understand how you arrive at a different curve. What am I missing?

pavpanchekha 1y ago
The minimization is regularized, meaning you add a penalty term for large coefficients. The coefficients will be different for the two bases, meaning the regularization will work differently.
- bcoates 1y ago
  Ok, yeah, doing a little googling that makes sense. I kind of feel that the article author was burying the lede by saying this was about ML optimization where apparently regularization is the norm(so to speak lol) and basis selection is the whole ball game indirectly through the way it influences convex optimization

ssegert 1y ago

See also this stackexchange answer, which makes basically the same point: https://stats.stackexchange.com/questions/560383/how-can-we-explain-the-bad-reputation-of-higher-order-polynomials/560625#560625 https://stats.stackexchange.com/questions/560383/how-can-we-... I think the posted article has some important confusions. First is the distinction between a basis and an objective. If I fit a polynomial to go through every point in my dataset, I will end up with exactly the same resulting solution, it doesn't matter what basis I use to represent it (although the basis-specific coefficients will of course differ). This is because all polynomial bases (by definition) represent the same hypothesis class, and the recipe "fit a polynomial that passes through every point" can be expressed as an optimization problem over that hypothesis class. More generally, any two bases will give exactly the same solution when optimizing for the same objective (ignoring things like floating point errors). So why do the results with Bernstein basis look better than for the standard basis? It's because they are actually optimizing a different objective function (which is explicitly written out in the stackexchange post). So in that sense the Bernstein-vs.-standard basis is really a comparison between different objective functions rather than between different bases. It so happens that the solution to the new objective function has a simple expression in terms of the Bernstein basis; but in principle I could set up and solve the objective in terms of the standard basis and obtain exactly the same result. From this perspective, the Bernstein polynomials are nothing more than a convenient computational device for expressing the solution to the objective. The OP kind of gets at this with the distinction between Fitting and Interpolation, but seems to conflate different fitting procedures with different bases. Secondly, there is actually no need for explicit regularization when fitting Bernstein polynomials (cf. the stackexchange post). The way the OP fits Bernstein polynomials is non-standard. Although one can say that the specific form of the objective function provides an important source of implicit regularization. So in conclusion I think the OP has importantly mis-attributed the source of success of the Bernstein method. It does not have to do with explicit regularization or choice of basis, and has everything to do with re-defining the objective function.