量化自适应学习中未知参数带来的代价,给出多个问题的紧致下界。
The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems
- 通过切片归一化极小极大比,形式化非主流信息的适应性代价。
- 在有限时域内,高斯认证的最优归一化平方半宽为 log(eM) + log log(e^eT)。
- 适用于模型监控、在线优化等场景,尤其适合动态选择查询的分析者。
自适应过程必须在无法获取某些辅助信息(如梯度尺度或光滑指数)的情况下运行,而鲁棒过程则需应对数据观测后才确定的坐标与检查时间。此类比较需明确定义奥丁优势与有效性契约。我们通过切片归一化极小极大比来形式化非主流信息的适应性,并单独定义从预设高斯查询扩展到任意事后检查的鲁棒性代价。核心结果是高斯认证的有限时域组合律:对于 M 个独立坐标,在样本均值中心化的矩形类中,保护所有坐标及前 T 个时刻的族级认证器,其最优归一化平方半宽为 log(eM) + log log(e^eT)。通过分段时段拼接获得上界;跨坐标的独立高斯块增量与几何时间尺度构成匹配下界,且已在几何检查点网格上成立,强制实现最大宽度的分位数,导致选择与停止的代价叠加。两个基准情形补全图景:在线凸优化中未知梯度尺度的代价为常数,而在嵌套霍尔德类上的逐点适应代价为 (log n / log log n)^(s1/(2s1+1))。作为模型监控工具,该法则允许分析者在任意数据相关时间检查任意 M 个切片指标:固定查询带的选定覆盖度急剧下降,当 M=1 时降至 0.30,M≥10 时归零;而分段拼接认证器则以迭代对数宽度代价维持族级覆盖。实验检验了两项尖锐预测,两者均未被推翻。
原文摘要 · Abstract (English)
Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。