MGDA Converges under Generalized Smoothness, Provably

We thank the reviewer moXU for the time and valuable feedback! Here are our responses.

Weakness 1: We believe our proof is reliable and kindly request the reviewer to rethink the point. This inequality holds and here are the details steps. It is a widely used inequality in the analysis of Multi-objective optimization, such as Lemma 6 in MoCo [a].

Weakness 5: Thanks for pointing it out. In the deterministic setting, the gap between the initial function and optimal value $\Delta$ is bounded and can be assumed as a constant since the loss function is typically non-negative. Thus $M=\mathcal O(\Delta)$ is also a constant. For the stochastic setting, $M=\mathcal O(\frac{\Delta}{\delta})$ and we provide the dependencies on other parameters: $\rho\le \mathcal O(\delta^2 \epsilon^2), \beta\le \mathcal O(\min\\{\frac{\delta\epsilon^2}{M^4},\frac{\rho}{M^2}\\}), \alpha\le \mathcal O(\min\\{\beta, \frac{\rho}{\ell(M+1)^2}, \frac{\rho}{M^2}, \frac{\delta }{\rho T},\frac{1}{\beta TM^2}\\})$ and $T\ge\Theta(\max\\{\frac{1}{\delta \alpha \epsilon^2},\frac{M^2}{\delta^2 \epsilon^4}\\})$.

Question 1: We have used 3 different samples in Algorithm 3. The first sample comes from the model update and a double-sampling strategy is used in the weight update process. Therefore, we specify $i\in[3]$. We have made it clearer in the revision.

Question 2: Thanks for pointing out this problem. To get the average CA distance bounded, there are no requirements on $n_s$. In our theorem 6 for iteration-wise CA distance, we require $n_s\ge \max\\{\frac{1}{K\sigma},\frac{36K\sigma(6+20\beta\rho)}{\delta\rho^2\epsilon^2}\\}$ to bound $\mathbb E[\\|w_{t}-w_{t,\rho}^*\\|^2$ in the order of $\mathcal O(\delta \epsilon^2)$ for any $t\le T$. A larger $n_s$ makes the gap smaller but increases the computation. However, a smaller batch will fail to guarantee the iteration-wise CA bounded with high probability.

We thank the reviewer Ksvn for the time and valuable feedback! Here are our responses.

Weakness 1: Thank you for the question. This assumption is already the weakest one in the generalized smooth studies, where most of them assume $\ell(a)$ is a linear function of $a$. Even for the single task problem, only the convergence with high probability can be obtained in the stochastic setting when $\ell(a)=\mathcal O(a^2)$ and no convergence is guaranteed even for deterministic setting when $\ell(a)>\mathcal O(a^2)$. The relaxation of this limitation is a very interesting topic and deserves more attention from both single-objective and multi-objective societies.

Weakness 2: Thank you for the question. We believe there may be a misunderstanding regarding the focus of this paper. Our work investigates the convergence of MGDA under generalized smoothness rather than proposing new algorithms, and we would like to clarify our contributions accordingly.

From a theoretical standpoint, this paper is the first to examine the convergence of MGDA under generalized smoothness conditions, which has not been previously addressed. All prior MGDA-related studies rely on standard $L$-smooth and bounded-gradient assumptions, which may not hold in neural network training. Because of that, we could not apply the analytical techniques in those papers but start the analysis from the generalized smoothness.

From the algorithmic standpoint, fast approximation implementation is not our main contribution, either. A similar idea was proposed by FAMO to significantly save computational cost as we mentioned in lines 319-322. However, there is no theoretical convergence analysis of this algorithm. In this paper, we not only fill this gap but also relax the assumption to generalized smoothness. Finally, the concept of warm start is essential in our algorithm to ensure an iteration-wise CA distance under generalized smoothness, representing a key aspect of our algorithmic innovation. Once again, our paper primarily emphasizes the convergence analysis of MGDA under generalized smoothness, as our novel and significant contribution.

Weakness 3: Thanks for the question. We would like to clarify our analytical techniques accordingly. [1] only focuses on the single-task optimization problem and it takes non-trivial efforts to get our theoretical results in a multi-objective setting. [1] requires the objective functions to be generalized smooth. However, in this paper, any linear combinations of generalized smooth functions are no longer generalized smooth. In a stochastic setting, it is easy to show the single function value bounded with high probability [1]. However, in the MOO setting it requires more effort to control function values for every task. Moreover, [1] does not need to find the CA direction and all exiting methods on MOO to get the CA directions do not work due to the unbounded gradient introduced by generalized smoothness. In the stochastic setting, bounding the single-function value with high probability is relatively straightforward [1]. However, in the MOO setting, it requires more effort to control the function values across all tasks.

Furthermore, [1] does not address the problem of finding the conflict-avoidant (CA) direction, which is essential in MOO. Existing MOO methods for determining CA directions fail under generalized smoothness due to the unbounded gradients it introduces. This is the first work to solve the challenges of finding CA direction under generalized smoothness.

Importantly, we incorporate the warm start procedure as both an analytical and algorithmic novelty. To the best of our knowledge, no prior single-loop MGDA-based algorithm has achieved iteration-wise CA distance, not to mention the generalized smoothness settings. By leveraging the warm start, we can control the error term of the weight initialization from the beginning, ensuring improved control over iteration-wise CA distance.

Finally, while the fast approximation is more efficient, it lacks theoretical guarantees in prior work. We address this gap by providing a convergence analysis along with a CA distance bound. In a word, these contributions establish the novelty and significance of our analytical techniques.

Weakness 4: Thank you for the suggestion. To address your concern, in the revised pdf, we report the mean and standard deviation of $\Delta m\%$ since it serves as an overall metric to evaluate the performance. For our method, $\Delta m\%=3.94\pm1.19$ can be found in the Table 3.

We thank the reviewer YM5v for the time and valuable feedback! Here are our responses.

Weakness 1: Thanks for pointing it out. We have moved the definition of $\mathcal{W}$ from section 2.3 to Definition 3 in the revision. We also add a notation summary in the Appendix in the revision.

Weakness 2: Though the preliminaries in Section 2 are not our original contribution, we believe they are essential for providing readers who may be less familiar with this topic a foundational understanding. Including these concepts ensures clarity and a good presentation of our paper. However, we would like to shorten it slightly without hurting its readability.

Weakness 3: Thanks for pointing it out. In the deterministic setting, $\Delta$ is the gap between the initial function value and optimal value, which is bounded and can be assumed as a constant since the loss function is typically non-negative. Thus $M=\mathcal O(\Delta)$ is also a constant. For the stochastic setting, $M$ depends on $\frac{1}{\delta}$ and we provide the dependencies on other parameters: $\rho\le \mathcal O(\delta^2 \epsilon^2), \beta\le \mathcal O(\min\\{\frac{\delta\epsilon^2}{M^4},\frac{\rho}{M^2}\\}), \alpha\le \mathcal O(\min\\{\beta, \frac{\rho}{\ell(M+1)^2}, \frac{\rho}{M^2}, \frac{\delta }{\rho T},\frac{1}{\beta TM^2}\\})$ and $T\ge\Theta(\max\\{\frac{1}{\delta \alpha \epsilon^2},\frac{M^2}{\delta^2 \epsilon^4}\\})$.

Question 1: Minimizing a vector as in Eq. (1) means minimizing different objective functions simultaneously. This is a standard formulation in the context of multi-objective optimization as shown in MoCo, SDMGrad, FairGrad, etc.

Question 2: We have mentioned in lines 512-513 that the local smoothness is computed according to the method in Section H.3 in the paper, "Why gradient clipping accelerates training: A theoretical justification for adaptivity" with available code in https://github.com/JingzhaoZhang/why-clipping-accelerates. The local smoothness is computed as $\widehat{L}(x_t)=\max_{\gamma\in\{\delta,2\delta,...,1\}}\frac{\\|\nabla f(x_t+\gamma d)-\nabla f(x_t)\\|}{\\|\gamma d\\|},$ where $\delta\in(0,1)$ is a small value, $d=x_{t+1}-x_t$.

Question 3: Thanks for pointing it out. This is a typo here that $f_*$ should be $f_i^*$. We have fixed it in the revision.

Question 4: Thanks for pointing it out. For Theorem 1, $c_1,c_2,c_3$ are any fixed constant, we can set all of them to $1$. Then $F=\Delta+3$. In the deterministic setting, $\Delta$ is the gap between the initial function value and optimal value, which is bounded and can be assumed as a constant since the loss function is typically non-negative. If $\ell$ is the widely studied linear function, then we have $M=\mathcal O(\Delta)$ and [a] shows a total sample complexity of $\mathcal{O}(M^2\epsilon^{-2})$. Theorem 1 then requires $\alpha, \beta \le \mathcal O(M^{-2})$, thus it require $\mathcal{O}(M^3\epsilon^{-2})$. The additional complexity in our methods is introduced because we required smaller stepsize $\beta$ to update the CA direction which the CA direction is not needed in a single-task setting. However, in a deterministic setting, $M$ is a constant. Thus it should not be an issue.

Question 5: Yes, the generalized smoothness condition brings benefits in practice. Under the generalized smoothness condition, we design more complicated step sizes, which are smaller compared with methods for standard $L$-smoothness in order to bound the function values for all tasks. Otherwise, the training of MGDA with larger stepsizes may diverge. The relaxation of requirements on step sizes needs additional operations such as clipping and momentum, which changes the structure of MGDA and is not the focus of this paper.

Question 1: Good question. To the best of our knowledge, existing studies on iteration-wise CA distance are conducted under stochastic settings, with SDMGrad being a representative work. We are not aware of any deterministic variants. Additionally, we have evaluated the performance of MoCo-warm start, and the results on both Cityscapes and NYU-v2 datasets are provided below. As shown in the tables, the warm start strategy consistently enhances performance. The warm start procedure requires very low sample complexity, as it computes the gradients only once and reuses them throughout the gradient descent. Thus, it does not affect the total sample complexity as the main loop dominates. The warm start process is introduced to achieve iteration-wise CA distance.

Table: Multi-task supervised learning on Cityscapes dataset.

Table: Multi-task supervised learning on NYU-v2 dataset.

Besides, thank you for your suggestion. We have incorporated the sample complexity in Table 1 with the most relevant papers, including MoCo, SDMGrad, and MoDo, as these are the only works that examine the CA distance. For other papers that do not explore the CA distance or rely on dissimilar assumptions, we have marked their sample complexity as N/A.

Question 2: Thanks for pointing this out. It is OK to use the same sample but the union bound are similar and the term $K$ can not be moved. This is because in Eq 16 and 17 the term $K$ is introduced by the estimate error for each task. Even the tasks share the same sample, the estimate errors for each task are different thus the $K$ in the union bound is requried. The only difference is in Section C.4 that for any $t\le T$ and $i\in [3]$, the elements of $\varepsilon_{t,i}$ are dependent and it requires more efforts to bound this norm square. By using multiple samples, the elements of $\varepsilon_{t,i}$ are independent, which makes its norm square easy to bound.

Question 3: Good question! We have checked the stochastic variant of MGDA-FA with bounded variance assumption. It turns out that there will be additional error terms that are not easy to control. We provide a brief analysis here following the same steps in Theorem 10 (Appendix). Since we have the bounded variance assumption now, we can derive

$

\mathbb{E}[\langle w_t-w, \nabla F(x_t)^\top\nabla F(x_t)w_t\rangle]\leq\frac{1}{2\beta}\mathbb{E}[\|w_t-w\|^2-\|w_{t+1}-w\|^2]+\rho+\frac{\alpha K\ell(M+1)M^2}{2}+\beta(C_1^\prime)^2+\frac{2\beta\sigma_F^2}{\alpha^2}+\frac{4\sigma_F}{\alpha}.

$

Then the equation (34) will become

$

\mathbb{E}[F(x_{k+1})w-F(x_0)w]\leq\frac{\alpha}{\beta}+\alpha\rho T+\frac{\alpha^2K\ell(M+1)M^2T}{2}+\alpha\beta(C_1^\prime)^2T+\frac{2\beta\sigma_F^2 T}{\alpha}+4\sigma_F T.

$

As a result, we cannot get the result that $f_i(x_{k+1})-f_i^*\leq F$ since we cannot control the additional terms. Meanwhile, if we use a large batch $n_s$, the above inequality would become

$

\mathbb{E}[F(x_{k+1})w-F(x_0)w]\leq\frac{\alpha}{\beta}+\alpha\rho T+\frac{\alpha^2K\ell(M+1)M^2T}{2}+\alpha\beta(C_1^\prime)^2T+\frac{2\beta\sigma_F^2 T}{\alpha n_s}+4\frac{\sigma_F T}{\sqrt{n_s}}.

$

Then with an extremely large batch size $n_s=\mathcal{O}(T^2)$, it could converge but this selection is impractical and computationally consuming. Therefore, the analysis for the stochastic variant of MGDA-FA is not straightforward under generalized smoothness.

Question 4: Excellent insight! A warm start can indeed facilitate bilevel optimization. In this context, the inner problem typically produces an iterative decay of $\\|y_t-y(x_t)^*\\|$, where $x_t, y_t$ are variables of the outer and inner problem, respectively. $y(x_t)^*$ represents the optimal point of the inner problem at the $t$-th epoch. If a warm start is added before the bi-level main loop, $\\|y_0-y(x_0)^*\\|$ is already in a small magnitude, which makes bi-level optimization easier. Furthermore, this warm start process is not a MOO problem's simple structure. It can be applied to other problems such as bilevel optimization.

We thank the reviewer Wanu for the time and valuable feedback! Here are our responses.

Weakness 1: Thanks for pointing it out. $\mathcal{W}$ is the probability simplex over $[K]$. We have moved the definition from section 2.3 to Definition 3 in the revision.

Weakness 2: Thanks for the question. We believe that the selection in Theorem 2 is reasonable and here is the reason. Let us say we choose $\alpha, \beta, \rho=\epsilon^2$ and $T=\epsilon^{-4}$. Then the selection for $\rho$ becomes $\rho=\min\\{\mathcal{O}(\epsilon^2), \epsilon, \mathcal{O}(1), \mathcal{O}(\epsilon^2)\\}$. Then there is no contradiction since $\rho=\epsilon^2\ll\epsilon\ll 1$. We have noticed that the notations are not clear and we revise them as follows. Following your suggestion, we rewrite the selections for the parameters in Theorem 2: we choose $\rho\le \mathcal O(\epsilon^2), \beta\le \mathcal O(\min\\{\epsilon^2,\rho\\}), \alpha\le \mathcal O(\min\\{\beta, \rho, \frac{1}{\beta T}, \frac{1}{\rho T}\\})$ and $T\ge \max\\{\frac{1}{\alpha \epsilon^2},\frac{1}{\epsilon^4}\\}$ we can get the convergence. Thus we need to set $\alpha,\beta, \rho \le \mathcal O(\epsilon^2)$ and $T\ge \Theta(\epsilon^{-4})$. More details about the dependences on $M,\delta$ will be shown in the answer for weakness 4.

Weakness 3: For the deterministic setting, $M$ depends on the $\Delta$, which is the gap between the initial function value and optimal value. Since the loss function is typically non-negative, $\Delta$ is bounded by the initial function value and can be assumed as a constant. The scale of $M$ also depends on the $\ell$ function. We then show a fair comparison between our average CA distance methods (algorithms 1 and 4) with [a] when $\ell$ is a linear function. Then we have $M=\mathcal O(\Delta)$ and [a] shows a total sample complexity of $\mathcal{O}(M^2\epsilon^{-2})$. Our algorithm 1 requires $\mathcal{O}(M^3\epsilon^{-2})$. The additional complexity in our methods is introduced because we required smaller stepsize $\beta$ to update the CA direction while the CA direction is not needed in single-task setting. Our algorithm 4 requires $\mathcal{O}(M^5\epsilon^{-2})$ due to the employment of fast approximation. However, in the deterministic setting, $M$ is a constant. Thus it should not be an issue.

[a] Li, H., Qian, J., Tian, Y., Rakhlin, A., & Jadbabaie, A. (2024). Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36.

Weakness 4: Thanks for pointing this out. We first rewrite the selections of parameters: $\rho\le \mathcal O(\delta^2 \epsilon^2), \beta\le \mathcal O(\min\\{\frac{\delta\epsilon^2}{M^4},\frac{\rho}{M^2}\\}), \alpha\le \mathcal O(\min\\{\beta, \frac{\rho}{\ell(M+1)^2}, \frac{\rho}{M^2}, \frac{\delta }{\rho T},\frac{1}{\beta TM^2}\\})$ and $T\ge\Theta (\max\\{\frac{1}{\delta \alpha \epsilon^2},\frac{M^2}{\delta^2 \epsilon^4}\\})$. The scale of $M,\ell(M+1)$ also depends on the $\ell$ function. We then show a fair comparison between our average CA distance method with [a] when $\ell$ is a linear function. For stochstic settting, we then have that $M,\ell(M+1)=\mathcal O(\frac{\Delta}{\delta})$. Thus the total sample complexity in [a] is $\mathcal O(\delta^{-4}\epsilon^{-4})$. By choosing $\rho\le \mathcal O(\delta^2\epsilon^2),\beta\le \mathcal O(\delta^5\epsilon^2),\alpha\le \mathcal O(\delta^5\epsilon^2)$ and $T\ge \Theta(\delta^{-6}\epsilon^{-4})$, our sample complexity is $\mathcal O(\delta^{-6}\epsilon^{-4})$. The additional complexity in our methods is introduced because we required smaller stepsize $\beta$ to update the CA direction while the CA direction is not needed in single-task setting.

Weakness 5: Good observation. We speculate that the fast approximation may introduce substantial errors in practice, potentially leading to inaccuracies in the weight update process. Meanwhile, the experiment uses the stochastic variant of MGDA-FA. According to our response to your Question 3, the convergence analysis is not straightforward under stochastic settings. However, it is premature to conclude that this approach has limited utility. This fast approximation comes from a similar idea in FAMO [b] and their performance is satisfying because they apply a logarithmic loss technique. We can also use this logarithmic technique to enhance our performance. We have added this discussion in Section B.2.

[b] Liu, B., Feng, Y., Stone, P., & Liu, Q. (2024). Famo: Fast adaptive multitask optimization. Advances in Neural Information Processing Systems, 36.

Weakness 6: Thanks for pointing them out. We have revised all related typos.