揭示了凸优化中可追溯性与学习误差的深层权衡
On Traceability in $\ell_p$ Stochastic Convex Optimization
- 通过分析算法输出识别训练样本的能力，定义可追溯性
- 在ℓₚ几何下，低误差学习必然导致高可追溯性，存在阈值现象
- 为差分隐私学习提供新下界，对隐私保护有重要启示
本文研究在ℓₚ几何下的随机凸优化（SCO）中，准确学习是否必须具备可追溯性。若一个学习算法能通过输出识别出至少m个训练样本，则称其为m-可追溯。我们发现，在所有p∈[1,∞)下，存在一个过剩风险阈值：低于此阈值的样本高效学习者必然是可追溯的，且可追溯的样本数占训练集比例为常数。当p∈[1,2]时，该阈值恰好等于差分隐私（DP）算法能达到的最佳过剩风险，表明存在尖锐相变；当p∈(2,∞)时，该阈值给出了新的DP学习下界，部分解决了该场景下的开放问题。研究过程中，我们证明了一个稀疏版本的指纹识别引理，对领域具有独立价值。
原文摘要 · Abstract (English)
In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under $\ell_p$ geometries. Informally, we say a learning algorithm is $m$-traceable if, by analyzing its output, it is possible to identify at least $m$ of its training samples. Our main results uncover a fundamental tradeoff between traceability and excess risk in SCO. For every $p\in [1,\infty)$, we establish the existence of an excess risk threshold below which every sample-efficient learner is traceable with the number of samples which is a constant fraction of its training sample. For $p\in [1,2]$, this threshold coincides with the best excess risk of differentially private (DP) algorithms, i.e., above this threshold, there exist algorithms that are not traceable, which corresponds to a sharp phase transition. For $p \in (2,\infty)$, this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route to establishing these results, we prove a sparse variant of the fingerprinting lemma, which is of independent interest to the community.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。