解决了一维根抗集中问题,给出无维度损失的精确刻画。
Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws
- 基于投影关联速度与有序根律,建立根分布抗集中新理论
- 首次实现无√N损失的维度无关上界,关键常数为系数密度上界A
- 适用于依赖、奇异系数分布,可直接用于机器学习后悔率分析
本文回答了Balcan、Pegden和Sharma在分段Lipschitz函数在线优化背景下提出的一维局部根抗集中问题。对于均匀特征曲线及相对于对称凸体K上均匀测度密度有界于A的系数,最坏情况区间命中常数等于A乘以一个截面平均投影关联速度。当系数支持在立方体上时,该速度在普适常数意义下等价于投影Lipschitz常数,从而得到一个精确的、维度无关的刻画,消除了此前的√N损失。对于任意系数分布下的首一d次多项式,我们证明区间命中常数有限当且仅当有序实根律具有有界密度,且因子-d比较是紧的。通过条件与联合系数空间面积公式及双图证书,该判别准则可验证依赖与奇异系数分布的情形。此外,我们给出两个图学习应用,完成从转换到后悔率的链条:一个代价敏感的高斯-RBF调和分类器利用投影关联定理,达到期望后悔率~O((An²De^{BD}/ℓ+1)√T);一个公共偏移多项式核模型通过有序根的刚性平移,即使诱导系数分布在环境系数空间中奇异,仍可实现~O((qn²κ+1)√T)的后悔率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。