In this paper, we study a class of non-smooth non-convex problems in the form
of $\min_{x}[\max_{y\in Y}\phi(x, y) - \max_{z\in Z}\psi(x, z)]$, where both
$\Phi(x) = \max_{y\in Y}\phi(x, y)$ and $\Psi(x)=\max_{z\in Z}\psi(x, z)$ are
weakly convex functions, and $\phi(x, y), \psi(x, z)$ are strongly concave
functions in terms of $y$ and $z$, respectively. It covers two families of
problems that have been studied but are missing single-loop stochastic
algorithms, i.e., difference of weakly convex functions and weakly convex
strongly-concave min-max problems. We propose a stochastic Moreau envelope
approximate gradient method dubbed SMAG, the first single-loop algorithm for
solving these problems, and provide a state-of-the-art non-asymptotic
convergence rate. The key idea of the design is to compute an approximate
gradient of the Moreau envelopes of $\Phi, \Psi$ using only one step of
stochastic gradient update of the primal and dual variables. Empirically, we
conduct experiments on positive-unlabeled (PU) learning and partial area under
ROC curve (pAUC) optimization with an adversarial fairness regularizer to
validate the effectiveness of our proposed algorithms.

本文研究了一类非光滑非凸问题，提出了一种基于随机 Moreau 包络梯度方法的单循环算法来解决这类问题，该算法在解决非光滑非凸问题上取得了最先进的非渐进收敛速率，通过实验证明了算法的有效性。

差的最大结构弱凸函数的单循环随机算法

Single-loop Stochastic Algorithms for Difference of Max-Structured  Weakly Convex Functions

Bilevel optimization has received more and more attention recently due to its
wide applications in machine learning. In this paper, we consider bilevel
optimization in decentralized networks. In particular, we propose a novel
single-loop algorithm for solving decentralized bilevel optimization with
strongly convex lower level problem. Our algorithm is fully single-loop and
does not require heavy matrix-vector multiplications when approximating the
hypergradient. Moreover, unlike existing methods for decentralized bilevel
optimization and federated bilevel optimization, our algorithm does not require
any gradient heterogeneity assumption. Our analysis shows that the proposed
algorithm achieves the best known convergence rate for bilevel optimization
algorithms.

在这篇论文中，我们考虑了分散网络中的双层优化问题，提出了一种针对具有强凸下层问题的分散式双层优化的新型单循环算法。我们的算法完全是单循环算法，在逼近超梯度时不需要进行复杂的矩阵向量乘法。此外，与现有的分散式双层优化和联邦双层优化方法不同的是，我们的算法不需要任何梯度异质性假设。我们的分析结果显示，该算法达到了迄今为止双层优化算法的最佳收敛速度。

分布式双层优化的单循环算法

A Single-Loop Algorithm for Decentralized Bilevel Optimization

Stochastic Bilevel optimization usually involves minimizing an upper-level
(UL) function that is dependent on the arg-min of a strongly-convex lower-level
(LL) function. Several algorithms utilize Neumann series to approximate certain
matrix inverses involved in estimating the implicit gradient of the UL function
(hypergradient). The state-of-the-art StOchastic Bilevel Algorithm (SOBA) [16]
instead uses stochastic gradient descent steps to solve the linear system
associated with the explicit matrix inversion. This modification enables SOBA
to match the lower bound of sample complexity for the single-level counterpart
in non-convex settings. Unfortunately, the current analysis of SOBA relies on
the assumption of higher-order smoothness for the UL and LL functions to
achieve optimality. In this paper, we introduce a novel fully single-loop and
Hessian-inversion-free algorithmic framework for stochastic bilevel
optimization and present a tighter analysis under standard smoothness
assumptions (first-order Lipschitzness of the UL function and second-order
Lipschitzness of the LL function). Furthermore, we show that by a slight
modification of our approach, our algorithm can handle a more general
multi-objective robust bilevel optimization problem. For this case, we obtain
the state-of-the-art oracle complexity results demonstrating the generality of
both the proposed algorithmic and analytic frameworks. Numerical experiments
demonstrate the performance gain of the proposed algorithms over existing ones.

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