The Equioscillation Theorem: A Necessary and Sufficient Condition for Optimal Polynomial Approximation
While reading recently, I came across an "Equioscillation Theorem" concerning optimal polynomial approximation, whose proof also involves differentiating an infinity norm. I found both the result and the proof quite novel, so I'm writing this note to record it.
References: 《Notes on how to prove Chebyshev's equioscillation theorem》 and 《Approximation Theory – Lecture 5》.
Equioscillation
Let's start by presenting the result:
Equioscillation Theorem
Let $f(x)$ be a polynomial of degree at most $n$, and let $g(x)$ be a continuous function on the interval $[a,b]$. Then
\begin{equation}f^* = \mathop{\text{argmin}}_f \max_{x\in[a,b]} |f(x) - g(x)|\end{equation}
holds if and only if there exist $a\leq x_0 < x_1 < \cdots < x_{n+1} \leq b$ and $\sigma\in\{0,1\}$ such that
\begin{equation}f^*(x_k) - g(x_k) = (-1)^{k+\sigma} \max_{x\in[a,b]} |f^*(x) - g(x)|\end{equation}
The equioscillation theorem is sometimes simply called "Chebyshev's theorem," since it was first discovered by Chebyshev. Although the theorem's statement looks complicated, it actually has an intuitive geometric meaning, as shown in the figure below:
Equioscillation Theorem
Put simply, the best degree-$n$ polynomial approximation to a function must cross the original function alternately — which matches our intuition — and the equioscillation theorem tells us that this "maximum error must recur alternately at least $n+2$ times." This is a remarkably strong quantitative signal.
The idea behind the derivative
The error metric used in the equioscillation theorem is $\max\limits_{x\in[a,b]} |f(x) - g(x)|$, i.e., we want the maximum error to be as small as possible. Its advantage is that it automatically focuses on where the error is largest, without introducing extra hyperparameters to tune.
We know that the standard way to find an extremum is to take the derivative and set it to zero. However, differentiating a metric involving $\max$ is not entirely trivial. Note that we have
\begin{equation}\max_{x\in[a,b]} |f(x) - g(x)| = \lim_{p\to\infty} \left(\int_a^b |f(x)-g(x)|^p\right)^{1/p} = \Vert f(x)-g(x)\Vert_{\infty}\end{equation}
that is, it is the infinity-order version of the $l_p$ norm. If $p$ is a finite number, then the derivative can be computed directly with a fixed formula, but when $p\to\infty$, some new subtleties may arise. In that case, the safest approach is to go back to the original definition of the derivative:
\begin{equation}\mathcal{D}_x[h(x),u] = \lim_{\epsilon\to 0} \frac{h(x + \epsilon u) - h(x)}{\epsilon}\end{equation}
If the limit exists and can be expressed as an inner product with $\langle \varphi(x),u\rangle$, then $\varphi(x)$ is the derivative (gradient) of $h(x)$. If $h(x)$ attains its minimum at $x$, then for sufficiently small nonzero $\epsilon$, the inequality $h(x + \epsilon u) \geq h(x)$ must always hold; and since this inequality holds for arbitrary $u$, it can only be that $\varphi(x)=0$ — which is precisely the principle behind setting the derivative to zero to find extrema.
A simple example
Let's start with a simple example. Define $h(x_1,x_2) = \max(x_1,x_2)$, and consider the one-sided limit
\begin{equation}\mathcal{D}_{x_1,x_2}[h(x_1,x_2),(u_1,u_2)] = \lim_{\epsilon\to 0^+} \frac{\max(x_1 + \epsilon u_1,x_2 + \epsilon u_2) - \max(x_1,x_2)}{\epsilon}\end{equation}
We now discuss this case by case. The first case is $x_1 > x_2$. Note that we are considering the limit as $\epsilon$ becomes arbitrarily small, so when $x_1 \neq x_2$, adding $\epsilon u_1, \epsilon u_2$ is not enough to change the ordering, i.e., $x_1 + \epsilon u_1 > x_2 + \epsilon u_2$, so
\begin{equation}\mathcal{D}_{（x_1,x_2）}[h(x_1,x_2),(u_1,u_2)] = \lim_{\epsilon\to 0^+} \frac{(x_1 + \epsilon u_1) - x_1}{\epsilon} = u_1\end{equation}
Similarly, when $x_1 < x_2$ we have
\begin{equation}\mathcal{D}_{（x_1,x_2）}[h(x_1,x_2),(u_1,u_2)] = \lim_{\epsilon\to 0^+} \frac{(x_2 + \epsilon u_2) - x_2}{\epsilon} = u_2\end{equation}
Finally, when $x_1=x_2$, we have $\max(x_1 + \epsilon u_1,x_2 + \epsilon u_2)=x_1 + \epsilon \max(u_1, u_2)$, so
\begin{equation}\mathcal{D}_{（x_1,x_2）}[h(x_1,x_2),(u_1,u_2)] = \lim_{\epsilon\to 0^+} \frac{(x_1 + \epsilon \max(u_1, u_2)) - x_1}{\epsilon} = \max(u_1,u_2)\end{equation}
This can be generalized similarly to $\boldsymbol{x}=(x_1,\cdots,x_n),\boldsymbol{u}=(u_1,\cdots,u_n)$. On closer inspection one finds the pattern is "first locate the position(s) where $\boldsymbol{x}$ attains its maximum, then find the corresponding maximum of $\boldsymbol{u}$," i.e.,
\begin{equation}\mathcal{D}_{\boldsymbol{x}}[\max(\boldsymbol{x}),\boldsymbol{u}] = \lim_{\epsilon\to 0^+} \frac{\max(\boldsymbol{x} + \epsilon \boldsymbol{u}) - \max(\boldsymbol{x})}{\epsilon} = \max_{i\in\mathop{\text{argmax}}(\boldsymbol{x})} u_i\end{equation}
Here we don't rule out the possibility that the maximum of $\boldsymbol{x}$ is attained at more than one position, so $\mathop{\text{argmax}}(\boldsymbol{x})$ is a set.
It's not hard to see that the expression above cannot be written in the form $\langle \boldsymbol{\varphi}(\boldsymbol{x}),\boldsymbol{u}\rangle$, which means the $\max$ operator does not, strictly speaking, have a gradient. Of course, the probability of two numbers being exactly equal is small, so if we assume the maximum is attained at a unique position, then the gradient can be separated out, giving $\mathop{\text{onehot}}(\mathop{\text{argmax}}(\boldsymbol{x}))$ — and this is exactly what the $\max$ operator does in deep learning frameworks.
Adding absolute values
Let $|\boldsymbol{x}|$ be the new vector obtained by taking the absolute value of each component of $\boldsymbol{x}$. Now let's consider the derivative of $\max(|\boldsymbol{x}|)$. We note that
\begin{equation}\max(|\boldsymbol{x}|) = \max((-\boldsymbol{x}, \boldsymbol{x}))\end{equation}
Here $(-\boldsymbol{x}, \boldsymbol{x})$ denotes concatenating two vectors into a new vector. After removing the absolute values, we can directly plug in the result from the previous section
\begin{equation}\mathcal{D}_{\boldsymbol{x}}[\max(|\boldsymbol{x}|),\boldsymbol{u}] = \mathcal{D}_{(-\boldsymbol{x},\boldsymbol{x})}[\max((-\boldsymbol{x},\boldsymbol{x})),(-\boldsymbol{u},\boldsymbol{u})] = \max_{i\in\mathop{\text{argmax}}((-\boldsymbol{x},\boldsymbol{x}))} (-\boldsymbol{u},\boldsymbol{u})_i\end{equation}
This can be simplified further. Note that when $x_i\neq 0$, at most one of $\pm x_i$ can be the maximum. If $x_i$ is the maximum, it must be positive, and the value participating in the ordering is $u_i$; otherwise it is negative, and the value participating in the ordering is $-u_i$. So we have
\begin{equation}\mathcal{D}_{\boldsymbol{x}}[\max(|\boldsymbol{x}|),\boldsymbol{u}] = \max_{i\in\mathop{\text{argmax}}((-\boldsymbol{x},\boldsymbol{x}))} (-\boldsymbol{u},\boldsymbol{u})_i = \max_{i\in\mathop{\text{argmax}}(|\boldsymbol{x}|)} \mathop{\text{sign}}(x_i) u_i \end{equation}
which can also be written as
\begin{equation}\mathcal{D}_{\boldsymbol{x}}[\Vert\boldsymbol{x}\Vert_{\infty},\boldsymbol{u}] = \max_{i\in\mathop{\text{argmax}}(|\boldsymbol{x}|)} \mathop{\text{sign}}(x_i) u_i \end{equation}
The premise for this to hold is $\boldsymbol{x}\neq \boldsymbol{0}$. It can be generalized to functions on a closed interval: $\forall f,g\in \mathcal{C}[a,b],f\neq 0$, we have
\begin{equation}\mathcal{D}_f[\Vert f\Vert_{\infty},g] = \max_{x\in\mathop{\text{argmax}}(|f(x)|)} \mathop{\text{sign}}(f(x)) g(x) \end{equation}
This is the key derivative identity needed to prove the equioscillation theorem. It's worth pointing out that throughout the proofs in these two sections, we only relied on case analysis, without using any approximation. So we can find a sufficiently small threshold $\tau$ such that for all $\forall \epsilon\in[0,\tau]$, the following holds:
\begin{equation}\Vert f + \epsilon g\Vert_{\infty} = \Vert f\Vert_{\infty} + \epsilon\, \mathcal{D}_f[\Vert f\Vert_{\infty},g] = \Vert f\Vert_{\infty} + \epsilon\max_{x\in\mathop{\text{argmax}}(|f(x)|)} \mathop{\text{sign}}(f(x)) g(x) \label{eq:eps-x}\end{equation}
Necessary and sufficient conditions
This section formally takes up the discussion of optimal approximation. We first prove a more general result than polynomial approximation, due to Kolmogorov (yes, the same K as in KAN):
Kolmogorov's Theorem
Let $\mathcal{S}\subseteq \mathcal{C}[a,b]$ be a linear subspace of $\mathcal{C}[a,b]$, with $f\in \mathcal{S}$ and $g\in \mathcal{C}[a,b]$. Then
\begin{equation}f^* = \mathop{\text{argmin}}_f \Vert f - g\Vert_{\infty} = \mathop{\text{argmin}}_f \max_{x\in[a,b]} |f(x) - g(x)|\end{equation}
holds if and only if, for every $h\in \mathcal{S}$,
\begin{equation}\mathcal{D}_{f^*}[\Vert f^* - g\Vert_{\infty}, h] = \max_{x\in\mathop{\text{argmax}}(|f^*(x) - g(x)|)} \mathop{\text{sign}}(f^*(x) - g(x)) h(x) \geq 0\label{eq:cond-1}\end{equation}
The proof has two parts, necessity and sufficiency. Necessity follows directly from equation $\eqref{eq:eps-x}$ and the definition of the minimum, so we mainly focus on sufficiency. From the expansion
\begin{equation}\begin{aligned} |f(x) - g(x)|^2 =&\, |f(x)-f^*(x)+f^*(x)-g(x)|^2 \\[6pt] =&\, |f(x)-f^*(x)|^2 + 2(f(x)-f^*(x))(f^*(x)-g(x)) + |f^*(x)-g(x)|^2 \end{aligned}\label{eq:cond-1x}\end{equation}
Since $f,f^*\in \mathcal{S}$, we have $f-f^* \in \mathcal{S}$. Let $h=f-f^*$, and take $x$ to be the $x$ that makes condition $\eqref{eq:cond-1}$ hold. Then
\begin{equation}(f(x)-f^*(x))(f^*(x)-g(x)) = h(x) \mathop{\text{sign}}(f^*(x)-g(x))|f^*(x)-g(x)| \geq 0\end{equation}
Substituting into equation $\eqref{eq:cond-1x}$ gives $|f(x) - g(x)|^2 \geq |f^*(x)-g(x)|^2$, which means $\Vert f-g\Vert_{\infty} \geq \Vert f^* - g\Vert_{\infty}$, so $f^*$ is the optimal approximation.
Proof of the theorem
To complete the proof of the equioscillation theorem, we take the subspace $\mathcal{S}$ to be the set of all polynomials of degree at most $n$. For the reader's convenience, let's restate the theorem here:
Equioscillation Theorem
Let $f(x)$ be a polynomial of degree at most $n$, and let $g(x)$ be a continuous function on the interval $[a,b]$. Then
\begin{equation}f^* = \mathop{\text{argmin}}_f \Vert f(x) - g(x)\Vert_{\infty}= \mathop{\text{argmin}}_f \max_{x\in[a,b]} |f(x) - g(x)|\end{equation}
holds if and only if there exist $a\leq x_0 < x_1 < \cdots < x_{n+1} \leq b$ and $\sigma\in\{0,1\}$ such that
\begin{equation}f^*(x_k) - g(x_k) = (-1)^{k+\sigma}\Vert f^*(x) - g(x)\Vert_{\infty} = (-1)^{k+\sigma} \max_{x\in[a,b]} |f^*(x) - g(x)|\label{eq:cond-2}\end{equation}
Let $\mathcal{E} = \Vert f^*(x) - g(x)\Vert_{\infty}$. The equioscillation theorem has three key points: 1) the maximum error $\mathcal{E}$ occurs at least $n+2$ times; 2) $\pm \mathcal{E}$ alternates in sign exactly; 3) this constitutes a necessary and sufficient condition for optimality.
Similarly, we prove necessity and sufficiency separately. Let's start with sufficiency. By Kolmogorov's theorem, we only need to show that, given that condition $\eqref{eq:cond-2}$ holds, there cannot exist $h\in \mathcal{S}$ such that for all $\forall x\in\mathop{\text{argmax}}(|f^*(x) - g(x)|)$,
\begin{equation}\mathop{\text{sign}}(f^*(x) - g(x)) h(x) < 0\end{equation}
The reason is that $\pm \mathcal{E}$ alternates in sign $n+2$ times. If the above held, then $h(x)$ would have to change sign at least $n+1$ times, and by the intermediate value theorem $h(x)$ would have at least $n+1$ distinct zeros — contradicting the fact that $h\in \mathcal{S}$ is a polynomial of degree $n$.
As for necessity, by Kolmogorov's theorem, in this case $\forall h\in \mathcal{S}$ satisfies
\begin{equation}\max_{x\in\mathop{\text{argmax}}(|f^*(x) - g(x)|)} \mathop{\text{sign}}(f^*(x) - g(x)) h(x) \geq 0\label{eq:cond-3}\end{equation}
for all such cases. We first sort the elements of $\mathop{\text{argmax}}(|f^*(x) - g(x)|)$ in increasing order, and then merge adjacent elements with the same sign of $f^*(x) - g(x)$ into groups. Necessity then amounts to saying that we can always split them into at least $n+2$ groups. Suppose we could only split them into $m \leq n + 1$ groups; then we could find $m-1$ separating points $z_1 < z_2 < \cdots < z_{m-1}$ for these $m$ groups. Consider
\begin{equation}h_{\pm}(x) = \pm (x-z_1)(x-z_2)\cdots (x - x_{m-1})\in \mathcal{S}\end{equation}
At least one of $h_{\pm}(x)$ exists, and it is always of opposite sign to $f^*(x) - g(x)$ ($\forall x \in \mathop{\text{argmax}}(|f^*(x) - g(x)|)$); suppose it is $h_+(x)$. Then
\begin{equation} \mathop{\text{sign}}(f^*(x) - g(x)) h_+(x) < 0,\qquad \forall x\in\mathop{\text{argmax}}(|f^*(x) - g(x)|)\end{equation}
which contradicts $\eqref{eq:cond-3}$. Hence $m > n+1$, meaning the number of elements of $\mathop{\text{argmax}}(|f^*(x) - g(x)|)$ is at least $n+2$, and the sign of $f^*(x) - g(x)$ changes at least $n+1$ times accordingly.
Uniqueness of the optimum
A natural question is whether the optimal polynomial approximation in the equioscillation theorem is unique. The answer is yes. This proof is also rather elegant, and follows the note 《Chebyshev Equioscillation Theorem》.
Suppose $f_1^*, f_2^*$ are two optimal polynomials for $g$. We first show that $(f_1^* + f_2^*)/2$ is also an optimal approximation:
\begin{equation}\left\Vert \frac{f_1^* + f_2^*}{2} - g\right\Vert_{\infty} = \left\Vert \frac{f_1^* - g}{2} + \frac{f_2^* - g}{2}\right\Vert_{\infty}\leq \frac{1}{2}\Vert f_1^* - g\Vert_{\infty} + \frac{1}{2}\Vert f_2^* - g\Vert_{\infty} = \mathcal{E} \end{equation}
The last equality holds because $f_1^*, f_2^*$ are both optimal approximations, so $\Vert f_1^* - g\Vert_{\infty} = \Vert f_2^* - g\Vert_{\infty} = \mathcal{E}$. Since the maximum error of $(f_1^* + f_2^*)/2$ also does not exceed $\mathcal{E}$, it is also an optimal approximation.
Then, by the equioscillation theorem, there exist at least $n+2$ distinct $x$ such that
\begin{equation}\frac{f_1^*(x) + f_2^*(x)}{2} - g(x) = \pm\mathcal{E} \end{equation}
And since
\begin{equation}\frac{f_1^* + f_2^*}{2} - g = \frac{f_1^* - g}{2} + \frac{f_2^* - g}{2}\end{equation}
and $f_1^*(x) - g(x),f_2^*(x) - g(x)\in[-\mathcal{E},\mathcal{E}]$, $f_1^*(x) - g(x),f_2^*(x) - g(x)$ must have the same sign and both equal $\mathcal{E}$ or $-\mathcal{E}$. This means the polynomial $f_1^*-f_2^*$ has at least $n+2$ zeros. But $f_1^*-f_2^*$ is a polynomial of degree $n$, and having $n+2$ zeros means it must be identically zero, i.e., $f_1^*=f_2^*$.
Two variants
Finally, let's give variants of the equioscillation theorem for odd polynomials and even polynomials. Odd/even polynomials are polynomials containing only odd/even powers, such as $x + 2x^3$ and $1 + 4x^2 + x^4$. Their characteristic feature is that zeros necessarily occur in positive-negative pairs, so an odd/even polynomial of degree at most $2n+1$ has at most $n$ zeros on $(0,\infty)$.
For odd/even polynomials, we have
Equioscillation Theorem – Odd/Even
Let $f(x)$ be an odd/even polynomial of degree at most $2n+1$, and let $g(x)$ be a continuous function on the interval $[a,b]\subset (0,\infty)$. Then
\begin{equation}f^* = \mathop{\text{argmin}}_f \Vert f(x) - g(x)\Vert_{\infty}= \mathop{\text{argmin}}_f \max_{x\in[a,b]} |f(x) - g(x)|\end{equation}
holds if and only if there exist $a\leq x_0 < x_1 < \cdots < x_{n+1} \leq b$ and $\sigma\in\{0,1\}$ such that
\begin{equation}f^*(x_k) - g(x_k) = (-1)^{k+\sigma}\Vert f^*(x) - g(x)\Vert_{\infty} = (-1)^{k+\sigma} \max_{x\in[a,b]} |f^*(x) - g(x)|\end{equation}
The proof steps are essentially the same as for the general equioscillation theorem, requiring only minor adjustments to the details, which we leave to interested readers. In fact, these two theorems can be merged into a more general version:
Equioscillation Theorem – (n,t,r)
Let $f(x)$ be a polynomial of degree at most $n$, let $g(x)$ be a continuous function on the interval $[a,b]\subset (0,\infty)$, and let $r,t$ be two non-negative integers. Then
\begin{equation}f^* = \mathop{\text{argmin}}_f \Vert x^r f(x^t) - g(x)\Vert_{\infty}= \mathop{\text{argmin}}_f \max_{x\in[a,b]} |x^r f(x^t) - g(x)|\end{equation}
holds if and only if there exist $a\leq x_0 < x_1 < \cdots < x_{n+1} \leq b$ and $\sigma\in\{0,1\}$ such that
\begin{equation}x_k^r f^*(x_k^t) - g(x_k) = (-1)^{k+\sigma}\Vert x^s f^*(x^t) - g(x)\Vert_{\infty} = (-1)^{k+\sigma} \max_{x\in[a,b]} |x^s f^*(x^t) - g(x)|\end{equation}
The underlying reason, in all cases, is that the function $x^r f(x^t)$ has at most $n$ zeros in $(0,\infty)$.
Summary
This post introduced the Equioscillation Theorem for optimal polynomial approximation, together with the related question of differentiating the infinity norm.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.