Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws
2026-08-03 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how often certain kinds of polynomial equations hit small intervals on the real line, which is important for optimizing functions with sharp changes. They provide precise formulas describing this hitting behavior based on properties of the polynomial coefficients, improving past results by removing certain errors that grew with dimension. For specific polynomial families and coefficient distributions, they give clear conditions under which hitting intervals is controllable. They also apply these findings to graph-based machine learning methods, showing how these mathematical results lead to bounds on prediction errors over time.
local root anti-concentrationpiecewise-Lipschitz functionsprojective Lipschitz constantinterval-hitting constantmonic polynomialsreal roots distributioncoefficient lawsgraph learningregret boundsGaussian-RBF kernel
Authors
Zijun Wang, Yuchen Miao, Yifan Hu, Huanmin Liu
Abstract
This paper answers the one-dimensional local root anti-concentration questions posed by Balcan, Pegden, and Sharma in the context of online optimization of piecewise-Lipschitz functions. For a homogeneous feature curve and coefficients whose density relative to the uniform law on a symmetric convex body $K$ is bounded by $A$, we show that the worst-case interval-hitting constant equals $A$ times a section-averaged projective incidence speed. For cube-supported coefficients, this speed is equivalent, up to universal constants, to the projective Lipschitz constant. This yields a sharp, dimension-free characterization and removes the previous $\sqrt N$ loss. For monic degree-$d$ polynomials under arbitrary coefficient laws, we prove that the interval-hitting constant is finite if and only if the ordered real-root laws have bounded densities, with a factor-$d$ comparison that is sharp. Conditional and joint coefficient-space area formulas, together with a two-chart certificate, make this criterion verifiable for dependent and singular coefficient laws. We also give two graph-learning applications that complete the transition-to-regret chain. A cost-sensitive Gaussian-RBF harmonic classifier uses the projective incidence theorem and achieves expected regret $\widetilde O((An^2D e^{BD}/\ell+1)\sqrt T)$. A common-offset polynomial-kernel model uses rigid translation of the ordered roots and achieves $\widetilde O((qn^2κ+1)\sqrt T)$ regret, even when the induced coefficient law is singular in the ambient coefficient space.