arXiv:2411.05868math.OCcs.LG2024-11NeurIPS被引 1

提出无放回采样算法,加速双层优化收敛

Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling

  • 采用无放回采样策略,降低超梯度计算复杂度
  • 理论证明收敛速度优于传统独立采样方法
  • 适用于双层优化、极小极大及复合优化场景

双层优化近年来取得显著进展,基于随机梯度的算法被广泛采用。然而,这些算法普遍依赖独立采样假设,导致超梯度计算复杂,增加计算成本。本文研究双层优化中的样本选择策略,提出一种基于无放回采样的算法,相较于依赖独立采样的方法,实现了更快的收敛速率。此外,将讨论扩展至条件双层优化,以及极小极大和复合优化两个特例。在合成数据与真实世界应用上验证了算法有效性,数值结果清晰展示其优越性。

原文摘要 · Abstract (English)

Bilevel Optimization has experienced significant advancements recently with the introduction of new efficient algorithms. Mirroring the success in single-level optimization, stochastic gradient-based algorithms are widely used in bilevel optimization. However, a common limitation in these algorithms is the presumption of independent sampling, which can lead to increased computational costs due to the complicated hyper-gradient formulation of bilevel problems. To address this challenge, we study the example-selection strategy for bilevel optimization in this work. More specifically, we introduce a without-replacement sampling based algorithm which achieves a faster convergence rate compared to its counterparts that rely on independent sampling. Beyond the standard bilevel optimization formulation, we extend our discussion to conditional bilevel optimization and also two special cases: minimax and compositional optimization. Finally, we validate our algorithms over both synthetic and real-world applications. Numerical results clearly showcase the superiority of our algorithms.

双层优化采样策略收敛速度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。