MGDA Converges under Generalized Smoothness, Provably

## Abstract

Abstract Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning. Recent works provide some effective algorithms with theoretical analysis but they are limited by the standard L 𝐿 L italic_L -smooth or bounded-gradient assumptions, which typically do not hold for neural networks, such as Long short-term memory (LSTM) models and Transformers. In this paper, we study a more general and realistic class of generalized ℓ ℓ \ell roman_ℓ -smooth loss functions, where ℓ ℓ \ell roman_ℓ is a general non-decreasing function of gradient norm. We revisit and analyze the fundamental multiple
gradient descent algorithm (MGDA) and its stochastic version with double sampling for solving the generalized ℓ ℓ \ell roman_ℓ -smooth MOO problems, which approximate the conflict-avoidant (CA) direction that maximizes the minimum improvement among objectives. We provide a comprehensive convergence analysis of these algorithms and show that they converge to an ϵ italic-ϵ \epsilon italic_ϵ -accurate Pareto stationary point with a guaranteed ϵ italic-ϵ \epsilon italic_ϵ -level average CA distance (i.e., the gap between the updating direction and the CA direction) over all iterations,
where totally 𝒪 ⁢ ( ϵ − 2 ) 𝒪 superscript italic-ϵ 2 \mathcal{O}(\epsilon^{-2}) caligraphic_O ( italic_ϵ start_POSTSUPERSCRIPT - 2 end_POSTSUPERSCRIPT ) and 𝒪 ⁢ ( ϵ − 4 ) 𝒪 superscript italic-ϵ 4 \mathcal{O}(\epsilon^{-4}) caligraphic_O ( italic_ϵ start_POSTSUPERSCRIPT - 4 end_POSTSUPERSCRIPT ) samples are needed for deterministic and stochastic settings, respectively.
We prove that they can also guarantee a tighter ϵ italic-ϵ \epsilon italic_ϵ -level CA distance in each iteration using more samples. Moreover, we analyze an efficient variant of MGDA named MGDA-FA using only 𝒪 ⁢ ( 1 ) 𝒪 1 \mathcal{O}(1) caligraphic_O ( 1 ) time and space, while achieving the same performance guarantee as MGDA.

## 1 Introduction

There have been a variety of emerging applications of multi-objective optimization (MOO), such as online advertising [], autonomous driving [], and reinforcement learning []. Mathematically, the MOO problem takes the following formulation.

$$ $\displaystyle F^{*}=\min_{x\in\mathbb{R}^{m}}{F}(x):=(f_{1}(x),f_{2}(x),...,f_ {K}(x)),$ (1) $$

where $K$ is the total number of objectives and $f_{k}(x)$ is the $k$-objective function given model parameters $x$. Under the stochastic setting, $f_{k}(x)=\mathbb{E}_{s}[f_{k}(x;s)]$, where $s$ denotes data samples. This problem is challenging due to the gradient conflict that some objectives with larger gradients dominate the update direction at the sacrifice of
significant performance degeneration on the less-fortune objectives with smaller gradients. A variety of MOO-based methods have been proposed to mitigate this conflict and find a more balanced solution among all objectives. In particular, the multiple gradient descent algorithm (MGDA) [] aims to find a conflict-avoidant (CA) update direction that maximizes the minimal improvement among all objectives and converges to a Pareto stationary point at which there is no common descent direction for all objective functions.
This idea then inspired numerous follow-up methods including but not limited to CAGrad [], PCGrad [], GradDrop [], FAMO [] and FairGrad [] with a convergence guarantee in the deterministic setting with full-gradient computations.
The theoretical understanding of the convergence and complexity of stochastic MOO is not well-developed until very recently. [] proposed stochastic multi-gradient (SMG) as a stochastic version of MGDA, and established its convergence guarantee. [] analyzed the non-convergence issues of MGDA,
CAGrad and PCGrad in the stochastic setting, and further proposed a convergent approach named CR-MOGM. More recently, [] and [] proposed single-loop stochastic MOO methods named MoCo and MoDo, and proved their convergence to an $\epsilon$-accurate Pareto stationary point while guaranteeing an $\epsilon$-level average CA distance(^1^11CA distance means the distance between the updating direction and the CA direction. Its formal definition can be found in Section 2.4) over all iterations. [] proposed a double-loop algorithm named SDMGrad that enables to obtain an unbiased stochastic multi-gradient via a double-sampling strategy. They established the convergence of SDMGrad with a guaranteed $\epsilon$-level CA distance in every iteration, which we call as iteration-wise CA distance.

Figure: Figure 1: Local smoothness constant vs. gradient norm for training SegNet on CityScapes dataset of Task 1.
Refer to caption: extracted/5896848/scatter_plot_GS_task1.png

However, all existing works are limited by the standard $L$-smooth and bounded-gradient assumptions.
Nevertheless, a recent study [] indicates that such assumptions may not necessarily be true for the training of neural networks and an alternative $(L_{0},L_{1})$-smoothness condition was observed and studied, which assumes the Lipschitz constant to be linear in the gradient norm and the gradient norm to be potentially infinite. Furthermore, this phenomenon has been consistently observed in our experiments (e.g., see Figure 1). Interestingly, it has been widely observed that
MGDA algorithms always converge even under such generalized smoothness conditions [, , ]. This naturally raises a thought-provoking question:

- Q.
Can the fundamental MGDA algorithm provably converge under the generalized smoothness condition, while achieving a sufficiently small CA distance?

This question remains open due to the following challenges.
The analysis of existing MOO methods cannot be generalized to this $(L_{0},L_{1})$-smoothness directly due to the possible unbounded smoothness or gradient norm. In addition, all existing works [, , , , , , , ] in generalized smoothness are limited to the single task problems, which are fundamentally different from the MOO problems since even though each single task is generalized smooth, the linear combination of these tasks is not necessarily generalized smooth. In this paper, we provide an affirmative answer to this question. Our main contributions are summarized below.

### 1.1 Our Contributions

We establish a comprehensive convergence analysis for MGDA under the generalized smoothness condition, in both the deterministic and stochastic settings.
Moreover, the analysis covers both the average CA distance and the iteration-wise CA distance.

Weakest assumptions in MOO. In this paper, we investigate the generalized $\ell$-smooth assumption, where $\ell$ is a general non-decreasing function of gradient norm, and includes both the standard $L$-smooth and $(L_{0},L_{1})$-smooth assumptions as special cases.
This assumption finds many applications, such as LSTM models [], transformers [], distributionally robust optimization [] and higher-order polynomial functions []. In addition, we do not make any bounded-gradient assumption, which is required in previous analysis to ensure the bounded multi-gradient approximation.
To the best of our knowledge, this is the first work to investigate generalized smoothness in MOO problems. Table 1 presents a detailed comparison of assumptions with existing analyses.

Convergence analysis.
We first show that the vanilla MGDA method can converge to an $\epsilon$-accurate Pareto stationary point, while guaranteeing a small $\epsilon$-level average CA distance. A warm start process is introduced before the main loop of MGDA to achieve a more aggressive $\epsilon$-level iteration-wise CA distance. In the stochastic setting, we provide the convergence guarantee for MGDA with a double sampling, which was introduced by [, ] to obtain unbiased multi-gradient approximations. Furthermore,
we analyze a computation- and memory-efficient variant of MGDA, named MGDA with fast approximation (MGDA-FA), which updates the objective weights $w$ using only forward passes of $F(\cdot)$ rather than gradient $\nabla F$, effectively reducing $O(K)$ time and space to $O(1)$ without hurting the performance guarantee.

Sample complexity comparison. To achieve an $\epsilon$-accurate Pareto stationary point and an $\epsilon$-level average CA distance, we show that MGDA require $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-4})$ samples in the deterministic and stochastic settings, respectively. Both of these complexities match with the existing best results.
Furthermore, to achieve an $\epsilon$-level iteration-wise CA distance, MGDA with warm start requires an increased number of samples, at the order of $\mathcal{O}(\epsilon^{-11})$ and $\mathcal{O}(\epsilon^{-17})$ respectively, in both deterministic and stochastic scenarios, due to smaller step sizes and mini-batch data sampling. Typically, achieving an $\epsilon$-level iteration-wise CA distance results in much higher sample complexity, such as $\mathcal{O}(\epsilon^{-24})$ in [], $\mathcal{O}(\epsilon^{-16})$ in [] and $\mathcal{O}(\epsilon^{-12})$ in [] for non-convex stochastic setting. Moreover, we show that MGDA-FA achieves the same performance guarantee as vanilla MGDA.

### 1.2 Related Works

Gradient-based multi-objective optimization.
A variety of gradient manipulation techniques have emerged for simultaneous learning of multiple tasks. One prevalent category of methods adjusts the weights of various objectives according to factors such as uncertainty [], gradient norm [], and training complexity []. Methods based on MOO have garnered increased attention due to their systematic designs, enhanced training stability, and model-agnostic nature. For instance, [] framed Multi-Task Learning (MTL) as a MOO problem and introduced an optimization method akin to MGDA [].
Afterward, many MGDA-based methods have been proposed to mitigate gradient conflict with promising empirical performance. Among them, PCGrad [] avoids conflict by projecting the gradient of each task on the norm plane of other tasks. GradDrop [] randomly drops out conflicted gradients. CAGrad [] adds a constraint on the update direction to be close to the average gradient. NashMTL [] and
FairGrad [] formulated MTL as a bargaining game and a resource allocation problem, respectively. Theoretically, [] proposed a provably convergent stochastic MOO method named MoCo
based on an auxiliary tracking variable for gradient approximation. [] characterized the trade-off among optimization, generalization, and conflict avoidance in MOO.
[] proposed and analyzed a stochastic MOO method named SDMGrad with a preference-oriented regularizer. However, all these works rely on the $L$-smoothness and bounded-gradient assumptions. In contrast, this paper focuses on the MOO problems with generalized $\ell$-smooth objectives.

**Table 1: Comparison to assumptions in existing analyses. MGDA [] assumes the access of optimal update direction and step size for each iteration and gets an asymptotic result thus is omitted in the table. Explanation on the upper footmarks: $1:$ (LS) indicates that the objectives are standard $L$-smooth while (GS) the objectives are generalized $\ell$-smooth as defined in Definition 1; $2:$ (OD) denotes the assumption of optimal direction in each iteration, (C) denotes the convex loss function assumption, (BC) denotes a lower bound on multi-task curvature, which is defined as $H(f,x,x^{\prime})=\int_{0}^{1}\nabla f(x)^{\top}\nabla^{2}f(x+a(x-x^{\prime})) \nabla f(x)da$ for a function $f$, (BF) denotes the bounded function value assumption and (BG) denotes the bounded gradient assumption.**
| Method | Smoothness (^1^1footnotemark: 1) | Assumption(^2^2footnotemark: 2) | Setting |
| --- | --- | --- | --- |
| CAGrad [] | (LS) | (OD) | Deterministic |
| PCGrad [] | (LS) | (C) or (BC) | Deterministic |
| SMG [] | (LS) | (BG) | Stochastic |
| CR-MOGM [] | (LS) | (BF) and (BG) | Stochastic |
| MoCo [] | (LS) | (BF) and (BG) | Stochastic |
| MoDo [] | (LS) | (BG) | Stochastic |
| SDMGrad [] | (LS) | (BG) | Stochastic |
| MGDA (Them. 1 and 3 ) | (GS) | N/A | Deterministic |
| Stochastic MGDA (Them. 2 and 6) | (GS) | N/A | Stochastic |

Generalized smoothness.
The generalized $(L_{0},L_{1})$-smoothness was firstly proposed by [], which was observed from extensive empirical experiments in training neural networks. A clipping algorithm was developed by [] and the convergence rate was provided. Later, [] analyzed the convergence of a normalized momentum method. The SPIDER algorithm was also applied to solve generalized smooth problems in [, ], where [] studied a new notion of $\alpha$-symmetric generalized smoothness, which includes $(L_{0},L_{1})$-smoothness as a special case. Very recently, a new generalized $\ell$-smoothness condition was studied in [, ], which is the weakest smoothness condition and includes all the smoothness conditions discussed above. However, all the existing works on generalized smoothness are limited to single-task optimizations and the understanding of MOO is insufficient. This paper provides the first study of MOO under the generalized $\ell$-smoothness condition.

## 2 Preliminaries

### 2.1 Generalized smoothness

The standard $L$-smoothness condition is widely investigated in existing optimization studies [, ], which assumes a function $f:\mathcal{X}\to\mathbb{R}$ to be $L$-smooth if there exists a bounded constant $L$ such that for any $x,y\in\mathcal{X}$,
$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|.$
Nevertheless, recent studies show that in the training of neural networks such as LSTM models [], transformers [], distributionally robust optimization [] and high-order polynomials functions [], the standard $L$-smoothness assumption does not hold. Instead, a generalized $(L_{0},L_{1})$-smoothness assumption was observed and studied in the training of LSTM models in [], which assumes that for any $x\in\mathcal{X}$,
$\|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|.$
This assumption implies the Lipschitz constant is potentially unbounded and reduces to the $L$-smoothness if $L_{1}=0$. Later, a more generalized assumption was proposed and studied in []:

###### Definition 1 .

(Generalized $\ell$-smoothness, Definition 1 in []). A real-valued differentiable function $f:\mathcal{X}\rightarrow\mathbb{R}$ is generalized $\ell$-smooth if $\|\nabla^{2}f(x)\|\leq\ell(\|\nabla f(x)\|)$ almost everywhere in $\mathcal{X}$, where $\ell:[0,+\infty)\rightarrow(0,+\infty)$ is a continuous non-decreasing function.

The $(L_{0},L_{1})$-smoothness is a special case of generalized $\ell$-smoothness, where $\ell(a)=L_{0}+L_{1}a$.
There is another definition of generalized smooth, which is widely used and is equivalent to the $\ell$-smoothness:

###### Definition 2 .

(($r,\ell$)-smoothness, Definition 2 in []). A real-valued differentiable function $f:\mathcal{X}\rightarrow\mathbb{R}$ is $(r,\ell)$-smooth
if 1) for any $x\in\mathcal{X},B(x,r(\|\nabla f(x)\|))\in\mathcal{X}$, and 2) for any $x_{1},x_{2}\in B(x,r(\|\nabla f(x)\|)),\|\nabla f(x_{1})-\nabla f(x_{2})\|\leq
\ell(\|\nabla f(x)\|)\|x_{1}-x_{2}\|$, where for continuous functions $r,\ell:[0,+\infty)\rightarrow(0,+\infty)$, $r$ is non-increasing, $\ell$ is non-decreasing and $B(x,R)$ is the Euclidean ball centered at $x$ with radius $R$.

In $B(x,r(\|\nabla f(x)\|))$, the function $f$ is also $L$-smooth where $L=\ell(\|\nabla f(x)\|)$. Proposition 3.2 in [] shows that Definition 1 and Definition 2 are equivalent:
An $(r,\ell)$-smooth function is $\ell$-smooth; and a generalized $\ell$-smooth function satisfying Assumption 1
is $(r,m)$-smooth where $m(u):=\ell(u+a)$ and $r(u):=a/m(u)$ for any $a>0$.

###### Definition 1 .

###### Definition 2 .

### 2.2 Pareto concepts in multi-objective optimization (MOO)

As described before, MOO aims to find points at which there is no common descent direction for all objectives. Considering two points $x_{1},x_{2}\in\mathbb{R}^{m}$, we claim that $x_{1}$ dominates $x_{2}$ if $f_{i}(x_{1})\geq f_{i}(x_{2})$ for all $i\in[K]$ and $F(x_{1})\neq F(x_{2})$. We say a point is Pareto optimal if it is not dominated by any other point. In other words, we cannot improve one objective without compromising another when we reach a Pareto optimal point. In the general non-convex setting, MOO aims to find a Pareto stationary point defined as follows.

###### Definition 3 .

We say $x\in\mathbb{R}^{m}$ is a Pareto stationary point if $\min_{w\in\mathcal{W}}\|\nabla F(x)w\|^{2}=0$. In practice, we call $x$ an $\epsilon$-accurate Pareto stationary point if $\min_{w\in\mathcal{W}}\|\nabla F(x)w\|^{2}\leq\epsilon^{2}$.

###### Definition 3 .

### 2.3 Existing MOO Algorithms

Deterministic MOO. One of the big challenges of MOO is the gradient conflict, i.e., the gradients of different objectives may vary heavily in scale such that the largest gradient dominates the update direction. As a result, the performance of those objectives with smaller gradients [] may be significantly compromised. As the most fundamental MOO algorithm, MGDA tends to find a balanced update direction for all objectives by considering the minimum improvement across all objectives and maximize it by solving the following problem

$$ $\displaystyle\max_{d\in\mathbb{R}^{m}}\min_{i\in[K]}\Big{\{}\frac{1}{\alpha}(f _{i}(x)-f_{i}(x-\alpha d))\Big{\}}\approx\max_{d\in\mathbb{R}^{m}}\min_{i\in[K ]}\langle\nabla f_{i}(x),d\rangle,$ (2) $$

where $\alpha$ is the step size, $d$ is the update direction, and the first-order Taylor approximation is applied at $x$. To efficiently solve the above problem in eq. 2, we substitute the following relation

$$ $\displaystyle\max_{d\in\mathbb{R}^{m}}\min_{i\in[K]}\langle\nabla f_{i}(x),d \rangle-\frac{1}{2}\|d\|^{2}=\max_{d\in\mathbb{R}^{m}}\min_{w\in\mathcal{W}} \Big{\langle}\sum_{k=1}^{K}\nabla f_{i}(x)w_{i},d\Big{\rangle}-\frac{1}{2}\|d \|^{2},$ (3) $$

where $\mathcal{W}$ is the probability simplex over $[K]$, and the regularization term $-\frac{1}{2}\|d\|^{2}$ is to regulate the magnitude of our update direction. The solution to the problem in eq. 3 can be obtained by solving the following problem []:

$$ $\displaystyle d^{*}=\nabla F(x)w^{*};\;\;s.t.\;w^{*}\in\arg\min_{w\in\mathcal{ W}}\frac{1}{2}\|\nabla F(x)w\|^{2}.$ (4) $$

The above approach has been widely used in various variants of MGDA such as SDMGrad, CAGrad, and PCGrad [, , ].

Stochastic MOO. SMG [] is the first stochastic MGDA. It directly replaces the gradients with stochastic gradients and the update rule becomes

$$ $\displaystyle d_{s}^{*}=\nabla F(x;s)w_{s}^{*};\;\;s.t.\;w_{s}^{*}\in\arg\min_ {w\in\mathcal{W}}\frac{1}{2}\|\nabla F(x;s)w\|^{2},$ $$

where $\nabla F(x;s)$ is the estimate of $\nabla F(x)$ based on the sample $s$.
However, this leads to a biased gradient estimation of the update direction $d_{s}^{*}$, and thus it requires an increasing batch size. To solve this issue, another work MoCo [] introduces a tracking variable $Y$ as a stochastic estimation of the true gradient. Afterward, a double-sampling strategy is proposed by [, ] to generate a near-unbiased update direction.

Strong assumptions in analysis. All the works mentioned above require bounded gradients such as [, , ] or $L$-smoothness such as [, , , ]. Their analyses do not apply to generalized $\ell$-smoothness objectives, since the Lipschitz constant is potentially infinity.

### 2.4 Conflict-avoidant (CA) direction and CA distance

We call the update direction $d^{*}$ in eq. 4 the conflict-avoidant (CA) direction since it mitigates gradient conflict. Though it may not be feasible to calculate the exact CA direction, we aim to find an update direction to be close to the CA direction. Therefore, measuring the gap between the CA direction and the estimated update direction is important, which we define as the CA distance.

###### Definition 4 .

$\|d-d^{*}\|$ is the CA distance between estimated update direction $d$ and CA direction $d^{*}$.

The larger the CA distance is, the further the estimated update direction will be away from the CA direction, and the more conflict there will be. In single-loop algorithms, MoCo and MoDo [, ], the average CA distance over iteration is of the order of $\epsilon$ while the double-loop algorithm SDMGrad [] guarantees an $\epsilon$-order CA distance in every iteration. In this work, we analyze the CA distance in both cases and provide convergence results.

###### Definition 4 .

## 3 MGDA Algorithms under Generalized Smoothness

### 3.1 MGDA with and without Warm Start

It has been shown in eq. 4 that MGDA needs to approximate the optimal weight $w^{*}$ and the optimal updating direction $d^{*}$.
However, since the optimal weight $w^{*}$ of the convex function is not unique, we deal with this issue by adding an $\ell_{2}$ regularization term and the problem becomes

$$ $\displaystyle w_{\rho}^{*}=\arg\min_{w\in\mathcal{W}}\frac{1}{2}\|\nabla F(x)w \|^{2}+\frac{\rho}{2}\|w\|^{2}.$ (5) $$

Besides the benefit of a unique solution, adding an $\ell_{2}$ regularization term also makes $w_{\rho}^{*}(x)$ Lipschitz continuous []. Note that $w^{*}(x)$ may not be Lipschitz continuous because $\nabla F(x)^{\top}\nabla F(x)$ may not be positive definite. Nevertheless, the analysis of CA distance is difficult because $w^{*}$ may not be Lipschitz continuous. Thus, we will characterize the gap between $w^{*}$ and $w_{\rho}^{*}$ plus the change of $w_{\rho}^{*}$ after adding this $\ell_{2}$ regularization term. As a result, the update rules become Lines 5-6 in Algorithm 1. We first update $w_{t}$ by a projected gradient descent process and compute the update direction $d_{t}=\nabla F(x_{t})w_{t}$ to update model parameters.

For our single-loop algorithm, CA distance is proportional to the term $\|w_{t}-w_{t,\rho}^{*}\|$, which decreases as the algorithm iterates with some error terms controlled by appropriately chosen small step sizes. If we initialize $w_{0}$ randomly, $\|w_{0}-w_{0,\rho}^{*}\|$ will be a constant order, and so will the first CA distance. Meanwhile, we can only get an $\epsilon$-order CA distance after a certain iteration number $t^{\prime}>1$ when $\|w_{t^{\prime}}-w_{t^{\prime},\rho}^{*}\|$ takes an $\epsilon$ order. Thus, we introduce an extra warm start process using Algorithm 2 to guarantee the new $w_{0}$ is close enough to $w_{0,\rho}^{*}$ and a small level CA distance in every iteration. However, this warm start process is not needed if we only require a small averaged CA distance.

Figure: Algorithm 1 Single loop MGDA with and without warm start

Figure: Algorithm 2 warm-start($w_{0}$, $x_{0}$, $\rho$)

### 3.2 Stochastic MGDA with Double Sampling

In the stochastic setting, our algorithm keeps the same structure, having a warm start process if we aim to control the CA distance in every iteration. In Algorithm 2, we do the same projected gradient descent without using stochastic gradients. This is because we only need to
compute $\nabla F(x_{0})^{\top}\nabla F(x_{0})$ once and reuse it in the whole loop, which does not bring a computational burden. Then in the update loop, we update the weight and model parameters accordingly. We use a double-sampling strategy here to make the weight gradient estimator unbiased [] such that $d_{t}$ is a near-unbiased multi-gradient
$\mathbb{E}[\nabla G_{2}(x_{t})^{\top}\nabla G_{3}(x_{t})w_{t}+\rho w_{t}]=
\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}+\rho w_{t},$
where $\nabla G_{2}(x_{t})$ and $\nabla G_{3}(x_{t})$ are independent and unbiased estimates of $\nabla F(x_{t})$.
Similarly, we do not involve a warm start process if we require the average CA distance to be small.

Figure: Algorithm 3 Stochastic MGDA with Double Sampling

### 3.3 MGDA with Fast Approximation

It can be seen from Algorithm 1 and Algorithm 3 that MGDA requires $\mathcal{O}(K)$ space and time to compute and store all task gradients at each iteration for updating the weight $w_{t}$. This becomes a drawback when the number of tasks or the model size is large. Motivated by [], one solution is to use the Taylor Theorem to approximate the gradient for updating the weight $w_{t}$ as

$$ $\displaystyle{F}(x_{t})-{F}(x_{t+1})=\nabla F(x_{t})^{\top}(x_{t}-x_{t+1})-R(x _{t})=\alpha\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}-R(x_{t}),$ $$

where $R(x_{t})$ is the remainder term and it takes the order $R(x_{t})=o(\|x_{t}-x_{t+1}\|^{2})$, which can be made sufficiently small by adjusting the step size. By incorporating this fast approximation (FA) in Algorithm 1, we then present MGDA-FA in Algorithm 4 (shown in Appendix B), where $x_{t}$ is updated along the update direction $d_{t}=\nabla F(x_{t})w_{t}$ to get $x_{t+1}$ following by the update rule of $w_{t}$

$$ $\displaystyle w_{t+1}=\Pi_{\mathcal{W}}\Big{(}w_{t}-\beta\Big{[}\frac{F(x_{t}) -F(x_{t+1})}{\alpha}+\rho w_{t}\Big{]}\Big{)}.$ (6) $$

As a result, in the model parameters update process, MGDA-FA only requires one backward process by calculating the gradient of $F(x_{t})w_{t}$ w.r.t. $x_{t}$ without storing it, and additional forward processes to compute $F(x_{t+1})$ in the weight update process. This approach saves computational and memory costs in the practical implementation significantly. Most importantly, we provide a theoretical guarantee for this efficient method (in eq. 6).

## 4 Convergence Analysis under Average CA distance

In this section, we provide the theoretical results for Algorithms 1 and 3 without warm starts to obtain an $\epsilon$-accurate Pareto stationary point, with the average CA distance over iterations in $\mathcal{O}(\epsilon)$.

### 4.1 Deterministic setting

###### Assumption 1 .

Each objective function $f_{i}$ $\forall i\in[K]$ is twice differentiable and lower bounded by $f_{i}^{*}:=\inf_{x\in\mathbb{R}^{m}}f_{i}(x)>-\infty$.

###### Assumption 2 .

Each objective function $f_{i}$ $\forall i\in[K]$ is generalized $\ell$-smooth defined in Definition 1, where $\ell:[0,+\infty)\rightarrow(0,+\infty)$ is a continuous non-decreasing function such that $\varphi(a)=\frac{a^{2}}{2\ell(2a)}$ is monotonically increasing for any $a\geq 0$.

These assumptions are the most relaxed ones in existing MOO works since they directly assume objective smoothness or gradient/function value boundness [, , , , , , ]. It also includes the widely studied standard $L$-smoothness [, , ], $(L_{0},L_{1})$-smoothness [] as special cases. Moreover, for any $0\leq\gamma\leq 2$ and $x\in\mathcal{X}$, our assumption even holds for function $f$ such that $\|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|^{\gamma}$, where $\gamma$ are limited to $[0,1]$ in [].

We then provide our theoretical results. Let $c>0$ and $F>0$ be some constants such that
$\Delta+c\leq F,$
where $\Delta=\max_{i\in[K]}\{f_{i}(x_{0})-f^{*}\}$.
Define $M=\sup\{z\geq 0|\varphi(z)\leq F\}$. We then have the following convergence rate for Algorithm 1:

###### Theorem 1 .

Let Assumptions 1 and 2 hold. Set $\beta\leq\mathcal{O}(\frac{1}{M^{2}}),\alpha\leq\mathcal{O}(\frac{1}{M^{2}}+
\frac{1}{M\ell(M+1)}),T\geq\max\Big{(}\Theta\big{(}\frac{1}{\alpha\epsilon^{2}
}\big{)},\Theta\left(\frac{1}{\beta\epsilon^{2}}\right)\Big{)}$ and $\rho=\mathcal{O}(\epsilon^{2})$. We then have that
$\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq\epsilon^{2}.$

The full version with detailed constants and detailed proof can be found in Appendix C.1. Theorem 1 provides the first convergence rate to obtain an $\epsilon$-accurate Pareto stationary point for MOO problems with generalized $\ell$-smooth objectives. Moreover, it achieves the optimal sample complexity in the order of $\mathcal{O}(\epsilon^{-2})$for GD with a single standard $L$-smooth objective []. The MOO problems with generalized $\ell$-smooth objectives are challenging due to two reasons: 1) $\|\nabla F(x)\|$ is potentially unbounded in our generalized $\ell$-smoothness setting, making all existing analysis in MOO [, , , , , , ] not applicable. 2) the update of $x$ includes all gradient information from each task, making the existing adaptive methods for single generalized smooth functions invalid.

To solve the challenges in Theorem 1, we find that a bounded function value implies a bounded gradient norm. Thus in our proof, we use induction to show that with parameters selected in Theorem 1, for any $w\in\mathcal{W}$ and $t\leq T$, we have that $F(x_{t})w$ is upper bounded by $F$. Consequently, for any $i\in[K]$, we have that $\|\nabla f_{i}(x)\|\leq M$, which solves the unbounded gradient norm problem in our generalized smoothness setting. Then we can show that $\|\nabla F(x_{t})w_{t}\|$ converges.

###### Corollary 1 .

Under the same setting in Theorem 1, $\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|^{
2}\leq\mathcal{O}(\epsilon^{2})$.

The proof is available in Appendix C.2. Corollary 1 shows that the average CA distance converges.

###### Assumption 1 .

###### Assumption 2 .

###### Theorem 1 .

###### Corollary 1 .

### 4.2 Stochastic setting

In the stochastic setting, we assume that we have access to an unbiased stochastic gradient ${\nabla}f_{i}(x;s)$ instead of the true gradient $\nabla f_{i}(x)$, where $s$ is the collected samples. To prove convergence, we have the following assumption.

###### Assumption 3 .

There exists some $\sigma\geq 0$ such that $\mathbb{E}[\|{\nabla}f_{i}(x;s)-\nabla f_{i}(x)\|^{2}]\leq\sigma^{2}$ for any $i\in[K]$.

Assumption 3 indicates bounded gradient variances, which is widely studied [, , ].

Let $s_{t,i}=(s_{t,i,1},s_{t,i,2},...,s_{t,i,k})$ be the $i$-th collection of samples at time $t$ in the stochastic model and $F(x_{t};s_{t,i})=(f_{1}(x_{t};s_{t,i,1}),f_{2}(x_{t};s_{t,i,2}),...,f_{k}(x_{t
};s_{t,i,k})).$
In this section, we choose
$G_{i}(x_{t})=F(x_{t};s_{t,i})$
for any $i\in[3]$. Define $\varepsilon_{t,i}=(\varepsilon_{t,i,1},\varepsilon_{t,i,2},...,\varepsilon_{t,
i,k})=\nabla F(x_{t})-\nabla G_{i}(x_{t})$.

Let $F,c>0$ and $0<\delta\leq\frac{1}{2}$ be some constants such that $F\geq\frac{4(\Delta+c)}{\delta}$ and $M=\sup\{z\geq 0|\varphi(z)\leq F\}$. Define the following random variables $\tau_{1}=\min\{t|\exists i\in[K],f_{i}(x_{t+1})-f_{i}^{*}>F\}\wedge T,\tau_{2}
=\min\{t|\exists i\in[K],j\in[3],\|\varepsilon_{t,j,i}\|>\frac{L_{0}}{\sqrt{
\alpha\rho}}\}\wedge T,\tau_{3}=\min\{t|\exists i,j\in[K],\|\varepsilon_{t,2,i
}\|\|\varepsilon_{t,3,j}\|>\frac{L_{1}}{\sqrt{\alpha\rho}}\}\wedge T$ and $\tau=\min\{\tau_{1},\tau_{2},\tau_{3}\}$,
where $L_{0},L_{1}>0$ are some constants and $a\wedge b$ denotes $\min(a,b)$.
We have the following theorem for Algorithm 3::

###### Theorem 2 .

Let Assumptions 1, 2, 3 hold. Set $\alpha\leq\min\{\mathcal{O}(\ell(M+1)),\mathcal{O}(\beta),\mathcal{O}(\rho),
\mathcal{O}\left(\frac{1}{\sqrt{T}}\right),\mathcal{O}(\epsilon^{2})\}$, $\beta\leq\min\{\mathcal{O}\left(\frac{1}{\alpha{T}}\right),\mathcal{O}(
\epsilon^{2}),\mathcal{O}(\rho)\}$, $\rho=\min\{\mathcal{O}\left(\frac{1}{\alpha T}\right),\mathcal{O}(\frac{1}{
\sqrt{\alpha T}}),\mathcal{O}\left(\frac{\epsilon}{\sqrt{\beta}}\right),
\mathcal{O}(\epsilon^{2})\}$ and $T\geq\Theta\left(\frac{1}{\alpha\epsilon^{2}}+\frac{1}{\epsilon^{4}}\right)$. We then have that
$\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq\epsilon^{2},$
with the probability at least $1-\delta$.

The full version and detailed proof can be found in Appendix C.3. When we set $\alpha,\beta,\rho=\mathcal{O}(\epsilon^{2})$ and $T\geq\mathcal{O}(\epsilon^{-4})$, we can find an $\epsilon$-stationary point with the optimal sample complexity in the order of $\mathcal{O}(\epsilon^{-4})$ for SGD with a single $L$-smooth objective []. Note that in the proof of Theorem 1, we show for each $t\leq T$ and $w\in W$, we have that $F(x_{t})w$ is bounded by applying a small constant step size $\alpha$ and $\beta$. However, this condition does not necessarily hold for our stochastic setting due to the unbounded gradient noise. To solve this problem, we introduce stopping time $\tau$. The advantages are as follows: 1) for any $t\leq\tau$, $w\in W$, we have that $F(x_{t})w$ is bounded; 2) for any $t<\tau$, the norm of gradient noise is bounded; 3) due to the optimal stopping theorem, for any $w\in W$ and $i\in[3]$, we have that $\mathbb{E}[\sum_{t=0}^{\tau}\varepsilon_{t,i}w]=0$. Based on these properties, we can further get the following lemma:

###### Lemma 1 .

Using the parameters selected in Theorem 2, we have that

$$ $\displaystyle\mathbb{E}[F(x_{\tau})w]-F^{*}w\leq\frac{\delta F}{8}-\frac{ \alpha}{2}\mathbb{E}\left[\sum_{t=0}^{\tau-1}\|\nabla F(x_{t})w_{t}\|^{2} \right].$ (7) $$

The proof of Lemma 1 is available in C.4. Lemma 1 indicates that $\frac{\alpha}{2}\mathbb{E}\left[\sum_{t=0}^{\tau-1}\|\nabla F(x_{t})w_{t}\|^{2
}\right]$ is bounded by some constant and if $\tau=T$ with high probability, we have that $\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\Big{|}
\tau=T\right]\leq\mathcal{O}\left(\frac{1}{\alpha T}\right)$. Note that
$\{\tau<T\}=\{\tau_{2}<T\}\cup\{\tau_{3}<T\}\cup\{\tau_{1}<T,\tau_{2}=T,\tau_{3
}=T\}.$
The first two events are related to the gradient noise, where the probabilities can be bounded by Assumption 3 and Chebyshev’s inequality. The last event indicates that for some $i\in[K]$, we have
$f_{i}(x_{\tau})-f_{i}^{*}\leq\frac{F}{2}.$
Based on Lemma 1 and Markov inequality, we can show that $\mathbb{P}(\{\tau_{1}<T,\tau_{2}=T,\tau_{3}=T\})\leq\frac{\delta}{4}$ and we can further show that $\mathbb{P}(\tau=T)\geq 1-\frac{\delta}{2}$. We then have that $\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}$ converges with high probability. Similar to Corollary 1, Theorem 2 also implies the average of CA distances converges with time with high probability.

###### Assumption 3 .

###### Theorem 2 .

###### Lemma 1 .

## 5 Convergence Analysis under Iteration-wise CA distance

In Section 4 we show that the average CA distance is bounded under generalized smooth conditions. The average CA distance is also studied in MoCo [] and MoDo [] with the bounded gradient assumption and these works only focus on guarantees of the average CA distance over iterations. However, a $\epsilon$-level average CA distance only implies the smallest CA distance to be $\epsilon$-level. Since we want to keep the update direction close enough to the CA direction, it is better to have a tighter bound of CA distances. In this section, we show the iterative CA distance is $\mathcal{O}(\epsilon)$ with a warm-start process and convergence results for Algorithms 1, 3, and 4.

### 5.1 Deterministic setting

Deterministic setting without fast approximation.
We first provide results about bounded iteration-wise CA distance for Algorithm 1 with a warm start.

###### Theorem 3 .

Let Assumptions 1 and 2 hold. Set $\beta^{\prime}\leq\frac{1}{M^{2}},\rho=\mathcal{O}(\epsilon^{2}),\beta\leq
\mathcal{O}(\epsilon^{4}),\alpha\leq\mathcal{O}(\epsilon^{9})$, $N\geq O(\epsilon^{-2})$ as constants, and $T\geq\Theta(\epsilon^{-11})$. All the parameters satisfy the requirements in the formal version of Theorem 1 and we have
$\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|\leq\mathcal{O}(\epsilon).$

The finite time error bound and the full proof can be found in Appendix D.1. Since our parameters satisfy the requirements in the formal version of Theorem 1, we can find an $\epsilon$-accurate Pareto stationary point with $\mathcal{O}(\epsilon^{-11})$ samples. In the analysis of CA distance, we show that the CA distance can be bounded by the term $\|w_{t}-w_{t,\rho}^{*}\|$ plus the strongly-convex constant $\rho$. Meanwhile, there is a decay relation between $\|w_{t+1}-w_{t+1,\rho}^{*}\|$ and $\|w_{t}-w_{t,\rho}^{*}\|$ with some error terms controlled by step sizes. Nevertheless, the error terms will accumulate since we do telescoping on this decay relation, which will be the dominating term. Thus, step sizes have to be much smaller than the choices in Theorem 1 to guarantee iteration-wise small CA distance.

Deterministic setting with fast approximation.
In this section, we show the convergence rate of Algorithm 4 and bounded iteration-wise CA distance.

###### Theorem 4 .

Let Assumptions 1 and 2 hold. Set $N\geq O(\epsilon^{-2})$, $\beta^{\prime}\leq\frac{1}{M^{2}},\rho=\min\left(\mathcal{O}(\epsilon^{2}),
\mathcal{O}\left(\frac{1}{\alpha T}\right)\right),\beta\leq\mathcal{O}(
\epsilon^{2}),\alpha\leq\min\left(\mathcal{O}(\beta),\mathcal{O}(\epsilon^{2})
,\mathcal{O}\left(\frac{1}{\beta T}\right)\right)$ as constants, $T\geq\max\left(\Theta\left(\frac{1}{\alpha\epsilon^{2}}\right),\Theta\left(
\frac{1}{\beta\epsilon^{2}}\right)\right)$. We have
$\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq\epsilon^{2}.$

The full version with detailed constants and proof can be found in the Section D.2. We can easily extend the analysis in Section C.1 to the convergence analysis of Algorithm 4 under the average CA distance, because the only extra effort is dealing with the remainder term, which can be simply bounded by the smallest step size. As a result, the sample complexity remains the same $\mathcal{O}(\epsilon^{-11})$ to achieve a Pareto stationary point.

###### Theorem 5 .

Let Assumptions 1 and 2 hold. We choose $\beta^{\prime}\leq\frac{1}{M^{2}},\rho=\mathcal{O}(\epsilon^{2}),\beta\leq
\mathcal{O}(\epsilon^{4}),\alpha\leq\mathcal{O}(\epsilon^{9})$, $N\sim O(\epsilon^{-2})$ as constants, and $T\geq\Theta(\epsilon^{-11})$. We have that
$\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|\leq\mathcal{O}(\epsilon).$

###### Theorem 3 .

###### Theorem 4 .

###### Theorem 5 .

### 5.2 Stochastic setting

In this section, we show that Algorithm 3 with a warm start and mini-batches achieves a bounded iteration-wise CA distance with high probability. In this section, we choose
$G_{i}(x_{t})=\frac{1}{n_{s}}\sum_{i=n_{s}i-n_{s}+1}^{n_{s}i}F(x_{t};s_{t,i}),$
where $n_{s}$ is the size of the mini-batch.

###### Theorem 6 .

Let Assumptions 1, 2 and 3 hold. Set $\beta^{\prime}\leq\frac{1}{M^{2}}$, $\alpha\leq\mathcal{O}(\epsilon^{9})$, $\beta\leq\mathcal{O}(\epsilon^{4})$, $\rho=\mathcal{O}(\epsilon^{2})$,
$n_{s}\geq\mathcal{O}(\epsilon^{-6}),N\geq\mathcal{O}(\epsilon^{-2}),$ and $T\geq\Theta(\epsilon^{-11})$, and all the parameters satisfy the requirements in Theorem 2. We then have
$\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|\leq\mathcal{O}(\epsilon),$
with the probability at least $1-\delta$.

The full version with detailed constants and proof can be found in Appendix D.4. Since our parameters satisfy all requirements in Theorem 2, we can find an $\epsilon$-accurate Pareto stationary point with high probability.
Compared with Theorem 2, to guarantee an iteration-wise CA distance, despite our warm start process, a mini-batch method is required in our analysis. This is because given $\tau=T$, the gradient is not unbiased. In Theorem 2, the optimal stopping theorem is applied which indicates that the expectation of the cumulative gradient is zero. However, for each iteration, this optimal stopping theorem does not hold and the estimated error is controlled by the size of the mini-batch. Then, the sample complexity to get a Pareto stationary point becomes $\mathcal{O}(\epsilon^{-17})$ due to necessary mini-batch $n_{s}$.

Table: Table 2: Multi-task supervised learning on NYU-v2 dataset for different MOO methods comparison.

###### Theorem 6 .

## 6 Experiments

In this experiment, we evaluate the performance of the Cityscapes[] and NYU-v2 [] datasets. The former involves 2 pixel-wise tasks: 7-class semantic segmentation (Task 1) and depth estimation (Task 2) while the latter involves 3 pixel-wise tasks: 13-class
semantic segmentation, depth estimation and surface normal estimation. Following the same experiment setup of [], we build a SegNet [] as the model. We compare the performance of MGDA with a warm start, which is used to ensure a small CA distance per iteration and mitigate gradient conflicts, against
popular MGDA-type methods including MGDA [], PCGrad [], GradDrop [], CAGrad [], MoCo [], MoDo [], Nash-MTL [], and FAMO []. Since SDMGrad [] incorporates a preference-based regularization within the MGDA framework, we exclude it from the tables to ensure a fair comparison. We utilize the metric $\mathbf{\Delta m\%}$ to reflect the overall performance, which considers the average per-task performance drop versus the single-task (STL) baseline to assess methods. It can be observed in Table 2 and Figure 2 that MGDA-warm start has a much more balanced performance. Meanwhile, the proposed MGDA-FA is much faster as shown in Figure 4 in the Appendix.

We also illustrate the relationship between the gradient norm and the local smoothness for each task of the Cityscapes dataset. To do this, we compute them according to the method provided in Section H.3 in []. We scatter the local smoothness constant against gradient norms in Figure 1 for the semantic segmentation task and depth estimation task in Figure 3 (in the appendix), respectively. Both results demonstrate a positive correlation between them, which further substantiates the necessity of our analysis. More experimental details can be found in Appendix A.

Figure: Figure 2: Multi-task learning on Cityscapes dataset.

## 7 Conclusion

Building upon our observations of MGDA convergence under the $(L_{0},L_{1})$ smoothness condition, this paper provides a rigorous convergence analysis for both the fundamental MGDA and its stochastic variant under a more challenging, relaxed, and practical generalized
$\ell$-smoothness assumption. Furthermore, we introduce a warm start progress to provide a more precise control over the iteration-wise CA distance. Our analysis also shows that an efficient variant named MGDA-FA, which uses only $\mathcal{O}(1)$ time and space, achieves the same performance guarantee as MGDA. We anticipate that the convergence analysis developed in this work will provide valuable insights for analyzing other MOO algorithms such as CAGrad, PCGrad, FairGrad and FAMO under the generalized smoothness condition. The warm-start strategy may be of independent interest to other single-loop MOO algorithms to achieve a sufficiently small iteration-wise CA distance.

## Appendix A Experimental details

### A.1 Relation between gradient norms and the local smoothness

We show the relation between local smoothness and gradient norms of each task in this part. Both results demonstrate a positive correlation between them, which further substantiates the necessity of our analysis.

Figure: Figure 3: Local smoothness constant vs. Gradient norm on training SegNet on CityScapes dataset of each task. Task 1 on the left and Task 2 on the right.
Refer to caption: extracted/5896848/scatter_plot_GS_task1.png

### A.2 Results and running time comparison between MGDA-warm start and MGDA-FA

We compare the results and average running time of the proposed algorithms, MGDA-warm start and MGDA-FA of the Cityscapes []. The time in Figure 4 is an average of the total running time over epochs (in minutes). The result solidifies the advantage of the fast approximation.

Figure: Figure 4: Multi-task learning on Cityscapes dataset.

### A.3 Implementation details

Multi-task learning on Cityscapes dataset. Following the experiment setup in [], we train
our method for 200 epochs, using SGD optimizers for both model parameters and weights, and the batch size for Cityscapes is 8. We
compute the averaged test performance over the last 10 epochs as the final performance measure. We fix the $\beta=0.5$ and do a grid search on hyperparameters including $N\in[10,20,40,50],\alpha\in[0.0001,0.0002,0.0005,0.001]$, and $\rho\in[0.01,0.05,0.1,0.2,0.5,0.6,0.7,0.8,0.9,1]$ and choose the best result from them. It turns out our best performance is based on the choice that $N=40,\alpha=0.0005,\beta=0.5$, and $\rho=0.5$. The choice of hyperparameters for MGDA-FA turns out to be the same as that for MGDA-warm start. All experiments are run on NVIDIA RTX A6000.

$\Delta m\%$ reflects the average per-task performance drop versus the single-task (STL) baseline $b$ to assess method $m$. We calculate it by the following equation

$$ $\Delta m\%=\frac{1}{K}\sum_{k=1}^{K}(-1)^{l_{k}}(M_{m,k}-M_{b,k})/M_{b,k} \times 100,$ $$

where $K$ is the number of metrics, $M_{b,k}$ is the value of metric $M_{k}$ obtained by baseline $b$, and $M_{m,k}$ obtained by the compared method $m$. $l_{k}=1$ if the evaluation metric $M_{k}$ on task $k$ prefers a higher value and 0 0 otherwise.

Generalized smoothness illustration. To illustrate the relation between gradient norms and local smoothness, we run SGD on each task separately without the warm start process. Since there is no weight update process, we only need to choose $\alpha=0.0005$ for both tasks.

## Appendix B Algorithm

Figure: Algorithm 4 MGDA with Fast Approximation (MGDA-FA)

## Appendix C Detailed Proofs for Average CA Distance

### C.1 Formal version and proof of Theorem 1

Let $c_{1}>0,c_{2}>0$, $c_{3}\geq 0$ and $F>0$ be some constants such that

$$ $\displaystyle\Delta+c_{1}+{c_{2}}+c_{3}\leq F.$ (8) $$

Define $M=\sup\{z\geq 0|\varphi(z)\leq F\}$. We then have the following convergence rate for Algorithm 1 without warm start:

###### Theorem 7 .

Suppose Assumptions 1 and 2 are satisfied, and we choose constant step sizes that $\beta\leq\frac{1}{4KM^{2}},\alpha\leq\min\left(c_{1}\beta,\frac{1}{2\ell(M+1)}
,\frac{1}{M\ell(M+1)}\right),T\geq\max\left(\frac{10\Delta}{\alpha\epsilon^{2}
},\frac{10}{\epsilon^{2}\beta}\right)\sim\Theta(\epsilon^{-2})$, and $\rho\leq\min\left(\frac{\epsilon^{2}}{20},\sqrt{\frac{\epsilon^{2}}{10\beta}},
\frac{c_{2}}{2T\alpha},\sqrt{\frac{c_{3}}{T\alpha\beta}}\right)\sim\mathcal{O}
(\epsilon^{2})$. We have that

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq \epsilon^{2}.$ (9) $$

###### Proof.

Compared with the standard $L$-smoothness, the generalized smoothness is more challenging to address due to the unbounded Lipschitz constant. Lemma 2 demonstrates that a bounded function value implies a bounded gradient norm, which further implies a bounded Lipschitz constant. In the following, we solve the unbounded Lipschitz constant problem by showing that the function value is bounded with the parameters selected in Theorem 1. We prove that for any $i\in K$ and $t\leq T$ we have that $f_{i}(x_{t})-f_{i}^{*}\leq F$ by induction.

Base Case: since all $c_{1},c_{2},c_{3},M$ are non-negative, according to (8) we have that $f_{i}(x_{0})-f_{i}^{*}\leq\Delta\leq F$ holds for any $i\in[K]$.

Induction step: assume that for any $i\in[K]$ and $t\leq k<T$, we have that $f_{i}(x_{t})-f_{i}^{*}\leq F$ holds. We then prove that $f_{i}(x_{k+1})-f_{i}^{*}\leq F$ holds for any $i\in[K]$.

For $f_{i}(x_{t})-f_{i}^{*}\leq F$, based on the monotonicity shown in Lemma 2, we have that $\|\nabla f_{i}(x_{t})\|\leq M$. From assumption 2, we have that $f_{i}(x)$ is $\left(\frac{1}{\ell(\|\nabla f_{i}(x))\|+1)},\ell(\|\nabla f_{i}(x)\|+1)\right)$-smooth by setting $a=1$. For any $t\leq k$, we have that

$$ $\displaystyle\|x_{t+1}-x_{t}\|=\alpha\|\nabla F(x_{t})w_{t}\|\leq\alpha M\leq \frac{1}{\ell(M+1)}\leq\frac{1}{\ell(\|\nabla f_{i}(x_{t})\|+1)},$ $$

where the second inequality is due to $\alpha\leq\frac{1}{M\ell(M+1)}$ and the last inequality is due to $\|\nabla f_{i}(x_{t})\|\leq M$. Based on Assumption 2, Definition 2 and Lemma 3.3 in [], we have the following descent lemma:

$$ $\displaystyle f_{i}(x_{t+1})$ $\displaystyle\leq f_{i}(x_{t})-\alpha\langle\nabla f_{i}(x_{t}),\nabla F(x_{t} )w_{t}\rangle+\frac{\ell(\|\nabla f_{i}(x_{t})\|+1)}{2}\alpha^{2}\|\nabla F(x_ {t})w_{t}\|^{2}$ $\displaystyle\leq f_{i}(x_{t})-\alpha\langle\nabla f_{i}(x_{t}),\nabla F(x_{t} )w_{t}\rangle+\frac{\ell(M+1)}{2}\alpha^{2}\|\nabla F(x_{t})w_{t}\|^{2}.$ $$

As a result, for any $w\in\mathcal{W}$, we have that

$$ $\displaystyle F(x_{t+1})w\leq F(x_{t})w-\alpha\langle\nabla F(x_{t})w,\nabla F (x_{t})w_{t}\rangle+\frac{\ell(M+1)}{2}\alpha^{2}\|\nabla F(x_{t})w_{t}\|^{2}.$ (10) $$

Based on the update process of $w$, we have that

$$ $\displaystyle w_{t+1}$ $\displaystyle=\Pi_{\mathcal{W}}\Big{(}w_{t}-\beta\Big{(}\nabla F(x_{t})^{\top} \nabla F(x_{t})w_{t}+\rho w_{t}\Big{)}\Big{)}.$ $$

It then follows that

$$ $\displaystyle\|w_{t+1}-w\|^{2}$ $\displaystyle=\Big{\|}\Pi_{\mathcal{W}}\Big{(}w_{t}-\beta\Big{(}\nabla F(x_{t} )^{\top}\nabla F(x_{t})w_{t}+\rho w_{t}\Big{)}\Big{)}-w\Big{\|}^{2}$ $\displaystyle\leq\Big{\|}\Big{(}w_{t}-\beta\Big{(}\nabla F(x_{t})^{\top}\nabla F (x_{t})w_{t}+\rho w_{t}\Big{)}\Big{)}-w\Big{\|}^{2}$ $\displaystyle=\|w_{t}-w\|^{2}-2\beta\left\langle w_{t}-w,(\nabla F(x_{t})^{ \top}\nabla F(x_{t})+\rho I)w_{t}\right\rangle$ $\displaystyle+\beta^{2}\left\|(\nabla F(x_{t})^{\top}\nabla F(x_{t})+\rho I)w_ {t}\right\|^{2},$ $$

where the inequality is due to the non-expansiveness of projection.
By rearranging the above inequality, we have that

$$ $\displaystyle\langle w_{t}-w,\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}\rangle$ $\displaystyle\leq\frac{1}{2\beta}\left(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2}\right )+2\rho+\beta KM^{2}\|\nabla F(x_{t})w_{t}\|^{2}+\beta\rho^{2}.$ (11) $$

Plug (C.1) into (10), and we can show that

$$ $\displaystyle F(x_{t+1})w-F(x_{t})w$ $\displaystyle\leq-\alpha\|\nabla F(x_{t})w_{t}\|^{2}+\frac{\ell(M+1)}{2}\alpha ^{2}\|\nabla F(x_{t})w_{t}\|^{2}$ $\displaystyle+\frac{\alpha}{2\beta}\left(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2} \right)+\alpha\beta KM^{2}\|\nabla F(x_{t})w_{t}\|^{2}+\alpha\beta\rho^{2}+2 \alpha\rho.$ (12) $$

Taking sums of (C.1) from $t=0$ to $k$, for any $w\in\mathcal{W}$ we have that

$$ $\displaystyle F(x_{k+1})w-F(x_{0})w$ $\displaystyle\leq-\sum_{t=0}^{k}\alpha\|\nabla F(x_{t})w_{t}\|^{2}+\sum_{t=0}^ {k}\left(\frac{\ell(M+1)}{2}\alpha^{2}+\alpha\beta KM^{2}\right)\|\nabla F(x_{ t})w_{t}\|^{2}$ $\displaystyle+\frac{\alpha}{2\beta}\|w_{0}-w\|^{2}+T\alpha\beta\rho^{2}+2T\alpha\rho$ $\displaystyle\leq\frac{\alpha}{2\beta}\|w_{0}-w\|^{2}+T\alpha\beta\rho^{2}+2T \alpha\rho,$ (13) $$

where the first inequality is due to $k<T$ and the last inequality is due to that $\alpha\leq\frac{1}{2\ell(M+1)}$ and $\beta KM^{2}\leq{\frac{1}{4}}$.
Thus for any $i\in[K]$ it can be shown that

$$ $\displaystyle f_{i}(x_{t+1})-f_{i}^{*}\leq f_{i}(x_{0})-f_{i}^{*}+\frac{\alpha }{\beta}+T\alpha\beta\rho^{2}+2T\alpha\rho\leq F,$ $$

since we have that $\frac{\alpha}{\beta}\leq c_{1},T\alpha\beta\rho^{2}\leq c_{3}$ and $2T\alpha\rho\leq c_{2}$. Now we finish the induction step and can show that $f_{i}(x_{k+1})-f_{i}^{*}\leq F$ and (C.1) hold for all $k<T$ and $i\in[K]$.

Specifically, for $\alpha<\frac{1}{2\ell(M+1)},\beta\leq\frac{1}{4KM^{2}}$, according to (C.1), for $k=T-1$
we have that

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq\frac{ 2(F(x_{0})w-F^{*}w)}{\alpha T}+\frac{2}{\beta T}+2\beta\rho^{2}+4\rho\leq \epsilon^{2},$ $$

which completes our proof.
∎

###### Lemma 2 .

(Lemma 3.5 in []) If a function $f$ is $\ell$-smooth, we have that

$$ $\displaystyle\varphi(\|\nabla f(x)\|)=\frac{\|\nabla f(x)\|^{2}}{2\ell(2\| \nabla f(x)\|)}\leq f(x)-f^{*}.$ (14) $$

###### Theorem 7 .

###### Proof.

###### Lemma 2 .

### C.2 Proof of Corollary 1

###### Proof.

Recall that

$$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|^{2}\leq\|\nabla F (x_{t})w_{t}\|^{2}-\|\nabla F(x_{t})w_{t}^{*}\|^{2}\leq\|\nabla F(x_{t})w_{t} \|^{2},$ $$

where the first inequality follows from the optimal condition. Then we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}-\nabla F(x_{t}) w_{t}\|^{2}\leq\frac{1}{T}\sum_{t=0}^{T-1}|\|\nabla F(x_{t})w_{t}\|^{2}= \mathcal{O}(\epsilon^{2}),$ $$

where we follow the same setting in Theorem 1. The proof is complete.
∎

###### Proof.

### C.3 Formal Version and Its Proof of Theorem 2

Let $c_{1}>0,c_{2}>0,c_{3}>0,c_{4}>0,c_{5}>0,c_{6}>0$ be some constants. Let $F>0$ and $0<\delta\leq\frac{1}{2}$ be some constants such that

$$ $\displaystyle F\geq\frac{8(\Delta+c_{1}+c_{2}+c_{3}+c_{4}+c_{5}+c_{6})}{\delta},$ $$

where
$\Delta=\max_{i\in[d]}\{f_{i}(x_{0})-f^{*}\}$. Let $L_{0}>0,L_{1}>0,b_{1}>0,b_{2}>0,b_{3}>0$ be some constants.

For
$\alpha\leq\min\{\frac{\ell(M+1)}{2\max(1,M)},c_{1}\beta,\rho\min\left\{\frac{1
}{4L_{0}^{2}\ell(M+1)^{2}},\frac{b_{1}^{2}}{(3M\sqrt{K}L_{0}+M\sqrt{K}L_{1})^{
2}},\frac{b_{2}}{\ell(M+1)L_{0}^{2}}\right\},\frac{c_{2}}{\sqrt{2T}M(3\sigma+
\sigma^{2}),},\\
\frac{\sqrt{c_{3}}}{\sqrt{\ell(M+1)\sigma^{2}T}},\frac{\delta\epsilon^{2}}{48
\sigma^{2}\ell(M+1)}\}$,
$\beta\leq\min\{\frac{c_{4}}{4K\alpha T(M^{2}+\sigma^{2})^{2}},\frac{\delta
\epsilon^{2}}{192K(M^{2}+\sigma^{2})^{2}},\frac{b_{3}\rho}{8KM^{2}L_{0}^{2}+4
KL_{1}^{2}}\},\\
\rho\leq\min\{\frac{c_{5}}{\alpha T},{\frac{\sqrt{c_{6}}}{\sqrt{\alpha\beta T}
}},\frac{\delta\epsilon^{2}}{48},\sqrt{\frac{\delta\epsilon^{2}}{48\beta}},
\frac{\delta L_{0}^{2}}{24K\sigma^{2}\alpha T},\frac{\delta L_{1}^{2}}{8K^{2}
\sigma^{4}\alpha T}\}$,
and $T\geq\max\{\frac{48\Delta+48c_{1}}{\delta\alpha\epsilon^{2}},\frac{4608M^{2}(3
\sigma+\sigma^{2})^{2}}{\delta^{2}\epsilon^{4}}\}$ such that

$$ $\displaystyle b_{1}+b_{2}+c_{1}+\alpha\rho(1+\beta\rho)+4\alpha\beta KM^{4} \leq\frac{F}{2}.$ (15) $$

Define the following random variables

$$ $\displaystyle\tau_{1}=\min\{t|\exists i\in[K],f_{i}(x_{t+1})-f_{i}^{*}>F\} \wedge T,$ $\displaystyle\tau_{2}=\min\{t|\exists i\in[K],j\in[3],\|\varepsilon_{t,j,i}\|> \frac{L_{0}}{\sqrt{\alpha\rho}}\}\wedge T,$ $\displaystyle\tau_{3}=\min\{t|\exists i,j\in[K],\|\varepsilon_{t,2,i}\|\| \varepsilon_{t,3,j}\|>\frac{L_{1}}{\sqrt{\alpha\rho}}\}\wedge T,$ $\displaystyle\tau=\min\{\tau_{1},\tau_{2},\tau_{3}\}.$ $$

We then have the following theorem:

###### Theorem 8 .

If Assumptions 1, 2 and 3 hold, with the parameters selected above, we have that

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq \epsilon^{2},$ $$

with the probability at least $1-\delta$.

###### Proof.

Small probability of the event $\{\tau<T\}$.

We first show that the probability of the event $\{\tau<T\}$ is small: $\mathbb{P}(\tau<T)\leq\delta$. Note that

$$ $\displaystyle\{\tau<T\}=\{\tau_{2}<T\}\cup\{\tau_{3}<T\}\cup\{\tau_{1}<T,\tau_ {2}=T,\tau_{3}=T\}.$ $$

For any $i\in[K],j\in[3]$, we have that

$$ $\displaystyle\mathbb{P}(\|\varepsilon_{t,j,i}\|>\frac{L_{0}}{\sqrt{\alpha\rho} })=\mathbb{P}(\|\varepsilon_{t,j,i}\|^{2}>\frac{L_{0}^{2}}{{\alpha\rho}})\leq \frac{\sigma^{2}{\alpha\rho}}{L_{0}^{2}},$ $$

where the last inequality is due to Chebyshev’s inequality. Based on the union bound, we have that

$$ $\displaystyle\mathbb{P}(\{\tau_{2}<T\})\leq\sum_{t=0}^{T-1}\sum_{j=1}^{K}\sum_ {i=1}^{3}\mathbb{P}(\|\varepsilon_{t,j,i}\|>\frac{L_{0}}{\sqrt{\alpha\rho}}) \leq\frac{3K\sigma^{2}{\alpha\rho}T}{L_{0}^{2}}\leq\frac{\delta}{8}$ (16) $$

since $\rho\leq\frac{\delta L_{0}^{2}}{24K\sigma^{2}\alpha T}$.
Similarly, we have that

$$ $\displaystyle\mathbb{P}(\|\varepsilon_{t,2,i}\|\|\varepsilon_{t,3,i}\|>\frac{L _{1}}{\sqrt{\alpha\rho}})=\mathbb{P}(\|\varepsilon_{t,2,i}\|^{2}\|\varepsilon_ {t,3,i}\|^{2}>\frac{L_{1}^{2}}{{\alpha\rho}})\leq\frac{\sigma^{4}{\alpha\rho}} {L_{1}^{2}}.$ $$

It follows that

$$ $\displaystyle\mathbb{P}(\{\tau_{3}<T\})\leq\sum_{t=0}^{T-1}\sum_{i=1}^{K}\sum_ {j=1}^{K}\mathbb{P}(\|\varepsilon_{t,2,i}\|\|\varepsilon_{t,3,i}\|>\frac{L_{1} }{\sqrt{\alpha\rho}})\leq\frac{K^{2}\sigma^{4}{\alpha\rho}T}{L_{1}^{2}}\leq \frac{\delta}{8}.$ (17) $$

We then bound the probability of the event $\{\tau_{1}<T,\tau_{2}=T,\tau_{3}=T\}$. Since $\tau=\tau_{1}<T,$ we have that for some $i\in[K]$, $f_{i}(x_{\tau+1})-f_{i}^{*}>F$.

According to (C.4) shown in Lemma 1, for any $i\in[K]$ and $t=\tau$ we have that

$$ $\displaystyle f_{i}(x_{\tau+1})-f_{i}(x_{\tau})$ $\displaystyle\leq\alpha\|\nabla F(x_{\tau})w\|\|\varepsilon_{t,1}w_{t}\|+{\ell (M+1)}\alpha^{2}\|\varepsilon_{t,1}w_{t}\|^{2}+\frac{\alpha}{\beta}+\alpha\rho +\alpha\beta\rho^{2}$ $\displaystyle+\alpha M\|\varepsilon_{t,2}\|+\alpha M\|\varepsilon_{t,3}\|+ \alpha\|\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\|$ $\displaystyle+4\alpha\beta KM^{4}+4\alpha\beta M^{2}\|\varepsilon_{t,2}\|^{2}+ 4\alpha\beta M^{2}\|\varepsilon_{t,3}\|^{2}+4\alpha\beta\|\varepsilon_{t,2}^{ \top}\varepsilon_{t,3}w_{t}\|^{2}$ $\displaystyle\leq\alpha M\frac{L_{0}}{\sqrt{\alpha\rho}}+{\ell(M+1)}\alpha \frac{L_{0}^{2}}{{\rho}}+\frac{\alpha}{\beta}+\alpha\rho+\alpha\beta\rho^{2}$ $\displaystyle+\alpha M\frac{\sqrt{K}L_{0}}{\sqrt{\alpha\rho}}+\alpha M\frac{ \sqrt{K}L_{0}}{\sqrt{\alpha\rho}}+\alpha M\frac{\sqrt{K}L_{1}}{\sqrt{\alpha \rho}}$ $\displaystyle+4\alpha\beta KM^{4}+4\alpha\beta M^{2}\frac{KL_{0}^{2}}{{\alpha \rho}}+4\alpha\beta M^{2}\frac{KL_{0}^{2}}{{\alpha\rho}}+4\alpha\beta\frac{KL_ {1}^{2}}{{\alpha\rho}}$ $\displaystyle\leq b_{1}+b_{2}+b_{3}+c_{1}+\alpha\rho(1+\beta\rho)+4\alpha\beta KM ^{4}$ $\displaystyle\leq\frac{F}{2},$ $$

where the first inequality is due to that $\tau_{2}=\tau_{3}=T$, and the second one is due to $\frac{\beta}{\rho}\leq\frac{b_{3}}{8KM^{2}L_{0}^{2}+4KL_{1}^{2}}$ and $\frac{\alpha}{\rho}\leq\min\left\{\frac{b_{1}^{2}}{(3M\sqrt{K}L_{0}+M\sqrt{K}L
_{1})^{2}},\frac{b_{2}}{\ell(M+1)L_{0}^{2}}\right\}$.

However, for some $i\in[K]$, $f_{i}(x_{\tau+1})-f_{i}^{*}>F$. Thus for this task, we have that

$$ $\displaystyle f_{i}(x_{\tau})-f_{i}^{*}\leq\frac{F}{2}.$ $$

According to Lemma 1, we have that

$$ $\displaystyle\mathbb{E}[f_{i}(x_{\tau})-f_{i}^{*}]\leq\frac{\delta}{8}.$ $$

Based on Markov inequality, it follows that

$$ $\displaystyle\mathbb{P}\left(f_{i}(x_{\tau})-f_{i}^{*}\leq\frac{F}{2}\right) \leq\frac{\mathbb{E}[f_{i}(x_{\tau})-f_{i}^{*}]}{F/2}\leq\frac{\delta}{4},$ (18) $$

which indicates that $\mathbb{P}(\tau_{1}<T,\tau_{2}=T,\tau_{3}=T)\leq\frac{\delta}{4}$. It follows that $\mathbb{P}(\tau<T)\leq\frac{\delta}{2}$.

Convergence of $\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\Big{|}
\tau=T\right]$.
Based on (C.4) in Lemma 1, we have that

$$ $\displaystyle\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t} \|^{2}\Big{|}\tau=T\right]$ $\displaystyle\leq\frac{1}{T}\frac{1}{\mathbb{P}(\tau=T)}\mathbb{E}\left[\sum_{ t=0}^{\tau-1}\|\nabla F(x_{t})w_{t}\|^{2}\right]$ $\displaystyle\leq\frac{4F(x_{0})w-4F^{*}w+\frac{4\alpha}{\beta}}{\alpha T}+ \frac{4\sqrt{2}M(3\sigma+\sigma^{2})}{\sqrt{T}}+4\alpha\sigma^{2}\ell(M+1)+4\rho$ $\displaystyle+4\beta\rho^{2}+16\beta KM^{4}+32\beta KM^{2}\sigma^{2}+16\beta K \sigma^{4}$ $\displaystyle\leq\frac{\delta}{2}\epsilon^{2},$ $$

where the second inequality is due to $\delta<\frac{1}{2}$ and the last inequality is due to our selection of parameters.
As a result, we have that

$$ $\displaystyle\mathbb{P}\left(\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t} \|^{2}>\epsilon^{2}\Big{|}\tau=T\right)\leq\frac{\mathbb{E}\left[\frac{1}{T} \sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\geq\epsilon^{2}\Big{|}\tau=T \right]}{\epsilon^{2}}\leq\frac{\delta}{2},$ (19) $$

where the first probability is due to Markov inequality.
Thus we have that

$$ $\displaystyle\mathbb{P}\left(\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t} \|^{2}\leq\epsilon^{2}\right)$ $\displaystyle\geq 1-\mathbb{P}\left(\tau<T\right)-\mathbb{P}\left(\frac{1}{T} \sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}>\epsilon^{2}\Big{|}\tau=T\right) \mathbb{P}\left(\tau=T\right)$ $\displaystyle\geq 1-\delta,$ $$

where the last inequality is due to (16), (17), (18), and (19).
This completes the proof.
∎

###### Theorem 8 .

###### Proof.

### C.4 Proof of Lemma 1

###### Proof.

For all $i\in[K],t\leq\tau$, we have $f_{i}(x_{t})-f_{i}^{*}\leq F$ which further implies that $\|\nabla f_{i}(x_{t})\|\leq M$. Moreover, we have that for any $t\leq\tau$ and $i\in[K]$,

$$ $\displaystyle\|x_{t+1}-x_{t}\|\leq\alpha\|\nabla G_{1}(x_{t})w_{t}\|\leq\alpha (\|\nabla F(x_{t})w_{t}\|+\|\varepsilon_{t,1}w_{t}\|)\leq\alpha\left(M+\frac{L _{0}}{\sqrt{\alpha\rho}}\right)\leq\frac{1}{\ell(M+1)}.$ $$

Since $f_{i}(x)$ is $\left(\frac{1}{\ell(\|\nabla f_{i}(x))\|+1)},\ell(\|\nabla f_{i}(x)\|+1)\right)$-smooth, it follows that

$$ $\displaystyle f_{i}(x_{t+1})-f_{i}(x_{t})\leq-\alpha\langle\nabla f_{i}(x_{t}) ,\nabla G_{1}(x_{t})w_{t}\rangle+\frac{\ell(\|\nabla f_{i}(x_{t})\|+1)}{2} \alpha^{2}\|\nabla G_{1}(x_{t})w_{t}\|^{2}.$ $$

As a result, for any $w\in\mathcal{W}$, we have that

$$ $\displaystyle F(x_{t+1})w$ $\displaystyle\leq F(x_{t})w-\alpha\langle\nabla F(x_{t})w,\nabla G_{1}(x_{t})w _{t}\rangle+\frac{\ell(M+1)}{2}\alpha^{2}\|\nabla G_{1}(x_{t})w_{t}\|^{2}$ $\displaystyle\leq F(x_{t})w-\alpha\langle\nabla F(x_{t})w,\nabla F(x_{t})w_{t} \rangle+\alpha\langle\nabla F(x_{t})w,\varepsilon_{t,1}w_{t}\rangle$ $\displaystyle+{\ell(M+1)}\alpha^{2}\|\nabla F(x_{t})w_{t}\|^{2}+{\ell(M+1)} \alpha^{2}\|\varepsilon_{t,1}w_{t}\|^{2}$ (20) $$

Based on the update process of $w$, we have that

$$ $\displaystyle\|w_{t+1}-w\|^{2}$ $\displaystyle=\|\Pi_{\mathcal{W}}\big{(}w_{t}-\beta[{\nabla G_{2}(x_{t})^{\top }\nabla G_{3}(x_{t})w_{t}}+\rho w_{t}]\big{)}-w\|^{2}$ $\displaystyle\leq\|\big{(}w_{t}-\beta[{\nabla G_{2}(x_{t})^{\top}\nabla G_{3}( x_{t})w_{t}}+\rho w_{t}]\big{)}-w\|^{2}$ $\displaystyle=\|w_{t}-w\|^{2}-2\beta\langle w_{t}-w,(\nabla G_{2}(x_{t})^{\top }\nabla G_{3}(x_{t})+\rho)w_{t}\rangle$ $\displaystyle+\beta^{2}\|(\nabla G_{2}(x_{t})^{\top}\nabla G_{3}(x_{t})+\rho)w _{t}\|^{2},$ $$

where the inequality follows from the non-expansiveness of projection.
It follows that

$$ $\displaystyle 2\beta\langle w_{t}-w,\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}\rangle$ $\displaystyle\leq\left(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2}\right)+2\beta\rho+2 \beta^{2}\rho^{2}$ $\displaystyle+2\beta\left\langle w_{t}-w,\varepsilon_{t,2}^{\top}\nabla F(x_{t })w_{t}+\nabla F(x_{t})^{\top}\varepsilon_{t,3}w_{t}-\varepsilon_{t,2}^{\top} \varepsilon_{t,3}w_{t}\right\rangle$ $\displaystyle+2\beta^{2}\|\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}- \varepsilon_{t,2}^{\top}\nabla F(x_{t})w_{t}-\nabla F(x_{t})^{\top}\varepsilon _{t,3}w_{t}+\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\|^{2}$ $\displaystyle\leq\left(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2}\right)+2\beta\rho+2 \beta^{2}\rho^{2}$ $\displaystyle+2\beta\left\langle w_{t}-w,\varepsilon_{t,2}^{\top}\nabla F(x_{t })w_{t}+\nabla F(x_{t})^{\top}\varepsilon_{t,3}w_{t}-\varepsilon_{t,2}^{\top} \varepsilon_{t,3}w_{t}\right\rangle$ $\displaystyle+8\beta^{2}KM^{4}+8\beta^{2}M^{2}\|\varepsilon_{t,2}\|^{2}+8\beta ^{2}M^{2}\|\varepsilon_{t,3}\|^{2}+8\beta^{2}\|\varepsilon_{t,2}^{\top} \varepsilon_{t,3}w_{t}\|^{2}.$ (21) $$

Combine (C.4) and (C.4), and we can get that

$$ $\displaystyle F(x_{t+1})w-F(x_{t})w$ $\displaystyle\leq-\alpha\|\nabla F(x_{t})w_{t}\|^{2}+\alpha\langle\nabla F(x_{ t})w,\varepsilon_{t,1}w_{t}\rangle$ $\displaystyle+{\ell(M+1)}\alpha^{2}\|\nabla F(x_{t})w_{t}\|^{2}+{\ell(M+1)} \alpha^{2}\|\varepsilon_{t,1}w_{t}\|^{2}$ $\displaystyle+\frac{\alpha}{2\beta}\left(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2} \right)+\alpha\rho+\alpha\beta\rho^{2}$ $\displaystyle+\alpha\left\langle w_{t}-w,\varepsilon_{t,2}^{\top}\nabla F(x_{t })w_{t}+\nabla F(x_{t})w_{t}^{\top}\varepsilon_{t,3}-\varepsilon_{t,2}^{\top} \varepsilon_{t,3}w_{t}\right\rangle$ $\displaystyle+4\alpha\beta KM^{4}+4\alpha\beta M^{2}\|\varepsilon_{t,2}\|^{2}+ 4\alpha\beta M^{2}\|\varepsilon_{t,3}\|^{2}+4\alpha\beta\|\varepsilon_{t,2}^{ \top}\varepsilon_{t,3}w_{t}\|^{2}.$ (22) $$

Taking expectation and sum up (C.4) from $t=0$ to $\tau-1$, we have that

$$ $\displaystyle\mathbb{E}[F(x_{\tau})w]-F(x_{0})w$ $\displaystyle\leq-\frac{\alpha}{2}\mathbb{E}\left[\sum_{t=0}^{\tau-1}\|\nabla F (x_{t})w_{t}\|^{2}\right]+\alpha\mathbb{E}\left[\sum_{t=0}^{\tau-1}\langle \nabla F(x_{t})w,\varepsilon_{t,1}w_{t}\rangle\right]$ $\displaystyle+\alpha\mathbb{E}\left[\sum_{t=0}^{\tau-1}\left\langle w_{t}-w, \varepsilon_{t,2}^{\top}\nabla F(x_{t})w_{t}+\nabla F(x_{t})w_{t}^{\top} \varepsilon_{t,3}-\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\right\rangle\right]$ $\displaystyle+{\ell(M+1)}\alpha^{2}\mathbb{E}\left[\sum_{t=0}^{\tau-1}\| \varepsilon_{t,1}w_{t}\|^{2}\right]+\frac{\alpha}{2\beta}\|w_{0}-w\|^{2}+ \alpha\rho T+\alpha\beta\rho^{2}T$ $\displaystyle+4\alpha\beta KM^{4}T+4\alpha\beta M^{2}\mathbb{E}\left[\sum_{t=0 }^{\tau-1}\|\varepsilon_{t,2}\|^{2}\right]$ $\displaystyle+4\alpha\beta M^{2}\mathbb{E}\left[\sum_{t=0}^{\tau-1}\| \varepsilon_{t,3}\|^{2}\right]+4\alpha\beta\mathbb{E}\left[\sum_{t=0}^{\tau-1} \|\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\|^{2}\right]$ $\displaystyle\leq-\frac{\alpha}{2}\mathbb{E}\left[\sum_{t=0}^{\tau-1}\|\nabla F (x_{t})w_{t}\|^{2}\right]+\alpha\mathbb{E}\left[\sum_{t=0}^{\tau-1}\langle \nabla F(x_{t})w,\varepsilon_{t,1}w_{t}\rangle\right]$ $\displaystyle+\alpha\mathbb{E}\left[\sum_{t=0}^{\tau-1}\left\langle w_{t}-w, \varepsilon_{t,2}^{\top}\nabla F(x_{t})w_{t}+\nabla F(x_{t})w_{t}^{\top} \varepsilon_{t,3}-\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\right\rangle\right]$ $\displaystyle+{\ell(M+1)}\alpha^{2}T\sigma^{2}+\frac{\alpha}{\beta}+\alpha\rho T +\alpha\beta\rho^{2}T$ $\displaystyle+4\alpha\beta KM^{4}T+4\alpha\beta KM^{2}T\sigma^{2}$ $\displaystyle+4\alpha\beta KM^{2}T\sigma^{2}+4\alpha\beta TK\sigma^{4},$ (23) $$

where the last inequality is due to that $\tau\leq T$ and for any $i\in[K],j\in[3]$, $\mathbb{E}\left[\sum_{t=0}^{\tau-1}\|\varepsilon_{t,j,i}\|^{2}\right]\leq
\mathbb{E}\left[\sum_{t=0}^{T-1}\|\varepsilon_{t,j,i}\|^{2}\right]\leq TK
\sigma^{2}$. By the optional stopping
theorem, we have that

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{\tau}\langle\nabla F(x_{t})w, \varepsilon_{t,1}w_{t}\rangle\right]=0,$ $$

which further implies that

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{\tau-1}\langle\nabla F(x_{t})w, \varepsilon_{t,1}w_{t}\rangle\right]$ $\displaystyle=-\mathbb{E}[\langle\nabla F(x_{\tau})w,\varepsilon_{\tau,1}w_{ \tau}\rangle]$ $\displaystyle\leq\mathbb{E}[M\|\varepsilon_{\tau,1}w_{\tau}\|]\leq M\sqrt{ \mathbb{E}[\|\varepsilon_{\tau,1}w_{\tau}\|^{2}]}$ $\displaystyle\leq M\sqrt{\mathbb{E}\left[\sum_{t=0}^{T}\|\varepsilon_{t,1}w_{t }\|^{2}\right]}\leq M\sigma\sqrt{T+1}$ $\displaystyle\leq\sqrt{2}M\sigma\sqrt{T}.$ (24) $$

Similarly, we have $\mathbb{E}\left[\sum_{t=0}^{\tau-1}\langle\nabla F(x_{t})w,\varepsilon_{t,2}w_
{t}\rangle\right]\leq\sqrt{2}M\sigma\sqrt{T}$, $\mathbb{E}\left[\sum_{t=0}^{\tau-1}\langle\nabla F(x_{t})w,\varepsilon_{t,3}w_
{t}\rangle\right]\leq\sqrt{2}M\sigma\sqrt{T}$
and $\mathbb{E}\left[\sum_{t=0}^{\tau-1}\langle\nabla F(x_{t})w,\varepsilon_{t,2}^{
\top}\varepsilon_{t,3}w_{t}\rangle\right]\leq\sqrt{2K}M\sigma^{2}\sqrt{T}$.

Based on (C.4) and (C.4), we have that

$$ $\displaystyle\mathbb{E}[F(x_{\tau})w]-F^{*}w$ $\displaystyle\leq F(x_{0})w-F^{*}w-\mathbb{E}\left[\sum_{t=0}^{\tau-1}\frac{ \alpha}{2}\|\nabla F(x_{t})w_{t}\|^{2}\right]+\alpha\sqrt{2T}M(3\sigma+\sigma^ {2})$ $\displaystyle+{\ell(M+1)}\alpha^{2}T\sigma^{2}+\frac{\alpha}{\beta}+\alpha\rho T +\alpha\beta\rho^{2}T$ $\displaystyle+4\alpha\beta KM^{4}T+4\alpha\beta KM^{2}T\sigma^{2}$ $\displaystyle+4\alpha\beta KM^{2}T\sigma^{2}+4\alpha\beta TK\sigma^{4}$ $\displaystyle\leq\frac{\delta F}{8}-\mathbb{E}\left[\sum_{t=0}^{\tau-1}\frac{ \alpha}{2}\|\nabla F(x_{t})w_{t}\|^{2}\right],$ (25) $$

which completes the proof.
∎

###### Proof.

## Appendix D Detailed Proofs for Iteration-wise CA Distance

We first provide some useful lemmas, which will be used in our main theorems.

###### Lemma 3 (Continuity of $w_{t,\rho}^{*}$ ) .

Suppose Assumptions 1 and 2 are satisfied. If for any $i\in[K],\|\nabla f_{i}(x_{t})\|\leq M$ and $\|x_{t}-x_{t+1}\|\leq\frac{1}{\ell(M+1)}$, we have,

$$ $\displaystyle\|w_{\rho}^{*}(x_{t})-w_{\rho}^{*}(x_{t+1})\|\leq 2\rho^{-1}KM \ell(M+1)\|x_{t}-x_{t+1}\|=L_{w}\|x_{t}-x_{t+1}\|.$ $$

###### Proof.

We first define that $w_{Q,\rho}(x_{t})\in\mathcal{W}$ is the $Q$-th iterate of a function $J(w)=\frac{1}{2}\|\nabla F(x_{t})w\|^{2}+\frac{\rho}{2}\|w\|^{2}$ using projected gradient descent (PGD) with a constant step size $\beta$. The update rule is $w_{Q+1,\rho}(x_{t})=\Pi_{\mathcal{W}}\Big{(}\big{(}(1-\beta\rho)I-\beta\nabla F
(x_{t})^{\top}\nabla F(x_{t})\big{)}w_{Q,\rho}(x_{t})\Big{)}$. By the non-expansiveness of projection, we have

$$ $\displaystyle\|w_{Q+1,\rho}$ $\displaystyle(x_{t})-w_{Q+1,\rho}(x_{t+1})\|$ $\displaystyle\leq$ $\displaystyle\|\big{(}(1-\beta\rho)I-\beta\nabla F(x_{t})^{\top}\nabla F(x_{t} )\big{)}w_{Q,\rho}(x_{t})$ $\displaystyle-\big{(}(1-\beta\rho)I-\beta\nabla F^{\top}(x_{t+1})\nabla F(x_{t +1})\big{)}w_{Q,\rho}(x_{t+1})\|$ $\displaystyle\leq$ $\displaystyle\|(1-\beta\rho)I-\beta\nabla F(x_{t})^{\top}\nabla F(x_{t})\|\|w_ {Q,\rho}(x_{t})-w_{Q,\rho}(x_{t+1})\|$ $\displaystyle+\beta\|\big{(}\nabla F(x_{t})^{\top}\nabla F(x_{t})-\nabla F^{ \top}(x_{t+1})\nabla F(x_{t+1})\big{)}w_{Q,\rho}(x_{t+1})\|$ $\displaystyle\leq$ $\displaystyle(1-\beta\rho)\|w_{Q,\rho}(x_{t})-w_{Q,\rho}(x_{t+1})\|$ $\displaystyle+\beta\|\big{(}\nabla F(x_{t})^{\top}\nabla F(x_{t})-\nabla F^{ \top}(x_{t+1})\nabla F(x_{t+1})\big{)}w_{Q,\rho}(x_{t+1})\|.$ $$

Since we set $w_{0,\rho}(x_{t})=w_{0,\rho}(x_{t+1})$ and $\|w_{Q,\rho}(x_{t+1})\|\leq 1$, telescoping the above inequality from $t=0,1,...,T-1$ gives,

$$ $\displaystyle\|w_{Q,\rho}$ $\displaystyle(x_{t})-w_{Q,\rho}(x_{t+1})\|\leq\rho^{-1}\|\nabla F(x_{t})^{\top }\nabla F(x_{t})-\nabla F^{\top}(x_{t+1})\nabla F(x_{t+1})\|.$ (26) $$

Then according to the Cauchy-Schwartz inequality, it follows that

$$ $\displaystyle\|w_{\rho}^{*}(x_{t})-w_{\rho}^{*}(x_{t+1})\|\leq$ $\displaystyle\lim_{Q\rightarrow\infty}\big{(}\|w_{\rho}^{*}(x_{t})-w_{Q,\rho}( x_{t})\|+\|w_{\rho}^{*}(x_{t+1})-w_{Q,\rho}(x_{t+1})\|$ $\displaystyle+\|w_{Q,\rho}(x_{t})-w_{Q,\rho}(x_{t+1})\|\big{)}$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\lim_{Q\rightarrow\infty}\big{(}\|w_{\rho}^{*}(x_{t})-w_{Q,\rho}( x_{t})\|+\|w_{\rho}^{*}(x_{t+1})-w_{Q,\rho}(x_{t+1})\|\big{)}$ $\displaystyle+\rho^{-1}\|\nabla F(x_{t})^{\top}\nabla F(x_{t})-\nabla F^{\top} (x_{t+1})\nabla F(x_{t+1})\|$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle\lim_{Q\rightarrow\infty}2\sqrt{\frac{4}{\rho\beta Q}}+\rho^{-1} \|\nabla F(x_{t})^{\top}\nabla F(x_{t})-\nabla F^{\top}(x_{t+1})\nabla F(x_{t+ 1})\|,$ (27) $$

where $(i)$ follows from eq. 26 and $(ii)$ follows from the convergence of PGD (Theorem 1.1, []) on $\rho$-strongly convex objectives that

$$ $\displaystyle\|w_{\rho}^{*}(x_{t})-w_{Q,\rho}(x_{t})\|^{2}\leq\frac{2}{\rho} \big{(}J(w_{\rho}^{*}(x_{t}))-J(w_{Q,\rho}(x_{t}))\big{)}\leq\frac{2}{\rho} \frac{\|w_{0,\rho}(x_{t})-w_{\rho}^{*}(x_{t})\|^{2}}{2\beta Q}\leq\frac{4}{ \rho\beta Q}.$ $$

Then lemma 3 can be bounded by

$$ $\displaystyle\|w_{\rho}^{*}(x_{t})-w_{\rho}^{*}(x_{t+1})\|\leq$ $\displaystyle\rho^{-1}\|\nabla F(x_{t})^{\top}\nabla F(x_{t})-\nabla F^{\top}( x_{t+1})\nabla F(x_{t+1})\|$ $\displaystyle\leq$ $\displaystyle\rho^{-1}\|\nabla F(x_{t})+\nabla F(x_{t+1})\|\|\nabla F(x_{t})- \nabla F(x_{t+1})\|$ $\displaystyle\leq$ $\displaystyle 2\rho^{-1}KM\ell(M+1)\|x_{t}-x_{t+1}\|,$ $$

where the last inequality follows from $\|\nabla f_{i}(x_{t})\|\leq M$ and $f_{i}(x)$ is $\Big{(}\frac{1}{\ell(\|\nabla f_{i}(x)\|+1)},\ell(\|\nabla f_{i}(x)\|+1)\Big{)}$-smooth by setting $a=1$. The proof is complete.
∎

###### Lemma 4 .

Given $w_{t}^{*}=\arg\min_{w\in\mathcal{W}}\frac{1}{2}\|\nabla F(x_{t})w\|^{2}$ and $w_{t,\rho}^{*}=\arg\min_{w\in\mathcal{W}}\frac{1}{2}\|\nabla F(x_{t})w\|^{2}+
\frac{\rho}{2}\|w\|^{2}$, we have

$$ $\displaystyle\|\nabla F(x_{t})w_{t}^{*}-\nabla F(x_{t})w_{t,\rho}^{*}\|\leq \sqrt{\rho}.$ $$

###### Proof.

Recall that $w_{t,\rho}^{*}=\arg\min_{w\in\mathcal{W}}\frac{1}{2}\|\nabla F(x_{t})w\|^{2}+
\frac{\rho}{2}\|w\|^{2}$, then we have

$$ $\displaystyle\frac{1}{2}\|\nabla F(x_{t})w_{t}^{*}\|^{2}+\frac{\rho}{2}\|w_{t} ^{*}\|^{2}-\frac{1}{2}\|\nabla F(x_{t})w_{t,\rho}^{*}\|^{2}-\frac{\rho}{2}\|w_ {t,\rho}^{*}\|^{2}\geq 0.$ $$

By rearranging the above inequality, we have

$$ $\displaystyle\|\nabla F(x_{t})w_{t,\rho}^{*}\|^{2}-\|\nabla F(x_{t})w_{t}^{*} \|^{2}\leq\rho(\|w_{t,\rho}^{*}\|^{2}-\|w_{t}^{*}\|^{2})\leq\rho.$ $$

Then recall that $w_{t}^{*}=\arg\min_{w\in\mathcal{W}}\frac{1}{2}\|\nabla F(x_{t})w\|^{2}$, we have

$$ $\displaystyle\|\nabla F(x_{t})w_{t}^{*}-\nabla F(x_{t})w_{t,\rho}^{*}\|^{2}=$ $\displaystyle\|\nabla F(x_{t})w_{t}^{*}\|^{2}+\|\nabla F(x_{t})w_{t,\rho}^{*} \|^{2}-2\langle\nabla F(x_{t})w_{t}^{*},\nabla F(x_{t})w_{t,\rho}^{*}\rangle$ $\displaystyle\leq$ $\displaystyle\|\nabla F(x_{t})w_{t,\rho}^{*}\|^{2}-\|\nabla F(x_{t})w_{t}^{*} \|^{2}$ $\displaystyle\leq$ $\displaystyle\rho,$ $$

where the first inequlity follows from the optimality that

$$ $-2\langle w_{t,\rho}^{*},\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}^{*}\rangle \leq-2\|\nabla Fw_{t}^{*}\|^{2}.$ $$

The proof is complete.
∎

###### Lemma 5 .

Suppose Assumptions 1 and 2 are satisfied. If for any $i\in[K],\|\nabla f_{i}(x_{t})\|\leq M$ and $\|x_{t}-x_{t+1}\|\leq\frac{1}{\ell(M+1)}$, we have

$$ $\displaystyle\|R(x_{t})\|\leq\frac{\alpha^{2}K\ell(M+1)M^{2}}{2}$ $$

###### Proof.

According to the Talyor Theorem, we have the following result for any objective function $f_{i}(x_{t}),i\in[K]$.

$$ $\displaystyle f_{i}(x_{t+1})=f_{i}(x_{t})+\nabla f_{i}^{\top}(x_{t})(x_{t+1}-x _{t})+R_{i}(x_{t}),$ $$

where $R_{i}(x_{t})$ is the remainder term. Then according to the descent lemma of each objective function $f_{i}(x)$, we have

$$ $\displaystyle f_{i}(x_{t+1})\leq$ $\displaystyle f_{i}(x_{t})+\nabla f_{i}^{\top}(x_{t})(x_{t+1}-x_{t})+\alpha^{2 }\frac{\ell(\|\nabla f_{i}(x_{t})\|+1)}{2}\|\nabla F(x_{t})w_{t}\|^{2}$ $\displaystyle\leq$ $\displaystyle f_{i}(x_{t})+\nabla f_{i}^{\top}(x_{t})(x_{t+1}-x_{t})+\alpha^{2 }\frac{\ell(M+1)}{2}\|\nabla F(x_{t})w_{t}\|^{2}.$ $$

Then we can obtain

$$ $\displaystyle R_{i}(x_{t})\leq\alpha^{2}\frac{\ell(M+1)}{2}\|\nabla F(x_{t})w_ {t}\|^{2}.$ $$

Thus, according to the Cauchy-Schwartz inequality, we have

$$ $\displaystyle\|R(x_{t})\|\leq\alpha^{2}\frac{\ell(M+1)}{2}\|\nabla F(x_{t})w_{ t}\|^{2}.$ $$

The proof is complete.
∎

###### Lemma 3 (Continuity of w t , ρ ∗ superscript subscript 𝑤 𝑡 𝜌 w_{t,\rho}^{*} italic_w start_POSTSUBSCRIPT italic_t , italic_ρ end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT ) .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

### D.1 Proof of Theorem 3

###### Theorem 9 .

Suppose Assumptions 1 and 2 are satisfied. We choose $\beta^{\prime}\leq\frac{1}{M^{2}},N\sim\mathcal{O}(\epsilon^{-2}),\beta\leq
\min\left(\frac{\epsilon^{2}\rho}{C_{1}^{2}},\epsilon^{2}\right),\alpha\leq
\min\left(c_{1}\beta,\frac{1}{\ell(M+1)},\frac{\beta\rho\epsilon}{2L_{w}\sqrt{
M}},\frac{\rho\epsilon^{2}}{2L_{w}MC_{1}}\right),T\geq\max\left(\frac{10\Delta
}{\alpha\epsilon^{2}},\frac{10}{\epsilon^{2}\beta}\right)\sim\Theta(\epsilon^{
-11})$, and $\rho\leq\min\left(\frac{\epsilon^{2}}{20},\frac{c_{2}}{2T\alpha}\right)\sim
\mathcal{O}(\epsilon^{2})$. The CA distance in every iteration takes the order of $\mathcal{O}(\epsilon)$.

###### Proof.

Since our parameters satisfy all requirements in Theorem 1, we have that $\|\nabla f_{i}(x_{t})\|\leq M$. According to the definition of CA distance, we have

$$ $\displaystyle\|\nabla F$ $\displaystyle(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle=$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t,\rho}^{*}+\nabla F(x_{ t})w_{t,\rho}^{*}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t,\rho}^{*}\|+\|\nabla F (x_{t})w_{t,\rho}^{*}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle\sqrt{K}M\|w_{t}-w_{t,\rho}^{*}\|+\sqrt{\rho},$ (28) $$

where $(i)$ follows from Cauchy-Schwartz inequality and $(ii)$ follows from $\|\nabla f_{i}(x_{t})\|\leq M$ for any $i$ and Lemma 4. Then for the first term in the above inequality on the right-hand side (RHS), we have

$$ $\displaystyle\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}=\|w_{t+1}-w_{t,\rho}^{*}\|^{2}+ \|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}-2\langle w_{t+1}-w_{t,\rho}^{*},w_{t+1 ,\rho}^{*}-w_{t,\rho}^{*}\rangle.$ (29) $$

For the first term on the RHS in the above inequality, we have

$$ $\displaystyle\|w_{t+1}-w_{t,\rho}^{*}\|^{2}\overset{(i)}{\leq}$ $\displaystyle\|w_{t}-\beta[\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}+\rho w_{ t}]-w_{t,\rho}^{*}\|^{2}$ $\displaystyle=$ $\displaystyle\|w_{t}-w_{t,\rho}^{*}\|^{2}-2\beta\langle\nabla F(x_{t})^{\top} \nabla F(x_{t})w_{t}+\rho w_{t},w_{t}-w_{t,\rho}^{*}\rangle$ $\displaystyle+\beta^{2}\|\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}+\rho w_{t} \|^{2}$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle(1-2\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}+\beta^{2}(\rho+\sqrt{K }M^{2})^{2},$ (30) $$

where $(i)$ follows from the non-expansiveness of projection and $(ii)$ follows from properties of strong convexity and Cauchy-Schwartz inequality. Then for the second term on the RHS in eq. 29, we have

$$ $\displaystyle\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}\leq L_{w}^{2}\|x_{t}-x_{t +1}\|^{2}=L_{w}^{2}\alpha^{2}\|\nabla F(x_{t})w_{t}\|^{2}\leq\alpha^{2}L_{w}^{ 2}M^{2}.$ (31) $$

Then for the last term on the RHS in eq. 29, we have

$$ $\displaystyle-2$ $\displaystyle\langle w_{t+1}-w_{t,\rho}^{*},w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\rangle$ $\displaystyle\leq$ $\displaystyle 2\|w_{t+1}-w_{t,\rho}^{*}\|\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|$ $\displaystyle\leq$ $\displaystyle 2(\|w_{t+1}-w_{t}\|+\|w_{t}-w_{t,\rho}^{*}\|)\|w_{t+1,\rho}^{*}- w_{t,\rho}^{*}\|$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle 2\alpha\beta L_{w}\|\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}+ \rho w_{t}\|\|\nabla F(x_{t})w_{t}\|+\beta\rho\|w_{t}-w_{t,\rho}^{*}\|^{2}+ \frac{4}{\beta\rho}\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\alpha\beta L_{w}M(\sqrt{K}M^{2}+\rho)+\beta\rho\|w_{t}-w_{t, \rho}^{*}\|^{2}+\frac{4\alpha^{2}L_{w}^{2}M^{2}}{\beta\rho},$ (32) $$

where $(i)$ follows from the update rule in Algorithm 1, Lemma 3, and Young’s inequality. Then substituting section D.1, eq. 31 and section D.1 into eq. 29, we have

$$ $\displaystyle\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}\leq$ $\displaystyle(1-\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}+\beta^{2}(\rho+\sqrt{K} M^{2})^{2}+\alpha^{2}L_{w}^{2}M^{2}$ $\displaystyle+2\alpha\beta L_{w}M(\sqrt{K}M^{2}+\rho)+\frac{4\alpha^{2}L_{w}^{ 2}M^{2}}{\beta\rho}$ $\displaystyle\leq$ $\displaystyle(1-\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}+\beta^{2}C_{1}^{2}+ \alpha^{2}L_{w}^{2}M^{2}+2\alpha\beta L_{w}MC_{1}+\frac{4\alpha^{2}L_{w}^{2}M^ {2}}{\beta\rho},$ $$

where the last inequality follows from Lemma 5 and $C_{1}=\sqrt{K}M^{2}+\rho$. Then we do telescoping over $t=0,1,...,T-1$

$$ $\displaystyle\|w_{T}-w_{T,\rho}^{*}\|^{2}\leq$ $\displaystyle(1-\beta\rho)^{T}\|w_{0}-w_{0,\rho}^{*}\|^{2}+\frac{\beta}{\rho}C _{1}^{2}+\frac{\alpha^{2}}{\beta\rho}L_{w}^{2}M^{2}+\frac{2\alpha L_{w}M}{\rho }C_{1}+\frac{4\alpha^{2}L_{w}^{2}M^{2}}{\beta^{2}\rho^{2}}.$ $$

Then recalling that $L_{w}=\mathcal{O}(\frac{1}{\rho})$ and substituting the above inequality into section D.1, we have

$$ $\displaystyle\|\nabla F(x_{t})w_{t}$ $\displaystyle-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\leq$ $\displaystyle\sqrt{K}M\Big{[}(1-\beta\rho)^{t}\|w_{0}-w_{0,\rho}^{*}\|^{2}+ \frac{\beta}{\rho}C_{1}^{2}+\frac{\alpha^{2}}{\beta\rho}L_{w}^{2}M+$ $\displaystyle\frac{2\alpha L_{w}M}{\rho}C_{1}+\frac{4\alpha^{2}L_{w}^{2}M^{2}} {\beta^{2}\rho^{2}}\Big{]}^{\frac{1}{2}}+\sqrt{\rho}$ $\displaystyle=$ $\displaystyle\mathcal{O}\Big{(}(1-\beta\rho)^{\frac{t}{2}}\|w_{0}-w_{0,\rho}^{ *}\|+\sqrt{\frac{\beta}{\rho}}+\frac{\alpha}{\beta\rho^{2}}+\sqrt{\rho}\Big{)}.$ $$

Since we run projected gradient descent for the strongly convex function $J(w_{n})=\frac{1}{2}\|\nabla F(x_{0})w_{n}\|^{2}+\frac{\rho}{2}\|w_{n}\|^{2}$ in the N-loop in Algorithm 1, according to Theorem 10.5 [], we have by choosing $\beta^{\prime}\in(0,\frac{1}{M^{2}}]$

$$ $\|w_{0}-w_{0,\rho}^{*}\|^{2}=\|w_{N}-w_{0,\rho}^{*}\|^{2}\leq 2\Big{(}1-\frac{ \rho}{M^{2}}\Big{)}^{N}.$ $$

Thus, $\|w_{0}-w_{0,\rho}^{*}\|=\mathcal{O}(\epsilon)$ as $N\sim\mathcal{O}(\rho^{-1})$.
CA distance takes the order of $\epsilon$ in every iteration by choosing $\rho\sim\mathcal{O}(\epsilon^{2}),\beta\sim\mathcal{O}(\epsilon^{4})$, $\alpha\sim\mathcal{O}(\epsilon^{9})$, and $N\sim\mathcal{O}(\epsilon^{-2})$. The proof is complete.
∎

###### Theorem 9 .

###### Proof.

### D.2 Formal Version and Its Proof of Theorem 4

Let $c_{1}>0,c_{2}^{\prime}>0$, $c_{3}^{\prime},c_{4}^{\prime}\geq 0$, and $F>0$ be some constants such that

$$ $\displaystyle\Delta+c_{1}+{c_{2}^{\prime}}+c_{3}^{\prime}+c_{4}^{\prime}\leq F$ $$

We then have the following convergence rate for Algorithm 4.

###### Theorem 10 .

Suppose Assumptions 1 and 2 are satisfied, and we choose constant step sizes that $\beta\leq\frac{\epsilon^{2}}{C_{1}^{\prime 2}},\alpha\leq\min\left(c_{1}\beta,
\sqrt{\frac{2c_{3}^{\prime}}{K\ell(M+1)M^{2}T}},\frac{2c_{4}^{\prime}}{\beta C
_{1}^{\prime 2}T},\frac{\epsilon^{2}}{K\ell(M+1)M^{2}}\right),\rho\leq\left(
\frac{\epsilon^{2}}{2},\frac{c_{2}^{\prime}}{\alpha T}\right)$, and $T\geq\max\left(\frac{10\Delta}{\alpha\epsilon^{2}},\frac{10}{\epsilon^{2}\beta
}\right)$. We have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq \epsilon^{2}$ $$

###### Proof..

Following similar steps in Section C.1, we also prove that for any $i\in K$ and $t\leq T$, we have that $f_{i}(x_{t})-f_{i}^{*}\leq F$ by induction.

Base case: since all constants $c_{1},c_{2}^{\prime},c_{3}^{\prime},c_{4}^{\prime}$ are non-negative, we have that $f_{i}(x_{0})-f_{i}^{*}\leq\Delta\leq F$ holds for any $i\in[K]$.

Induction step: assume that for any $i\in[K]$ and $t\leq k<T$, $f_{i}(x_{t})-f_{i}^{*}\leq F$ holds. We then prove $f_{i}(x_{k+1})-f_{i}^{*}\leq F$ holds for any $i\in[K]$. Following similar steps in Section C.1, we have

$$ $\displaystyle F(x_{t+1})w\leq F(x_{t})w-\alpha\langle\nabla F(x_{t})w,\nabla F (x_{t})w_{t}\rangle+\frac{\alpha^{2}\ell(M+1)}{2}\|\nabla F(x_{t})w_{t}\|^{2}.$ (33) $$

Based on the update rule of $w$ and non-expansiveness of projection, we have

$$ $\displaystyle\|w_{t+1}-w\|^{2}\leq$ $\displaystyle\Big{\|}w_{t}-\beta\Big{(}\frac{F(x_{t})-F(x_{t+1})}{\alpha}+\rho w _{t}\Big{)}-w\Big{\|}^{2}$ $\displaystyle=$ $\displaystyle\Big{\|}w_{t}-\beta\Big{(}\nabla F(x_{t})^{\top}\nabla F(x_{t})w_ {t}+\rho w_{t}+\frac{R(x_{t})}{\alpha}\Big{)}-w\Big{\|}^{2}$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\|w_{t}-w\|^{2}-2\beta\langle w_{t}-w,(\nabla F(x_{t})^{\top} \nabla F(x_{t})+\rho I)w_{t}\rangle+2\frac{\beta}{\alpha}\|R(x_{t})\|+\beta^{2 }(C_{1}^{\prime})^{2}$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle\|w_{t}-w\|^{2}-2\beta\langle w_{t}-w,(\nabla F(x_{t})^{\top} \nabla F(x_{t})+\rho I)w_{t}\rangle$ $\displaystyle+\alpha\beta K\ell(M+1)M^{2}+\beta^{2}(C_{1}^{\prime})^{2},$ $$

where $(i)$ follows from Cauchy-Schwartz inequality and $C_{1}^{\prime}=\sqrt{K}M^{2}+\rho+\frac{\alpha^{2}K\ell(M+1)M^{2}}{2}$, and $(ii)$ follows from Lemma 5.
Then we have

$$ $\displaystyle\langle w_{t}-w,\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}\rangle\leq$ $\displaystyle\frac{1}{2\beta}(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2})+\rho$ $\displaystyle+\frac{\alpha K\ell(M+1)M^{2}}{2}+\frac{\beta(C_{1}^{\prime})^{2} }{2}.$ $$

Then substitute the above inequality into eq. 33, we can obtain

$$ $\displaystyle F(x_{t+1})w-F(x_{t})\leq$ $\displaystyle-\alpha\|\nabla F(x_{t})w_{t}\|^{2}+\frac{\alpha^{2}\ell(M+1)}{2} \|\nabla F(x_{t})w_{t}\|^{2}$ $\displaystyle+\frac{\alpha}{2\beta}(\|w_{t}-w\|^{2}-\|w_{t+1}-w\|^{2})+\alpha \rho+\frac{\alpha^{2}K\ell(M+1)M^{2}}{2}+\frac{\alpha\beta(C_{1}^{\prime})^{2} }{2}.$ $$

Then taking sums of the above inequality from $t=0$ to $k$, for any $w\in\mathcal{W}$, we have

$$ $\displaystyle F(x_{k+1})w-F(x_{0})w\leq$ $\displaystyle-\sum_{t=0}^{k}\alpha\|\nabla F(x_{t})w_{t}\|^{2}+\sum_{t=0}^{k} \frac{\alpha^{2}\ell(M+1)}{2}\|\nabla F(x_{t})w_{t}\|^{2}$ $\displaystyle+\frac{\alpha}{2\beta}\|w_{0}-w\|^{2}+\alpha\rho T+\frac{\alpha^{ 2}K\ell(M+1)M^{2}T}{2}+\frac{\alpha\beta(C_{1}^{\prime})^{2}T}{2}$ $\displaystyle\leq$ $\displaystyle\frac{\alpha}{\beta}+\alpha\rho T+\frac{\alpha^{2}K\ell(M+1)M^{2} T}{2}+\frac{\alpha\beta(C_{1}^{\prime})^{2}T}{2},$ (34) $$

where the last inequality follows from $\alpha\leq\frac{1}{\ell(M+1)}$. Thus, for any $i\in[K]$, it can be shown that

$$ $\displaystyle f_{i}(x_{k+1})-f_{i}^{*}\leq f_{i}(x_{0})-f_{i}^{*}+\frac{\alpha }{\beta}+\alpha\rho T+\frac{\alpha^{2}K\ell(M+1)M^{2}T}{2}+\frac{\alpha\beta(C _{1}^{\prime})^{2}T}{2}\leq F,$ $$

since we have that $\frac{\alpha}{\beta}\leq c_{1}$, $\alpha\rho T\leq c_{2}^{\prime}$, $\frac{\alpha^{2}K\ell(M+1)M^{2}T}{2}\leq c_{3}\prime$, $\frac{\alpha\beta(C_{1}^{\prime})^{2}T}{2}\leq c_{4}^{\prime}$. Now we finish the induction step and can show that $f_{i}(x_{k})-f_{i}^{*}\leq F$ and section D.2 hold for all $k<T$ and $i\in[K]$. Specifically, for $\alpha\leq\frac{1}{\ell(M+1)}$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq\frac{ 2F(x_{0})w-2F^{*}w}{\alpha T}+\frac{2}{\beta T}+2\rho+\alpha K\ell(M+1)M^{2}+ \beta(C_{1}^{\prime})^{2}.$ $$

Then following the choice of step sizes, we can obtain

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla F(x_{t})w_{t}\|^{2}\leq \epsilon^{2}.$ $$

The proof is complete.
∎

###### Theorem 10 .

###### Proof..

### D.3 Formal Version and Its Proof of Theorem 5

###### Theorem 11 .

Suppose Assumptions 1 and 2 are satisfied. We choose $\beta^{\prime}\leq\frac{1}{M^{2}},N\sim\mathcal{O}(\epsilon^{-2}),\beta\leq
\min\left(\frac{\epsilon^{2}\rho}{(C_{1}^{\prime})^{2}},\epsilon^{2}\right),
\alpha\leq\min\left(c_{1}\beta,\frac{2c_{3}^{\prime}}{\beta c_{1}^{\prime}T},
\frac{1}{\ell(M+1)},\frac{\beta\rho\epsilon}{2L_{w}\sqrt{M}},\frac{\rho
\epsilon^{2}}{2L_{w}MC_{1}^{\prime}}\right),T\geq\max\left(\frac{10\Delta}{
\alpha\epsilon^{2}},\frac{10}{\epsilon^{2}\beta}\right)\sim\Theta(\epsilon^{-1
1})$, and $\rho\leq\min\left(\frac{\epsilon^{2}}{20},\frac{c_{2}^{\prime}}{2T\alpha}
\right)\sim\mathcal{O}(\epsilon^{2})$. The CA distance in every iteration takes the order of $\mathcal{O}(\epsilon)$.

###### Proof.

According to the definition of CA distance, we have

$$ $\displaystyle\|\nabla F$ $\displaystyle(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle=$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t,\rho}^{*}+\nabla F(x_{ t})w_{t,\rho}^{*}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t,\rho}^{*}\|+\|\nabla F (x_{t})w_{t,\rho}^{*}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle\sqrt{K}M\|w_{t}-w_{t,\rho}^{*}\|+\sqrt{\rho},$ (35) $$

where $(i)$ follows from Cauchy-Schwartz inequality and $(ii)$ follows from $\|\nabla f_{i}(x_{t})\|\leq M$ for any $i$ and Lemma 3. Then for the first term in the above inequality on the right-hand side (RHS), we have

$$ $\displaystyle\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}=\|w_{t+1}-w_{t,\rho}^{*}\|^{2}+ \|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}-2\langle w_{t+1}-w_{t,\rho}^{*},w_{t+1 ,\rho}^{*}-w_{t,\rho}^{*}\rangle.$ (36) $$

For the first term on the RHS in the above inequality, we have

$$ $\displaystyle\|w_{t+1}-w_{t,\rho}^{*}\|^{2}\overset{(i)}{\leq}$ $\displaystyle\Big{\|}w_{t}-\beta\Big{(}\frac{F(x_{t})-F(x_{t+1})}{\alpha}+\rho w _{t}\Big{)}-w_{t,\rho}^{*}\Big{\|}^{2}$ $\displaystyle=$ $\displaystyle\Big{\|}w_{t}-\beta\Big{(}\nabla F(x_{t})^{\top}\nabla F(x_{t})w_ {t}+\rho w_{t}+\frac{R(x_{t})}{\alpha}\Big{)}-w_{t,\rho}^{*}\Big{\|}^{2}$ $\displaystyle=$ $\displaystyle\|w_{t}-w_{t,\rho}^{*}\|^{2}-2\beta\langle\nabla F(x_{t})^{\top} \nabla F(x_{t})w_{t}+\rho w_{t},w_{t}-w_{t,\rho}^{*}\rangle$ $\displaystyle-2\frac{\beta}{\alpha}\langle R(x_{t}),w_{t}-w_{t,\rho}^{*} \rangle+\beta^{2}\|\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t}+R(x_{t})+\rho w_ {t}\|^{2}$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle(1-2\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}+2\frac{\beta}{\alpha} \|R(x_{t})\|+\beta^{2}(\rho+\sqrt{K}M^{2}+\|R(x_{t})\|)^{2},$ (37) $$

where $(i)$ follows from the non-expansiveness of projection and $(ii)$ follows from properties of strong convexity and Cauchy-Schwartz inequality. Then for the second term on the RHS in eq. 36, we have

$$ $\displaystyle\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}\leq L_{w}^{2}\|x_{t}-x_{t +1}\|^{2}=L_{w}^{2}\alpha^{2}\|\nabla F(x_{t})w_{t}\|^{2}\leq\alpha^{2}L_{w}^{ 2}M.$ (38) $$

Then for the last term on the RHS in eq. 36, we have

$$ $\displaystyle-2\langle w_{t+1}$ $\displaystyle-w_{t,\rho}^{*},w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\rangle$ $\displaystyle\leq$ $\displaystyle 2\|w_{t+1}-w_{t,\rho}^{*}\|\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|$ $\displaystyle\leq$ $\displaystyle 2(\|w_{t+1}-w_{t}\|+\|w_{t}-w_{t,\rho}^{*}\|)\|w_{t+1,\rho}^{*}- w_{t,\rho}^{*}\|$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle 2\alpha\beta L_{w}\Big{\|}\frac{F(x_{t})-F(x_{t+1})}{\alpha}+ \rho w_{t}\Big{\|}\|\nabla F(x_{t})w_{t}\|+\beta\rho\|w_{t}-w_{t,\rho}^{*}\|^{ 2}+\frac{4}{\beta\rho}\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\alpha\beta L_{w}M(\sqrt{K}M^{2}+\|R(x_{t})\|+\rho)+\beta\rho\| w_{t}-w_{t,\rho}^{*}\|^{2}+\frac{4\alpha^{2}L_{w}^{2}M}{\beta\rho}.$ (39) $$

Then substituting section D.3, eq. 38 and section D.3 into eq. 36, we have

$$ $\displaystyle\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}\leq$ $\displaystyle(1-\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}+2\frac{\beta}{\alpha}\| R(x_{t})\|+\beta^{2}(\rho+\sqrt{K}M^{2}+\|R(x_{t})\|)^{2}$ $\displaystyle+\alpha^{2}L_{w}^{2}M+2\alpha\beta L_{w}M(\sqrt{K}M^{2}+\|R(x_{t} )\|+\rho)+\frac{4\alpha^{2}L_{w}^{2}M}{\beta\rho}$ $\displaystyle\leq$ $\displaystyle(1-\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}+\alpha\beta K\ell(M+1)M ^{2}+\beta^{2}(C_{1}^{\prime})^{2}$ $\displaystyle+\alpha^{2}L_{w}^{2}M+2\alpha\beta L_{w}MC_{1}^{\prime}+\frac{4 \alpha^{2}L_{w}^{2}M}{\beta\rho},$ $$

where the last inequality follows from Lemma 5 and $C_{1}^{\prime}=\sqrt{K}M^{2}+\rho+\frac{\alpha^{2}K\ell(M+1)M^{2}}{2}$. Then we do telescoping over $t=0,1,...,T-1$

$$ $\displaystyle\|w_{T}-w_{T,\rho}^{*}\|^{2}\leq$ $\displaystyle(1-\beta\rho)^{T}\|w_{0}-w_{0,\rho}^{*}\|^{2}+\frac{\alpha}{\rho} K\ell(M+1)M^{2}+\frac{\beta}{\rho}(C_{1}^{\prime})^{2}$ $\displaystyle+\frac{\alpha^{2}}{\beta\rho}L_{w}^{2}M+\frac{2\alpha L_{w}M}{ \rho}C_{1}^{\prime}+\frac{4\alpha^{2}L_{w}^{2}M}{\beta^{2}\rho^{2}}.$ $$

Then substituting the above inequality into section D.3, we have

$$ $\displaystyle\|\nabla F(x_{t})w_{t}$ $\displaystyle-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\leq$ $\displaystyle\sqrt{K}M\Big{[}(1-\beta\rho)^{t}\|w_{0}-w_{0,\rho}^{*}\|^{2}+ \frac{\alpha}{\rho}K\ell(M+1)M^{2}+\frac{\beta}{\rho}(C_{1}^{\prime})^{2}$ $\displaystyle+\frac{\alpha^{2}}{\beta\rho}L_{w}^{2}M+\frac{2\alpha L_{w}M}{ \rho}C_{1}^{\prime}+\frac{4\alpha^{2}L_{w}^{2}M}{\beta^{2}\rho^{2}}\Big{]}^{ \frac{1}{2}}+\sqrt{\rho}$ $\displaystyle=$ $\displaystyle\mathcal{O}\Big{(}(1-\beta\rho)^{\frac{t}{2}}\|w_{0}-w_{0,\rho}^{ *}\|+\sqrt{\frac{\alpha}{\rho^{2}}}+\sqrt{\frac{\beta}{\rho}}+\frac{\alpha}{ \beta\rho^{2}}+\sqrt{\rho}\Big{)}.$ $$

Since we run projected gradient descent for the strongly convex function $J(w_{n})=\frac{1}{2}\|\nabla F(x_{0})w_{n}\|^{2}+\frac{\rho}{2}\|w_{n}\|^{2}$ in the N-loop in Algorithm 4, according to Theorem 10.5 [], we have

$$ $\|w_{0}-w_{0,\rho}^{*}\|^{2}=\|w_{N}-w_{0,\rho}^{*}\|^{2}\leq 2\Big{(}1-\frac{ \rho}{M^{2}+\rho}\Big{)}^{N}.$ $$

Thus, $\|w_{0}-w_{0,\rho}^{*}\|=\mathcal{O}(\epsilon)$ as $N\sim\mathcal{O}(\rho^{-1})$.
CA distance takes the order of $\epsilon$ in every iteration by choosing $\rho\sim\mathcal{O}(\epsilon^{2}),\beta\sim\mathcal{O}(\epsilon^{4})$, $\alpha\sim\mathcal{O}(\epsilon^{9})$, and $N\sim\mathcal{O}(\epsilon^{-2})$. The proof is complete.
∎

###### Theorem 11 .

###### Proof.

### D.4 Formal Version of Its Proof of Theorem 6

Let $\alpha,\beta,\rho,T$ satisfy all requirements for Theorem 2 with $\delta<\frac{1}{2}$. Moreover, for $\rho\sim\mathcal{O}(\epsilon^{2}),N\sim\mathcal{O}(\epsilon^{-2}),\beta\leq
\frac{\delta\rho\epsilon^{2}}{60(1+KM^{4})}\sim\mathcal{O}(\epsilon^{4}),n_{s}
\geq\max\{\frac{1}{K\sigma},\frac{36K\sigma(6+20\beta\rho)}{\delta\rho^{2}
\epsilon^{2}}\}\sim\mathcal{O}(\epsilon^{-6})$ and $\alpha\leq\sqrt{\frac{\delta\beta^{2}\rho^{2}\epsilon^{2}}{12L_{w}^{2}(2M^{2}+
4\sigma^{2})(\beta\rho+1)}}\sim\mathcal{O}(\epsilon^{9})$ and $T\sim\Theta(\epsilon^{-11})$, we have the following theorem:

###### Theorem 12 .

If Assumptions 1, 2 and 3 hold, with the values of the parameters mentioned above, we have that for each $t\leq T$,

$$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|\sim\mathcal{O}( \epsilon),$ $$

with the probability at least $1-\delta$.

###### Proof.

When $\tau=T$ and $t<\tau$, according to the definition of CA distance, we have

$$ $\displaystyle\|\nabla F$ $\displaystyle(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle=$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t,\rho}^{*}+\nabla F(x_{ t})w_{t,\rho}^{*}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t,\rho}^{*}\|+\|\nabla F (x_{t})w_{t,\rho}^{*}-\nabla F(x_{t})w_{t}^{*}\|$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle\sqrt{K}M\|w_{t}-w_{t,\rho}^{*}\|+\sqrt{\rho},$ (40) $$

where $(i)$ follows from Cauchy-Schwartz inequality and $(ii)$ follows from $\|\nabla f_{i}(x_{t})\|\leq M$ for any $i\in[K]$ and Lemma 4.
We then show that for any $t\leq\tau$, we have that $\mathbb{E}[\|w_{t}-w_{t,\rho}^{*}\|^{2}|\tau=T]\leq\frac{\delta}{2}\epsilon^{2}$ by induction.

Base case: Since we run projected gradient descent for the strongly convex function $J(w_{n})=\frac{1}{2}\|\nabla F(x_{0})w_{n}\|^{2}+\frac{\rho}{2}\|w_{n}\|^{2}$ in the N-loop in Algorithm 1, according to Theorem 10.5 [], we have by choosing $\beta^{\prime}\in(0,\frac{1}{M^{2}}]$

$$ $\|w_{0}-w_{0,\rho}^{*}\|^{2}=\|w_{N}-w_{0,\rho}^{*}\|^{2}\leq 2\Big{(}1-\frac{ \rho}{M^{2}}\Big{)}^{N}.$ $$

Thus, $\|w_{0}-w_{0,\rho}^{*}\|^{2}=\mathcal{O}(\frac{\delta}{2}\epsilon^{2})$ as $N\sim\mathcal{O}(\rho^{-1})$.

Induction: Assume we have that $\mathbb{E}[\|w_{t}-w_{t,\rho}^{*}\|^{2}|\tau=T]\leq\epsilon^{2}$, we will show that $\mathbb{E}[\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}|\tau=T]\leq\epsilon^{2}$ holds for any $t<\tau$ in the following proof.
We first divide $\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}$ into three parts:

$$ $\displaystyle\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}=\|w_{t+1}-w_{t,\rho}^{*}\|^{2}+ \|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}-2\langle w_{t+1}-w_{t,\rho}^{*},w_{t+1 ,\rho}^{*}-w_{t,\rho}^{*}\rangle.$ (41) $$

For the first term on the RHS in the above inequality, we have that

$$ $\displaystyle\|w_{t+1}-w_{t,\rho}^{*}\|^{2}$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\Big{\|}w_{t}-\beta\Big{(}\nabla G_{2}(x_{t})^{\top}\nabla G_{3}( x_{t})w_{t}+\rho w_{t}\Big{)}-w_{t,\rho}^{*}\Big{\|}^{2}$ $\displaystyle=$ $\displaystyle\|w_{t}-w_{t,\rho}^{*}\|^{2}-2\beta\langle\nabla G_{2}(x_{t})^{ \top}\nabla G_{2}(x_{t})w_{t}+\rho w_{t},w_{t}-w_{t,\rho}^{*}\rangle$ $\displaystyle+\beta^{2}\|\nabla G_{2}(x_{t})^{\top}\nabla G_{3}(x_{t})w_{t}+ \rho w_{t}\|^{2}$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle(1-2\beta\rho)\|w_{t}-w_{t,\rho}^{*}\|^{2}$ $\displaystyle+2\beta\left\langle w_{t}-w_{t,\rho}^{*},\varepsilon_{t,2}^{\top} \nabla F(x_{t})w_{t}+\nabla F(x_{t})^{\top}\varepsilon_{t,3}w_{t}-\varepsilon_ {t,2}^{\top}\varepsilon_{t,3}w_{t}\right\rangle$ $\displaystyle+\beta^{2}\|\rho w_{t}+\nabla F(x_{t})^{\top}\nabla F(x_{t})w_{t} -\varepsilon_{t,2}^{\top}\nabla F(x_{t})w_{t}-\nabla F(x_{t})^{\top} \varepsilon_{t,3}w_{t}+\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\|^{2},$ (42) $$

where $(i)$ follows from the non-expansiveness of projection and $(ii)$ follows from properties of strong convexity and Cauchy-Schwartz inequality. Taking the conditional expectation of (D.4), we have that for any $a_{1}>0$,

$$ $\displaystyle\mathbb{E}[\|w_{t+1}-w_{t,\rho}^{*}\|^{2}|\tau=T]$ $\displaystyle\leq$ $\displaystyle\frac{\delta}{2}(1-2\beta\rho)\epsilon^{2}+2\beta\mathbb{E}[\|w_{ t}-w_{t,\rho}^{*}\|\|\varepsilon_{t,2}^{\top}\nabla F(x_{t})w_{t}+\nabla F(x_{ t})^{\top}\varepsilon_{t,3}w_{t}-\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t }\||\tau=T]$ $\displaystyle+\mathbb{E}[\beta^{2}\|\rho w_{t}+\nabla F(x_{t})^{\top}\nabla F( x_{t})w_{t}-\varepsilon_{t,2}^{\top}\nabla F(x_{t})w_{t}-\nabla F(x_{t})^{\top }\varepsilon_{t,3}w_{t}+\varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\|^{2}| \tau=T]$ $\displaystyle\leq$ $\displaystyle\beta(\mathbb{E}[a_{1}\|w_{t}-w_{t,\rho}^{*}\|^{2}+\|\varepsilon_ {t,2}^{\top}\nabla F(x_{t})w_{t}+\nabla F(x_{t})^{\top}\varepsilon_{t,3}w_{t}- \varepsilon_{t,2}^{\top}\varepsilon_{t,3}w_{t}\|^{2}/a_{1}|\tau=T]])$ $\displaystyle+\frac{\delta}{2}(1-2\beta\rho)\epsilon^{2}+5\beta^{2}\rho^{2}+5 \beta^{2}KM^{4}+5\beta^{2}\mathbb{E}[M\|\epsilon_{t,2}\|^{2}|\tau=T]$ $\displaystyle+5\beta^{2}\mathbb{E}[M\|\epsilon_{t,3}\|^{2}|\tau=T]+5\beta^{2} \mathbb{E}[\|\epsilon_{t,2}\|^{2}\|\epsilon_{t,3}\|^{2}|\tau=T],$ (43) $$

where the last inequality is due to that for $t\leq\tau=T$, and for any $i\in[K]$, we have that $\|\nabla f_{i}(x_{t})\|\leq M.$
Then for the second term on the RHS in eq. 41, we have

$$ $\displaystyle\mathbb{E}[\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}|\tau=T]$ $\displaystyle\leq\mathbb{E}[L_{w}^{2}\|x_{t}-x_{t+1}\|^{2}|\tau=T]$ $\displaystyle=\mathbb{E}[L_{w}^{2}\alpha^{2}\|\nabla F(x_{t},s_{t,1})w_{t}\|^{ 2}|\tau=T]$ $\displaystyle\leq\mathbb{E}[\alpha^{2}L_{w}^{2}(M+\|\epsilon_{t,1}w_{t}\|)^{2} |\tau=T],$ (44) $$

where the first inequality is due to Lemma 3, where $L_{w}\sim\mathcal{O}(\rho)$.
Then for the last term on the RHS in eq. 41, for any $a_{2}>0,a_{3}>0$, we have that

$$ $\displaystyle\mathbb{E}[-2\langle w_{t+1}-w_{t,\rho}^{*},w_{t+1,\rho}^{*}-w_{t ,\rho}^{*}\rangle|\tau=T]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[2\|w_{t+1}-w_{t,\rho}^{*}\|\|w_{t+1,\rho}^{*}-w_{t, \rho}^{*}\||\tau=T]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[2(\|w_{t+1}-w_{t}\|+\|w_{t}-w_{t,\rho}^{*}\|)\|w_{t+1, \rho}^{*}-w_{t,\rho}^{*}\||\tau=T]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[a_{2}\|w_{t+1}-w_{t}\|^{2}+\frac{1}{a_{2}}\|w_{t+ 1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}+a_{3}\|w_{t}-w_{t,\rho}^{*}\|^{2}+\frac{1}{a_ {3}}\|w_{t+1,\rho}^{*}-w_{t,\rho}^{*}\|^{2}|\tau=T\right]$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\mathbb{E}\left[a_{2}\beta^{2}\|\nabla G_{2}(x_{t})^{\top}\nabla G _{3}(x_{t})w_{t}+\rho w_{t}\|^{2}+a_{3}\frac{\delta}{2}\epsilon^{2}+\left( \frac{1}{a_{2}}+\frac{1}{a_{3}}\right)\alpha^{2}L_{w}^{2}(M+\|\epsilon_{t,1}w_ {t}\|)^{2}|\tau=T\right]$ $\displaystyle\leq$ $\displaystyle a_{2}(5\beta^{2}\rho^{2}+5\beta^{2}KM^{4}+5\beta^{2}\mathbb{E}[M \|\epsilon_{t,2}\|^{2}|\tau=T]$ $\displaystyle+5\beta^{2}\mathbb{E}[M\|\epsilon_{t,3}\|^{2}|\tau=T]+5\beta^{2} \mathbb{E}[\|\epsilon_{t,2}\|^{2}|\|\epsilon_{t,3}\|^{2}|\tau=T])$ $\displaystyle+\mathbb{E}\Big{[}\left(\frac{1}{a_{2}}+\frac{1}{a_{3}}\right) \alpha^{2}L_{w}^{2}(M+\|\epsilon_{t,1}w_{t}\|)^{2}|\tau=T\Big{]}+a_{3}\frac{ \delta}{2}\epsilon^{2},$ (45) $$

where $(i)$ follows from the non-expansiveness of projection and (D.4), and the last inequality is from (D.4).
Then substituting section D.4, section D.4 and section D.4 into eq. 41, we have

$$ $\displaystyle\mathbb{E}[\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}|\tau=T]$ $\displaystyle\leq$ $\displaystyle(1-2\beta\rho+\beta a_{1}+a_{3})\frac{\delta}{2}\epsilon^{2}$ $\displaystyle+\beta^{2}(5\rho^{2}+5KM^{4})(1+a_{2})$ $\displaystyle+M\left(\frac{3\beta}{a_{1}}+5\beta^{2}+5\beta^{2}a_{2}\right) \mathbb{E}[\|\varepsilon_{t,2}\|^{2}|\tau=T]$ $\displaystyle+M\left(\frac{3\beta}{a_{1}}+5\beta^{2}+5\beta^{2}a_{2}\right) \mathbb{E}[\|\varepsilon_{t,3}\|^{2}|\tau=T]$ $\displaystyle+\left(\frac{3\beta}{a_{1}}+5\beta^{2}+5\beta^{2}a_{2}\right) \mathbb{E}[\|\varepsilon_{t,2}\|^{2}\|\varepsilon_{t,3}\|^{2}|\tau=T]$ $\displaystyle+\mathbb{E}\Big{[}\left(1+\frac{1}{a_{2}}+\frac{1}{a_{3}}\right) \alpha^{2}L_{w}^{2}(M+\|\epsilon_{t,1}w_{t}\|)^{2}|\tau=T\Big{]}$ $\displaystyle\leq$ $\displaystyle(1-2\beta\rho+\beta a_{1}+a_{3})\frac{\delta}{2}\epsilon^{2}$ $\displaystyle+\beta^{2}(5\rho^{2}+5KM^{4})(1+a_{2})$ $\displaystyle+M\left(\frac{3\beta}{a_{1}}+5\beta^{2}+5\beta^{2}a_{2}\right) \left({\frac{4K\sigma}{n_{s}}}+\frac{{2}K^{2}\sigma^{2}}{n_{s}^{2}}\right)$ $\displaystyle+\left(1+\frac{1}{a_{2}}+\frac{1}{a_{3}}\right)\alpha^{2}L_{w}^{2 }\left(2M^{2}+\frac{4\sigma^{2}}{n_{s}}\right),$ (46) $$

where the last inequality is due to that for any $i\in[3]$,

$$ $\displaystyle\mathbb{E}[\|\epsilon_{t,i}\||\tau=T]\leq\sqrt{\mathbb{E}[\| \epsilon_{t,i}\|^{2}|\tau=T]}\leq\sqrt{\mathbb{E}[\|\epsilon_{t,i}\|^{2}]/ \mathbb{P}(\tau=T)}\leq\sqrt{\frac{2K}{n_{s}}}\sigma$ $$

and

$$ $\displaystyle\mathbb{E}[\|\epsilon_{t,2}\|\|\epsilon_{t,3}\||\tau=T]$ $\displaystyle\leq\sqrt{\mathbb{E}[\|\epsilon_{t,2}\|^{2}\|\epsilon_{t,3}\|^{2} |\tau=T]}$ $\displaystyle\leq\sqrt{\mathbb{E}[\|\epsilon_{t,2}\|^{2}\|\epsilon_{t,3}\|^{2} ]/\mathbb{P}(\tau=T)}$ $\displaystyle\leq\sqrt{\mathbb{E}[\|\epsilon_{t,2}\|^{2}]\mathbb{E}[\|\epsilon _{t,3}\|^{2}]/\mathbb{P}(\tau=T)}$ $\displaystyle\leq\frac{\sqrt{2}K\sigma^{2}}{n_{s}}\sigma.$ $$

According to (D.4), with $a_{1}=0.5\rho,a_{2}=1,a_{3}=0.5\beta\rho,\beta\leq\frac{\delta\rho\epsilon^{2}
}{60(1+KM^{4})},n_{s}\geq\max\{\frac{1}{K\sigma},\frac{36K\sigma(6+20\beta\rho
)}{\delta\rho^{2}\epsilon^{2}}\}$ and $\alpha\leq\sqrt{\frac{\delta\beta^{2}\rho^{2}\epsilon^{2}}{12L_{w}^{2}(2M^{2}+
4\sigma^{2})(\beta\rho+1)}}$,
we have that

$$ $\displaystyle\mathbb{E}[\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}|\tau=T]\leq\frac{ \delta}{2}\epsilon^{2}.$ $$

We then complete our induction and prove that for any $t<\tau$, we have that $\mathbb{E}[\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}|\tau=T]\leq\frac{\delta}{2}
\epsilon^{2}$.

As a result, we have that

$$ $\displaystyle\mathbb{P}\left(\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}>\epsilon^{2}\Big {|}\tau=T\right)\leq\frac{\mathbb{E}\left[\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}\Big {|}\tau=T\right]}{\epsilon^{2}}\leq\frac{\delta}{2},$ $$

where the first probability is due to Markov inequality.
Thus we have that

$$ $\displaystyle\mathbb{P}\left(\|w_{t+1}-w_{t+1,\rho}^{*}\|^{2}\leq\epsilon^{2}\right)$ $\displaystyle\geq 1-\mathbb{P}\left(\tau<T\right)-\mathbb{P}\left(\|w_{t+1}-w_ {t+1,\rho}^{*}\|^{2}\Big{|}\tau=T\right)\mathbb{P}\left(\tau=T\right)$ $\displaystyle\geq 1-\delta,$ (47) $$

where the last inequality is because our parameters satisfy all the requirements in Theorem 2, thus $\mathbb{P}(\tau<T)\leq\frac{\delta}{2}$.
Then based on (D.4), by setting $\rho\sim\mathcal{O}(\epsilon^{2})$, we have that $\|\nabla F(x_{t})w_{t}-\nabla F(x_{t})w_{t}^{*}\|\sim\mathcal{O}(\epsilon)$ with probability at least $1-\delta$ for each iteration $t$, which completes the proof.
∎

###### Theorem 12 .

###### Proof.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: - **References for Optimal rates for deterministic variants of per-iteration CA distance** : Can the authors provide any references for deterministic iteration-level CA distance to compare Theorems 3 and 4. Further, can the authors compare the performance of their warm-start procedure to existing baselines? Do warm-start procedures achieve optimal sample complexity for these cases? It might be helpful to include the sample complexity results in Table 1 for a quick comparison to baselines.

- **Independent samples for each $f_i$ for stochastic variants**: For 
stochastic variants (Line 387) at each iteration $t$, $F(x_t;s_{t,i})$ requires a different sample $s_{t,i,j}$ to evaluate $f_j$ for $j\in [K]$. Is this necessary for the analysis? Does using the same sample for all $f_j$ change the analysis, as in practice, one might take a single minibatch to evaluate all $f_j$ at each iteration. Further, in Eq 16 and 17, using the same sample can remove the terms of $K$ from the union bound while still obtaining similar results.

- **Stochastic MGDA-FA** : If there is a bound the variance of $F(x;s)$ for instance $\mathbb{E}[\|F(x;s) - F(x)\|^2]\leq \sigma_F^2, \forall x$ or for each function $f_j(x;s)$, then would it be possible to analyze a stochastic variant of MGDA-FA by combining the analysis of the deterministic MGDA-FA and stochastic MGDA? Are there any reasons why the authors believe this shouldn't be possible or straightforward?

- **Warm-start procedure for general bi-level optimization**: MOO is bi-level optimization problem, where the inner optimization problem solves for best $w$ and the outer optimization solves for $x$. The warm-start procedure here implies that for single loop solutions to bilevel optimization, the inner problem is already very accurate, $\mathcal{O}(\epsilon)$ to be precise. This makes solving the bi-level optimization easier, as the inner problem is already almost solved.
Can this technique be applied to ohter bi-level optimization problems, where a single warm-start conveniently solves the inner problem accurately? Or is this an artifact of the MOO problem's simple structure?
soundness: 3
strengths: - **Presentation**: The paper is easy to follow, even for readers without expertise in MOO. The MOO problem under generalized smoothness, the MGDA algorithm, and the warm-start procedure are well-motivated. Further, the proof sketch also provides a good overview of key ideas, atleast for average CA distance.


- **Novel algorithms**: A warm-start procedure appears in (Xiao et al 2023), however, it requires running two-loops, one of warm start of $w$ and other for $x$. In contrast, the proposed warm-start algorithm is run only once at initialization for $w$, and then the simple MGDA algorithm takes over. Even with this "weaker" warm-start, the authors can achieve stronger per-iteration $\epsilon$-CA distance. Algorithm 4, MGDA-FA, seems novel, and utilizes zeroth-order optimization intelligently, without worsening theoretical guarantees in the deterministic case.


- **Weak assumptions**: All existing works require $L$-smoothness and bounded gradients, while this paper requires only generalized smoothness. For their proofs, they show that gradients are indeed bounded by initial suboptimality, $\max_{i\in [K]} (f_i(x_0) - f_i^\star)$ for MGDA updates in the deterministic case. In the stochastic case, their proof is more complicated, wherein they take  a union bound over all iterations until a stopping time to show that gradient noise is also bounded.


- **Best sample complexity**: Even under weaker conditions, the obtained sample complexities for average CA distance, $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-4})$ for deterministic and stochastic cases respectively, match the lower bounds for single-objective optimization under $L$-smoothness. For iteration level CA distance, it seems that the best sample complexity of existing methods with stronger assumptions is $\mathcal{O}(\epsilon^{-12})$ while their analysis obtains $\mathcal{O}(\epsilon^{-17})$.
summary: The authors analyze the problem of multi objective optimization (MOO), 
$$\begin{align*}
F^\star = \min_{x\in \mathbb{R}^d} F(x) = (f_1(x), f_2(x), \ldots f_K(x))
\end{align*}
$$
where each $f_i:\mathbb{R}^m \to \mathbb{R}$ when each $f_i$ has generalized $\ell$-smoothness. Generalized $\ell$-smoothness implies that $\|\nabla^2 f_i(x)\| \leq \ell(\|\nabla f_i(x)\|), \forall x$ for a continuous non-decreasing positive function $\ell$. This subsumes $(L_0, L_1)$-smoothness, where $\ell(a) = L_0 + L_1 a$, (Zhang et al 2019) and standard $L$-smoothness, where $\ell(a) = L$. Further,  NNs do not satisfy stronger notions of $L$-smoothness but satisfy generalized smoothness. 

The goal of MOO is to obtain $\epsilon$-accurate Pareto stationary point, defined as $\min_{w\in \mathcal{W}} \|\nabla F(x) w\|^2 \leq \epsilon^2$. This is referred to as $\epsilon$-CA distance (Conflict avoidant).

First, the authors analyze the existing MGDA algorithm in Algorithm 1 (Desideri 2012) and its stochastic variant in Algorithm 3, to obtain $\epsilon$-CA distance on average. The required sample complexity for these cases is $\mathcal{O}((\alpha\epsilon^2)^{-1}, (\beta\epsilon^2)^{-1})$(Theorem 1)  and $\mathcal{O}((\alpha \epsilon^2)^{-1} + \epsilon^{-4})$ (Theorem 2) respectively, which matches the sample complexity for single objective optimization under $L$-smoothness. Here, $\alpha$ and $\beta$ are step sizes to update  $w$ and $x$ in their algorithms.

Second, the authors consider a stronger metric, the per-iteration $\epsilon$-level CA distance, defined as $\|\nabla F(x_t)w_t - \nabla F(x_t) w_t^\star\| \leq O(\epsilon)$, where $x_t, w_t$ are iterates of the algorithm, and $w_t^\star \in \arg\min_{w\in \mathcal{W}} \|\nabla F(x_t) w\|^2$. To achieve this metric, the authors propose using a  warm-start for $w$ in deterministic setting (Algorithm 1), and warmstart with increasing batch size for stochastic setting (Algorithm 3), yielding sample complexities of $\mathcal{O}(\epsilon^{-11})$ (Theorem 3) and $\mathcal{O}(\epsilon^{-17})$ (Theorem 6) respectively.  Further, the authors propose a zeroth-order method modificiation to warm-start deterministic MGDA in Algorithm 4, which uses only $O(1)$ space and time and achieves per-iteration $\epsilon$-level CA distance with same sample complexity $\mathcal{O}(\epsilon^{-11})$.

A key advantage of their analysis is removing the bounded gradient assumption required by all existing works and they require sufficient effort to show such a bound exists implicitly for their algorithms.


Finally, on two multi-task learning datasets (Cityscapes and NYU-v2), their warm start method obtains best average performance across all tasks.


**References** --
- (Zhang et al 2019) Why gradient clipping accelerates training: A theoretical justification for adaptivity. Arxiv.
- (Desideri 2012) Multiple-gradient descent algorithm (mgda) for multiobjective optimization. CRM.
weaknesses: - **Theory**:
    - **Definition of $\mathcal{W}$:** The authors have not defined the set $\mathcal{W}$, however across the proof(Line 809, Eq 11), they use $\max_{w\in \mathcal{W}}\|w\| \leq 1$. It seems to be the unit sphere in $K$ dimensions. 
    - **Choice of step size does not work in Theorem 2:** The parameters $\alpha,\beta,\rho = \mathcal{O}(\epsilon^2)$ do not work out for Theorem 2 as each of $\alpha, \beta$ and $\rho$ depend on other two. Consider $\rho \leq \frac{1}{\sqrt{\alpha T}}$ in Theorem 2, which for $T = \epsilon^{-4}$ and $\alpha  = \epsilon^{2}$ implies, $\rho \leq \epsilon$. For $\epsilon << 1$, $\rho=\epsilon^2$ does not satisfy this condition. Ideally, the authors should provide the condition for parameters in a sequential manner, for instance, $\rho$ depends on $\beta$ and $\alpha$, $\beta$ depends on $\alpha$ not $\rho$ and $\alpha$ doesn't depend on either $\beta$ or $\rho$. This would ensure that such inconsistent parameter values do not arise. Also, I am no longer sure that $T = \mathcal{O}(\epsilon^{-4})$ can be obtained for choice of $\alpha,\beta,\rho$ satisfying all constraints in Theorem 2. 
    - **Value of $M$:**  For the deterministic case (Theorems 1, 3, 4 and 5), the value of step sizes depend on $M$ defined in Line 357, which is a function of $\ell$ and initial function suboptimality. Therefore, while the bounds in these theorems scale well with  $\epsilon$, they might not do so with $M$. If the scaling with $M$ in these theorems matches that of single-objective generalized $\ell$-smooth optimization from (Li et al 2024), or if is small under certain conditions on $\ell$, then it should not be an issue.
    - **Dependence on high probability error $\delta$ in stochastic variants (Theorem 2 and 6):** The authors do not provide the dependence on the high probability error $\delta$ in Theorems 2 and 6. For high probability guarantees, we would want to know if we can make $\delta$ extremely small, for instance $\mathcal{O}(\epsilon)$, or if it works only for a constant $\delta$. From Theorem 8, it seems that a constant $\delta \in (0,\frac{1}{2})$ might work, but the authors should provide more details on this. The union bound  over all iterations should force $\delta$ to not be very small.
    
    
 
- **Poor empirical Performance of MGDA-FA**: While MGDA-FA achieves the same performance as warm-start MGDA theoretically(Theorems 3 and 4), it performs much worse in experiments (Table 4). Its performance is better than only $2$ of the $8$ baselines in Table 3, while warm-start MGDA outperforms all $8$ baselines. The authors do not discuss possible causes for this. Even though MGDA-FA is fast in practice, as its error is very large, its usefulness is limited.




- **Typos**: $f_i^\star$ in the definition of $\Delta$ in Line 357 and "optional stopping theorem" in Line 407-408.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: - What is the meaning of minimizing a vector as in Eq. (1)? I suggest that the authors may make it clearer, in the context of multi-objectives.
- Could the authors elaborate how they computed the local smoothness for Figure 1?
- What is $f_*$ in the definition of $\Delta$ in Line 357?
- Take Theorem 1 as an example. Could the authors provide a more detailed discussion on the constants $c$, $F$ and $M$, like how tight they can be in some special case? I found the current convergence result is hard to parse.
- Would generalized smoothness bring any benefits in practice, like providing guidance on how to choose the step sizes?
soundness: 3
strengths: - The analysis of MGDA under generalized smoothness is new. Their analysis further relax the assumptions such as bounded function values or bounded gradients assumed in prior work. 
- The authors use a general notion of generalized smoothness, i.e., in terms of a non-decreasing function $\ell$ instead of the original one with $ell(a) = L_0 + L_1 a$.
- The authors further study a variant of MGDA, which approximates the gradient in each iteration to save memory and time.
summary: This paper studies the multi-objective optimization (MOO) problem under generalized $ell$-smoothness, where $\ell$ is a general non-decreasing function of gradient norm. The authors provide the first convergence analysis of multiple gradient descent algorithm (MGDA) (and its variant with fast approximation) under this setting, in terms of $\epsilon$-Pareto stationarity and $\epsilon$-level conflict-avoidant (CA) distance. The resulting complexities with respect to $\epsilon$-Pareto stationarity and $\epsilon$-level average CA distance match the best known results.
weaknesses: - The notation of this paper is a bit unclear. In multiple places, the authors introduce something before they define the notation, so the write-up should be refined. For example, the authors should define $\mathcal{W}$ in Definition 3.
- The preliminaries on generalized smoothness from Section 2.1 is redundant, as those are not proposed by this work and not the main contribution here. 
- All the complexity results of this paper are only stated in terms of $\epsilon$. A more clear statements with dependencies on other problem parameters would be better.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. In lines 389 and 393, why are $i \in [3]$ and $j \in [3]$ specified? What is the rationale behind selecting only the first three sample collections?
2. In Section 5.2, the analysis involves mini-batch algorithms, yet the effect of batch size on the results is not discussed. How would adjusting the batch size impact the findings?
soundness: 2
strengths: 1. The theoretical analysis is comprehensive and robust.
2. The paper is clearly written and well-organized, making the concepts easy to follow.
summary: This paper offers a rigorous convergence analysis for both deterministic and stochastic variants of the Multiple Gradient Descent Algorithm (MGDA) under a generalized $\ell$-smoothness assumption. The authors demonstrate that these methods converge to an $\epsilon$-accurate Pareto stationary point while maintaining an $\epsilon$-level average conflict-avoidant (CA) distance over all iterations. The sample complexity is shown to be $\mathcal{O}(\epsilon^{-2})$ in the deterministic setting and $\mathcal{O}(\epsilon^{-4})$ in the stochastic setting. Additionally, the authors introduce a warm start strategy to enable more precise control over iteration-wise CA distance. They also analyze MGDA-FA, a variant that reduces the computational complexity to $\mathcal{O}(1)$ in both time and space, making it notably efficient.
weaknesses: 1. Assumption 2, which posits that $\phi(a) = \frac{a^2}{2\ell(2a)}$ is monotonically increasing, restricts $\ell(a) \leq \mathcal{O}(a^2)$. This places a strict limitation on the class of generalized $\ell$-smooth functions considered.
2. The paper's novelty is somewhat limited. From an algorithmic standpoint, MGDA was introduced several years ago, and the fast approximation presented here constitutes a relatively minor modification.
3. The novelty of the analytical techniques is also limited, as the approach used closely resembles that of [1].
4. The experimental results would benefit from the addition of confidence intervals to clarify statistical significance, particularly given the small differences in performance observed.
5. In the main theorems, the authors use big-O notation without specifying constants. Providing explicit constants would enhance clarity and interpretability.

**Reference**:

[1] Li, Haochuan, et al. "Convex and non-convex optimization under generalized smoothness." Advances in Neural Information Processing Systems 36 (2024).

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: For specific questions, please refer to the "Weakness" section.
I would be willing to raise my score if these  questions concerned are well addressed.
soundness: 2
strengths: 1.Writing: This work is presented with good writing style, where the summarized problems with detailed explanations make it easy for readers to understand the problem addressed in this article. 

2.Novelty: The paper investigates a more general and realistic class of generalized $\ell$-smooth loss functions, which has been rarely considered in previous work. Additionally, a warm start strategy is proposed in the algorithm design to initialize the parameter $\omega$ for enhanced performance.

3.Experiments: Several scenarios and recent baselines are considered, implying improvements in accuracy and robustness under various distributional shifts.
summary: This paper investigates a broader class of generalized $\ell$-smooth loss functions, where $\ell$ is a non-decreasing function of the gradient norm. We analyze the multiple gradient descent algorithm (MGDA) and its stochastic variant for addressing generalized ℓ\ellℓ-smooth multi-objective optimization (MOO) problems. Its comprehensive convergence analysis demonstrates that these algorithms converge to an $\epsilon$-accurate Pareto stationary point, ensuring guaranteed average conflict-avoidant distances.
weaknesses: 1.Unreliable theoretical analysis: The theoretical work in this paper appears to lack reliability. A simple review of the proofs in the appendix reveals that the proof of Corollary 1 is entirely incorrect. 

The inequality
$$
\left\|\nabla F\left(x_t\right) w_t-\nabla F\left(x_t\right) w_t^*\right\|^2 \leq\left\|\nabla F\left(x_t\right) w_t\right\|^2-\left\|\nabla F\left(x_t\right) w_t^*\right\|^2,
$$ 
does not hold.

2.Originality of the algorithm. Could you clarify the differences between the algorithm presented in this paper and MGDA [1]?  Could you elaborate on how the algorithm mentioned in this paper improves the performance of MGDA?

[1]Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization.  Comptes Rendus Mathematique, 350(5-6):313–318, 2012.

3.Warm start. Can the warm start strategy be applied to other multi-objective optimization algorithms? Would incorporating this strategy significantly improve algorithm performance?

4.Computational complexity. 
The paper may not provide a comprehensive assessment of the computational efficiency and practicality of the proposed method in real-world applications. Like the computational complexity analysis or empirical time/memory cost.

Meta-review: This paper analyzes the multi-objective optimization problem where the goal is to minimize the minimum of K different objectives. The standard measure for optimality in this case is called \epsilon-conflict-avoidant (CA). The main contribution of the paper is to extend existing analysis to the setting where the objectives are "general l-smooth", where the Hessian is bounded by a function of norm of gradient. For standard CA definition the result matches the earlier results that assume smoothness. The paper also considers a stronger version of CA and gets results with worse \epsilon dependency. The reviewers agree that the results are novel and the generalization to general smoothness is interesting. Most reviewers also find the empirical results convincing, although there are some concerns on the performance of MGDA-FA. Overall all reviewers are positive.

Decision: Accept (Poster)