Oct, 2023

上下文随机双层优化

PDF
TL;DR我们引入了上下文随机双层优化（CSBO）—— 一种在下层问题最小化给定某些上下文信息和上层决策变量条件下的期望的随机双层优化框架。该框架扩展了经典的随机双层优化，使得下层决策者不仅对上层决策者的决策做出最优响应，还对一些侧面信息做出响应，并且存在多个甚至无数个追随者。它涵盖了元学习、个性化联邦学习、端到端学习和侧面信息的 Wasserstein 分布鲁棒优化等重要应用。由于存在上下文信息，现有的经典随机双层优化的单循环方法无法收敛。为了克服这个挑战，我们引入了一种基于多层蒙特卡罗（MLMC）技术的高效双循环梯度方法，并建立了其样本复杂度和计算复杂度。当专门应用于随机非凸优化时，我们的方法与现有下界相匹配。对于元学习，我们的方法的复杂度不依赖于任务数量。数值实验进一步验证了我们的理论结果。
contextual stochastic bilevel optimizationmeta-learningpersonalized federated learningend-to-end learningwasserstein distributionally robust optimization
发现论文，激发创造
  • 具有下层背景上下文的随机双层优化与决策过程

    我们介绍了一种基于情境马尔可夫决策过程（CMDP）的双层优化策略模型（BO-CMDP），该模型可以看作是领导者和随机情境共同决定多个马尔可夫决策过程（MDP）的设定，在各种应用中寻求最佳决策策略，进而应用于 MDP 模型设计、税务设计、奖励塑造和动态机制设计等领域。我们提出了一种基于梯度下降的随机超级策略（HPGD）算法用于求解 BO-CMDP 问题，并证明了其收敛性。该算法只利用随从者的轨迹观察，使得随从者可以使用任何训练过程而领导者无需了解具体算法，使得该模型适用于各种实际应用场景。我们还考虑了领导者能够影响随从者训练的情形，并提出了一种加速算法。我们通过实验证明了我们算法的性能。

    Jun, 2024

  • 双动量方法用于下层约束双层优化

    通过利用非光滑隐函数定理，提出一种新的双层约束双目标函数优化的超梯度方法，并基于双动量方法和自适应步长方法提出了一种单循环单时间尺度算法，经证明它可以返回一个（δ，ε）- 稳定点，迭代次数约为 O (d2^2ε^-4)，在两个应用上的实验证明了该方法的有效性。

    Jun, 2024

  • 多任务随机双层优化的随机降方差方法

    本文提出了快速随机化算法来解决非凸随机双层优化问题，在 Lipschitz 连续条件下建立了单一下层问题和具有 $m>1$ 个下层问题（多任务 SBO）的非凸 SBO 的样本复杂度，以及在梯度主导函数下的更快收敛结果。

    May, 2021

  • 关于双层优化问题的稳定性和泛化性

    本文针对双层 (随机) 优化问题，探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系，并在一般性情形下给出了稳定性界限的分析，通过实验证明了迭代次数对泛化误差的影响。

    Oct, 2022

  • 一种用于随机双层优化的单时间尺度方法

    本论文提出了一种单时间尺度的随机双层最优化算法 (STABLE)，用于解决机器学习中的双层次优化问题，具有较高的效率和样本复杂度。

    Feb, 2021

  • 基于模型的因果贝叶斯优化

    在本论文中，我们考虑了在 Causal Bayesian Optimization 基础上的一般化问题，即其他代理或外部事件也会对系统进行干预。我们将此广义 CBO 的形式化称为 Adversarial Causal Bayesian Optimization（ACBO），并引入了第一个具有有限遗憾的 ACBO 算法：Causal Bayesian Optimization with Multiplicative Weights（CBO-MW）。

    Jul, 2023

  • 松弛平滑条件下随机双层优化的最优算法

    本文提出了一种新的完全单循环和免除海森矩阵的算法框架，用于随机双层优化，并在标准光滑性假设下提出了更紧密的分析，进而展示了算法的普遍性。

    Jun, 2023

  • 基于模型的因果贝叶斯优化

    本文提出了一种基于模型和因果贝叶斯优化算法的方法，学习一个完整的系统模型并通过乐观的原则进行探索和开发，以解决在未知结构方程模型下如何干预以最大化目标变量的问题，并通过实验得到了有益的结果。

    Nov, 2022

  • Bayesian 优化中相关背景变量的成本感知学习

    本文介绍了一个基于敏感性分析的模型选择上下文优化算法（Sensitivity-Analysis-Driven Contextual BO），该算法可以在考虑环境上下文信息的同时最小化最优化成本，并在多个综合研究中表现出明显的改进。

    May, 2023

  • 一种能够实现随机和全局方差缩减算法的双层优化框架

    本研究提出了一种新的方法来解决大规模实证风险最小化中双层优化问题的梯度计算难以求解的问题，设计了 SABA（基于 SAGA 算法的）全局方差缩减算法，该算法收敛速度达到了 $O (rac1T)$， 实现了线性收敛，并得到了实验证明。

    Jan, 2022