跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.26515 · v1

Simple Private Noisy SGD is Minimax-Optimal under Population Strong Convexity

简单私有噪声SGD在总体强凸性下是极小极大最优的

首次提交 2026-11-20 01:58
版本更新 2026-11-20 01:58
雷达观测 2026-11-20 12:52
arXiv ↗PDF ↗

摘要

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.

作者备注:34 Pages

AI 论文解读

基于摘要 · 非全文审阅

作者证明单次遍历、固定步长和常数批大小的简单噪声SGD在强凸Lipschitz损失下达到极小极大最优参数估计误差率,并首次给出私有逻辑回归中无多对数项的最优率。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-20 01:58 · 最新观测版本

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.

查看此版本解读 →查看此版本原文 ↗