线性回归的私有梯度下降：更紧凑的误差界限和特定实例的不确定性估计
内容提要
本文综述线性回归在隐私保护与随机优化下的进展，涵盖差分隐私、局部差分隐私、指数机制等算法，兼顾精度与隐私；并分析随机梯度下降及其平均、加权迭代变体的收敛与泛化，涉及偏差方差最优性、高维稳健性及对抗污染。
延伸解读
隐私保护与精度平衡的演进
文章梳理了线性回归在差分隐私、局部差分隐私等框架下的算法进展。从早期针对小型数据集的差分隐私线性回归，到基于指数机制选择Tukey深度高模型以克服边界和超参数困难，再到平衡标准误差与隐私保护的最小化极限风险算法，体现了隐私保护与模型精度之间的持续权衡。不同隐私模型（中心化与局部）需要完全不同的算法设计，且局部差分隐私下稀疏线性回归存在基本差异。
随机梯度下降的理论深化
随机梯度下降及其变体是文章的另一主线。研究涵盖了平均恒定步长SGD的渐近分析、加权迭代平均算法对不可知参数的最小二乘回归，以及SGD泛化误差的理论上限。这些工作揭示了收敛速度、偏差方差最优性、高维稳健性等性质，并强调梯度方差、局部光滑性和损失函数敏感度对泛化性能的关键影响，为理解随机优化提供了新见解。
高维与对抗环境下的稳健性挑战
文章涉及高维线性回归在对抗性污染下的稳健模型问题，针对高斯分布生成的未修正样本给出了几乎最紧的上界和计算下界。同时，局部差分隐私下的稀疏线性回归研究提出了非交互式算法，在亚高斯分布下提供估计误差上界，并探讨了利用额外公开未标记数据进一步提升性能的可能性。这些结果凸显了在复杂数据环境中兼顾隐私与稳健性的难度。
Q&A
线性回归的差分隐私算法有哪些主要类型？
文章提到了基于指数机制的线性回归算法、隐私迭代硬阈值追踪、以及针对凸经验风险最小化的差分隐私算法等。这些算法在差分隐私框架下，通过不同机制（如指数机制）实现隐私保护，并适用于简单光滑函数家族。
局部差分隐私下的稀疏线性回归有什么新进展？
文章提出了一种创新的非交互式局部差分隐私（NLDP）算法，在数据服从亚高斯分布时，为估计误差提供了上界；当服务器有额外公开未标记数据时，误差上界可进一步提高。还研究了序贯交互式LDP模型，并发现了非私有、中心差分隐私和局部差分隐私模型在稀疏线性回归上的基本差异。
随机梯度下降的泛化误差如何理论分析？
文章提供了依赖于SGD迭代路径上评估的随机梯度的本地统计信息的泛化误差理论上限，关键因素包括梯度的方差、目标函数沿SGD路径的局部光滑性、损失函数对最终输出的扰动敏感度以及信息理论泛化界限等。
高维线性回归在对抗性污染下如何实现稳健估计？
文章研究了高维线性回归在对抗性污染下的稳健模型问题，针对从高斯分布生成的未修正样本的基本情况，给出了几乎最紧的上界和计算下界。
平均随机梯度下降的收敛性有什么理论保证？
文章对最小二乘回归问题中平均恒定步长随机梯度下降（也称最小均方误差）进行了详细的渐近分析，在强凸情况下提供了高度渐近展开式，为随机逼近算法提供了新见解。
如何平衡线性回归中的隐私保护与标准误差？
文章探讨了平衡标准误差和隐私保护之间的关系，提出了最小化极限风险下的差分隐私约束算法，包括隐私迭代硬阈值追踪，并在实际数据集中展示了数值表现。
