重新审视随机多级复合优化中的多级复合优化

科学领域:

• 优化理论 优化理论
• 机器学习 机器学习
• 应用数学 应用数学 应用数学

背景情况:

• 随机多级组合优化涉及复杂的客观函数,由多个平滑函数组成.
• 现有的优化方法往往表现出低于最佳的样本复杂性或需要大批次大小,限制了它们的实际适用性.
• 解决这些局限性对于在各种科学领域推进高效和可扩展的优化技术至关重要.

研究的目的:

• 开发一种新的优化方法,即随机多级差异减少 (SMVR),以克服传统方法的局限性.
• 为了获得最佳的样本复杂度,在非凸,凸和强烈凸的条件中找到静止点/Polyak-Łojasiewicz (PL) 条件目标函数.
• 引入适应性学习速度能力,以增强实践融合.

主要方法:

• 引入了基于预期的优化所使用的随机多级变量减少 (SMVR) 方法.
• 提出了针对凸和Polyak-Łojasiewicz (PL) 或强烈凸函数量身定制的阶段 SMVR 变体.
• 开发了用于有限和优化案例的SMVR-FS算法和用于利用自适应学习速率的自适应SMVR.

主要成果:

• 在预期情况下,SMVR实现了非凸的目标的最佳 $\mathcal{O}(1/\epsilon^{3}) $ 样本复杂性.
• 阶段 SMVR 变体实现 $\mathcal{O}(1/\epsilon^{2}) $ 的凸和 $\mathcal{O}(1/\mu\epsilon)) $ 的 $\mu$-PL 或强烈凸的函数,匹配下限.
• SMVR-FS和自适应型SMVR在有限和实践中的收方面表现出更高的复杂性.

结论:

• 拟议的SMVR方法及其变体为随机多级组合优化提供了对样本复杂性的显著改进.
• 这些方法可以实现最佳或接近最佳的理论复杂性,而不需要大批量,从而提高效率.
• 适应式SMVR方法显示出更快的实际收的承诺,使其成为复杂优化问题的有价值工具.