简单私有噪声SGD在总体强凸性下是极小极大最优的
Simple Private Noisy SGD is Minimax-Optimal under Population Strong Convexity
Valentin Roth, Marco Avella Medina
AI 速读 基于摘要
作者证明单次遍历、固定步长和常数批大小的简单噪声SGD在强凸Lipschitz损失下达到极小极大最优参数估计误差率,并首次给出私有逻辑回归中无多对数项的最优率。
math.ST · cs.LG · stat.ML
查看原文摘要
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.