大型预审慎的模型可以私下微调以实现非私有模型的性能。这些结果中的一个共同主题是令人惊讶的观察结果，即高维模型可以实现有利的隐私性权衡。这似乎与差异私有凸学习的模型尺寸依赖性相矛盾，并提出了以下研究问题：差异私人学习的性能何时不会随着模型大小的增加而降低？我们确定投影到子空间上的梯度的幅度是决定性能的关键因素。为了确切地为私人凸学习的特征，我们引入了一个条件，即我们将限制Lipschitz的连续性限制并得出了在其他条件下与维度无关的过多经验和人口风险的界限。我们从经验上表明，在大型语言模型的私人微调中，在本地最佳距离附近评估的梯度主要由一些主要组件控制。这种行为类似于我们在凸面设置中获得尺寸独立界限的条件。我们的理论和经验结果共同为大规模私人微调成功提供了可能的解释。

在本文中，通过引入低噪声条件，我们研究了在随机凸出优化（SCO）的环境中，差异私有随机梯度下降（SGD）算法的隐私和效用（概括）表现。对于点心学习，我们建立了订单$ \ Mathcal {o} \ big（\ frac {\ sqrt {\ sqrt {d \ log（1/\ delta）}} {n \ epsilon} \ big）和$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ \ \ \\ \ \ \ \ \ big（\ frac {\ frac {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt { Mathcal {o} \ big（{n^{ - \ frac {1+ \ alpha} {2}}}}}}+\ frac {\ sqrt {d \ log（1/\ delta）}}} ）$（\ epsilon，\ delta）$ - 差异化私有SGD算法，分别是较高的和$ \ alpha $ -h \'分别较旧的光滑损失，其中$ n $是样本尺寸，$ d $是维度。对于成对学习，受\ cite {lei2020sharper，lei2021Generalization}的启发，我们提出了一种基于梯度扰动的简单私人SGD算法，该算法满足$（\ epsilon，\ delta）$ - 差异性限制，并开发出了新颖的私密性，并且算法。特别是，我们证明我们的算法可以实现多余的风险利率$ \ MATHCAL {o} \ big（\ frac {1} {\ sqrt {n}}}+\ frac {\ frac {\ sqrt { delta）}}} {n \ epsilon} \ big）$带有梯度复杂性$ \ mathcal {o}（n）$和$ \ mathcal {o} \ big（n^{\ frac {\ frac {2- \ alpha} {1+ alpha} {1+ \ alpha}}}+n \ big）$，用于强烈平滑和$ \ alpha $ -h \'olde R平滑损失。此外，在低噪声环境中建立了更快的学习率，以实现平滑和非平滑损失。据我们所知，这是第一次实用分析，它提供了超过$ \ Mathcal {o} \ big（\ frac {1} {\ sqrt {\ sqrt {n}}+\ frac {\ sqrt {d sqrt {d \ sqrt {d \ sqrt { log（1/\ delta）}}} {n \ epsilon} \ big）$用于隐私提供成对学习。

在本文中，我们重新审视了私人经验风险最小化（DP-erm）和差异私有随机凸优化（DP-SCO）的问题。我们表明，来自统计物理学（Langevin Exfusion（LD））的经过良好研究的连续时间算法同时为DP-SCO和DP-SCO提供了最佳的隐私/实用性权衡，$ \ epsilon $ -DP和$ $ \ epsilon $ -DP和$ （\ epsilon，\ delta）$ - dp均用于凸和强烈凸损失函数。我们为LD提供新的时间和尺寸独立统一稳定性，并使用我们为$ \ epsilon $ -DP提供相应的最佳超额人口风险保证。 $ \ epsilon $ -DP的DP-SCO保证的一个重要属性是，它们将非私人最佳界限匹配为$ \ epsilon \与\ infty $。在此过程中，我们提供了各种技术工具，这些工具可能引起独立的关注：i）在两个相邻数据集上运行损失功能时，一个新的r \'enyi Divergence绑定了LD，ii）最后一个过多的经验风险范围迭代LD，类似于Shamir和Zhang的嘈杂随机梯度下降（SGD）和iii）的LD，对LD进行了两期多余的风险分析，其中第一阶段是当扩散在任何合理意义上都没有在任何合理意义上融合到固定分布时，在第二阶段扩散已收敛到吉布斯分布的变体。我们的普遍性结果至关重要地依赖于LD的动力学。当它融合到固定分布时，我们获得了$ \ epsilon $ -DP的最佳界限。当它仅在很短的时间内运行$ \ propto 1/p $时，我们在$（\ epsilon，\ delta）$ -DP下获得最佳界限。在这里，$ p $是模型空间的维度。

我们研究了凸面和非凸面设置的差异私有随机优化。对于凸面的情况，我们专注于非平滑通用线性损耗（GLL）的家庭。我们的$ \ ell_2 $ setting算法在近线性时间内实现了最佳的人口风险，而最知名的差异私有算法在超线性时间内运行。我们的$ \ ell_1 $ setting的算法具有近乎最佳的人口风险$ \ tilde {o} \ big（\ sqrt {\ frac {\ log {n \ log {d}} {n \ varepsilon} \ big）$，以及避免\ Cite {ASI：2021}的尺寸依赖性下限为一般非平滑凸损耗。在差别私有的非凸面设置中，我们提供了几种新算法，用于近似居住的人口风险。对于具有平稳损失和多面体约束的$ \ ell_1 $ tuce，我们提供第一个近乎尺寸的独立速率$ \ tilde o \ big（\ frac {\ log ^ {2/3} {d}} {{（n \ varepsilon）^ {1/3}}} \大）在线性时间。对于具有平滑损耗的约束$ \ ell_2 $ -case，我们获得了速率$ \ tilde o \ big（\ frac {1} {n ^ {1/3}} + \ frac {d ^ { 1/5}} {（n \ varepsilon）^ {2/5}} \ big）$。最后，对于$ \ ell_2 $ -case，我们为{\ em非平滑弱凸}的第一种方法提供了速率$ \ tilde o \ big（\ frac {1} {n ^ {1/4}} + \ FRAC {D ^ {1/6}} {（n \ varepsilon）^ {1/3}} \ big）$，它在$ d = o（\ sqrt {n}）时匹配最好的现有非私有算法$。我们还将上面的所有结果扩展到Non-Convex $ \ ell_2 $ setting到$ \ ell_p $ setting，其中$ 1 <p \ leq 2 $，只有polylogarithmic（维度在尺寸）的速度下。

我们提出了一个新的框架，用于对凸函数的差异私有优化，这些功能是任意规范$ \ normx {\ cdot} $中的Lipschitz。我们的算法基于一种正规的指数机制，该机制从密度$ \ propto \ exp（-k（f+\ mu r））$中进行样品，其中$ f $是经验损失，$ r $是一种常规化器，它与强烈的convex convex converize尊重$ \ normx {\ cdot} $，将\ cite {gll22}的最新作品推广到非Euclidean设置。我们表明，这种机制可以满足高斯差异隐私，并通过使用凸几何形状的本地化工具来解决DP-MER（经验风险最小化）和DP-SCO（随机凸优化）。我们的框架是第一个在一般规范空间中适用于私有凸优化的框架，并直接恢复了镜下下降的非私有SCO率，作为隐私参数$ \ eps \ to \ infty $。作为应用程序，对于LipsChitz优化了$ \ ell_p $ norms for（1，2）$中的所有$ p \ norms，我们获得了第一个最佳隐私性权衡权衡；对于$ p = 1 $，我们提高了最近的作品\ cite {asifkt21，bassilygn21}获得的权衡，至少通过对数因素。我们的$ \ ell_p $ norm和schatten- $ p $规范优化框架与多项式时间采样器相辅相成，我们的查询复杂性明确绑定。

我们重新审视使​​用公共数据来改善差异私有（DP）模型培训的隐私/实用权折衷的问题。在这里，公共数据是指没有隐私问题的辅助数据集。我们考虑与私人培训数据相同的分发的公共数据。对于凸损失，我们表明镜子血清的变体提供了与模型的维度（$ p $）的人口风险保证。具体地，我们将镜像血液应用于由公共数据生成的丢失作为镜像映射，并使用私有（敏感）数据生成的丢失的DP梯度。为了获得维度独立性，我们需要$ g_q ^ 2 \ leq p $公共数据样本，其中$ g_q $是损失功能各向同性的量度。我们进一步表明，我们的算法具有天然的“噪音稳定性”属性：如果围绕当前迭代公共损失，请以$ V $的方向满足$ \ alpha_v $ -strong凸性，然后使用嘈杂的渐变而不是确切的渐变偏移我们的下一次迭代$ v $ v $比例为$ 1 / alpha_v $（与DP-SGD相比，换档是各向同性的）。在前作品中的类似结果必须使用预处理器矩阵形式的公共数据明确地学习几何图形。我们的方法也适用于非凸损失，因为它不依赖于凸起假设以确保DP保证。我们通过显示线性回归，深度学习基准数据集（Wikitext-2，Cifar-10和Emnist）以及联合学习（StackOverflow）来证明我们的算法的经验效果。我们表明，我们的算法不仅显着改善了传统的DP-SGD和DP-FedAVG，它没有访问公共数据，而且还可以改善DP-SGD和DP-FedAVG对已与公众预先培训的模型数据开始。

通过确保学习算法中的差异隐私，可以严格降低大型模型记忆敏感培训数据的风险。在本文中，我们为此目的研究了两种算法，即DP-SGD和DP-NSGD，它们首先剪辑或归一化\ textIt \ textIt {每样本}梯度以绑定灵敏度，然后添加噪声以使精确信息混淆。我们通过两个常见的假设分析了非凸优化设置中这两种算法的收敛行为，并实现了$ \ nathcal {o} \ left（\ sqrt [4] {\ frac {\ frac {d \ log（1/\ delta） ）} {n^2 \ epsilon^2}} \ right）$ $ d $ - 二维模型，$ n $ samples和$（\ epsilon，\ delta）$ - dp，它改进了以前的改进在较弱的假设下的界限。具体而言，我们在DP-NSGD中引入了一个正规化因素，并表明它对融合证明至关重要，并巧妙地控制了偏见和噪声权衡。我们的证明故意处理针对私人环境指定的按样本梯度剪辑和标准化。从经验上讲，我们证明这两种算法达到了相似的最佳准确性，而DP-NSGD比DP-SGD更容易调整，因此在计算调整工作时可能有助于进一步节省隐私预算。

在均匀的Lipschitzness的简单假设下，即每样本样本梯度均匀地界限的大多数先前的收敛结果是在均匀的私有随机梯度下降（DP-SGD）中得出的。在许多问题，例如使用高斯数据的线性回归中，此假设是不现实的。我们可以通过假设每个样本梯度具有\ textit {样品依赖性}上限，即每样本的Lipschitz常数，而它们本身可能是无限的，那么我们就会放松均匀的唇。当按样本Lipschitz常数具有有限的矩时，我们在凸函数和非凸函数上得出DP-SGD的新收敛结果。此外，我们还提供了针对DP-SGD中选择剪辑标准的原则指导，以使其满足我们轻松的Lipschitzness的凸设置，而无需在Lipschitz常数上做出分配假设。我们通过基准测试数据集的实验来验证建议的有效性。

我们研究了差异私有线性回归的问题，其中每个数据点都是从固定的下高斯样式分布中采样的。我们提出和分析了一个单次迷你批次随机梯度下降法（DP-AMBSSGD），其中每次迭代中的点都在没有替换的情况下进行采样。为DP添加了噪声，但噪声标准偏差是在线估计的。与现有$（\ epsilon，\ delta）$ - 具有子最佳错误界限的DP技术相比，DP-AMBSSGD能够在关键参数（如多维参数）（如多维参数）等方面提供几乎最佳的错误范围$，以及观测值的噪声的标准偏差$ \ sigma $。例如，当对$ d $二维的协变量进行采样时。从正常分布中，然后由于隐私而引起的DP-AMBSSGD的多余误差为$ \ frac {\ sigma^2 d} {n} {n}（1+ \ frac {d} {\ epsilon^2 n}）$，即当样本数量$ n = \ omega（d \ log d）$，这是线性回归的标准操作制度时，错误是有意义的。相比之下，在此设置中现有有效方法的错误范围为：$ \ mathcal {o} \ big（\ frac {d^3} {\ epsilon^2 n^2} \ big）$，即使是$ \ sigma = 0 $。也就是说，对于常量的$ \ epsilon $，现有技术需要$ n = \ omega（d \ sqrt {d}）$才能提供非平凡的结果。

We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. Combining ReSQue with recent advances in ball oracle acceleration [CJJJLST20, ACJJS21], we develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings. For a SCO objective constrained to the unit ball in $\mathbb{R}^d$, we obtain the following results (up to polylogarithmic factors). We give a parallel algorithm obtaining optimization error $\epsilon_{\text{opt}}$ with $d^{1/3}\epsilon_{\text{opt}}^{-2/3}$ gradient oracle query depth and $d^{1/3}\epsilon_{\text{opt}}^{-2/3} + \epsilon_{\text{opt}}^{-2}$ gradient queries in total, assuming access to a bounded-variance stochastic gradient estimator. For $\epsilon_{\text{opt}} \in [d^{-1}, d^{-1/4}]$, our algorithm matches the state-of-the-art oracle depth of [BJLLS19] while maintaining the optimal total work of stochastic gradient descent. We give an $(\epsilon_{\text{dp}}, \delta)$-differentially private algorithm which, given $n$ samples of Lipschitz loss functions, obtains near-optimal optimization error and makes $\min(n, n^2\epsilon_{\text{dp}}^2 d^{-1}) + \min(n^{4/3}\epsilon_{\text{dp}}^{1/3}, (nd)^{2/3}\epsilon_{\text{dp}}^{-1})$ queries to the gradients of these functions. In the regime $d \le n \epsilon_{\text{dp}}^{2}$, where privacy comes at no cost in terms of the optimal loss up to constants, our algorithm uses $n + (nd)^{2/3}\epsilon_{\text{dp}}^{-1}$ queries and improves recent advancements of [KLL21, AFKT21]. In the moderately low-dimensional setting $d \le \sqrt n \epsilon_{\text{dp}}^{3/2}$, our query complexity is near-linear.

我们在差分隐私（DP）的约束下，用重型数据研究随机凸优化。大多数关于此问题的事先工作仅限于损耗功能是Lipschitz的情况。相反，正如王，肖，德拉达斯和徐\ Cite {wangxdx20}所引入的那样，假设渐变的分布已涉及$ k $ --th时刻，我们研究了一般凸损失功能。我们在集中DP下提供了改善的上限，用于凸起的凸起和强凸损失功能。一路上，我们在纯粹和集中的DP下获得了私人平均估计的私有平均估计的新算法。最后，我们证明了私有随机凸性优化的近乎匹配的下限，具有强凸损失和平均估计，显示纯净和浓缩的DP之间的新分离。

在本文中，我们研究了非平滑凸函数的私人优化问题$ f（x）= \ mathbb {e} _i f_i（x）$ on $ \ mathbb {r}^d $。我们表明，通过将$ \ ell_2^2 $正规器添加到$ f（x）$并从$ \ pi（x）\ propto \ exp（-k（f（x）+\ mu \ \ | | x \ | _2^2/2））$恢复已知的最佳经验风险和$（\ epsilon，\ delta）$ - dp的已知最佳经验风险和人口损失。此外，我们将展示如何使用$ \ widetilde {o}（n \ min（d，n））$ QUERIES $ QUERIES $ f_i（x）$用于DP-SCO，其中$ n $是示例数/用户和$ d $是环境维度。我们还在评估查询的数量上给出了一个（几乎）匹配的下限$ \ widetilde {\ omega}（n \ min（d，n））$。我们的结果利用以下具有独立感兴趣的工具：（1）如果损失函数强烈凸出并且扰动是Lipschitz，则证明指数机制的高斯差异隐私（GDP）。我们的隐私约束是\ emph {optimal}，因为它包括高斯机制的隐私性，并使用等仪不等式证明了强烈的对数concove措施。 （2）我们展示如何从$ \ exp（-f（x） - \ mu \ | x \ | |^2_2/2）$ g $ -lipschitz $ f $带有$ \ eta $的总变化中的错误（电视）使用$ \ widetilde {o}（（g^2/\ mu）\ log^2（d/\ eta））$无偏查询到$ f（x）$。这是第一个在dimension $ d $和精度$ \ eta $上具有\ emph {polylogarithmic依赖的查询复杂性的采样器。

我们研究随机梯度下降（SGD）在多大程度上被理解为“常规”学习规则，该规则通过获得良好的培训数据来实现概括性能。我们考虑基本的随机凸优化框架，其中（一通道，无需替代）SGD在经典上是众所周知的，可以最大程度地降低人口风险，以$ o（1/\ sqrt n）$ $ O（1/\ sqrt n）$，并且出人意料地证明，存在问题实例SGD解决方案既表现出$ \ omega（1）$的经验风险和概括差距。因此，事实证明，从任何意义上讲，SGD在算法上都不是稳定的，并且其概括能力不能通过均匀的收敛性或任何其他当前已知的概括性结合技术来解释（除了其经典分析外）。然后，我们继续分析与替代SGD密切相关的相关性，为此我们表明不会发生类似现象，并证明其人口风险实际上确实以最佳速度融合。最后，我们在没有替换SGD的背景下解释了我们的主要结果，用于有限的和凸优化问题，并得出多上类别制度的上限和下限，从而在先前已知的结果上有了显着改善。

当算法的内部状态\ emph {private}时，迭代随机学习算法的信息泄漏是什么？每个特定培训时期对通过已发布的模型泄漏的贡献是多少？我们研究了此问题的嘈杂梯度下降算法，并在整个训练过程中对r \'enyi差异隐私损失的\ emph {dynamics}进行建模。我们的分析跟踪了\ emph {tigh}绑定在r \'enyi差异上的一对概率分布之间的差异，而不是在相邻数据集中训练的模型的参数。我们证明，隐私损失对平稳且强烈凸出的损失函数的呈指数呈指数收敛，这是对组成定理的显着改进（通过在所有中间梯度计算中，其总价值高于其总价值来过度估计隐私损失）。对于Lipschitz，光滑且强烈凸出的损失功能，我们证明了最佳效用，具有较小的梯度复杂性，用于嘈杂的梯度下降算法。

我们提出并分析了算法，以解决用户级差分隐私约束下的一系列学习任务。用户级DP仅保证只保证个人样本的隐私，而是保护用户的整个贡献（$ M \ GE 1 $ Samples），而不是对信息泄漏提供更严格但更现实的保护。我们表明，对于高维平均估计，具有平稳损失，随机凸优化和学习假设类别的经验风险最小化，具有有限度量熵，隐私成本随着用户提供的$ O（1 / \ SQRT {M}）$减少更多样本。相比之下，在增加用户数量$ N $时，隐私成本以较快的价格降低（1 / n）$率。我们将这些结果与下界相提并论，显示了我们算法的最低限度估计和随机凸优化的算法。我们的算法依赖于私有平均估计的新颖技术，其任意维度与误差缩放为浓度半径$ \ tai $的分布而不是整个范围。

随机优化在最小化机器学习中的目标功能方面发现了广泛的应用，这激发了许多理论研究以了解其实际成功。大多数现有研究都集中在优化误差的收敛上，而随机优化的概括分析却落后了。在实践中经常遇到的非洞穴和非平滑问题的情况尤其如此。在本文中，我们初始化了对非凸和非平滑问题的随机优化的系统稳定性和概括分析。我们介绍了新型算法稳定性措施，并在人口梯度和经验梯度之间建立了定量联系，然后进一步扩展，以研究经验风险的莫罗（Moreau）膜之间的差距和人口风险的差距。据我们所知，尚未在文献中研究稳定性与概括之间的这些定量联系。我们引入了一类采样确定的算法，为此我们为三种稳定性度量而开发界限。最后，我们将这些讨论应用于随机梯度下降及其自适应变体的误差界限，我们在其中显示如何通过调整步骤大小和迭代次数来实现隐式正则化。

在本文中，我们研究了差异化的私人经验风险最小化（DP-erm）。已经表明，随着尺寸的增加，DP-MER的（最坏的）效用会减小。这是私下学习大型机器学习模型的主要障碍。在高维度中，某些模型的参数通常比其他参数更多的信息是常见的。为了利用这一点，我们提出了一个差异化的私有贪婪坐标下降（DP-GCD）算法。在每次迭代中，DP-GCD私人沿梯度（大约）最大条目执行坐标梯度步骤。从理论上讲，DP-GCD可以通过利用问题解决方案的结构特性（例如稀疏性或准方面的）来改善实用性，并在早期迭代中取得非常快速的进展。然后，我们在合成数据集和真实数据集上以数值说明。最后，我们描述了未来工作的有前途的方向。

我们提出了一种基于优化的基于优化的框架，用于计算差异私有M估算器以及构建差分私立置信区的新方法。首先，我们表明稳健的统计数据可以与嘈杂的梯度下降或嘈杂的牛顿方法结合使用，以便分别获得具有全局线性或二次收敛的最佳私人估算。我们在局部强大的凸起和自我协调下建立当地和全球融合保障，表明我们的私人估算变为对非私人M估计的几乎最佳附近的高概率。其次，我们通过构建我们私有M估计的渐近方差的差异私有估算来解决参数化推断的问题。这自然导致近​​似枢轴统计，用于构建置信区并进行假设检测。我们展示了偏置校正的有效性，以提高模拟中的小样本实证性能。我们说明了我们在若干数值例子中的方法的好处。

成对学习是指损失函数取决于一对情况的学习任务。它实例化了许多重要的机器学习任务，如双级排名和度量学习。一种流行的方法来处理成对学习中的流数据是在线梯度下降（OGD）算法，其中需要将当前实例配对以前具有足够大的尺寸的先前实例的电流实例，因此遭受可扩展性问题。在本文中，我们提出了用于成对学习的简单随机和在线梯度下降方法。与现有研究的显着差异是，我们仅将当前实例与前一个构建梯度方向配对，这在存储和计算复杂性中是有效的。我们为凸和非凸起的展示结果，优化和泛化误差界以及平滑和非光滑问题都开发了新颖的稳定性结果，优化和泛化误差界限。我们引入了新颖的技术来解耦模型的依赖性和前一个例子在优化和泛化分析中。我们的研究解决了使用具有非常小的固定尺寸的缓冲集开发OGD的有意义的泛化范围的开放问题。我们还扩展了我们的算法和稳定性分析，以便为成对学习开发差异私有的SGD算法，这显着提高了现有结果。

随机梯度下降（SGDA）及其变体一直是解决最小值问题的主力。但是，与研究有差异隐私（DP）约束的经过良好研究的随机梯度下降（SGD）相反，在理解具有DP约束的SGDA的概括（实用程序）方面几乎没有工作。在本文中，我们使用算法稳定性方法在不同的设置中建立DP-SGDA的概括（实用程序）。特别是，对于凸 - 凸环设置，我们证明DP-SGDA可以在平滑和非平滑案例中都可以根据弱原始二元人群风险获得最佳的效用率。据我们所知，这是在非平滑案例中DP-SGDA的第一个已知结果。我们进一步在非convex-rong-concave环境中提供了实用性分析，这是原始人口风险的首个已知结果。即使在非私有设置中，此非convex设置的收敛和概括结果也是新的。最后，进行了数值实验，以证明DP-SGDA在凸和非凸病例中的有效性。