Bilevel optimization has seen an increasing presence in various domains of
applications. In this work, we propose a framework for solving bilevel
optimization problems where variables of both lower and upper level problems
are constrained on Riemannian manifolds. We provide several hypergradient
estimation strategies on manifolds and study their estimation error. We provide
convergence and complexity analysis for the proposed hypergradient descent
algorithm on manifolds. We also extend the developments to stochastic bilevel
optimization and to the use of general retraction. We showcase the utility of
the proposed framework on various applications.

提出了一个在黎曼流形上求解双层优化问题的框架，研究了超梯度估计策略，分析了算法的收敛性和复杂度，扩展了到随机双层优化和一般回退的应用。

黎曼流形上的双层优化框架

A Framework for Bilevel Optimization on Riemannian Manifolds

Bilevel optimization has become a powerful tool in a wide variety of machine
learning problems. However, the current nonconvex bilevel optimization
considers an offline dataset and static functions, which may not work well in
emerging online applications with streaming data and time-varying functions. In
this work, we study online bilevel optimization (OBO) where the functions can
be time-varying and the agent continuously updates the decisions with online
streaming data. To deal with the function variations and the unavailability of
the true hypergradients in OBO, we propose a single-loop online bilevel
optimizer with window averaging (SOBOW), which updates the outer-level decision
based on a window average of the most recent hypergradient estimations stored
in the memory. Compared to existing algorithms, SOBOW is computationally
efficient and does not need to know previous functions. To handle the unique
technical difficulties rooted in single-loop update and function variations for
OBO, we develop a novel analytical technique that disentangles the complex
couplings between decision variables, and carefully controls the hypergradient
estimation error. We show that SOBOW can achieve a sublinear bilevel local
regret under mild conditions. Extensive experiments across multiple domains
corroborate the effectiveness of SOBOW.

本文研究了在线双层优化（OBO）问题，提出了一种基于窗口平均的单循环在线双层优化器（SOBOW），用于处理时间变化的函数和真超梯度不可得的问题，并通过解开决策变量之间的复杂耦合关系并精确控制超梯度估计误差，来实现亚线性双层局部遗憾的性能。通过在多个领域进行广泛实验证实了 SOBOW 的有效性。

非凸时变目标的双层优化

Non-Convex Bilevel Optimization with Time-Varying Objective Functions

Bilevel optimization has become a powerful framework in various machine
learning applications including meta-learning, hyperparameter optimization, and
network architecture search. There are generally two classes of bilevel
optimization formulations for machine learning: 1) problem-based bilevel
optimization, whose inner-level problem is formulated as finding a minimizer of
a given loss function; and 2) algorithm-based bilevel optimization, whose
inner-level solution is an output of a fixed algorithm. For the first class,
two popular types of gradient-based algorithms have been proposed for
hypergradient estimation via approximate implicit differentiation (AID) and
iterative differentiation (ITD). Algorithms for the second class include the
popular model-agnostic meta-learning (MAML) and almost no inner loop (ANIL).
However, the convergence rate and fundamental limitations of bilevel
optimization algorithms have not been well explored.
This thesis provides a comprehensive convergence rate analysis for bilevel
algorithms in the aforementioned two classes. We further propose principled
algorithm designs for bilevel optimization with higher efficiency and
scalability. For the problem-based formulation, we provide a convergence rate
analysis for AID- and ITD-based bilevel algorithms. We then develop
acceleration bilevel algorithms, for which we provide shaper convergence
analysis with relaxed assumptions. We also provide the first lower bounds for
bilevel optimization, and establish the optimality by providing matching upper
bounds under certain conditions. We finally propose new stochastic bilevel
optimization algorithms with lower complexity and higher efficiency in
practice. For the algorithm-based formulation, we develop a theoretical
convergence for general multi-step MAML and ANIL, and characterize the impact
of parameter selections and loss geometries on the their complexities.

本篇论文提供了多方面的双层优化算法收敛速度分析，包括问题和算法两个方面，提出了更加高效可扩展的算法设计，并最终提出了新的随机双层优化算法降低了实践中的复杂度并提高其效率。