随机凸优化的信息复杂性：泛化与记忆的应用
内容提要
该文汇总凸优化与在线学习研究，涵盖随机凸优化复杂度紧致估计、在线凸优化新框架与“p有效内存容量”、泛化信息论框架、序列凸优化信息限制、购买信息在线算法、分布式通信效率下界、ERM样本量、平滑强凸风险界、SAM泛化与隐私风险，以及随机约束在线凸优化算法。
延伸解读
信息复杂性：优化算法的内在限制
文章从信息论视角探讨了序列凸优化的内在限制，指出算法必须积累足够的目标信息才能获得最优解，这限制了优化速度。这种信息积累的视角类似于统计学中的极小界，但优化算法可以主动收集数据，从而在优化、实验设计、估计和主动学习之间建立联系。
在线凸优化新框架：p有效内存容量
文章提出了一个新的在线凸优化框架，利用过去的决策历史建模当前损失，并引入“p有效内存容量”量化历史决策的影响。该框架为政策遗憾提供了更好的上界，并适用于多种在线学习任务，为在线学习提供了新的分析工具。
泛化的信息论框架与条件互信息
文章提出了一个信息论框架，利用条件互信息量化算法输出与训练数据的关系，并通过VC维、压缩方案、差分隐私等方法获得有界的条件互信息，从而推导出泛化边界。这为理解机器学习算法的泛化性能提供了新的理论视角。
分布式优化的通信效率下界
文章研究了分布式凸学习与优化中通信效率的根本限制，指出当本地目标函数没有相似性时，即使设备计算能力无限，也可能需要多次通信往返。这揭示了分布式优化中通信效率的瓶颈，并指出在某些条件下现有算法已达到最坏复杂度，但仍有改进空间。
Q&A
随机凸优化的信息复杂性研究取得了哪些主要成果？
该研究提出了改善已知结果的方法，并获得了各种函数类的紧致极小复杂度估计。
在线凸优化中如何利用历史决策信息？
提出了一个新的在线凸优化框架，能够利用过去的决策历史对当前损失进行建模，并引入了“p有效内存容量”来量化过去决策对当前损失的最大影响。在此框架下，证明了一些政策遗憾的较好上界，并展示了该框架对于各种在线学习任务的适用性。
机器学习泛化性能的信息论框架是什么？
该论文提出了一个信息理论框架来研究机器学习算法的泛化性能，利用条件互信息量化算法输出和训练数据之间的关系，并提出基于VC维、压缩方案、差分隐私等方法来获得有界的条件互信息，从而得出泛化的各种形式。
序列凸优化中信息积累如何限制优化速度？
通过反馈信息理论的视角，研究序列凸优化的内在限制。证明了在优化算法中，为了获得最优解，算法必须能够积累关于目标的充分信息，这对于特定的假设和反馈类型限制了优化速度。技术类似于统计学文献中用于估计程序风险的极小界，但不同之处是优化算法可以以受控方式收集观测数据。特别地，证明了优化算法常常遵循收益不高于成本的规律。
购买信息如何帮助随机优化问题？
本文研究如何以在线学习问题的形式购买信息来帮助随机优化问题，提出了一个2-competitive算法和一个e/(e-1)-competitive随机化算法，特别应用于Min-Sum Set Cover优化问题。
分布式凸学习与优化的通信效率有哪些根本限制？
研究了分布式方法在凸学习与优化中所需要的通信效率的根本限制，在不同信息假设和函数类型条件下找到了现有算法已达到最坏复杂度的情况，同时也指出了仍有改进的余地，说明了当本地目标函数没有相似之处时，即使设备具有无限计算能力，也可能需要多次通信往返。
经验风险最小化需要多少数据点才能在真实总体上表现良好？
证明了实际上只需要大约d/ε+1/ε²个数据点，就足够使得任何经验风险最小化器（ERM）在真实总体上表现良好，从而解决了一个中心基础问题，即学习在真实总体上取得好的性能需要观察多少数据点。
如何利用平滑和强凸条件改善风险上界？
利用平滑和强凸条件改善风险上界，建立了新的凸优化式的有限样本错误分析方法。
SAM算法如何影响泛化性能和隐私风险？
通过数据存储在过参数化模型中的方式来研究寻求更平坦的神经网络损失优化算法如何导致更好的泛化性能，提出了新的指标来帮助确定哪些数据点在与普通SGD相比寻求更平坦最优解的算法中表现更好。发现了Sharpness Aware Minimization (SAM)所实现的泛化性能提升特别明显的非典型数据点，这需要数据的存储。这一观点帮助发现了与SAM相关的更高的隐私风险，并通过详尽的实证评估进行了验证。最后，提出了缓解策略以实现更理想的准确性与隐私权衡。
带随机约束的在线凸优化问题有哪些算法保证？
本文研究带随机约束的在线凸优化问题，提出了一种算法，能够达到预期和高概率的收益掉队和约束违反值等性能保证，并在真实数据中心调度问题上进行了实验验证。
