计图开源：面向大规模非凸双层优化问题的一阶非嵌套高效算法

近年来，大规模深度学习技术在多个领域展现出强大的应用潜力。然而，复杂深度学习任务往往存在多任务耦合关系。这种耦合关系不仅体现在子任务之间的相互依赖（如跨场景适应和多任务迁移），还体现在网络结构优化和超参数选择等方面。双层优化是一类用于建模耦合优化问题的数学工具，它提供了一个统一的视角来挖掘复杂学习任务中的多任务耦合的本质规律。

双层优化包含上下两个层次的优化，上层优化问题依赖于下层优化问题的最优解，且上下层的优化变量相互作用，导致理论分析与数值计算均面临挑战。现有的双层优化理论对下层单点的严格依赖（即最优解唯一），限制了算法的应用范围。此外现有算法通常依赖嵌套迭代和高阶梯度，导致计算代价高昂。由于神经网络结构和参数空间的复杂性，关于深度学习的优化问题通常是非凸的。为了满足真实应用需求，亟需设计适用于非凸优化目标且能够打破嵌套计算的一阶高效算法，以提高计算效率并确保算法的收敛性。

近日，大连理工大学刘日升教授团队在ICML 2024发表的研究工作提出了一阶非嵌套双层优化算法MEHA[1]，可适用于广泛的优化场景，并开源了基于计图(Jittor)深度学习框架的代码。

Part1

方案介绍

本文主要研究下层非凸或非光滑的双层优化问题[2]，其具体形式为：

其中S(x)为下层问题的解集，写作：

其中f(x)为光滑非凸函数，g(x)为部分非光滑函数。

本文的核心思路是重构下层问题。可利用下式构造下层问题的Moreau包络：

进而构造不等式约束

罚函数法是一种在约束优化问题中将约束条件转化为惩罚项并加入目标函数的方法。通过这种转化，优化问题可以变为无约束优化问题。本文利用罚函数得到了双层优化的单层近似问题，其形式为：

其中Ck为惩罚系数。通过求解其近似问题，本文构造了一阶非嵌套算法MEHA。每次迭代中使用一阶梯度方法交替更新变量，其算法细节图1所示。

图1. 一阶非嵌套算法MEHA

Part2

理论结果

非渐进收敛研究的是在确定的步数内，算法能否达到某种精度或满足某种条件。其重要性在于它能提供实际的算法性能评估。作者给出了严格的非渐进收敛理论。

表1是与当前能够求解上下层非凸的双层优化方法进行对比。一方面，本文给出的非渐进收敛算法没有依赖下层Polyak-Łojasiewicz(PL)条件。另一方面，所提方法实现了一阶和非嵌套高效计算，适用于广泛的优化场景。

表1 与求解上下层非凸问题的相关工作对比

Part3

实验结果

为了验证该方法的有效性，本文在非凸数值实验与网络结构搜索任务上进行了实验。

非凸数值实验：本文与两个能够求解下层非凸算法BOME[3]与IAPTT[4]进行了对比，结果如图2所示。通过在不同维度下的收敛情况对比，验证了算法在下层非凸情形的收敛性质。

图2. 不同维度下求解下层非凸问题的算法收敛曲线对比

少样本学习：表2左侧部分提供了在10-way 1-shot与20-way 1-shot少样本学习任务中达到90%精度所用时间比较，所提方法使用最少的训练时间达到了要求精度。

表2 少样本学习任务收敛速度与数据超清洗任务精度对比

网络结构搜索：表3对比了所提方案(MEHA)与其他专门设计方法的精度。其他方法需要依赖工程经验设计搜索策略与搜索空间。然而本文方法基于双层优化建模可以在具有理论收敛的前提下实现更好的性能提升。

表3 网络结构搜索不同阶段精度对比

目前已开源了计图(Jittor)实现的算法代码。相较于PyTorch，计图的本的计算效率提升了1.2倍。

Part4

结论与展望

本文提出了一种基于Moreau包络重构，能够求解下层非凸问题的双层优化算法。该方法避免了与Hessian相关的高阶计算，并将嵌套循环计算简化为交替计算，从而提升了在大规模学习任务中的实用性和效率。

面向实际应用，设计有效的大规模优化学习算法既耗时又具有挑战性。本文介绍的双层优化方法以其一阶和非嵌套计算的特点，适用于广泛的优化场景，有望为各类大规模学习任务提供有效支撑。

项目主页:

https://rsliu.tech/MEHA/

开源代码:

https://github.com/vis-opt-group/MEHA/tree/main/Jittor

原文:

https://arxiv.org/abs/2405.09927

参考文献

Risheng Liu, Zhu Liu, Wei Yao, Shangzhi Zeng, Jin Zhang，Moreau Envelope for Nonconvex Bi-Level Optimization: Single-Loop and Hessian-Free Solution Strategy，ICML 2024.
Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, Zhouchen Lin, Investigating Bi-Level Optimization for Learning and Vision From a Unified Perspective: A Survey and Beyond, IEEE TPAMI 2022, Vol. 44, No. 12, 10045-10067.
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, Qiang Liu, BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach, NeurIPS 2022, Vol. 35, 17248--17262.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, Jin Zhang, Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond, NeurIPS 2021, Vol. 34, 8662--8675.

GGC往期回顾

1. 2023年度SCI影响因子发布，CCF A类期刊影响因子有何变化？

2. CVMJ获最新期刊影响因子17.3，计算机学科软件工程类别排名第一

3. Scopus发布2023年度影响因子, CVMJ从11.1升至16.9, 排名4/106

4. 第四届“计图”人工智能算法挑战赛启动

5. 计图助力非十科技发布AI代码助手，代码大模型速度精度超越Copilot

可通过下方二维码，关注清华大学图形学实验室，了解图形学、Jittor框架、CVMJ期刊和CVM会议的相关资讯。

计图开源：面向大规模非凸双层优化问题的一阶非嵌套高效算法

计图开源：面向大规模非凸双层优化问题的一阶非嵌套高效算法

Search

Table of Contents