On the Approximation of Chebyshev Polynomials with Looped ReLU Networks

Looped models, which apply one layer repeatedly rather than stacking distinct layers, have been proposed as parameter-efficient and adaptive alternatives to deep Transformers for reasoning tasks. The precise relation between looping a layer and the observed increase in expressivity has not yet been characterized in detail. In this note, we offer an in-depth study of looped ReLU networks to approximate Chebyshev polynomials. Chebyshev polynomials are a central basis for polynomial approximation, and their convenient compositional structure makes them a natural setting for studying repeated computation. We ask how much width can be replaced by applying the same ReLU block several times. For approximating the degree-$K$ Chebyshev mode $T_K$ with uniform error $\varepsilon$, the classical equivalence between shallow ReLU networks and linear splines gives the tight one-pass width $\Theta(K/\sqrt{\varepsilon})$. By contrast, we prove that for $K=2^j$, an explicit tied loop that uses $O(\log K)$ updates needs only $O(\sqrt{K/\varepsilon})$ parameters.