Feb, 2024

随机凸优化的信息复杂性：泛化与记忆的应用

PDF
TL;DR通过研究随机凸优化（SCO）中记忆和学习之间的相互作用，我们使用条件互信息（CMI）的框架精确刻画了学习算法的准确性和 CMI 之间的权衡关系，回答了 Livni（2023 年）提出的一个开放问题。我们进一步设计了一个对特定的 SCO 问题能够准确识别出训练样本的对手，展示了记忆在 SCO 学习问题中的重要作用，并列举了我们结果的几个启示，如基于 CMI 的泛化边界的局限性和 SCO 问题样本不可压缩性。
发现论文，激发创造
  • 随机凸优化的预言机复杂度信息论下界

    本文研究使用计算机预测的随机凸优化的复杂性，提出了改善已知结果的方法，并获得了各种函数类的紧致极小复杂度估计。

    Sep, 2010

  • 在线凸优化算法（无内存限制）

    本文提出了一个新的在线凸优化框架，能够利用过去的决策历史对当前损失进行建模，并引入了 “p 有效内存容量” 来量化过去决策对当前损失的最大影响。在此框架下，证明了一些政策遗憾的较好上界，并展示了该框架对于各种在线学习任务的适用性。

    Oct, 2022

  • 通过条件互信息推理广义化问题

    该论文提出了一个信息理论框架来研究机器学习算法的泛化性能，利用条件互信息量化算法输出和训练数据之间的关系，并提出基于 VC 维、压缩方案、差分隐私等方法来获得有界的条件互信息，从而得出泛化的各种形式。

    Jan, 2020

  • 凸编程中基于信息的复杂性、反馈和动态

    通过反馈信息理论的视角，研究序列凸优化的内在限制。我们证明了，在优化算法中，为了获得最优解，算法必须能够积累关于目标的充分信息，这对于特定的假设和反馈类型限制了优化速度。我们的技术类似于统计学文献中用于估计程序风险的极小界，但不同之处是优化算法可以以受控方式收集观测数据。特别地，我们证明了优化算法常常遵循收益不高于成本的规律。我们利用这种方法推导了一类主动学习问题的基本下限，进一步实现了优化、实验设计、估计和主动学习中信息和量化信息之间的联系。

    Oct, 2010

  • 随机优化的购买信息

    本文研究如何以在线学习问题的形式购买信息来帮助随机优化问题，提出了一个 $2$-competitive 算法和一个 $e/(e-1)$-competitive 随机化算法，特别应用于 Min-Sum Set Cover 优化问题。

    Jun, 2023

  • 分布式凸优化的通信复杂度

    研究了分布式方法在凸学习与优化中所需要的通信效率的根本限制，在不同信息假设和函数类型条件下找到了现有算法已达到最坏复杂度的情况，同时也指出了仍有改进的余地，说明了当本地目标函数没有相似之处时（由于统计数据相似或其他原因），即使设备具有无限计算能力，也可能需要多次通信往返。

    Jun, 2015

  • 随机凸优化中 ERMs 的样本复杂度

    在这项工作中，我们证明了实际上只需要大约 d/ε+1/ε² 个数据点，就足够使得任何经验风险最小化器（ERM）在真实总体上表现良好，从而解决了一个中心基础问题，即学习在真实总体上取得好的性能需要观察多少数据点。

    Nov, 2023

  • 随机凸优化的经验风险最小化：$O (1/n)$ 和 $O (1/n^2)$ 类型的风险界

    利用平滑和强凸条件改善风险上界，建立了新的凸优化式 的有限样本错误分析方法。

    Feb, 2017

  • 关于尖锐感知极小化的记忆和隐私风险

    我们通过数据存储在过参数化模型中的方式来研究寻求更平坦的神经网络损失优化算法如何导致更好的泛化性能，我们提出了新的指标来帮助我们确定哪些数据点在与普通 SGD 相比寻求更平坦最优解的算法中表现更好。我们发现了 Sharpness Aware Minimization (SAM) 所实现的泛化性能提升特别明显的非典型数据点，这需要数据的存储。这一观点帮助我们发现了与 SAM 相关的更高的隐私风险，我们通过详尽的实证评估进行了验证。最后，我们提出了缓解策略以实现更理想的准确性与隐私权衡。

    Sep, 2023

  • 强凸性和利普希茨 Hessian 下的随机零阶优化：极小 - 最大样本复杂度

    在在线学习中，优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下，对二阶平滑和强凸函数进行优化的问题；通过提出匹配的上下界，第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法，结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画，从而使算法能够在偏差 - 方差权衡方面达到最优平衡，以及一种用于启动阶段的新的迭代方法，它能够保持无界 Hessian 的性能。

    Jun, 2024