关键词stochastic convex optimization
搜索结果 - 43
- 稀疏梯度的差分隐私优化
在大型嵌入模型应用的推动下，我们研究了带有个体梯度稀疏性的差分隐私（DP）优化问题，我们得到了经典均值估计问题的新近最优界限，但这是在稀疏数据情况下，改进了先前的算法，特别是在高维情况下。在此基础上，我们提出了几乎最优的 DP 算法和近似 - 随机凸优化中梯度下降的样本复杂度
我们分析了非光滑随机凸优化中全批量梯度下降（GD）的样本复杂性，表明 GD 的泛化误差与最优超参数选择的样本复杂性匹配，可以表示为 Θ(d/m + 1/√m)，其中 d 为维度，m 为样本大小，这与最坏情况下的经验风险最小化器相符，这意味着 - 加速无需参数的随机优化
提出一种方法，在光滑随机凸优化中实现接近最优的速率，几乎不需要先验问题参数知识，通过结合 UniXGrad 和 DoG，使用新的迭代稳定技术，在仅具有对 d0 和噪声大小的粗略上界的情况下，提供了对于子高斯噪声的高概率保证，并且在非光滑的情 - 约束条件下的随机优化：非渐近函解析
通过分析局部最小值下界与扰动问题解的关系，我们证明了方差减小的近端梯度算法在样本数量趋向无穷大时达到了局部最小值下界，除了普适常数和对数因子的样本大小外。
- 公共数据辅助的私有随机优化：功效与限制
公共数据辅助差分隐私算法的限制和能力研究，重点研究带有标记或无标记的公共数据的随机凸优化问题，通过建立 PA-DP 均值估计的新的下界，展示了算法的风险上限及最优策略，同时研究了未标记公共样本在隐私监督学习中的应用，并给出了广义线性模型的高 - 随机凸优化中的适应性代价
证明了在非光滑随机凸优化中的灵活性的不可能性结果，并引入了 “自适应性的代价”(PoA) 的概念来衡量由于参数的不确定性而导致的次优解的多样化增长。通过理论推导，证明了在初始化距离和梯度范数都不确定的情况下，PoA 至少是对于预期次优值是对 - 随机凸优化的信息复杂性：泛化与记忆的应用
通过研究随机凸优化（SCO）中记忆和学习之间的相互作用，我们使用条件互信息（CMI）的框架精确刻画了学习算法的准确性和 CMI 之间的权衡关系，回答了 Livni（2023 年）提出的一个开放问题。我们进一步设计了一个对特定的 SCO 问题 - 无参数随机优化有多自由？
该文章研究了无参数随机优化问题，探讨在什么条件下能够存在完全无参数的方法，并且通过简单的超参数搜索技术，证明了在凸和非凸环境下，可以实现优于当前先进算法的完全无参数方法。同时，对于仅有随机梯度的情况，该研究还提供了基于下限的 (部分) 无参 - 用梯度实现的维度冲击：随机凸优化中的梯度方法的泛化
研究了梯度方法在基础随机凸优化条件下的泛化性能，并关注其与维数的依赖关系。针对全批量梯度下降（GD），通过构建学习问题，在维数为 $ d = O（n^2）$ 的情况下，可以证明经过调整以达到经验风险最优表现的典型 GD（使用 n 个训练样本 - 随机凸优化中 ERMs 的样本复杂度
在这项工作中，我们证明了实际上只需要大约 d/ε+1/ε² 个数据点，就足够使得任何经验风险最小化器（ERM）在真实总体上表现良好，从而解决了一个中心基础问题，即学习在真实总体上取得好的性能需要观察多少数据点。
- 用户级差分隐私随机凸优化：具有最优收敛速率的高效算法
我们研究了具有用户级隐私的差分隐私随机凸优化（DP-SCO），其中每个用户可能拥有多个数据项。我们开发了新算法用于用户级 DP-SCO，在多项式时间内获得凸和强凸函数的最优速率，并且在维度上只要求用户数量呈对数增长。此外，我们的算法是第一个 - 无投影方法用于具有凸下层问题的随机简单双层优化
我们研究了一类随机二级优化问题，引入了一种新颖的随机二级优化方法，通过随机切割平面局部逼近下层问题的解集，并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下，我们的方法需要最多 $\tilde - ICML从自适应查询发布到机器消除学习
机器遗忘问题中设计高效算法的形式化，包括线性和前缀和查询类的高效遗忘算法以及其在随机凸优化问题和广义线性模型中的应用，提供了不同情况下的遗忘风险和查询复杂度。
- 联合差分隐私跨数据所有者的学习
本研究探讨了数据所有者在一种称为联合差分隐私的隐私保护机制下共同协作训练机器学习模型的方法，介绍了一种 DP-SGD 算法变体，研究了多分类问题的实证结果，并提供了与我们理论结果相一致的见解。
- 用户级私有凸优化
该研究介绍了一种新的具有用户级差分隐私保证的随机凸优化机制，收敛速度类似于 Levy 等人（2021）；Narayanan 等人（2022）的先前工作，但有两个重要改进。该机制不需要对损失进行任何平滑性假设，同时也是第一个其用户级隐私所需最 - $μ^2$-SGD: 双动量机制实现稳定随机优化
研究通过基于动量的两种近期机制，结合两者来得出新的梯度估计，设计基于 SGD 的算法和加速版本的算法，并展示这些新方法对学习率选择的鲁棒性以及在无噪音和有噪音情况下具有相同的最佳收敛速度。
- ICML插值区间中的私有优化：更快速率和难度结果
该研究使用随机凸优化方法解决私有化环境的插值问题，并提出了自适应算法来提高样本复杂性。
- ICML关于私人在线凸优化：在 $l_p$ 几何和高维情境赌徒中的最优算法
研究了使用差分隐私保护的在线随机凸优化问题，提出了一种具有递归梯度的私有在线 Frank-Wolfe 算法，可在线性时间内实现最优超额风险，并证明递归梯度的方差缩减结果在非平稳场景下也有理论保证。同时，该算法也被扩展到 p=1 的情况，可实 - ICML延迟反馈下的学习：隐含适应梯度延迟
针对多台异步运行的机器共同访问的内存环境下的随机凸优化问题，我们提出了一种鲁棒的约束训练方法，其非渐近收敛保证不依赖于更新延迟、目标平滑度和梯度方差的先验知识。与此相反，现有方法严重依赖于这些先验知识，因此不适用于所有共享资源的计算环境，如 - ICLR混洗私有随机凸优化
本文介绍一种名为 Shuffle Privacy 的隐私协议，使用交互式协议实现基于随机凸优化的消息混洗，并描述了一种新的求解二范数受限向量加和的过程，并在结合 Mini-batch SGD、加速梯度下降和 Nesterov 的平滑方法的基