研究证明 Noisy SGD 在强凸损失下达到 minimax 最优率
Simple Private Noisy SGD is Minimax-Optimal under Population Strong Convexity
做差分隐私机器学习的人值得看:作者证明最朴素的 Noisy SGD 在强凸逻辑回归上就是理论最优的,不用更复杂的机制,还消掉了以往结果里的 poly-log 项。下界用 Score Attack 推的,证明也只用标准凸分析,写论文或设计隐私训练流程都能直接引用。
一篇 arXiv 论文回答了差分隐私 Noisy SGD 是否与普通 SGD 一样具备统计 minimax 最优性的问题,结论是肯定的。论文对光滑强凸 Lipschitz 损失、紧致凸域上的单遍 Noisy SGD(固定步长、常数批大小)在 Rényi DP 下给出了参数估计误差上界。
针对强凸 GLM 场景,作者基于 Score Attack 框架推导出 minimax 下界,并证明上界与之匹配。这是首个针对私有逻辑回归(logistic regression)的 Noisy SGD minimax 最优率,去掉了已有结果中的 poly-logarithmic 项。
分析仅依赖标准凸分析工具,且在期望意义和高概率意义下给出相同的率,说明最简单的加噪 SGD 无需复杂机制即可在强凸问题上达到理论最优隐私-效用权衡。
Simple Private Noisy SGD is Minimax-Optimal under Population Strong Convexity
Stochastic gradient descent (SGD) is at the center of modern machine learning and is known to be statistically minimax-optimal in many regression settings, e.g., for convex Generalized Linear Models (GLMs). Yet, it is unknown whether its simplest differentially private Noisy SGD counterpart fulfills similar favorable guarantees even on strongly convex losses. We resolve this question affirmatively. We upper bound the parameter estimation error for a single pass of Noisy SGD with a fixed stepsize schedule and constant batch sizes on smooth and strongly convex Lipschitz losses over a compact convex domain under Renyi DP. Specialized to strongly convex GLMs, our error bounds match minimax lower bounds we derive based on the Score Attack framework. In particular, this provides the first minimax-optimal rate for Noisy SGD in private logistic regression, avoiding poly-logarithmic terms present in existing results. Our analysis is versatile as it relies on standard convex analysis and establishes the same rates in expectation and with high probability.
本条情报归属 AITOP「论文」核心追踪栏目。涉及核心实体与技术议题包括:Noisy SGD、differential privacy、logistic regression、GLM,读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明:本文原始线索采编自「arXiv cs.LG」(@Valentin Roth, Marco Avella Medina),经 AITOP 多维评分管线结构化提炼。