Quantifying and Optimizing Simplicity via Polynomial Representations
Tianren Zhang, Xiangxin Li, Minghao Xiao, Guanyu Chen, Feng Chen
ICML 2026
cs.AI
2026-05-28
The degree of polynomials fit along data-dependent interpolation paths predicts generalization better than sharpness, and as a regularizer lifts CIFAR-10 ViT-Tiny by +3 points.
Why deep nets generalize is usually blamed on "simplicity bias": models prefer simple solutions. But no one agrees on how to measure "simple," and the question is practical, not just philosophical. Train a pile of checkpoints and you want the one most likely to generalize; compare two recipes and you want the safer one. Today the go-to is sharpness, how steep the loss surface is, yet it is exquisitely sensitive to reparameterization and implementation details.
The paper lays out three requirements for a usable simplicity measure: general across tasks and architectures, computable on a trained large model, and (approximately) differentiable so it can double as a training target. Existing candidates fail at least one. Provable implicit biases (max-margin, minimum-norm) hold only in restricted regimes and do not extend to deep nets. Information-theoretic notions (compression, description length) are universal in principle but uncomputable for neural functions and never yield a loss. Geometry- and capacity-based measures (splines, linear-region counts) are architecture-bound and intractable at scale. Parameter-space proxies (norms, sharpness) dance to reparameterization. A metric satisfying all three is missing.
The trick is to crush a high-dimensional input down to one dimension and ask how curvy the function is along it.
Take two real samples x1, x2 and the line between them, x(a)=ax1+(1-a)x2 for a in [0,1]; that is an interpolation path. Evaluate the network along it, g(a)=f(x(a)), and a high-dimensional function collapses to a one-dimensional curve. Fit a Chebyshev orthogonal polynomial basis to g: P(a)=sumk ck Tk(2a-1). Chebyshev is chosen for numerical stability, and the sampling points come from a stratified Chebyshev-node scheme (randomized cosine sampling) that clusters points near the ends to tame Runge-type oscillations at the boundaries. When the output is high-dimensional, run PCA per path and fit polynomials only on the top-m components.
The metric is direct: the effective degree ED(P)=sumk |ck|k, each coefficient's magnitude weighted by its degree, summed. The closer the curve sits to a low-degree polynomial, the smaller ED. Average over PCA dimensions and over sampled path pairs to get a network-wide ED. Theorem 3.1 guarantees that with enough samples the random-path average preserves polynomial degree ordering, so degree-along-paths is a legitimate surrogate for functional degree.
The endpoints are real samples, so paths stay on the data manifold. This is not cosmetic: swap them for random pixels and the whole method dies, as the ablation shows.
ED is differentiable, with a closed-form gradient (Proposition 5.1) stabilized by damped least squares (TtT+eI) to avoid ill-conditioned inversion, so it drops straight in as a regularizer: L=Ltask+lambdaED. An engineering trick called label anchoring replaces the network output at the two boundary nodes (a=0, a=1) with the ground-truth label, keeping the ED term from fighting cross-entropy at the data points.
ED plays two roles: a measuring instrument and a regularizer.
As an instrument, it correlates with the generalization gap more tightly than every rival. On CIFAR-10 with ResNet18 and ViT-Tiny, ED has the strongest Pearson correlation with the gap; sharpness variants are clearly weaker and the parameter L2 norm is negatively or near-zero correlated. Fine-tuned CLIP ViT-B/32 on ImageNet tells the same story: ED positive, sharpness negative. The grokking experiment makes the point cleanest: on modular division over Z97 (30% train split), where a model first memorizes then abruptly generalizes, only ED tracks the phase transition. ED climbs during memorization, peaks near the validation-loss drop, then falls, meaning the eventual generalizing solution is genuinely simpler. The parameter norm rises monotonically and sharpness jitters, neither giving a readable turning point.
As a regularizer, gains are consistent across settings. CIFAR-10 ViT-Tiny:
| Method | Top-1 (%) |
| Baseline | 87.80 |
| Mixup | 88.83 |
| SAM | 87.85 |
| ASAM | 87.85 |
| Jacobian reg | 87.81 |
| ED (ours) | 90.82 |
ED beats the baseline by 3.02 points while SAM, ASAM, and Jacobian regularization sit flat. ImageNet from scratch with ViT-S/16: 71.37->72.76 (original recipe) and 74.42->75.01 (strong recipe). CLIP fine-tuning: ViT-B/32 reaches 76.20->77.14 on ImageNet with the five-set OOD average moving 44.04->45.31; ViT-B/16 goes 81.35->82.19. On text, GLUE with BERT-base gives RTE 70.28->71.12, MRPC 86.74->87.66, CoLA 62.31->62.45, whereas embedding mixup is not reliably helpful on text and sometimes hurts; ED is not. For RL, CNN-based PPO on Procgen with ED on the actor network improves generalization to unseen levels across all four environments tested.
ED as a cross-architecture, cross-task generalization diagnostic in a single number is worth more than the 3 points. Practitioners today have no reliable predictor of generalization for picking checkpoints or comparing recipes, and sharpness does not work. ED gives a one-number instrument that also happens to be a loss you can optimize, fusing measurement and optimization. The regularizer is architecture-agnostic, attaching to ViT, ResNet, BERT, CLIP, and a PPO actor alike, and it is orthogonal to existing tricks. Honest framing: the absolute ImageNet gain is around one point, so this is not a new SOTA. The sell is consistency, a small rise everywhere you plug it in.
"Simple" is not "robust," and that is ED's hardest ceiling. The authors show a failure case: splice MNIST 0/1 digits with CIFAR automobiles and trucks into one binary task solvable by either the simple MNIST cue or the complex CIFAR cue. The ED-regularized model (99.90) leans on the simpler but more fragile MNIST signal just as much as the baseline (99.85); randomize the MNIST half and accuracy craters to 48%. ED pushes toward simpler solutions, but when the simpler feature is the fragile one it makes things worse.
ED also depends hard on real-sample endpoints. The ablation replaces them with uniform random pixels and 90.82 collapses to 87.31, wiping out the gain entirely. The measure is distribution-aware by construction, not a pure function-space object, and real sampling carries a cost.
Compute overhead is real. Appendix G measures 6.14s to 9.75s per epoch on CIFAR-10 and 0.44s to 0.90s per step on CLIP fine-tuning, close to 2x. The authors call it acceptable, but at pretraining scale this is a genuine cost and both lambda and the sampling budget need tuning.
Theoretically, when degree-along-paths faithfully reflects functional simplicity beyond literal polynomial degree is only partly formalized, and the authors leave it open.