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

arXiv: https://arxiv.org/abs/2608.01670 · HTML: https://mlsanity.com/paper/2608.01670/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 21 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 4 of 4)

- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)

## Abstract (arXiv)

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 √ 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((An2D eBD/ℓ+1)√ T). A common-offset polynomial-kernel model uses rigid translation of the ordered roots and achieves widetilde O((qn2kappa+1)√ T) regret, even when the induced coefficient law is singular in the ambient coefficient space.