Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws

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 $\tilde{O}((A{n}^{2}D{e}^{BD}/\ell +1)\sqrt{T})$. A common-offset polynomial-kernel model uses rigid translation of the ordered roots and achieves $\tilde{O}((q{n}^2\hat{I}º+1)\sqrt{T})$ regret, even when the induced coefficient law is singular in the ambient coefficient space.

27 pages, 3 figures