PaperlayerView exact revision on arXiv

Source-linked AI summary

MGDA Converges under Generalized Smoothness, Provably

Qi Zhang, Peiyao Xiao, Shaofeng Zou, Kaiyi Ji

arXiv:2405.19440v5cs.LGmath.OCstat.ML

TL;DR

MOO methods have largely been analyzed under standard smoothness or bounded-gradient assumptions, which may not fit neural-network training. This paper analyzes deterministic and stochastic MGDA under generalized ℓ-smoothness, with average and iteration-wise CA-distance guarantees. The analysis gives sample-complexity bounds and shows MGDA-FA retains MGDA's performance guarantee with O(1) time and space.

  • Problem

    Existing MOO convergence analyses rely on standard L-smoothness or bounded gradients, while generalized-smoothness analyses have been limited to single-task optimization.

    Source: §1 · p. 2, §2.3 · p. 5

  • Method

    The paper analyzes MGDA under generalized ℓ-smoothness, including stochastic MGDA with double sampling, warm starts for iteration-wise CA distance, and the MGDA-FA variant.

    Source: §1.1 · pp. 2–3, §3.2 · p. 6

  • Results

    MGDA needs O(ϵ^-2) deterministic and O(ϵ^-4) stochastic samples for average CA distance, while iteration-wise distance requires O(ϵ^-11) and O(ϵ^-17), respectively; MGDA-FA matches MGDA's guarantee.

    Source: §1.1 · p. 3, §7 · p. 10

  • Takeaways & Limitations

    The analysis may provide insights for analyzing CAGrad, PCGrad, FairGrad, and FAMO under generalized smoothness.

    Source: §7 · p. 10

    The stochastic setting assumes unbiased stochastic gradients with variance bounded by σ² for every objective and x.

    Source: §4.2 · p. 8

Abstract

from arXiv · show

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$-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$-smooth loss functions, where $\ell$ 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$-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 $\epsilon$-accurate Pareto stationary point with a guaranteed $\epsilon$-level average CA distance (i.e., the gap between the updating direction and the CA direction) over all iterations, where totally $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-4})$ samples are needed for deterministic and stochastic settings, respectively. We prove that they can also guarantee a tighter $\epsilon$-level CA distance in each iteration using more samples. Moreover, we analyze an efficient variant of MGDA named MGDA-FA using only $\mathcal{O}(1)$ time and space, while achieving the same performance guarantee as MGDA.

1 INTRODUCTION

Multi-objective optimization must balance conflicting objectives, but existing convergence analyses rely on smoothness or gradient bounds that may not hold for neural networks. This paper extends MGDA convergence analysis to generalized ℓ-smooth MOO and studies its stochastic and efficient variants.

1 INTRODUCTION

  • Gradient conflict can let large-gradient objectives dominate updates, while existing analyses do not directly cover generalized-smooth MOO with potentially unbounded gradients or smoothness.The paper identifies a gap because prior generalized-smoothness analyses cover single-task optimization, not MOO.Source: §1 · pp. 1–2, §1.2 · p. 3

1.1 OUR CONTRIBUTIONS

  • Generalized ℓ-smoothness allows smoothness to depend on gradient norm and includes standard L-smooth and (L0, L1)-smooth assumptions, without requiring bounded gradients.The paper describes this as the first study of generalized smoothness in MOO.Source: §1.1 · p. 2
  • MGDA needs O(ϵ^-2) deterministic and O(ϵ^-4) stochastic samples for an ϵ-accurate Pareto stationary point and ϵ-level average CA distance.Iteration-wise CA distance requires O(ϵ^-11) and O(ϵ^-17) samples, respectively; MGDA-FA achieves MGDA's guarantees using O(1) time and space.Source: §1.1 · p. 3

1.2 RELATED WORKS

  • Prior generalized-smoothness work studied single-task optimization, while existing MOO methods rely on standard smoothness or bounded-gradient assumptions.The paper positions its analysis as addressing the resulting gap for generalized ℓ-smooth MOO.Source: §1 · p. 2, §1.2 · p. 3

2 PRELIMINARIES

The preliminaries define generalized smoothness and Pareto stationarity, then review MGDA and stochastic alternatives. They also define the conflict-avoidant direction and the distance used to measure its approximation.

2.1 GENERALIZED SMOOTHNESS

  • Generalized ℓ-smoothness bounds the Hessian norm by a non-decreasing function of gradient norm, includes (L0, L1)-smoothness, and does not require a bounded gradient.The paper notes that standard L-smoothness may fail in settings including neural-network training.Source: §2.1 · p. 4

2.2 PARETO CONCEPTS IN MULTI-OBJECTIVE OPTIMIZATION (MOO)

  • A Pareto stationary point has zero minimum norm among simplex-weighted combinations of the objective gradients; its ϵ-accurate version bounds that minimum by ϵ².The section distinguishes this non-convex target from Pareto optimality.Source: §2.2 · p. 4

2.3 EXISTING MOO ALGORITHMS

  • MGDA balances objectives by maximizing their minimum improvement, while stochastic MGDA variants address biased direction estimates through tracking or double sampling.The preliminaries note that existing MOO analyses rely on bounded gradients or standard L-smoothness, which does not cover generalized ℓ-smooth objectives.Source: §2.3 · p. 5

2.4 CONFLICT-AVOIDANT (CA) DIRECTION AND CA DISTANCE

  • The CA distance is the gap between an estimated update direction and the CA direction; prior methods guarantee it either on average or at every iteration.The section describes the CA direction as mitigating gradient conflict.Source: §2.4 · p. 5

3 MGDA ALGORITHMS UNDER GENERALIZED SMOOTHNESS

The algorithms adapt MGDA to generalized-smooth multi-objective problems through regularized weight updates, stochastic double sampling, and a fast approximation. Warm starts support iteration-wise CA-distance control, while the average-distance analysis does not require one.

3.1 MGDA WITH AND WITHOUT WARM START

  • Warm starts initialize the weights near the regularized optimum to support small CA distance at every iteration; they are unnecessary for an average-distance guarantee.The weight update uses projected gradient descent, and ℓ2 regularization makes the weight solution unique and Lipschitz continuous.Source: §3.1 · p. 6

3.2 STOCHASTIC MGDA WITH DOUBLE SAMPLING

  • Double sampling uses independent unbiased gradient estimates to make the stochastic weight-gradient estimator unbiased.The method retains a warm start for iteration-wise CA-distance control, but omits it when only average CA distance is required.Source: §3.2 · p. 6

3.3 MGDA WITH FAST APPROXIMATION

  • MGDA-FA approximates the weight update with a Taylor expansion whose remainder can be reduced by adjusting the step size.It computes the weighted model gradient in one backward pass without storing it, plus forward passes to evaluate F(x_{t+1}) for the weight update.Source: §3.3 · pp. 6–7
  • MGDA-FA reduces the weight-update cost from O(K) time and space to O(1) while retaining a theoretical guarantee.The variant updates objective weights using forward evaluations rather than storing all task gradients.Source: §3.3 · pp. 6–7

4 CONVERGENCE ANALYSIS UNDER AVERAGE CA DISTANCE

The analysis establishes average CA-distance convergence for deterministic and stochastic MGDA under generalized ℓ-smoothness. It gives deterministic and stochastic convergence guarantees, with stochastic analysis relying on bounded gradient variance and a stopping-time argument.

4 CONVERGENCE ANALYSIS UNDER AVERAGE CA DISTANCE

  • Generalized ℓ-smoothness includes standard L-smoothness and (L0, L1)-smoothness, and permits gradient norms to be unbounded.The analysis addresses the MOO setting, where combining task gradients makes existing single-objective adaptive methods inapplicable.Source: §4.1 · p. 7

4.1 DETERMINISTIC SETTING

  • O(ε^-2) samples suffice in the deterministic setting for an ε-accurate Pareto stationary point with an ε-level average CA distance.The theorem applies to twice-differentiable, lower-bounded objectives under generalized ℓ-smoothness, without requiring bounded gradients.Source: §4.1 · p. 7, §4 · p. 7
  • The deterministic proof uses bounded objective values to bound gradient norms, enabling convergence analysis despite potentially unbounded gradients.The proof maintains an upper bound on F(x_t)w and uses it to bound each objective gradient.Source: §4.1 · pp. 7–8

4.2 STOCHASTIC SETTING

  • O(ε^-4) samples suffice in the stochastic setting for an ε-stationary point, with high-probability convergence of the average CA distance.The analysis assumes bounded gradient variance and uses stopping time to bound function values and noise while preserving a zero-mean cumulative error.Source: §4.2 · p. 8

5 CONVERGENCE ANALYSIS UNDER ITERATION-WISE CA DISTANCE

The section strengthens average CA-distance results by establishing iteration-wise bounds. These tighter guarantees require warm starts and more samples; the stochastic analysis also requires mini-batches.

5 CONVERGENCE ANALYSIS UNDER ITERATION-WISE CA DISTANCE

  • Average CA-distance control does not provide a small CA distance at every iteration, motivating the stronger iteration-wise guarantee.The iteration-wise result uses a warm start; in the stochastic setting, mini-batches control per-iteration estimation error.Source: §5 · p. 9, §5.1 · p. 9, §5.2 · p. 9

5.1 DETERMINISTIC SETTING

  • O(ε^-11) samples achieve an ε-accurate Pareto stationary point with bounded iteration-wise CA distance in deterministic MGDA.The analysis requires smaller step sizes than the average-distance result because error terms accumulate in its decay argument.Source: §5.1 · p. 9
  • MGDA-FA retains the deterministic iteration-wise CA-distance guarantee, with O(ε^-11) sample complexity for Pareto stationarity.The fast-approximation analysis adds a remainder term bounded by the smallest step size.Source: §5.1 · p. 9

5.2 STOCHASTIC SETTING

  • With mini-batches and warm start, stochastic MGDA bounds iteration-wise CA distance by O(ε) with probability at least 1 − δ.The theorem uses batch size n_s = Ω(ε^-6) and T = Θ(ε^-11); the resulting sample complexity for Pareto stationarity is O(ε^-17).Source: §5.2 · p. 9

6 EXPERIMENTS

Experiments compare MGDA with warm start and other MOO methods on Cityscapes and NYU-v2 multi-task learning. The reported results emphasize balanced performance and a positive relationship between gradient norms and local smoothness.

6 EXPERIMENTS

  • MGDA with warm start is reported to have more balanced performance than the compared MOO methods on Cityscapes and NYU-v2.The experiments use Cityscapes’ semantic segmentation and depth-estimation tasks and NYU-v2’s segmentation, depth-estimation, and surface-normal tasks.Source: §6 · pp. 9–10, Table 2 · p. 10, Table 3 · p. 10
  • Experiments compare MGDA with warm start against MGDA, PCGrad, GradDrop, CAGrad, MoCo, MoDo, Nash-MTL, and FAMO.The comparison uses average per-task performance drop relative to the single-task baseline as an overall metric.Source: §6 · p. 10
  • The Cityscapes task results show a positive correlation between gradient norms and local smoothness.The study relates this observation to the motivation for analyzing generalized smoothness.Source: §6 · p. 10

7 CONCLUSION

The paper concludes that MGDA and its stochastic variant have convergence guarantees under generalized ℓ-smoothness, while MGDA-FA retains the same performance guarantee with O(1) time and space. It also reports a positive relationship between task gradient norms and local smoothness.

7 CONCLUSION

  • The conclusion presents generalized ℓ-smoothness convergence analysis for MGDA and its stochastic variant, and says MGDA-FA achieves the same guarantee using O(1) time and space.The authors also identify warm start as a way to control iteration-wise CA distance and suggest the analysis may inform other MOO algorithms.Source: §7 · p. 10

A NOTATION SUMMARY

B.1 RELATION BETWEEN GRADIENT NORMS AND THE LOCAL SMOOTHNESS

  • The Cityscapes task results show a positive correlation between gradient norms and local smoothness.Figure 2 plots local smoothness against gradient norm for Task 1 on the left and Task 2 on the right.Source: §B.1 · p. 14, Figure 2 · p. 14

B.2 RESULTS AND RUNNING TIME COMPARISON BETWEEN MGDA-WARM START AND MGDA-FA

The appendix compares MGDA-warm start with MGDA-FA on Cityscapes and examines warm start with other MOO methods. It also gives implementation settings and an algorithm listing for MGDA-FA.

B.2 RESULTS AND RUNNING TIME COMPARISON BETWEEN MGDA-WARM START AND MGDA-FA

  • MGDA-FA is reported as faster than MGDA-warm start, but its approximation may cause substantial weight-update errors in practice.The appendix also notes that convergence analysis of the stochastic variant is not revealed.Source: §B.2 · p. 14, Table 5 · p. 15

B.3 RESULTS OF OTHER MOO METHODS WITH WARM START

  • Warm start improves performance when applied to other MOO methods; MoDo-warm start exactly recovers the paper’s algorithm.The appendix evaluates MoCo-warm start on Cityscapes and NYU-v2.Source: §B.3 · p. 15, Table 6 · p. 15, Table 7 · p. 15

B.4 IMPLEMENTATION DETAILS

  • The implementation trains for 200 epochs and selects the best result from a grid search over N, α, and ρ, with β fixed at 0.5.Cityscapes uses batch size 8 and NYU-v2 uses batch size 2; the final measure averages test performance over the last 10 epochs. The reported metric Δm% is the average per-task performance drop versus the single-task baseline.Source: §B.4 · pp. 15–16

C ALGORITHM

  • The MGDA-FA listing initializes parameters and weights, applies warm start, updates model parameters, then updates weights using equation (6).The parameter update is shown as xt+1 = xt − α∇F(xt)wt.Source: C ALGORITHM · p. 16

D DETAILED PROOFS FOR AVERAGE CA DISTANCE

The appendix proofs address convergence under generalized smoothness by controlling function values, gradient norms, and update behavior. Additional proof fragments bound a probability event and develop ingredients for iteration-wise CA-distance analysis.

D.1 FORMAL VERSION AND PROOF OF THEOREM 1

  • Theorem 1’s proof strategy bounds objective values by induction, which bounds gradient norms and thereby controls the otherwise unbounded local smoothness.The appendix identifies a convergence-rate result for Algorithm 1 without warm start, but the supplied excerpt does not show its rate.Source: §D.1 · pp. 16–17

D.2 PROOF OF COROLLARY 1

  • The Corollary 1 proof follows the same setting as Theorem 1 and invokes the optimality condition for w* in an inequality.The supplied proof excerpt does not state the corollary’s conclusion.Source: §D.2 · p. 18

D.3 FORMAL VERSION AND ITS PROOF OF THEOREM 2

  • Theorem 2’s proof bounds the probability of the event {τ < T} by δ and concludes a probability bound of at least 1 − δ.The excerpt attributes intermediate bounds to Chebyshev’s and Markov’s inequalities and the union bound.Source: §D.3 · pp. 19–21

D.4 PROOF OF LEMMA 1

  • The Lemma 1 proof combines descent and weight-update inequalities, including terms for stochastic-gradient errors and projection.It takes expectations and sums the resulting inequality across iterations.Source: §D.4 · pp. 21–22

E DETAILED PROOFS FOR ITERATION-WISE CA DISTANCE

  • The iteration-wise CA-distance proofs use projected gradient descent with constant step size β on a ρ-strongly convex weight objective.One stated condition is bounded task gradients together with a bounded parameter-step length.Source: E DETAILED PROOFS FOR ITERATION-WISE… · pp. 23–24

E.1 PROOF OF THEOREM 3

Theorem 3’s proof selects parameters to obtain O(ϵ) CA distance in every iteration; the Theorem 4 proof establishes objective-gap bounds by induction.

E.1 PROOF OF THEOREM 3

  • Projected gradient descent on the strongly convex function J is used in the N-loop to obtain the inner iterate.The proof invokes a projected-gradient convergence result to select β′.Source: §E.1 · p. 26
  • O(ϵ) CA distance is achieved in every iteration with ρ = O(ϵ^2), β = O(ϵ^4), α = O(ϵ^9), and N = O(ϵ^-2).The proof also states that the inner iterate satisfies a distance bound of order O(ϵ).Source: §E.1 · p. 26

E.2 FORMAL VERSION AND ITS PROOF OF THEOREM 4

  • The Theorem 4 proof establishes by induction that each objective gap fi(xk) − f*i remains at most F for k < T.The proof uses α ≤ 1/ℓ(M+1) in its induction argument.Source: §E.2 · p. 27

E.3 FORMAL VERSION AND ITS PROOF OF THEOREM 5

Theorem 5’s proof uses an inner projected-gradient loop and parameter choices to obtain O(ϵ) CA distance at every iteration.

E.3 FORMAL VERSION AND ITS PROOF OF THEOREM 5

  • The proof bounds CA distance using the difference between the computed and optimal weight vectors, together with a √ρ term.The argument uses bounded objective gradients and a lemma to control the distance.Source: §E.3 · p. 28
  • The N-loop in Algorithm 4 runs projected gradient descent on the strongly convex function J.The proof invokes a projected-gradient convergence result for this inner loop.Source: §E.3 · p. 29
  • O(ϵ) CA distance is obtained in every iteration with ρ = O(ϵ^2), β = O(ϵ^4), α = O(ϵ^9), and N = Ω(ϵ^-2).The theorem proof states that the distance to the regularized inner solution is O(ϵ).Source: §E.3 · pp. 28–29

E.4 FORMAL VERSION OF ITS PROOF OF THEOREM 6

Theorem 6’s proof controls the stochastic weight-vector error with probability at least 1 − δ, yielding an O(ϵ) CA-distance bound at each iteration.

E.4 FORMAL VERSION OF ITS PROOF OF THEOREM 6

  • The stated stochastic sample-size condition is ns = Ω(ϵ^-6), alongside the lower bound shown for ns in the proof.The condition appears with the proof’s parameter choices and δ-dependent terms.Source: §E.4 · p. 29
  • Theorem 12 states a per-iteration guarantee for every t ≤ T under Assumptions 1, 2, and 3.The proof first controls the stochastic inner-loop error and then relates it to CA distance.Source: §E.4 · pp. 29, 32
  • With probability at least 1 − δ, the per-iteration difference between the computed and optimal gradient-weighted directions is O(ϵ) when ρ = O(ϵ^2).The proof derives this from a high-probability bound on the weight-vector error.Source: §E.4 · p. 32

Related papers

Loading 2405.19440v5…