Paper deep dive
MOON: Multi-Objective OrthoNormalized Updates for Multitask Learning
Shiji Zhou, Kunlin Lyu, Lei Zhang, Ruodong Wang, Yifan Sun
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-objective optimization (MOO) has demonstrated significant success in multi-task learning by mitigating task conflicts through gradient manipulation. However, most existing methods flatten model parameters into vectors and perform gradient manipulation under Euclidean geometry, thereby overlooking the matrix structure prevalent in modern architectures such as Transformers. In this paper, we show that gradient manipulation in Euclidean space does not generally yield the steepest descent direction under matrix geometry, potentially limiting optimization efficiency. Drawing from the theory of steepest descent for matrix-valued parameters, we propose MOON (Multi-Objective OrthoNormalized Updates), which performs gradient manipulation under spectral--nuclear norm geometry and uses the orthonormalized manipulated gradient for parameter updates. Theoretically, for smooth non-convex objectives, we establish convergence of the averaged Pareto-stationarity measure at rates of $\mathcal{O}(T^{-1/2})$ in the deterministic setting and $\mathcal{O}(T^{-1/4})$ under stochastic gradients. Empirical results across various benchmarks show that MOON consistently improves both optimization efficiency and final multi-task performance. Our code is available at this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2608.11749v1
- Canonical: https://arxiv.org/abs/2608.11749v1
Trouble viewing inline? Open PDF directly →
Full Text
88,746 characters extracted from source content.
Expand or collapse full text
MOON: Multi-Objective OrthoNormalized Updates for Multitask Learning Shiji Zhou 1,2,3 Kunlin Lyu 4 Lei Zhang 1 Ruodong Wang 4 Yifan Sun 2,4,∗ 1 Institute of Artificial Intelligence, Beihang University 2 Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, Beihang University 3 Beijing Academy of Artificial Intelligence (BAAI) 4 Center for Applied Statistics, School of Statistics, Renmin University of China ∗ Corresponding author Abstract Multi-objective optimization (MOO) has demonstrated significant success in multi-task learning by mitigating task conflicts through gradient manipulation. However, most existing methods flatten model parameters into vectors and perform gradient manipulation under Eu- clidean geometry, thereby overlooking the matrix structure prevalent in modern architectures such as Transformers. In this paper, we show that gradient manipulation in Euclidean space does not generally yield the steepest descent direction under matrix geometry, potentially lim- iting optimization efficiency. Drawing from the theory of steepest descent for matrix-valued parameters, we propose MOON (Multi-Objective OrthoNormalized Updates), which performs gradient manipulation under spectral–nuclear norm geometry and uses the orthonormalized manipulated gradient for parameter updates. Theoretically, for smooth non-convex objectives, we establish convergence of the averaged Pareto-stationarity measure at rates ofO(T −1/2 ) in the deterministic setting andO(T −1/4 ) under stochastic gradients. Empirical results across various benchmarks show that MOON consistently improves both optimization efficiency and final multi-task performance. Our code is available at https://github.com/KunlinLyu/MOON. Introduction A wide range of practical problems in machine learning are inherently multi-objective, where the objectives often conflict and must be traded off [Sener and Koltun, 2018, Peitz and Hotegni, 2025]. In deep learning, task conflicts often manifest as gradient conflicts, with task gradients exhibiting competing directions during optimization. Multi-objective optimization (MOO) methods [Zitzler and Thiele, 1999] mitigate task-gradient conflicts via gradient manipulation and have achieved great success in multi-task learning [Sener and Koltun, 2018, Yu et al., 2020, Navon et al., 2022, Liu et al., 2024]. Existing MOO methods such as MGDA [Sener and Koltun, 2018], PCGrad [Yu et al., 2020], FAMO [Liu et al., 2024], and other variants [Liu et al., 2021a,b, Navon et al., 2022] typically flatten model parameters into a single vector and then perform gradient manipulation in this Euclidean vector space. However, modern architectures, such as Transformers [Vaswani et al., 2017], are dominated by matrix-valued parameters. Blindly flattening all parameters into vectors ignores the linear-mapping structure of matrix-valued parameters and may fail to identify the steepest descent 1 arXiv:2608.11749v1 [cs.LG] 12 Aug 2026 direction under matrix geometry. This motivates MOO methods tailored to network architectures with matrix-valued parameters. One possible approach is to combine conventional MOO methods with matrix-aware optimizers such as Muon [Jordan et al., 2024], and MuonClip [Team et al., 2026], which exploit matrix structure through preconditioning or orthonormalized updates. However, conventional MOO manipulates gradients under Euclidean geometry, whereas matrix-aware optimizers apply structure-preserving transformations induced by matrix geometry. Naively combining them, therefore, lacks a consistent geometry and creates a theoretical gap between their underlying assumptions, creates a mismatch between their underlying optimization principles. Moreover, establishing MOO convergence under this matrix geometry is nontrivial. Since orthonormalization discards the singular-value magnitudes of the aggregated gradient, standard Euclidean descent analyses based on squared gradient norms are no longer directly applicable. The analysis must instead characterize Pareto stationarity under matrix geometry and exploit spectral–nuclear norm duality to connect the orthonormalized direction with optimization progress. To address these challenges, we propose Multi-Objective OrthoNormalized Updates (MOON), a geometrically consistent framework for multi-objective optimization with matrix-valued parameters [Bernstein and Newhouse, 2024]. Starting from simultaneous matrix-smooth upper bounds of the objectives, we formulate the selection of a common descent direction as a spectral-norm- regularized minimax problem. Through spectral–nuclear norm duality, the corresponding dual problem determines the task weights by minimizing the nuclear norm of the weighted aggregate gradient, while the solution to the primal problem is given by its polar factor. This formulation provides a principled connection between multi-objective gradient manipulation and orthonormalized matrix updates, distinguishing MOON from conventional MOO methods based on Euclidean geometry. For smooth non-convex objectives, we establish convergence of the averaged Pareto- stationarity measure at rates ofO(T −1/2 ) under deterministic gradients andO(T −1/4 ) under unbiased stochastic gradients. Extensive experiments further demonstrate that MOON accelerates optimization and achieves competitive or improved final performance across multiple benchmarks. Our main contributions are: (1) We propose MOON, a structure-aware MOO method. MOON is derived by our analysis of multi-objective steepest descent for matrix values, providing a geometrically consistent update for modern architectures. (2) We establish convergence to Pareto stationarity for smooth non-convex objectives, where MOON attains anO(T −1/2 ) rate under exact gradients and anO(T −1/4 ) rate under unbiased stochastic gradients with bounded noise. (3) We conduct extensive experiments on diverse multi-task scenarios with various architectures, demonstrating faster optimization and competitive or improved final performance compared with representative MOO baselines. Background Multi-Objective Optimization. Multi-objective optimization (MOO) aims to optimize multiple objectives simultaneously [Zitzler and Thiele, 1999]: min θ L(θ) = (ℓ 1 (θ),...,ℓ m (θ)) ⊤ ,(1) wherem≥2 denotes the number of objectives, andℓ i :R n → Ris thei-th loss function. Denote ∆ m as the (m−1)-dimensional probability simplex. The concept of Pareto optimality/stationarity [Cust ́odio et al., 2011] is introduced to determine whether a solution to MOO is optimal/critical. 2 Definition 1. Pareto Optimality: For any two solutionsθ,θ ′ , we say thatθdominatesθ ′ , denoted asθ ≺ θ ′ orθ ′ ≻ θ, ifℓ i (θ)≤ ℓ i (θ ′ ) for alli, and there exists anisuch thatℓ i (θ)< ℓ i (θ ′ ). A solutionθ ∗ is called Pareto optimal if it is not dominated by any other solution. Pareto Stationary: A solutionθis called Pareto stationary if there exists someλ∈∆ m such that P m i=1 λ i ∇ θ ℓ i (θ) = 0. The typical Multiple Gradient Descent Algorithm (MGDA) method [Sener and Koltun, 2018] has been shown to be the steepest method for MOO Fliege and Svaiter [2000]. Specifically, under the assumption ofL-smoothness with respect to the∥·∥ 2 norm, in each iterationt, MGDA aims to find a directiond t to maximize the minimum decrease in losses by solving the following subproblem: d t = arg min d∈R d max i∈[m] ∇ℓ i (θ t ) ⊤ d + L 2 ∥d∥ 2 2 .(2) The right-hand side∇ℓ i (θ t ) ⊤ d+ L 2 ∥d∥ 2 2 is actually the quadratic upper bound of the objective decreaseℓ i (θ t +d)−ℓ i (θ t ). MOO aims to optimize all the objectives simultaneously, and mathemat- ically to maximize the minimum objective decrease, which formulates the subproblem above. Other MOO methods such as PCGrad Yu et al. [2020], CAGrad Liu et al. [2021a] and other variants Zhou et al. [2022], Navon et al. [2022], Fernando et al. [2023], He et al. [2024] also share a similar idea of seeking a mutual descent direction by optimizing towards some specific upper bounds. Steepest Descent via Orthonormalized Updates. In modern neural network architectures, such as Transformer, matrix parameters are fundamental components. Suppose the objectiveL:R p×q → RisL-smooth with respect to the spectral norm∥·∥ S ∞ . Then L admits an upper bound that is quadratic in the spectral norm[Bernstein and Newhouse, 2024]. L(Θ)≤L(Θ ′ ) +⟨∇L(Θ ′ ), Θ− Θ ′ ⟩ + L 2 ∥Θ− Θ ′ ∥ 2 S ∞ .(3) By minimizing this quadratic upper bound, we obtain the steepest descent under the spectral norm. Proposition 1 (Steepest Descent for Matrix Parameters Bernstein and Newhouse [2024]). In each iteration t, steepest descent under the spectral norm aims to solve the following subproblem: ∆Θ t = arg min ∆Θ ⟨∇L(Θ t ), ∆Θ⟩ + L 2 ∥∆Θ∥ 2 S ∞ ,(4) where ⟨·,·⟩ denotes the Frobenius inner product. From Bernstein and Newhouse [2024] we know that, if∇L(Θ t ) has a reduced SVD given by ∇L(Θ t ) =U t Σ t V ⊤ t , the subproblem(4)is solved with a step sizeα t =Tr(Σ t ) =∥∇L(Θ t )∥ S 1 /L and an update: ∆Θ t =−α t ·U t V ⊤ t .(5) This result highlights a fundamental difference between steepest-descent updates for matrix- valued parameters and those derived under Euclidean vector geometry. Whereas the Euclidean gradient preserves the original singular-value magnitudes, the spectral-norm steepest-descent di- rection is characterized by the polar factorU t V ⊤ t , which preserves the singular subspaces while normalizing the nonzero singular values. Consequently, the resulting direction is less dominated by a few large singular components, while its overall update magnitude can be controlled separately by the learning rate. 3 Matrix-aware optimizers such as Shampoo [Gupta et al., 2018] and Muon [Jordan et al., 2024] have recently attracted increasing attention for exploiting matrix structure during optimization. Shampoo constructs structured preconditioners from gradient statistics, whereas Muon applies Newton–Schulz iterations to a momentum-smoothed gradient matrix to efficiently approximate its polar factor without an explicit singular value decomposition. Empirical studies have demonstrated the effectiveness and optimization efficiency of this strategy in large-scale Transformer training in large language models [Liu et al., 2025, Team et al., 2026]. Multi-Objective Orthonormalized Updates Although solving the Euclidean-norm minimax problem (Equation 2) yields the steepest descent direction in the Euclidean space, this direction may not be the steepest descent direction in the native matrix space of the matrix-valued parameters—such as the formulation shown in Equation 4. Consequently, existing methods struggle to adapt to the training of modern neural network architectures. Therefore, we extend the multi-objective optimization framework to matrix-valued parameters. For clarity, we present the derivation using a single matrix-valued parameter. For networks containing multiple matrix-valued parameter blocks, the same construction is applied blockwise. Suppose that for each objectiveℓ i :R p×q → Rthat isL-smooth with respect to the spectral norm∥·∥ S ∞ , we assume that an updateΘ t+1 =Θ t − αW t is performed at steptand derive its quadratic upper bound from Equation (3) ℓ i (Θ t+1 )≤ ℓ i (Θ t )− α⟨∇ℓ i (Θ t ),W t ⟩ + Lα 2 2 ∥W t ∥ 2 S ∞ .(6) Similar to Equation 2, we seek a mutual update direction in the matrix space that minimizes the worst-case upper bound. Thus, we aim to solve the following problem. Proposition 2. Letα ≤1/L. Minimizing the common upper bound is equivalent to solving the following spectral-norm-regularized minimax problem: min W t max i −⟨∇ℓ i (Θ t ),W t ⟩ + 1 2 ∥W t ∥ 2 S ∞ .(7) Consequently, we derive the quadratic upper bound for MOO with matrix parameters, which distinguishes our approach from traditional MOO methods. Since the primal problem (7) is difficult to solve, we usually consider the following dual problem. Proposition 3. The dual problem of (7) is min z∈∆ m 1 2 ∥ m X i=1 z i,t ∇ℓ i (Θ t )∥ 2 S 1 ,(8) where ∆ m denotes the probability simplex. Assume the optimum of the dual (8) isz ∗ and the manipulated gradientG t = P m i=1 z ∗ i,t ∇ℓ i (Θ t ) has full rank. The exact optimal solution of (7) is given by c W t = C·U t V ⊤ t , whereC=∥ P m i=1 z ∗ i,t ∇ℓ i (Θ t )∥ S 1 is the nuclear norm. IfC= 0, thenΘ t is Pareto stationary, and we set c W t =W t =0; otherwise, the following construction applies.U t ,V t are the left and right (compact) singular matrices of the manipulated gradient G t . 4 Proposition 3 derives the dual of problem (7) and shows how to recover the exact primal solution from the dual optimum. ForC >0, the orthonormalized direction used in Algorithm 1 is W t =U t V ⊤ t = 1 C c W t .Thus,W t retains the direction of the exact minimax solution, while the update magnitude is controlled separately by the learning rate α in Step 6. Remark: Comparison with Euclidean MOO methods. For a fixed iterateΘ t , define the weighted aggregate gradient asG t (z) = P m i=1 z i ∇ℓ i (Θ t ),z ∈∆ m .Convexity and spectral–nuclear norm duality can imply the optimization meaning of its nuclear norm (Appendix A.2): z ⊤ L(Θ t )− min Θ∈Ω z ⊤ L(Θ)≤ O ∥G t (z)∥ S 1 .(9) Thus, ∥G t (z)∥ S 1 provides a matrix-geometric certificate of the scalarized suboptimality at Θ t . Letz MOON t be an exact minimizer of the nuclear-norm dual problem in Equation(8), and let z E t ∈∆ m denote the weights obtained by a Euclidean min-norm method such as MGDA. Sincez E t is feasible for the MOON dual problem, the optimality of z MOON t gives G t z MOON t S 1 ≤ G t z E t S 1 .(10) Therefore, at the same iterate, the exact MOON weighting provides a no-looser nuclear-norm- dependent certificate than Euclidean min-norm weighting. Define the corresponding certificate gap as gap t := G t z E t S 1 − G t z MOON t S 1 ≥ 0.(11) For a fixed sequence of iterates, the difference between the corresponding certificate terms is ∆ cert = 1 T T X t=1 gap t ≥ 0,(12) with a strict inequality whenever the Euclidean weighting is not nuclear-norm optimal at least at one iterate 1 . Practical Implementation Applying the exact MOON formulation to large-scale training presents three practical challenges: fluctuations in the aggregate gradient, the cost of exact polar-factor computation, and the inner- loop optimization required to solve the dual problem (8). To address these challenges, practical MOON incorporates three components: (1) gradient momentum to stabilize the aggregate gradient across iterations, (2) Newton–Schulz iterations to efficiently approximate its polar factor, and (3) a single-step online update to track the dual task weights. Together, these components yield the practical MOON procedure summarized in Algorithm 1. Gradient Momentum. At iterationt, MOON constructs the weighted aggregate gradient G t = P m i=1 z i,t ∇ℓ i (Θ t ).Because both the stochastic task gradients and the task weights may change over time, directly constructing the matrix-aware update fromG t can lead to substantial iteration-to-iteration variation. We therefore maintain an exponential moving average M t = (1− μ)M t−1 + μG t ,0 < μ≤ 1.(13) The momentum matrix filters short-term variations in the aggregate gradient and provides a more stable matrix signal for constructing the subsequent orthonormalized direction. 1 We provide a case study to show this advantage in Appendix E 5 Algorithm 1 Multi-Objective OrthoNormalized updates 1:Input: Initial parameterΘ 1 ,M 0 ←0, loss functionsℓ i m i=1 , learning rateα,β, momentum 0 < μ≤ 1, weight decay of logits update γ, ξ 1 ← 0. 2: for t = 1 to T do 3:Normalize weight z t ← Softmax(ξ t ) 4:Compute composite gradient: G t = m X i=1 z i,t ∇ℓ i (Θ t ) 5:Compute momentum: M t = (1− μ)M t−1 + μG t 6:Perform orthonormalization on momentum by: W t = U t V ⊤ t (approximated by Newton-Schulz) 7:Update model parameter Θ t+1 = Θ t − αW t 8:Update weight logits by: ξ t+1 = ξ t − β(δ t + γξ t ) where δ t = [⟨W t ,∇ℓ 1 (Θ t )⟩,...,⟨W t ,∇ℓ m (Θ t )⟩] ⊤ 9: end for Polar-Factor Approximation. Given the momentum matrixM t , MOON uses its polar factor as the matrix-aware update direction: W t = Polar(M t ).(14) Since computing the exact polar factor through singular value decomposition can be expensive, we use a finite number of Newton–Schulz iterations to approximatePolar(M t ) similar to previous works Jordan et al. [2024], Bernstein and Newhouse [2024], Bj ̈orck and Bowie [1971], Kovarik [1970]. By convention, we define Polar(0) = 0, so that W t = 0 whenever M t = 0. Online Approximation of the Dual Weights. Solving the nuclear-norm dual problem(8) would introduce an expensive inner optimization loop. We instead use a single online update to track its solution, following the approximation strategy of FAMO [Liu et al., 2024]. We use the following momentum-based, scale-normalized surrogate direction for tracking the dual weights.: δ t = ∇ℓ 1 (Θ t ),W t ,...,⟨∇ℓ m (Θ t ),W t ⟩ ⊤ .(15) To maintain the simplex constraint, we parameterize the task weights using logits and update ξ t+1 = ξ t − β (δ t + γξ t ),z t+1 = Softmax ξ t+1 ,(16) whereβis the weight update stepsize, andγregularizes the logits. It provides an efficient momentum- based approximation to the exact dual solution while ensuring z t+1 ∈ ∆ m . 6 Convergence Analysis We analyze the convergence of MOON for smooth non-convex objectives. For anyΘ, define the nuclear-norm Pareto-stationarity measure G(Θ) := min z∈∆ m m X i=1 z i ∇ℓ i (Θ) S 1 .(17) In the unconstrained setting,G(Θ) = 0 if and only ifΘis Pareto stationary. We therefore study the averaged measure 1 T P T t=1 G(Θ t ). We first consider the deterministic setting. Theorem 1 (Deterministic Convergence). Suppose that each objectiveℓ i :R p×q → RisL-smooth with respect to the spectral norm. Assume that there exist constantsH >0 andB >0, independent of bothTandt, such thatmax t∈[T +1] max i∈[m] ∥∇ℓ i (Θ t )∥ S 1 ≤ H andmax t∈[T +1] max i∈[m] |ℓ i (Θ t )|≤ B. Chooseα= q B LT ,β= 1 mHT and 0< γ < mHT. Then, for every fixedμ ∈(0,1], the iterates generated by Algorithm 1 satisfy 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ O(T −1/2 ). The detailed proof is provided in Appendix A.3. Consequently, we demonstrate that our algorithm achieves a convergence rate ofO(1/ √ T), showing that MOON converges to Pareto stationarity at a standard sublinear rate for smooth non-convex optimization. We next consider unbiased stochastic task gradients. Theorem 2 (Stochastic Convergence). Under the same assumption as Theorem 1. We assume that the stochastic gradient estimator is unbiased and has variance bounded byσ. Choosingα= q μB TL , β= 1 (H+ √ mρσ)mT , 0< γ <(H+ √ mρσ)mTandμ=min √ LB σρ √ T ,1, whereρ:= p minp,q, then the iterations of Algorithm 1 satisfy 1 T T X t=1 E min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤O(1/T 1/4 ).(18) The detailed proof is provided in Appendix A.4. The expected Pareto-stationarity measure of MOON satisfiesO(T −1/4 ) bound. This slower rate reflects the additional error introduced by gradient noise and its interaction with momentum, and is also standard under stochastic gradients. Related Work Multi-objective Optimization. Multi-objective optimization (MOO) optimizes multiple tasks simultaneously, with the central challenge of resolving conflicts among task gradients [Sener and Koltun, 2018, Yu et al., 2020, Liu et al., 2021a, Navon et al., 2022, Liu et al., 2024]. Methods most relevant to our work follow two main lines. Loss balancing approaches [Kendall et al., 2018, Liu et al., 2019, Lin et al., 2021] adjust objective weights using loss statistics, optimizing an explicit weighted objective whose update is a linear combination of task-specific updates. These methods are often motivated by empirical heuristics and have limited theoretical support. Gradient manipulation methods [Sener and Koltun, 2018, Yu et al., 2020, Liu et al., 2021a,b, Navon et al., 2022, Fernando 7 et al., 2023, Liu et al., 2024] instead modify task gradients to obtain a common update direction that balances optimization across tasks. They generally provide stronger theoretical guarantees and often achieve better performance than loss balancing. However, existing methods typically flatten all parameters into a single vector, preventing them from attaining the steepest descent direction in the native non-Euclidean geometry of structured parameters. Our method preserves the matrix structure of the parameters and performs gradient manipulation directly in this geometry, improving both training efficiency and performance. Optimization for matrix-valued parameters. Modern architectures such as Transformers [Vaswani et al., 2017] are dominated by matrix-valued parameters, motivating optimizers that exploit this structure. K-FAC approximates layerwise Fisher blocks using Kronecker factors [Martens and Grosse, 2015]; Adafactor factorizes row- and column-wise second moments to reduce memory usage [Shazeer and Stern, 2018]; and Shampoo uses tensor-structured preconditioners to improve conditioning and accelerate convergence [Gupta et al., 2018]. Muon instead approximately orthog- onalizes momentum matrices for hidden-layer weights, producing efficient matrix-aware updates [Jordan et al., 2024]. Its theoretical properties have been studied from complementary perspectives: Li and Hong establish convergence guarantees [Li and Hong, 2025], while Kovalev interprets gradient orthogonalization as non-Euclidean trust-region optimization [Kovalev, 2025]. Subsequent work improves the efficiency, stability, and scalability of Muon. MuonBP reduces distributed communication through block-periodic orthogonalization [Khaled et al., 2025], while Polar Express develops GPU-friendly matrix-sign iterations for efficient polar-factor computation [Amsel et al., 2026]. MuonClip improves large-model training stability by controlling attention-logit growth through QK clipping [Team et al., 2026], and large-scale studies further demonstrate Muon’s practical efficiency and scalability in language-model pretraining [AI et al., 2025, Liu et al., 2025]. Despite these advances, such methods optimize a single aggregate objective and do not directly address conflicts among task objectives. MOON extends matrix-aware optimization to the multi- objective setting by combining task gradients according to the geometry of matrix-valued parameters and applying orthonormalized updates. This preserves parameter structure while resolving task conflicts, improving training efficiency and final performance in our experiments. Experiments In this section, we conduct experiments with MOON on several benchmarks to evaluate the performance and convergence. Our experiments cover simulation, multi-task scene understanding, classification, and regression. Experimental Setup. We consider 5 benchmarks widely used in multi-task learning research: MultiMNIST (2 tasks) [Sabour et al., 2017], NYU-v2 (3 tasks) [Silberman et al., 2012], CityScapes (2 tasks) [Cordts et al., 2016], QM9 (11 tasks) [Blum and Reymond, 2009] and CelebA (40 tasks) [Liu et al., 2015]. We compare the proposed method with 12 multi-objective optimization baselines: Single-task learning (STL), Linear Scalarization (LS), a scale-invariant baseline (SI) that applies equal weighting to the log losses, Random Loss Weighting (RLW) [Lin et al., 2021], Dynamic Weight Average (DWA) [Liu et al., 2019], Uncertainty Weighting (UW) [Kendall et al., 2018], MGDA [Sener and Koltun, 2018], PCGrad [Yu et al., 2020], CAGrad [Liu et al., 2021a], IMTL-G [Liu et al., 2021b], Nash-MTL [Navon et al., 2022], FAMO [Liu et al., 2024]. We discuss each experiment in the following subsections. 2 2 For more details about these experiments, see Appendix F. 8 Method SegmentationDepthSurface Normal ∆m% ↓ mIoU↑ Pix Acc↑ Abs Err↓ Rel Err↓ Angle Dist↓Within t ◦ ↑ Mean Median 11.25 22.5 30 STL38.30 63.760.67540.2780 25.01 19.21 30.14 57.20 69.15 LS39.29 65.330.54930.2263 28.15 23.96 22.09 47.50 61.08 5.59 SI38.45 64.270.53540.2201 27.60 23.37 22.53 48.57 62.32 4.39 RLW37.17 63.770.57590.2410 28.27 24.18 22.26 47.05 60.62 7.78 DWA39.11 65.310.55100.2285 27.61 23.18 24.17 50.18 62.39 3.57 UW36.87 63.170.54460.2260 27.04 22.61 23.54 49.05 63.65 4.05 MGDA28.40 58.240.59790.233525.00 19.49 29.56 56.84 69.11 1.23 PCGRAD39.22 65.980.53730.2273 27.27 23.08 23.17 49.23 62.98 3.40 GradDrop39.39 65.120.54550.2279 27.48 22.96 23.38 49.44 62.87 3.58 CAGrad39.00 65.770.55610.2135 26.30 21.53 25.86 52.47 65.65 -0.12 IMTL-G39.35 65.600.54260.2256 26.02 21.19 26.20 53.13 66.24 -0.76 NashMTL40.13 65.930.52610.2171 25.26 20.08 28.40 55.47 68.15 -4.04 FAMO36.41 63.200.54060.2182 25.0119.1430.22 57.45 69.37 -4.11 MOON (Ours) 39.4167.030.48910.2091 25.61 20.27 28.89 54.87 67.32-4.63 Table 2: Results on NYU-v2 (3 tasks) dataset. Each experiment is repeated over 3 random seeds and the mean is reported. The best average result is marked in bold. The task specific metrics and the average performance drop ∆m% are reported. A Toy Case To better understand why we cannot directly apply structure-aware optimizers such as Muon [Jordan et al., 2024] to existing MOO methods, we design a toy experiment to provide an intuitive illustration. In this experiment, we construct a 2-task optimization problem based on a multi-objective least-squares formulation. Given two 6-dimensional vectorsxandy, we define two objectives L 1 = 1 6 ∥Θx−y∥ 2 2 andL 2 = 1 6 ∥Θx+y∥ 2 2 over a matrix parameterΘ∈ R 6×6 . We optimizeΘusing three methods: (i) MGDA [Sener and Koltun, 2018], (i) MGDA with Muon optimizer [Jordan et al., 2024] applied directly, and (i) MOON. Then we plot the average of the two losses during the 1500-step optimization in Figure 1. Figure 1 shows the average loss of the two tasks over training steps in this toy experiment. MOON converges faster and reaches a lower final average loss, indicating a more balanced optimization on matrix-valued parameters. In contrast, directly applying Muon to MGDA fails to achieve the same improvement. Multi-task Classification We evaluate our method on MultiMNIST [Sabour et al., 2017] with Vision Transformer (ViT) [Dosovitskiy et al., 2021] backbone to assess convergence and performance under matrix-structured parameters. The ViT contains matrix-valued weights in the Transformer encoder (attention projec- tions and MLP linear layers). ViT is composed of 76.88% matrix parameters. We treat classifying the left and right digits as two tasks, reporting per-task cross-entropy training loss for convergence and test accuracy for performance. An additional classification experiment is conducted on CelebA, adopting a CNN backbone with 99.46% learnable convolutional weights treated as matrix parameters. In our experiments, we follow the treatment of convolutional weights in Muon [Jordan et al., 2024], converting 4D convolutional parameters into matrices by flattening the last three dimensions. It 9 030060090012001500 Step 8 12 16 20 24 Average Loss MGDA MGDA+Muon MOON Figure 1: Average loss curve on the toy case. 020406080100 Epoch 2 1.5 1 0.5 0.2 0.1 Training Loss FAMO MGDA Ours (a) ViT left task 020406080100 Epoch 2 1.5 1 0.5 0.2 0.1 Training Loss FAMO MGDA Ours (b) ViT right task Figure 2: Convergence of per-task training cross-entropy losses vs. training epochs on MultiMNIST. evaluates training efficiency and performance with a large number of objectives (40 tasks). In the MultiMNIST experiment, we observe from Figure 2 that our method reduces the training loss for both tasks more rapidly in the early stage and maintains a consistent advantage throughout training. Table 1 reports the test accuracies for the two classification tasks and their average. MOON achieves the best performance on both tasks and the highest average accuracy among all compared MOO methods. The right-hand side of Table 3 shows that MOON achieves performance comparable to state-of-the-art methods on the 40-task CelebA benchmark, further supporting the results. Multi-task Scene Understanding We apply MOON to multi-task scene understanding and evaluate it on the NYU-v2 [Silberman et al., 2012] and CityScapes [Cordts et al., 2016] benchmarks. We adopt the SegNet-MTAN architecture Badrinarayanan et al. [2017], Liu et al. [2019], a standard backbone for multi-task dense prediction. In this model, matrix-structured parameters or convolutional filters arise in the shared SegNet 10 MethodLeft Acc Right Acc Average Acc MGDA95.5894.1094.84 PCGrad94.2693.6093.93 CAGrad95.6594.7295.19 IMTL-G94.5794.4394.50 Nash-MTL95.3394.3894.86 FAMO95.8994.8895.39 MOON (Ours)95.9995.3195.65 Table 1: Test accuracy (%) on MultiMNIST (2 tasks). Per-task accuracies (left/right) and their average are reported. CityScapesCelebA Method SegmentationDepth ∆m% ↓ ∆m% ↓ mIoU↑ Pix Acc↑ Abs Err↓ Rel Err↓ STL74.01 93.160.012527.77 LS70.95 91.730.016133.8314.11 6.28 RLW74.57 93.410.015847.7924.38 5.22 DWA75.24 93.520.016044.3721.45 6.95 UW72.02 92.850.014030.135.895.78 MGDA69.60 91.870.013436.0511.02 10.93 PCGrad75.13 93.480.015442.0718.29 6.65 GradDrop75.27 93.530.015747.5423.73 7.80 CAGrad75.16 93.480.014137.6011.64 6.20 IMTL-G75.33 93.490.013538.4111.10 4.67 NashMTL75.41 93.660.012935.026.824.97 FAMO72.48 92.560.014829.526.934.72 MOON (Ours) 78.6194.360.012631.411.544.65 Table 3: Results on CityScapes (2 tasks) and CelebA (40 tasks) dataset. Each experiment is repeated over 3 random seeds and the mean is reported. The best average result is marked in bold. Task-specific metrics and the average performance drop∆m% are reported. 04080120160200 Epoch 0 20 40 60 Performance Drop FAMO MGDA Ours (a) NYU-v2 020406080100 Epoch 0 40 80 120 160 Performance Drop FAMO MGDA Ours (b) CityScapes Figure 3: Performance drop ∆m% relative to STL vs. train- ing epochs on NYU-v2 and CityScapes benchmarks. encoder-decoder as well as the MTAN attention, which account for 99.57% of all parameters. We measure multi-objective optimization performance using the average performance drop∆m% relative to the single-task learning (STL) baseline [Navon et al., 2022]. For each methodm, the performance drop is calculated by∆m% = 1 K P K i=1 (−1) δ i (M m i − M STL i )·100/M STL i , whereM m i denotes thei-th metric achieved by methodm, andδ i = 0 if higher values are better for metrici; otherwiseδ i = 1. Table 2 and Table 3 summarize the results on NYU-v2 and CityScapes, respectively. Figure 3 demonstrates how the test average performance drop ∆m% decreases during training. From Table 2 and Table 3, we observe that our method achieves state-of-the-art performance on both benchmarks. In particular, on CityScapes, it attains the best results on most task metrics. Figure 3 shows that our method exhibits faster descent on the performance drop∆m% than FAMO. This demonstrates that MOON not only converges faster but also achieves better results than traditional MOO methods, supporting our theoretical claims with practical evidence. 11 Method μ α ε HOMO ε LUMO ⟨R 2 ⟩ ZPVE U 0 U H G c v ∆m%↓ MAE↓ STL0.07 0.18 60.6 53.9 0.50 4.53 58.8 64.2 63.8 66.2 0.07 LS0.11 0.33 73.6 89.7 5.20 14.06 143.4 144.2 144.6 140.3 0.13 177.6 SI0.31 0.35 149.8 135.7 1.00 4.51 55.3 55.8 55.8 55.3 0.11 77.8 RLW0.11 0.34 76.9 92.8 5.87 15.47 156.3 157.1 157.6 153.0 0.14 203.8 DWA0.11 0.33 74.1 90.6 5.09 13.99 142.3 143.0 143.4 139.3 0.13 175.3 UW0.39 0.43 166.2 155.8 1.07 4.99 66.4 66.8 66.8 66.2 0.12 108.0 MGDA0.22 0.37 126.8 104.6 3.23 5.69 88.4 89.4 89.3 88.0 0.12 120.5 PCGrad0.11 0.29 75.9 88.3 3.94 9.15 116.4 116.8 117.2 114.5 0.11 125.7 CAGrad0.12 0.32 83.5 94.8 3.22 6.93 114.0 114.3 114.5 112.3 0.12 112.8 IMTL-G0.14 0.29 98.3 93.9 1.75 5.70 101.4 102.4 102.0 100.1 0.10 77.2 NashMTL0.10 0.25 82.9 81.9 2.43 5.38 74.5 75.0 75.1 74.2 0.09 62.0 FAMO0.16 0.28 85.0 87.0 1.81 5.13 68.2 68.5 68.7 67.8 0.09 57.3 MOON (Ours) 0.07 0.24 52.971.0 3.35 5.6746.446.746.946.3 0.0849.9 Table 4: Results on QM9 dataset (11 tasks). Each experiment is repeated over 3 random seeds and the mean is reported. The best average result is marked in bold. The task specific metrics and the average performance drop ∆m% are reported. Multi-task Regression We further evaluate MOON on multi-task regression using the QM9 molecular property prediction benchmark [Blum and Reymond, 2009]. Following standard practice, we treat predicting each of the 11 quantum-chemical properties as a separate task. We adopt a graph-level multi-task regression network, including matrix-valued parameters like edge-conditioned linear transformations in NNConv and the Set2Set internal LSTM weights [Gilmer et al., 2017], which account for 98.91% of all parameters. Details of the parameterization are provided in Appendix F. In Table 4 we report the mean absolute error (MAE) for each property. To summarize multi-objective performance, we also report the average performance drop ∆m% relative to the STL baseline. Table 4 shows that MOON achieves the best overall performance, attaining the lowest performance drop∆m% and the lowest MAE on most individual tasks. The reason is that gradient manipulation conducted in non-Euclidean spaces is more suitable for addressing matrix gradient conflicts. Conclusion This work addresses the geometric mismatch between conventional Euclidean MOO methods and the matrix-valued parameters prevalent in modern architectures such as Transformers. We proposed MOON (Multi-Objective OrthoNormalized Updates), which performs gradient manipulation under spectral–nuclear norm geometry and constructs matrix-aware orthonormalized updates. At any fixed iterate, the exact MOON weighting provides a nuclear-norm-based stationarity certificate no larger than that obtained by Euclidean min-norm weighting, thereby establishing its optimality for the matrix-geometric dual subproblem. For smooth non-convex objectives, we established convergence of the averaged Pareto-stationarity measure at rates ofO(T −1/2 ) in the deterministic setting and O(T −1/4 ) in the stochastic setting. Experiments demonstrate that MOON improves optimization efficiency while achieving competitive or improved final performance. 12 Acknowledgment This work was supported in part by the Beijing Major Science and Technology Project under Contract no. Z251100008125031, National Science Foundation of China (62401327), and the MOE Project of Key Research Institute of Humanities and Social Sciences (22JJD110001). This work was supported by Beijing Academy of Artificial Intelligence (BAAI). References Essential AI, Ishaan Shah, Anthony M. Polloreno, Karl Stratos, Philip Monk, Adarsh Chaluvaraju, Andrew Hojel, Andrew Ma, Anil Thomas, Ashish Tanwer, Darsh J Shah, Khoi Nguyen, Kurt Smith, Michael Callahan, Michael Pust, Mohit Parmar, Peter Rushton, Platon Mazarakis, Ritvik Kapila, Saurabh Srivastava, Somanshu Singla, Tim Romanski, Yash Vanjani, and Ashish Vaswani. Practical efficiency of muon for pretraining, 2025. URL https://arxiv.org/abs/2505.02222. Noah Amsel, David Persson, Christopher Musco, and Robert M. Gower. The polar express: Optimal matrix sign methods and their application to the muon algorithm, 2026. URL https: //arxiv.org/abs/2505.16932. Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. Segnet: A deep convolutional encoder- decoder architecture for image segmentation. IEEE transactions on pattern analysis and machine intelligence, 39(12):2481–2495, 2017. Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology, 2024. URL https://arxiv.org/abs/2409.20325. ̊ Ake Bj ̈orck and Clazett Bowie. An iterative algorithm for computing the best estimate of an orthogonal matrix. SIAM Journal on Numerical Analysis, 8(2):358–364, 1971. Lorenz C Blum and Jean-Louis Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database gdb-13. Journal of the American Chemical Society, 131(25): 8732–8733, 2009. Zhao Chen, Vijay Badrinarayanan, Chen-Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In International conference on machine learning, pages 794–803. PMLR, 2018. Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. Ana Lu ́ısa Cust ́odio, JF Aguilar Madeira, A Ismael F Vaz, and Lu ́ıs Nunes Vicente. Direct multisearch for multiobjective optimization. SIAM Journal on Optimization, 21(3):1109–1140, 2011. Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021. URL https://arxiv.org/abs/2010.11929. 13 Heshan Devaka Fernando, Han Shen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. In The Eleventh International Conference on Learning Representations, 2023. J ̈org Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, 51(3):479–494, 2000. Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263–1272. Pmlr, 2017. Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In International Conference on Machine Learning, pages 1842–1850. PMLR, 2018. Yifei He, Shiji Zhou, Guojun Zhang, Hyokun Yun, Yi Xu, Belinda Zeng, Trishul Chilimbi, and Han Zhao. Robust multi-task learning with excess risks. In International Conference on Machine Learning (ICML), 2024. Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https:// kellerjordan.github.io/posts/muon/. Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7482–7491, 2018. Ahmed Khaled, Kaan Ozkara, Tao Yu, Mingyi Hong, and Youngsuk Park. Muonbp: Faster muon via block-periodic orthogonalization, 2025. URL https://arxiv.org/abs/2510.16981. Dmitry Kovalev. Understanding gradient orthogonalization for deep learning via non-euclidean trust-region optimization, 2025. URL https://arxiv.org/abs/2503.12645. Zdislav Kovarik. Some iterative methods for improving orthonormality. SIAM Journal on Numerical Analysis, 7(3):386–389, 1970. Jiaxiang Li and Mingyi Hong. A note on the convergence of muon, 2025. URL https://arxiv.org/ abs/2502.02900. Baijiong Lin, Feiyang Ye, and Yu Zhang. A closer look at loss weighting in multi-task learning. arXiv preprint arXiv:2111.10603, 2021. Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. Advances in Neural Information Processing Systems, 34:18878–18890, 2021a. Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. Famo: Fast adaptive multitask optimization. Advances in Neural Information Processing Systems, 36, 2024. Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, Yanru Chen, Huabin Zheng, Yibo Liu, Shaowei Liu, Bohong Yin, Weiran He, Han Zhu, Yuzhi Wang, Jianzhou Wang, Mengnan Dong, Zheng Zhang, Yongsheng Kang, Hao Zhang, Xinran Xu, Yutao Zhang, Yuxin Wu, Xinyu Zhou, and Zhilin Yang. Muon is scalable for llm training, 2025. URL https://arxiv.org/abs/2502.16982. 14 Liyang Liu, Yi Li, Zhanghui Kuang, Jing-Hao Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. In International Conference on Learning Representations, 2021b. URL https://openreview.net/forum?id=IMPnRXEWpvr. Shikun Liu, Edward Johns, and Andrew J Davison. End-to-end multi-task learning with attention. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1871–1880, 2019. Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pages 3730–3738, 2015. Yining Lu and Meng Jiang. Uncovering cross-objective interference in multi-objective alignment, 2026. URL https://arxiv.org/abs/2602.06869. James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning, pages 2408–2417. PMLR, 2015. Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi-task learning as a bargaining game, 2022. URL https://arxiv.org/abs/2202. 01017. Sebastian Peitz and Sedjro Salomon Hotegni. Multi-objective deep learning: Taxonomy and survey of the state of the art. Machine Learning with Applications, page 100700, 2025. Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. Advances in neural information processing systems, 30, 2017. Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances in neural information processing systems, 31, 2018. Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International conference on machine learning, pages 4596–4604. PMLR, 2018. Nathan Silberman, Derek Hoiem, Pushmeet Kohli, and Rob Fergus. Indoor segmentation and support inference from rgbd images. In European conference on computer vision, pages 746–760. Springer, 2012. Kimi Team, Yifan Bai, Yiping Bao, Y. Charles, Cheng Chen, et al. Kimi k2: Open agentic intelligence, 2026. URL https://arxiv.org/abs/2507.20534. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33: 5824–5836, 2020. Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence of stochastic multi-objective gradient manipulation and beyond. Advances in Neural Information Processing Systems, 35:38103–38115, 2022. Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4): 257–271, 1999. 15 Appendix A Missing Proofs Throughout this appendix, we consider the idealized setting in whichW t is the exact polar factor of the momentum matrix M t , i.e., W t = Polar(M t ). The effect of replacing the exact polar factor with a finite-step Newton–Schulz approximation is analyzed separately in Appendix D. A.1 Description for Assumption In this paper, we have the following assumptions. Assumption 1. For eachi ∈[m], the objective functionℓ i :R p×q → Ris differentiable and L-smooth with respect to the spectral norm∥·∥ S ∞ , i.e., there exist a bounded constantL >0 such that for any Θ, Θ ′ ∈ R p×q , ∥∇ℓ i (Θ)−∇ℓ i (Θ ′ )∥ S 1 ≤ L∥Θ− Θ ′ ∥ S ∞ . Assumption 2. There exist a constantH >0 such that for anyi ∈[m] andt= 1,...,T+ 1, ∥∇ℓ i (Θ t )∥ S 1 ≤ H. Assumption 3. There exist a constantB >0 such that for anyi ∈[m] andt= 1,...,T+ 1, |ℓ i (Θ t )|≤ B. A.2 Proof of Remark 2 Suppose that everyℓ i : Ω⊆ R p×q → Ris convex, where Ω is a nonempty compact convex set, and that the spectral-norm diameter of Ω is uniformly bounded D := sup Θ,Θ ′ ∈Ω Θ− Θ ′ S ∞ . For any z ∈ ∆ m , let Θ ∗ t (z)∈ arg min Θ∈Ω z ⊤ L(Θ). Convexity and spectral–nuclear norm duality imply z ⊤ L(Θ t )− min Θ∈Ω z ⊤ L(Θ) ≤⟨G t (z), Θ t − Θ ∗ t (z)⟩ ≤ D∥G t (z)∥ S 1 . (19) A.3 Convergence Analysis for Deterministic Gradient Theorem 3 (Deterministic Convergence). Suppose that each objectiveℓ i :R p×q → RisL-smooth with respect to the spectral norm. Assume that there exist constantsH >0 andB >0, independent of bothTandt, such thatmax t∈[T +1] max i∈[m] ∥∇ℓ i (Θ t )∥ S 1 ≤ Handmax t∈[T +1] max i∈[m] |ℓ i (Θ t )|≤ B. Chooseα= q B LT ,β= 1 mHT and 0< γ < mHT. Then, for every fixedμ ∈(0,1], the iterates generated by Algorithm 1 satisfy 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ O(T −1/2 ). 16 Before the final proof, we first introduce the following Lemmas. Lemma 1. Assume that Assumption 2 holds and that 0< βγ <1. Then for anyt= 1,...,T, the weight updates in Algorithm 1 satisfy the following inequality ∥z t −z t+1 ∥ ∞ ≤ βH.(20) Proof.The softmax mapping is 1/2-Lipschitz with respect to theℓ ∞ norm. Indeed, for anyx,y ∈ R m , ∥softmax(x)− softmax(y)∥ ∞ ≤ 1 2 ∥x−y∥ ∞ . Consequently, ∥z t+1 −z t ∥ ∞ ≤ 1 2 ∥ξ t+1 −ξ t ∥ ∞ = β 2 ∥δ t + γξ t ∥ ∞ .(21) We first bound δ t . By the duality between the spectral norm and the nuclear norm, ∥δ t ∥ ∞ = max i∈[m] W t ,∇ℓ i (Θ t ) ≤∥W t ∥ S ∞ max i∈[m] ∥∇ℓ i (Θ t )∥ S 1 ≤ H.(22) Here, ∥W t ∥ S ∞ ≤ 1 follows from the polar-factor construction in Algorithm 1. In particular, if W t = U t V ⊤ t is obtained from a compact singular value decomposition, then ∥W t ∥ S ∞ ≤ 1. Next, the update of ξ t can be written as ξ t+1 = (1− βγ)ξ t − βδ t . Since 0 < βγ < 1, the coefficient 1− βγ is nonnegative. Thus, using (22), ∥ξ t+1 ∥ ∞ ≤ (1− βγ)∥ξ t ∥ ∞ + β∥δ t ∥ ∞ ≤ (1− βγ)∥ξ t ∥ ∞ + βH.(23) Unrolling (23) and using ξ 1 = 0 gives ∥ξ t ∥ ∞ ≤ βH t−2 X s=0 (1− βγ) s = H γ 1− (1− βγ) t−1 ≤ H γ .(24) Sincez t =Softmax(ξ t ), the 1/2-Lipschitz continuity of softmax under theℓ ∞ norm bounds the change inz t by the corresponding change in the logits. Applying the triangle inequality to the logit update and substituting ∥δ t ∥ ∞ ≤ H from (22) and ∥ξ t ∥ ∞ ≤ H/γ from (24), we obtain ∥z t+1 −z t ∥ ∞ ≤ β 2 (∥δ t ∥ ∞ + γ∥ξ t ∥ ∞ ) ≤ β 2 (H + H) = βH. This completes the proof. 17 Lemma 2. Assume that Assumption 1 and 2 hold, and that 0< βγ <1. Then for anyt= 1,...,T, the weight updates in Algorithm 1 satisfy the following inequality ∥M t − m X i=1 z i,t ∇ℓ i (Θ t )∥ S 1 ≤ (1− μ) t−1 ∥ m X i=1 z i,1 ∇ℓ i (Θ 1 )∥ S 1 + Lα μ + mH 2 μ β. (25) Proof. Let G t := m X i=1 z i,t ∇ℓ i (Θ t ) and E t := M t −G t . Using the momentum update M t = (1− μ)M t−1 + μG t , we obtain, for t≥ 2, E t = (1− μ) E t−1 +G t−1 −G t . Iterating this recursion and using M 0 = 0 gives ∥E t ∥ S 1 ≤ (1− μ) t ∥G 1 ∥ S 1 + t X j=2 (1− μ) t−j+1 ∥G j−1 −G j ∥ S 1 . Moreover, G j −G j−1 = m X i=1 z i,j ∇ℓ i (Θ j )−∇ℓ i (Θ j−1 ) + m X i=1 (z i,j − z i,j−1 )∇ℓ i (Θ j−1 ). By Assumptions 1–2, Lemma 1, and ∥Θ j − Θ j−1 ∥ S ∞ ≤ α, we have ∥G j −G j−1 ∥ S 1 ≤ Lα + mH 2 β. Since t X j=2 (1− μ) t−j+1 ≤ 1 μ , it follows that M t − m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ≤ (1− μ) t−1 m X i=1 z i,1 ∇ℓ i (Θ 1 ) S 1 + Lα μ + mH 2 β μ . We are now ready to prove Theorem 3. 18 Theorem 4. Suppose Assumption 1–3 hold, letℓ i :R p×q → Rbe non-convex for eachi ∈[m]. Suppose that 0 < βγ < 1, then the iterations of Algorithm 1 satisfy the following inequality 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 2B αT + 2H μT + 2Lα μ + 2mH 2 μ β + mHB β α + L 2 α. (26) Proof. Define G t := m X i=1 z i,t ∇ℓ i (Θ t ). By L-smoothness and Θ t+1 = Θ t − αW t , m X i=1 z i,t ℓ i (Θ t+1 )≤ m X i=1 z i,t ℓ i (Θ t )− α⟨G t ,W t ⟩ + Lα 2 2 . Since W t is the polar factor of M t , ⟨M t ,W t ⟩ =∥M t ∥ S 1 and ∥W t ∥ S ∞ ≤ 1. Therefore, −α⟨G t ,W t ⟩≤−α∥G t ∥ S 1 + 2α∥G t −M t ∥ S 1 . After adding and subtracting P i z i,t+1 ℓ i (Θ t+1 ) and rearranging, we obtain ∥G t ∥ S 1 ≤ 1 α m X i=1 z i,t ℓ i (Θ t )− m X i=1 z i,t+1 ℓ i (Θ t+1 ) ! + 1 α m X i=1 (z i,t+1 − z i,t )ℓ i (Θ t+1 ) + Lα 2 + 2∥G t −M t ∥ S 1 . Lemma 1 imply m X i=1 (z i,t+1 − z i,t )ℓ i (Θ t+1 ) ≤ mBHβ. Applying Lemma 2, summing over t = 1,...,T , and using ∥G 1 ∥ S 1 ≤ H, we obtain T X t=1 ∥G t ∥ S 1 ≤ 2B α + 2H μ + 2TLα μ + 2TmH 2 β μ + TmHBβ α + TLα 2 . Finally, since z t ∈ ∆ m , it is a feasible point of the minimization problem. Therefore, min z∈∆ m m X i=1 z i ∇ℓ i (Θ t ) S 1 ≤∥G t ∥ S 1 . Dividing the preceding inequality by T yields the claimed result. There is an immediate corollary of the above Theorem. 19 Corollary 1. Settingα= q B LT ,β= 1 mHT and 0< γ < mHTin Theorem 4, then, for any fixed μ∈ (0, 1], the following holds 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ O( r LB T + 1 T ) = O(1/ √ T ). (27) Proof. Since α = q B LT , β = 1 mHT and 0 < γ < mHT in Theorem 4, we have 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 2B αT + 2H μT + 2Lα μ + 2mH 2 μ β + mHB β α + L 2 α = ( 7 2 + 2 μ ) r LB T + 4H μ · 1 T = O( r LB T + 1 T ) = O(1/ √ T ). A.4 Convergence Analysis for Stochastic Gradient Theorem 5 (Stochastic Convergence). Under the same assumption as Theorem 1. We assume that the stochastic gradient estimator is unbiased and has variance bounded byσ. Choosingα= q μB TL , β= 1 (H+ √ mρσ)mT , 0< γ <(H+ √ mρσ)mTandμ=min √ LB σρ √ T ,1, whereρ:= p minp,q, then the iterations of Algorithm 1 satisfy 1 T T X t=1 E min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤O(1/T 1/4 ).(28) We now establish the convergence of MOON in the stochastic setting. LetF t denote the sigma- algebra containing all information available immediately before samplingζ t . In particular,Θ t is F t -measurable. For every i∈ [m] and t≥ 1, assume that, almost surely, E t g i (Θ t ;ζ t ) =∇ℓ i (Θ t ), and E t h g i (Θ t ;ζ t )−∇ℓ i (Θ t ) 2 F i ≤ σ 2 , where E t [·] := E[·|F t ] and σ > 0 is independent of t and T . No independence is required among the stochastic-gradient errors associated with different objectives at the same iteration. Therefore, the stochastic gradients may be computed using the same sampleζ t . Independence across iterations is not required either, provided that the above conditional assumptions hold. 20 Lemma 3. Assume that Assumption 2 holds, and that 0< βγ <1. Then for anyt= 1,...,T, the weight updates in Algorithm 1 satisfy the following inequality E [∥z t −z t+1 ∥ ∞ ]≤ β(H + √ mρσ).(29) Proof. Let η i,t := g i (Θ t ;ζ t )−∇ℓ i (Θ t ) denote the stochastic-gradient error. The softmax mapping is 1/2-Lipschitz with respect to the ℓ ∞ -norm. Therefore, ∥z t+1 −z t ∥ ∞ ≤ 1 2 ∥ξ t+1 −ξ t ∥ ∞ = β 2 ∥δ t + γξ t ∥ ∞ .(30) We first boundE∥δ t ∥ ∞ . By the duality between the spectral and nuclear norms and the almost- sure bound ∥W t ∥ S ∞ ≤ 1, ∥δ t ∥ ∞ = max i∈[m] W t ,g i (Θ t ;ζ t ) ≤ max i∈[m] g i (Θ t ;ζ t ) S 1 ≤ max i∈[m] ∥∇ℓ i (Θ t )∥ S 1 + max i∈[m] ∥η i,t ∥ S 1 ≤ H + max i∈[m] ∥η i,t ∥ S 1 .(31) For every matrix A∈ R p×q , ∥A∥ S 1 ≤ p minp,q∥A∥ F = ρ∥A∥ F . Consequently, E t max i∈[m] ∥η i,t ∥ S 1 ≤ ρ E t max i∈[m] ∥η i,t ∥ F ≤ ρ E t m X i=1 ∥η i,t ∥ 2 F ! 1/2 ≤ ρ m X i=1 E t ∥η i,t ∥ 2 F ! 1/2 ≤ ρ √ mσ.(32) Moreover, by L-smoothness and Θ t+1 = Θ t − αW t , the loss-difference approximation satisfies ℓ i (Θ t )− ℓ i (Θ t+1 ) α − ∇ℓ i (Θ t ),W t ≤ Lα 2 ∥W t ∥ 2 S ∞ ≤ Lα 2 , where the last inequality follows from ∥W t ∥ S ∞ ≤ 1. The penultimate inequality follows from Jensen’s inequality. Combining(31)and(32), and then taking total expectation, gives E∥δ t ∥ ∞ ≤ H + ρ √ mσ.(33) 21 For brevity, define C σ := H + ρ √ mσ. The dual-logit update can be written as ξ t+1 = (1− βγ)ξ t − βδ t . Since 0 < βγ < 1, we have E∥ξ t+1 ∥ ∞ ≤ (1− βγ)E∥ξ t ∥ ∞ + βE∥δ t ∥ ∞ ≤ (1− βγ)E∥ξ t ∥ ∞ + βC σ .(34) Unrolling (34) and using ξ 1 = 0, we obtain E∥ξ t ∥ ∞ ≤ βC σ t−2 X s=0 (1− βγ) s = C σ γ 1− (1− βγ) t−1 ≤ C σ γ .(35) Finally, taking expectations in(30)and applying the triangle inequality separate the contributions ofδ t andξ t . By(33)and(35), these two contributions are bounded byC σ andγ(C σ /γ) =C σ , respectively. Therefore, we obtain E∥z t+1 −z t ∥ ∞ ≤ β 2 (E∥δ t ∥ ∞ + γE∥ξ t ∥ ∞ ) ≤ β 2 (C σ + C σ ) = β H + ρ √ mσ . This completes the proof. Lemma 4. Assume that Assumptions 1 and 2 hold. Suppose thatM 0 =0, 0< μ ≤1, and 0 < βγ < 1. Then, for any t = 1,...,T , the iterates generated by Algorithm 1 satisfy E M t − m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ≤ (1− μ) t−1 m X i=1 z i,1 ∇ℓ i (Θ 1 ) S 1 + Lα μ + √ μρσ + (H + √ mρσ)mH μ β. (36) Proof. Define the weighted true gradient and the aggregated stochastic-gradient noise as G t := m X i=1 z i,t ∇ℓ i (Θ t ), ε t := m X i=1 z i,t g i (Θ t ;ζ t )−∇ℓ i (Θ t ) . 22 The momentum update can then be written as M t = (1− μ)M t−1 + μ(G t +ε t ). Unrolling this recursion gives M t = (1− μ) t M 0 + μ t X j=1 (1− μ) t−j (G j +ε j ). Subtracting G t and rearranging the deterministic terms yields M t −G t = (1− μ) t (M 0 −G 1 ) + t X j=2 (1− μ) t−j+1 (G j−1 −G j ) + μ t X j=1 (1− μ) t−j ε j . We first bound the variation of the weighted true gradient. For every j ≥ 2, G j −G j−1 = m X i=1 z i,j ∇ℓ i (Θ j )−∇ℓ i (Θ j−1 ) + m X i=1 (z i,j − z i,j−1 )∇ℓ i (Θ j−1 ). By Assumptions 1 and 2, ∥W j−1 ∥ S ∞ ≤ 1, and the stochastic weight-change bound E [∥z j −z j−1 ∥ ∞ ]≤ β(H + √ mρσ), we obtain E [∥G j −G j−1 ∥ S 1 ]≤ LE [∥Θ j − Θ j−1 ∥ S ∞ ] + H m X i=1 E [|z i,j − z i,j−1 |] ≤ Lα + (H + √ mρσ)mHβ. We next bound the stochastic-noise term. LetF j denote the history before samplingζ j . Since z j and Θ j are F j -measurable, the conditional unbiasedness assumption gives E[ε j |F j ] = 0. Moreover, by the convexity of the squared Frobenius norm, E ∥ε j ∥ 2 F |F j = E m X i=1 z i,j g i (Θ j ;ζ j )−∇ℓ i (Θ j ) 2 F F j 23 ≤ m X i=1 z i,j E h g i (Θ j ;ζ j )−∇ℓ i (Θ j ) 2 F F j i ≤ σ 2 . Becauseε j j≥1 is a martingale-difference sequence, the cross terms vanish. Using∥A∥ S 1 ≤ ρ∥A∥ F and Jensen’s inequality, we have E μ t X j=1 (1− μ) t−j ε j S 1 ≤ ρ v u u u t E μ t X j=1 (1− μ) t−j ε j 2 F ≤ ρμσ v u u t t X j=1 (1− μ) 2(t−j) ≤ √ μρσ. Applying the triangle inequality to the preceding decomposition, usingM 0 =0, and taking total expectation separate the momentum error into three parts: the initial error, the accumulated variation of the weighted true gradients, and the accumulated stochastic-gradient noise. The weighted-gradient variation at each step is bounded byLα+ (H+ √ mρσ)mHβ, while the expected nuclear norm of the accumulated noise is bounded by √ μρσ. Therefore, we obtain E [∥M t −G t ∥ S 1 ]≤ (1− μ) t ∥G 1 ∥ S 1 + √ μρσ + t X j=2 (1− μ) t−j+1 Lα + (H + √ mρσ)mHβ . Finally, since (1− μ) t ≤ (1− μ) t−1 and t X j=2 (1− μ) t−j+1 ≤ 1 μ , we conclude that E [∥M t −G t ∥ S 1 ]≤ (1− μ) t−1 ∥G 1 ∥ S 1 + Lα μ + √ μρσ + (H + √ mρσ)mH μ β. Substituting the definition of G t completes the proof. Now we are ready to prove Theorem 5 Theorem 6. Let Assumption 1 to 3 hold, letℓ i :R p×q → Rbe non-convex for eachi∈[m]. Then the iterations of Algorithm 1 satisfy the following inequality 1 T T X t=1 E min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 2B αT + 2H μT + (H + √ mρσ)mB β α + L 2 α + 2Lα μ + 2 √ μρσ + 2mH(H + √ mρσ) μ β. (37) 24 Proof. For brevity, define G t := m X i=1 z i,t ∇ℓ i (Θ t ). From the L-smoothness of each objective function, we have m X i=1 z i,t ℓ i (Θ t+1 )≤ m X i=1 z i,t ℓ i (Θ t ) + L 2 ∥Θ t+1 − Θ t ∥ 2 S ∞ + * m X i=1 z i,t ∇ℓ i (Θ t ), Θ t+1 − Θ t + ≤ m X i=1 z i,t ℓ i (Θ t ) + L 2 ∥Θ t+1 − Θ t ∥ 2 S ∞ +⟨M t , Θ t+1 − Θ t ⟩ + * m X i=1 z i,t ∇ℓ i (Θ t )−M t , Θ t+1 − Θ t + . Since Θ t+1 = Θ t − αW t , we have ⟨M t , Θ t+1 − Θ t ⟩ =⟨M t ,−αW t ⟩ =−α∥M t ∥ S 1 . The spectral-nuclear norm duality bounds the last inner product by ∥G t −M t ∥ S 1 ∥Θ t+1 − Θ t ∥ S ∞ . Moreover, ∥Θ t+1 − Θ t ∥ S ∞ = α∥W t ∥ S ∞ ≤ α, and the reverse triangle inequality gives ∥M t ∥ S 1 ≥∥G t ∥ S 1 −∥G t −M t ∥ S 1 . Substituting these two bounds into the smoothness inequality yields m X i=1 z i,t ℓ i (Θ t+1 )≤ m X i=1 z i,t ℓ i (Θ t ) + L 2 α 2 − α∥M t ∥ S 1 +∥ m X i=1 z i,t ∇ℓ i (Θ t )−M t ∥ S 1 ∥Θ t+1 − Θ t ∥ S ∞ ≤ m X i=1 z i,t ℓ i (Θ t ) + L 2 α 2 − α m X i=1 z i,t ∇ℓ i (Θ t ) S 1 + 2α m X i=1 z i,t ∇ℓ i (Θ t )−M t S 1 . Rearranging the preceding inequality, adding and subtracting P m i=1 z i,t+1 ℓ i (Θ t+1 ) to create a telescoping term, and taking total expectation gives the first inequality below. For the second inequality, we use E " m X i=1 (z i,t+1 − z i,t )ℓ i (Θ t+1 ) # ≤ mBE [∥z t+1 −z t ∥ ∞ ]≤ mBβ(H + √ mρσ), 25 together with Lemma 4. Therefore, E m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ≤ 1 α E " m X i=1 z i,t ℓ i (Θ t )− m X i=1 z i,t+1 ℓ i (Θ t+1 ) # + 1 α E " m X i=1 (z i,t+1 − z i,t )ℓ i (Θ t+1 ) # + L 2 α + 2E m X i=1 z i,t ∇ℓ i (Θ t )−M t S 1 ≤ 1 α E " m X i=1 z i,t ℓ i (Θ t )− m X i=1 z i,t+1 ℓ i (Θ t+1 ) # + 2(1− μ) t−1 ∥ m X i=1 z i,1 ∇ℓ i (Θ 1 )∥ S 1 + (H + √ mρσ)mB β α + L 2 α + 2Lα μ + 2 √ μρσ + 2mH(H + √ mρσ) μ β. Summing the preceding inequality fromt= 1 toT, the weighted-loss terms telescope. Since z t ∈ ∆ m and |ℓ i (Θ t )|≤ B, the two endpoint terms are bounded by 2B. Moreover, T X t=1 (1− μ) t−1 ≤ 1 μ , m X i=1 z i,1 ∇ℓ i (Θ 1 ) S 1 ≤ H. Consequently, T X t=1 E m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ≤ 1 α E " m X i=1 z i,1 ℓ i (Θ 1 )− m X i=1 z i,T +1 ℓ i (Θ T +1 ) # + 2H μ + (H + √ mρσ)TmB β α + TL 2 α + 2TLα μ + 2T √ μρσ + 2TmH(H + √ mρσ) μ β ≤ 2B α + 2H μ + (H + √ mρσ)TmB β α + TL 2 α + 2TLα μ + 2T √ μρσ + 2TmH(H + √ mρσ) μ β. Finally, since z t ∈ ∆ m is feasible, min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ m X i=1 z i,t ∇ℓ i (Θ t ) S 1 . 26 Dividing the preceding inequality byTand applying this pointwise bound proves the theorem. There is an immediate corollary of the above Theorem 6. Corollary 2. Settingα= q μB TL ,β= 1 (H+ √ mρσ)mT , 0< γ <(H+ √ mρσ)mTandμ=min √ LB σρ √ T ,1 in Theorem 6, the following holds 1 T T X t=1 E min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤O r LB T + ρ 2 σ 2 LB T 1/4 ! =O(1/T 1/4 ). (38) Proof.Sinceα= q μB TL ,β= 1 (H+ √ mρσ)mT , 0< γ <(H+ √ mρσ)mTandμ=min √ LB σρ √ T , 1in Theorem 6, we have 1 T T X t=1 E min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 2B αT + 2H μT + (H + √ mρσ)mB β α + L 2 α + 2Lα μ + 2 √ μρσ + 2mH(H + √ mρσ) μ β ≤ ( 4σρH LB + 1 2 ) r LB T + 7 ρ 2 σ 2 LB T 1/4 =O r LB T + ρ 2 σ 2 LB T 1/4 ! =O(1/T 1/4 ). B Convergence of Convex Case Theorem 7. Let Ω⊆ R p×q be a nonempty compact convex set satisfying diam S ∞ (Ω) := sup Θ,Θ ′ ∈Ω ∥Θ− Θ ′ ∥ S ∞ ≤ D. Suppose that each objectiveℓ i : Ω→ Ris convex and differentiable. Assume that the iterates generated by Algorithm 1 satisfy Θ t ∈ Ω, z t ∈ ∆ m , t = 1,...,T. Then 1 T T X t=1 max Θ ∗ ∈Ω min z ∗ ∈∆ m z ∗ ⊤ (L(Θ t )−L(Θ ∗ )) ≤ D T T X t=1 m X i=1 z i,t ∇ℓ i (Θ t ) S 1 . (39) 27 Proof. Fix any t∈1,...,T. Since z t ∈ ∆ m , for every Θ ∗ ∈ Ω, we have min z ∗ ∈∆ m z ∗ ⊤ (L(Θ t )−L(Θ ∗ )) ≤ z ⊤ t (L(Θ t )−L(Θ ∗ )).(40) Taking the maximum over Θ ∗ ∈ Ω on both sides gives max Θ ∗ ∈Ω min z ∗ ∈∆ m z ∗ ⊤ (L(Θ t )−L(Θ ∗ )) ≤ max Θ ∗ ∈Ω z ⊤ t (L(Θ t )−L(Θ ∗ )) = z ⊤ t L(Θ t )− min Θ ∗ ∈Ω z ⊤ t L(Θ ∗ ).(41) Because Ω is compact and each ℓ i is continuous, there exists Θ ∗ t ∈ arg min Θ∈Ω z ⊤ t L(Θ). Consequently, the right-hand side of (41) is m X i=1 z i,t ℓ i (Θ t )− ℓ i (Θ ∗ t ) . By the convexity of each ℓ i , we have ℓ i (Θ t )− ℓ i (Θ ∗ t )≤ ∇ℓ i (Θ t ), Θ t − Θ ∗ t . Since z i,t ≥ 0, multiplying by z i,t and summing over i yields z ⊤ t L(Θ t )−z ⊤ t L(Θ ∗ t ) ≤ * m X i=1 z i,t ∇ℓ i (Θ t ), Θ t − Θ ∗ t + .(42) Using the duality between the nuclear norm and the spectral norm, |⟨A,B⟩|≤∥A∥ S 1 ∥B∥ S ∞ , we obtain * m X i=1 z i,t ∇ℓ i (Θ t ), Θ t − Θ ∗ t + ≤ m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ∥Θ t − Θ ∗ t ∥ S ∞ ≤ D m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ,(43) where the last inequality follows from Θ t , Θ ∗ t ∈ Ω and diam S ∞ (Ω)≤ D. Combining (41)–(43), we obtain, for every t, max Θ ∗ ∈Ω min z ∗ ∈∆ m z ∗ ⊤ (L(Θ t )−L(Θ ∗ )) ≤ D m X i=1 z i,t ∇ℓ i (Θ t ) S 1 .(44) Summing this inequality over t = 1,...,T and dividing by T completes the proof. 28 C Approximation to Avoid Calculating Multiple Gradients In this section, we present an approximation of the weight update rule to avoid calculating multiple gradients in Algorithm 1. In Algorithm 1, we update z using a single gradient-descent step as follows z t+1 = z t − β∇ z 1 2 ∥z ⊤ t ∇L(Θ t )∥ 2 S 1 , whereL(Θ) = (ℓ 1 (Θ),...,ℓ m (Θ)) ⊤ . Let [a] i denote theith component of a vector. However, the update rule still necessitates information about the gradients of all the objectives. Therefore, we consider approximating the gradient∇ z ( 1 2 ∥z ⊤ t ∇L(Θ t )∥ 2 S 1 ) using first-order Taylor’s approximation: ∇ z 1 2 ∥z ⊤ t ∇L(Θ t )∥ 2 S 1 i =∥G t ∥ S 1 D ˆ ∇∥G t ∥ S 1 ,∇ℓ i (Θ t ) E =∥G t ∥ S 1 D U t V ⊤ t ,∇ℓ i (Θ t ) E =∥G t ∥ S 1 W t ,∇ℓ i (Θ t ) ≈ ∥G t ∥ S 1 α ℓ i (Θ t )− ℓ i (Θ t+1 ) , i∈ [m]. where ˆ ∇∥G t ∥ S 1 represents an element of the subdifferential of the nuclear norm atG t . This identity is exact in the no-momentum case μ = 1, where M t = G t and W t = Polar(G t ). The factor∥G t ∥ S 1 is a nonnegative scalar that does not change the update direction. Consistent with the practical algorithm, we retain the scale-normalized direction and control the update magnitude through the step size. Then consequently, we have an approximate method for solvingz t without backpropagation: z t+1 = z t − β ̃ δ t ,(45) [ ̃ δ t ] i = 1 α ℓ i (Θ t )− ℓ i (Θ t+1 ) , i∈ [m].(46) In practical MOON, we use the resulting scale-normalized dual direction in the logit-space update of Algorithm 1, which corresponds to an exponentiated-gradient-type online update on the simplex. D Effect of Finite-Step Newton–Schulz Approximation Error The convergence analysis before is stated in terms of the exact polar factor of the momentum matrix. In practice, however, Algorithm 1 computes the update direction using only a finite number of Newton–Schulz iterations. Consequently, the resulting update direction may differ from an exact polar factor. In this section, we quantify the effect of this approximation error on the deterministic convergence guarantee. We focus on the deterministic setting because it isolates the effect of the finite-step Newton–Schulz approximation from the error caused by stochastic-gradient noise. The stochastic case follows by the same argument after conditioning on the history up to iterationtand taking 29 total expectation. We therefore present only the deterministic proof to avoid repeating the same argument. We show that, under a uniform relative approximation condition, the finite-step Newton– Schulz implementation preserves theO(T −1/2 ) Pareto-stationarity rate, up to a multiplicative factor depending on the approximation accuracy. For each iteration t, define the weighted gradient matrix G t := m X i=1 z i,t ∇ℓ i (Θ t ), z t ∈ ∆ m , where ∆ m := ( z ∈ R m + : m X i=1 z i = 1 ) . The momentum matrix is updated according to M t = (1− μ)M t−1 + μG t ,0 < μ≤ 1. Let P t ∈ Polar(M t ) denote a polar factor of M t . In particular, P t satisfies ∥P t ∥ S ∞ ≤ 1, ⟨M t ,P t ⟩ =∥M t ∥ S 1 .(47) These properties remain valid whenM t is rank deficient; in this case,P t should be understood as any polar factor satisfying (47). Let f W t denote the direction returned by the finite-step Newton–Schulz iteration. The actual parameter update is Θ t+1 = Θ t − α f W t .(48) We impose the following approximation condition. Assumption 4. For every t≥ 1, there exists a polar factor P t ∈ Polar(M t ) such that ε t,q := f W t −P t S ∞ ≤ ε q < 1,(49) where q is the number of Newton–Schulz iterations and ε q is independent of t. Assumption 4 is a uniform operator-norm approximation condition. Through nuclear–spectral norm duality, it induces a relative loss of alignment proportional toε q ∥M t ∥ S 1 . Unlike an additive descent-error condition, it does not introduce a nonvanishing residual term into the final stationarity bound. Therefore, any fixed numberqof Newton–Schulz iterations preserves convergence to Pareto stationarity, provided that the uniform bound sup t≥1 f W t,q −P t S ∞ ≤ ε q < 1 holds along the optimization trajectory. In this case, the finite-step approximation affects only the constants in the convergence bound. Moreover, under the standard convergence regime of the employed Newton–Schulz iteration, the approximation error is nonincreasing with respect to the number of Newton–Schulz steps and satisfies ε q+1 ≤ ε q ,lim q→∞ ε q = 0. 30 Consequently, the effect of the finite-step approximation becomes weaker asqincreases, and the resulting convergence bound approaches the corresponding exact-polar bound. These properties also explain why Assumption 4 is reasonable under the standard Newton–Schulz convergence conditions. The following immediate consequence will be used repeatedly. Lemma 5. Under Assumption 4, f W t S ∞ ≤ 1 + ε t,q ≤ 1 + ε q .(50) Proof. By the triangle inequality and (47), f W t S ∞ ≤∥P t ∥ S ∞ + f W t −P t S ∞ ≤ 1 + ε t,q ≤ 1 + ε q . Lemma 6. Assume that Assumption 2 and 4 hold and that 0< βγ <1. Then for anyt= 1,...,T, the weight updates in Algorithm 1 satisfy the following inequality ∥z t −z t+1 ∥ ∞ ≤ βH(1 + ε q ).(51) Proof.The softmax mapping is 1/2-Lipschitz with respect to theℓ ∞ norm. Indeed, for anyx,y ∈ R m , ∥softmax(x)− softmax(y)∥ ∞ ≤ 1 2 ∥x−y∥ ∞ . Consequently, ∥z t+1 −z t ∥ ∞ ≤ 1 2 ∥ξ t+1 −ξ t ∥ ∞ = β 2 ∥δ t + γξ t ∥ ∞ .(52) We first bound δ t . By the duality between the spectral norm and the nuclear norm, ∥δ t ∥ ∞ = max i∈[m] D f W t ,∇ℓ i (Θ t ) E ≤∥ f W t ∥ S ∞ max i∈[m] ∥∇ℓ i (Θ t )∥ S 1 ≤ (1 + ε t,q )H ≤ (1 + ε q )H. Next, the update of ξ t can be written as ξ t+1 = (1− βγ)ξ t − βδ t . Since 0 < βγ < 1, the coefficient 1− βγ is nonnegative. Thus, using (53), ∥ξ t+1 ∥ ∞ ≤ (1− βγ)∥ξ t ∥ ∞ + β∥δ t ∥ ∞ ≤ (1− βγ)∥ξ t ∥ ∞ + β(1 + ε q )H.(53) Unrolling (53) and using ξ 1 = 0 gives ∥ξ t ∥ ∞ ≤ β(1 + ε q )H t−2 X s=0 (1− βγ) s 31 = (1 + ε q )H γ 1− (1− βγ) t−1 ≤ (1 + ε q )H γ . Sincez t =Softmax(ξ t ), the 1/2-Lipschitz continuity of softmax under theℓ ∞ norm bounds the change inz t by the corresponding change in the logits. Applying the triangle inequality to the logit update and substituting ∥δ t ∥ ∞ ≤ (1 + ε q )H and ∥ξ t ∥ ∞ ≤ (1 + ε q )H/γ, we obtain ∥z t+1 −z t ∥ ∞ ≤ β 2 (∥δ t ∥ ∞ + γ∥ξ t ∥ ∞ ) ≤ β 2 ((1 + ε q )H + (1 + ε q )H) = (1 + ε q )βH. This completes the proof. Lemma 7. Assume that Assumption 1, 2 and 4 hold, and that 0< βγ <1. Then for anyt= 1,...,T, the weight updates in Algorithm 1 satisfy the following inequality ∥M t − m X i=1 z i,t ∇ℓ i (Θ t )∥ S 1 ≤ (1− μ) t−1 ∥ m X i=1 z i,1 ∇ℓ i (Θ 1 )∥ S 1 + Lα(1 + ε q ) μ + mH 2 β(1 + ε q ) μ . (54) Proof. Let G t := m X i=1 z i,t ∇ℓ i (Θ t ) and E t := M t −G t . Using the momentum update M t = (1− μ)M t−1 + μG t , we obtain, for t≥ 2, E t = (1− μ) E t−1 +G t−1 −G t . Iterating this recursion and using M 0 = 0 gives ∥E t ∥ S 1 ≤ (1− μ) t ∥G 1 ∥ S 1 + t X j=2 (1− μ) t−j+1 ∥G j−1 −G j ∥ S 1 . Moreover, G j −G j−1 = m X i=1 z i,j ∇ℓ i (Θ j )−∇ℓ i (Θ j−1 ) + m X i=1 (z i,j − z i,j−1 )∇ℓ i (Θ j−1 ). By Assumptions 1–2, Lemma 6, and ∥Θ j − Θ j−1 ∥ S ∞ = α∥ f W j−1 ∥ S ∞ , we have ∥G j −G j−1 ∥ S 1 ≤ Lα(1 + ε q ) + mH 2 β(1 + ε q ). 32 Since t X j=2 (1− μ) t−j+1 ≤ 1 μ , it follows that M t − m X i=1 z i,t ∇ℓ i (Θ t ) S 1 ≤ (1− μ) t−1 m X i=1 z i,1 ∇ℓ i (Θ 1 ) S 1 + Lα(1 + ε q ) μ + mH 2 β(1 + ε q ) μ . Theorem 8. Suppose Assumption 1–4 hold, letℓ i :R p×q → Rbe non-convex for eachi ∈[m]. Suppose that 0 < βγ < 1, then the iterations of Algorithm 1 satisfy the following inequality 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 1 1− ε q 2B αT + 2H μT + 2Lα(1 + ε q ) μ + 2mH 2 β(1 + ε q ) μ + mHBβ(1 + ε q ) α + Lα(1 + ε q ) 2 2 . (55) Proof. Define G t := m X i=1 z i,t ∇ℓ i (Θ t ). By L-smoothness and Θ t+1 = Θ t − α f W t , m X i=1 z i,t ℓ i (Θ t+1 )≤ m X i=1 z i,t ℓ i (Θ t )− α⟨G t , f W t ⟩ + Lα 2 (1 + ε q ) 2 2 . Since f W t is the direction returned by the finite-step Newton–Schulz iteration,⟨M t , f W t ⟩= ⟨M t ,P t ⟩ +⟨M t , f W t −P t ⟩≥ (1− ε q )∥M t ∥ S 1 . Therefore, − α⟨G t , f W t ⟩≤−α⟨M t , f W t ⟩ + α⟨M t −G t , f W t ⟩ ≤−(1− ε q )α∥M t ∥ S 1 + (1 + ε q )α∥M t −G t ∥ S 1 ≤−(1− ε q )α(∥G t ∥ S 1 −∥M t −G t ∥ S 1 ) + (1 + ε q )α∥M t −G t ∥ S 1 ≤−(1− ε q )α∥G t ∥ S 1 + 2α∥M t −G t ∥ S 1 . 33 After adding and subtracting P i z i,t+1 ℓ i (Θ t+1 ) and rearranging, we obtain (1− ε q )∥G t ∥ S 1 ≤ 1 α m X i=1 z i,t ℓ i (Θ t )− m X i=1 z i,t+1 ℓ i (Θ t+1 ) ! + 1 α m X i=1 (z i,t+1 − z i,t )ℓ i (Θ t+1 ) + Lα(1 + ε q ) 2 2 + 2∥M t −G t ∥ S 1 . Lemma 6 imply m X i=1 (z i,t+1 − z i,t )ℓ i (Θ t+1 ) ≤ mBHβ(1 + ε q ). Applying Lemma 7, summing over t = 1,...,T , and using ∥G 1 ∥ S 1 ≤ H, we obtain (1− ε q ) T X t=1 ∥G t ∥ S 1 ≤ 2B α + 2H μ + 2TLα(1 + ε q ) μ + 2TmH 2 β(1 + ε q ) μ + TmHBβ(1 + ε q ) α + TLα(1 + ε q ) 2 2 . Finally, min z∈∆ m m X i=1 z i ∇ℓ i (Θ t ) S 1 ≤∥G t ∥ S 1 . Dividing the preceding inequality by (1− ε q )T yields the claimed result. There is an immediate corollary of the above Theorem. Corollary 3. Settingα= q B LT ,β= 1 mHT and 0< γ < mHTin Theorem 8, then, for any fixed μ∈ (0, 1], the following holds 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 1 1− ε q O(1/ √ T ).(56) Proof. Since α = q B LT , β = 1 mHT and 0 < γ < mHT in Theorem 8, we have 1 T T X t=1 min z ∗ t ∈∆ m ∥∇L(Θ t )z ∗ t ∥ S 1 ≤ 1 1− ε q 2B αT + 2H μT + 2Lα(1 + ε q ) μ + 2mH 2 β(1 + ε q ) μ + mHBβ(1 + ε q ) α 34 + Lα(1 + ε q ) 2 2 = 1 1− ε q 3 + 2(1 + ε q ) μ + (1 + ε q ) + (1 + ε q ) 2 2 r LB T + (4 + 2ε q )H μT = 1 1− ε q O(1/ √ T ). Increasing q improves all three approximation-dependent factors in Theorem 8: 1 1− ε q ,1 + ε q ,(1 + ε q ) 2 . Hence, the effect of the finite-step approximation becomes weaker as more Newton–Schulz steps are performed, and the bound continuously approaches the exact-polar convergence bound asq →∞. For any fixedqsatisfying the uniform conditionε q <1, the approximation changes only the constants and does not alter the O(T −1/2 ) deterministic convergence rate. E A Two-Task Matrix Example We present a two-task example to illustrate the difference between Euclidean gradient manipulation and the matrix-aware update derived in Proposition 3. Let the parameter be Θ∈ R 2×2 and define ℓ 1 (Θ) = 1 2 ∥Θ∥ 2 F +⟨A + B, Θ⟩, ℓ 2 (Θ) = 1 2 ∥Θ∥ 2 F +⟨A− B, Θ⟩, (57) where A = 2 0 0 1 , B = 01 −1 0 .(58) At Θ 0 = 0, the two losses have the same value, ℓ 1 (Θ 0 ) = ℓ 2 (Θ 0 ) = 0, and their gradients are g 1 =∇ℓ 1 (Θ 0 ) = A + B = 21 −1 1 , g 2 =∇ℓ 2 (Θ 0 ) = A− B = 2 −1 11 . (59) For a task weight z ∈ [0, 1], let s = 2z− 1. The weighted gradient is G(z) = zg 1 + (1− z)g 2 = A + sB = 2 s −s 1 . (60) 35 MGDA direction. MGDA selects the task weight by minimizing the squared Frobenius norm: 1 2 ∥G(z)∥ 2 F = 1 2 5 + 2s 2 .(61) The unique minimizer iss ∗ = 0, or equivalentlyz ∗ = 1/2, and henceG ∗ MGDA =A. To compare the two methods under the same spectral-norm trust-region budget, we normalize the MGDA direction to unit spectral norm: P MGDA = G ∗ MGDA ∥G ∗ MGDA ∥ S ∞ = 1 0 0 1 2 , ∥P MGDA ∥ S ∞ = 1. (62) MOON direction. MOON instead minimizes the squared nuclear norm. For any 2×2 matrixG, ∥G∥ 2 S 1 =∥G∥ 2 F + 2| det(G)|.(63) Since det(G(z)) = 2 + s 2 > 0, the MOON objective becomes 1 2 ∥G(z)∥ 2 S 1 = 1 2 5 + 2s 2 + 2(2 + s 2 ) = 1 2 9 + 4s 2 . (64) Its unique minimizer is also s ∗ = 0, so the optimal weighted gradient is G ∗ MOON = A = 2 0 0 1 .(65) The singular values of G ∗ MOON are 2 and 1. Therefore, its polar factor is P MOON = Polar(G ∗ MOON ) = UV ⊤ = I, ∥P MOON ∥ S ∞ = 1. (66) Because the singular values ofG ∗ MOON are unequal,P MGDA andP MOON are not scalar multiples of each other. Thus, their difference cannot be attributed solely to update scaling. Common descent comparison. We compare the two directions under the same unit spectral- norm budget. For MGDA, ⟨g 1 ,P MGDA ⟩ =⟨g 2 ,P MGDA ⟩ = 2 + 1 2 = 5 2 . (67) For MOON, ⟨g 1 ,P MOON ⟩ =⟨g 2 ,P MOON ⟩ = 2 + 1 = 3. (68) Consequently, min i∈1,2 ⟨g i ,P MOON ⟩ > min i∈1,2 ⟨g i ,P MGDA ⟩.(69) Hence, for the parameter update Θ + = Θ 0 −ηP , MOON provides a strictly larger first-order decrease for both objectives while using the same spectral-norm update budget: ∥ηP MGDA ∥ S ∞ =∥ηP MOON ∥ S ∞ = η.(70) 36 Quadratic upper-bound comparison. For either objective, ∥∇ℓ i (Θ)−∇ℓ i (Θ ′ )∥ S 1 =∥Θ− Θ ′ ∥ S 1 ≤ 2∥Θ− Θ ′ ∥ S ∞ . (71) Thus, both losses are 2-smooth with respect to the spectral norm. For either direction satisfying ∥P∥ S ∞ = 1, ℓ i (Θ 0 − ηP )≤ ℓ i (Θ 0 )− η⟨g i ,P⟩ + η 2 .(72) The corresponding upper bounds are ℓ i (Θ 0 − ηP MGDA )≤− 5 2 η + η 2 , ℓ i (Θ 0 − ηP MOON )≤−3η + η 2 . (73) Therefore, the MOON direction gives a strictly smaller worst-case quadratic upper bound for every η > 0. The exact objective values are ℓ i (Θ 0 − ηP MGDA ) =− 5 2 η + 5 8 η 2 , ℓ i (Θ 0 − ηP MOON ) =−3η + η 2 . (74) It follows that ℓ i (Θ 0 − ηP MOON ) < ℓ i (Θ 0 − ηP MGDA ), i∈1, 2,0 < η < 4 3 . (75) This example demonstrates that the advantage of MOON is not merely caused by a larger update magnitude. Under the same spectral-norm budget, its matrix-aware direction provides a strictly stronger common descent projection, a tighter worst-case quadratic upper bound, and a larger exact decrease for a nontrivial range of step sizes. F Experimental Details & Further Experiments F.1 Benchmarks and Baselines We consider five benchmarks widely used in multi-task learning research: MultiMNIST [Sabour et al., 2017], NYU-v2 [Silberman et al., 2012], CityScapes [Cordts et al., 2016], QM9 [Blum and Reymond, 2009] and CelebA [Liu et al., 2015]. Specifically, NYU-v2 is an indoor RGB-D dataset, comprising 1449 aligned RGB and depth images with pixel-level semantic annotations over 13 classes. In NYU-v2 benchmark, we consider image segmentation, depth prediction and surface normal prediction as three tasks. CityScapes is an urban street-scene benchmark with 5000 finely annotated stereo RGB image pairs providing dense per-pixel semantic labels for scene understanding. MultiMNIST is an MTL variant of MNIST dataset, where each image contains two randomly sampled MNIST digits. In MultiMNIST, we treat classifying each digit as a separate task. QM9 is a quantum-chemistry benchmark of over 130k small organic molecules with DFT-computed 3D geometries, widely used for molecular property prediction and multi-task learning. The objective is to predict 11 molecular properties. CelebA is a large-scale face attribute dataset containing over 200k facial images annotated with 40 binary attributes. We treat the prediction of each attribute as an individual task, resulting in a 40-task multi-task classification problem. 37 We compare the proposed method with 13 multi-objective optimization baselines: (1) Single- task learning (STL), training each task separately; (2) Linear Scalarization (LS), assigning equal weights to all tasks and minimizing the resulting weighted loss; (3) a scale-invariant baseline (SI) that applies equal weighting to the log losses; (4) Random Loss Weighting (RLW) [Lin et al., 2021], sampling task weights from a normal distribution; (5) Dynamic Weight Average (DWA) [Liu et al., 2019], adjusting task weights according to the rates of loss change; (6) Uncertainty Weighting (UW) [Kendall et al., 2018], incorporating task uncertainty to determine loss weights; (7) MGDA [Sener and Koltun, 2018], finding a common descent direction that yields balanced improvement across tasks at each step; (8) GradNorm [Chen et al., 2018], dynamically balancing task losses by adjusting their weights according to relative training rates and gradient magnitudes;(9) PCGrad [Yu et al., 2020], projecting the gradient of each task to that of other tasks before aggregation; (10) CAGrad [Liu et al., 2021a], minimizing the average loss while controlling the minimum decrease across tasks; (11) IMTL-G [Liu et al., 2021b], learning task weights such that the aggregated gradient has equal projection onto each task gradient; (12) Nash-MTL [Navon et al., 2022], formulating multi-objective optimization as a bargaining game and finding a solution that benefits all tasks; (13) FAMO [Liu et al., 2024], maximizing the worst-case improvement rate and using log losses to update task weights. F.2 Comparison with Naive Combinations with Muon To examine whether MOON can be replaced by Muon itself or by directly combining existing multi-objective optimization methods with Muon, we additionally evaluate Muon by using it as the optimizer under standard linear scalarization, as Muon itself can already achieve competitive MTL performance without an explicit MOO mechanism. We further construct two baselines, MGDA+Muon and FAMO+Muon, by retaining the original multi-objective gradient aggregation of MGDA and FAMO while replacing Adam with Muon for parameter updates. We evaluate all methods on MultiMNIST with the ViT backbone under the same setting as the main experiments. MethodLeft acc Right acc Average acc MGDA95.5894.1094.84 MGDA+Muon 94.6193.6594.13 FAMO95.8994.8895.39 FAMO+Muon 95.6194.3394.97 Muon95.3994.8295.11 MOON (Ours)95.9995.3195.65 Table 5: Performance comparison on MultiMNIST. Per-task test accuracies (%) and their average are reported. Each experiment is repeated over 3 random seeds and the mean is reported. As shown in Table 5, Muon itself also achieves competitive performance under linear scalarization, but still falls short of MOON. Replacing Adam with Muon degrades the performance of both MGDA and FAMO, while MOON achieves the best results. This shows that simply combining traditional multi-objective methods with Muon is insufficient. MOON instead formulates multi-objective optimization directly over matrix-valued parameters, jointly accounting for objective trade-offs and matrix update geometry. 38 F.3 Transformer Experiment on CelebA To further evaluate MOON on a larger dataset with a Transformer architecture, we conduct experiments on CelebA using a ViT backbone. CelebA contains 40 binary attribute prediction tasks, providing a substantially larger multi-objective setting than MultiMNIST. We compare MOON with representative multi-objective optimization methods under the same experimental setting. Method∆m%↓ MGDA19.20 PCGrad10.48 CAGrad12.61 IMTL-G7.96 Nash-MTL8.06 FAMO7.75 MOON (Ours)6.09 Table 6: Performance comparison on CelebA with a ViT backbone. Lower ∆m% indicates better overall multi-task performance. Each experiment is repeated over 3 random seeds and the mean is reported. As shown in Table 6, MOON achieves the lowest ∆m% among all compared methods. This demonstrates that MOON remains effective on a larger multi-task dataset with a Transformer architecture and scales well to a setting with 40 objectives. F.4 Multi-Objective Reinforcement Fine-Tuning on Qwen3-1.7B-Base To evaluate MOON beyond conventional supervised multi-task learning, we apply it to multi-objective reinforcement fine-tuning of Qwen3-1.7B-Base on MATH500, following the setup of Figure 1(c) in Lu and Jiang [2026]. The 500 problems are split into 300 training, 100 validation, and 100 test examples. The training split is used exclusively for policy optimization, while the validation split is used for monitoring, hyperparameter tuning, and checkpoint selection under a prespecified selection rule. The test split is withheld during training and model selection and is used only to evaluate the validation-selected checkpoint. Accordingly, Figure 5 reports validation learning curves, whereas final performance is evaluated on the held-out test split. REINFORCE is used to jointly optimize three alignment objectives: accuracy, conciseness, and clarity. All three objectives are implemented as verifiable binary rewards during training. Accuracy receives a reward of one when the final answer extracted from the last valid expression matches the ground-truth answer after standard MATH normalization, and zero otherwise. Conciseness receives a reward of one when the generated response is shorter than the running global average response length, and zero otherwise. Clarity receives a reward of one when the response contains a nonempty boxed answer and a step-by-step structure indicated by at least two enumerated steps or ordinal transitions, and zero otherwise. During evaluation, accuracy and clarity are reported as mean binary reward scores, while conciseness is reported as the mean response length in tokens, with lower values preferred. We compare MOON with Linear, GradNorm, MGDA, Nash-MTL, and FAMO. For MOON, the objective-specific policy-gradient signals are aggregated through the proposed matrix-aware multi-objective update to optimize the shared LLM parameters. As shown by the validation trajectories in Figure 5, MOON rapidly reaches a favorable trade- off across the three objectives. Its clarity score rises faster than those of most baselines, while 39 accuracy remains competitive and response length decreases steadily. On the held-out test set, the validation-selected MOON checkpoint maintains high clarity and competitive accuracy while producing substantially shorter responses. These results demonstrate that MOON remains effective for multi-objective reinforcement fine-tuning of a modern LLM and reaches a strong multi-objective solution with relatively few optimization steps. F.5 Ablation on Key Hyperparameters We study the sensitivity of MOON to two key hyperparameters, the task-weight update stepsizeβand the weight decay coefficientγ, on MultiMNIST with the ViT backbone. We vary one hyperparameter at a time while keeping the remaining settings unchanged. Each experiment is repeated over 3 random seeds and the mean is reported. γ10 −2 5×10 −2 10 −3 5×10 −3 10 −4 Average Acc 95.14 95.33 95.65 95.62 95.28 Table 7: Average accuracy (%) on MultiMNIST with different values of γ. β10 −5 5×10 −5 10 −4 5×10 −4 10 −3 Average Acc 95.11 95.5395.65 95.48 94.93 Table 8: Average accuracy (%) on MultiMNIST with different values of β. As shown in Tables 7 and 8, MOON maintains stable performance across a range ofβandγ, indicating that it is not sensitive to moderate variations of these hyperparameters. F.6 Ablation on Key Components Orthonormalized Updates. We conduct an ablation study on the MultiMNIST experiment to evaluate the impact of the orthonormalized updates. We compare MOON with that using the Euclidean-direction updates while retaining the matrix-norm-oriented task weighting. As shown in Table 9, without the orthonormalized update, using only matrix-norm-oriented task weighting leads to inferior performance. This indicates that the orthonormalized updates play an important role in the effectiveness of MOON. Momentum. We further conduct an ablation study on the momentum mechanism by directly constructing the update from the current aggregated gradient without momentum smoothing. As shown in Table 9, removing momentum results in a clear performance degradation. This indicates that the momentum is practically necessary. F.7 30-task Synthetic Data Regression Experiment To better understand steepest descent for matrix-valued parameters, we construct a multi-objective regression problem on synthetic data. We adopt an MLP with parameters including weight matrices of its hidden linear layers. We randomly generate 20-dimensional inputs and 30-dimensional targets, treating the regression of each target dimension as a separate task. The average square loss L= 1 nd P n i=1 ∥y i − ˆy i ∥ 2 2 across these tasks is used to demonstrate training efficiency, wheren 40 MethodLeftRightAverage MOON95.99 95.3195.65 (with Euclidean update)95.1894.4294.80 (without momentum)93.9693.4493.70 Table 9: Ablation on the orthonormalized updates and momentum on MultiMNIST. Test accuracies (%) for the left and right digit classification tasks and their average are reported. 02004006008001000 Step 1.0 0.8 0.6 0.4 Average Loss FAMO MGDA Ours Figure 4: Average squared loss after 1000 training steps on the synthetic data multi-objective regression problem. represents the sample size anddrepresents the output dimension. We compare the proposed MOON method with traditional Euclidian-based gradient manipulation methods like MGDA and FAMO. As shown in Figure 4, MOON converges faster and attains a lower average training loss than Euclidean-based gradient manipulation baselines. We observe that in the early stage, MOON quickly opens a clear gap over MGDA and FAMO, and this advantage persists throughout training. After 1k steps, MOON reduces the final average loss by about 20% compared to FAMO and about 15% to MGDA. F.8 Training Efficiency Comparison We evaluate the training efficiency of MOON on MultiMNIST by tracking the average training cross-entropy (CE) loss against wall-clock time, with MGDA and FAMO as baselines. As reported in Table 10, MOON attains a lower training loss under the same time budget throughout training. The gap widens at later stages: after 1,000 seconds, the average CE loss reaches 0.144 with MOON, compared with 0.215 for MGDA and 0.179 for FAMO. 41 0100200300400 Training Steps 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Accuracy Linear GradNorm MGDA Nash-MTL FAMO MOON (Ours) (a) Accuracy 0100200300400 Training Steps 0.0 0.2 0.4 0.6 0.8 1.0 Clarity Linear GradNorm MGDA Nash-MTL FAMO MOON (Ours) (b) Clarity 0100200300400 Training Steps 200 400 600 800 1000 Response Length Linear GradNorm MGDA Nash-MTL FAMO MOON (Ours) (c) Response length Figure 5: Multi-objective reinforcement fine-tuning of Qwen3-1.7B-Base on MATH500 following the setting of Figure 1(c) in Lu and Jiang [2026]. We report accuracy, clarity, and response length throughout training, where response length serves as the measure of conciseness. Higher accuracy and clarity are better, while shorter responses indicate better conciseness. Time (s) MGDA FAMO MOON 2000.500 0.3680.362 4000.339 0.2770.259 6000.273 0.2220.199 8000.229 0.1880.164 10000.215 0.1790.144 Table 10: Average training CE loss vs. training time. Method Time (s) MGDA1576 FAMO1105 MOON949 Table 11: Training time required to reach an average CE loss of 0.15. We also measure the wall-clock time required to reduce the average training CE loss below a common threshold. As shown in Table 11, MOON reaches an average CE loss of 0.15 approximately 39.8% faster than MGDA and 14.1% faster than FAMO. Thus, the additional computation introduced by MOON is offset by faster convergence, resulting in lower end-to-end training time. We further compare GPU memory usage on MultiMNIST. MGDA, FAMO, and MOON consume 2,076 MB, 2,076 MB, and 2,078 MB, respectively. This indicates that MOON exhibits no significant difference in memory overhead compared with the other MOO methods. Overall, MOON improves wall-clock convergence while retaining essentially the same memory footprint as MGDA and FAMO. F.9 Experimental Results with Error Bars In the following tables 12 to 15, we report the results of MOON with error bars. 42 MethodLeft Acc ↑ Right Acc ↑ Average Acc ↑ MOON (mean)95.9995.3195.65 MOON (std) ±0.07 ±0.10±0.07 Table 12: Test accuracy (%) on MultiMNIST (2 tasks). Each experiment is repeated over 3 random seeds. The mean and the standard deviation is reported. Per-task accuracies (left/right) and their average are reported. The best result is marked in bold. SegmentationDepthSurface Normal MethodmIoU ↑ Pix Acc ↑ Abs Err ↓ Rel Err ↓ Mean ↓ Median ↓ 11.25 ◦ ↑ 22.5 ◦ ↑ 30 ◦ ↑ ∆m%↓ MOON (mean) 39.4167.030.48910.209125.6120.2728.8954.87 67.32 -4.63 MOON (std) ±0.48 ±0.24 ±0.0024 ±0.0030 ±0.11 ±0.14 ±0.19 ±0.23 ±0.22 ±0.22 Table 13: Results on NYU-v2 (3 tasks) dataset. Each experiment is repeated over 3 random seeds. The mean and the standard deviation is reported. The best average result is marked in bold. The task specific metrics and the average performance drop ∆m% are reported. CityScapesCelebA SegmentationDepth∆m%↓ ∆m%↓ MethodmIoU ↑ Pix Acc ↑ Abs Err ↓ Rel Err ↓ MOON (mean)78.6194.360.012631.411.544.65 MOON (std) ±0.24 ±0.09 ±0.0008 ±1.00 ±0.60 ±0.08 Table 14: Results on CityScapes (2 tasks) and CelebA (40 tasks) dataset. Each experiment is repeated over 3 random seeds. The mean and the standard deviation is reported. The best average result is marked in bold. Task-specific metrics and the average performance drop∆m% are reported. Methodμα ε HOMO ε LUMO ⟨R 2 ⟩ZPVE U 0 U H G c v ∆m%↓ MAE ↓ MOON (mean) 0.070.2452.971.03.355.67 46.4 46.7 46.9 46.3 0.0849.9 MOON (std) ±0.006 ±0.009 ±2.8 ±2.3 ±0.035 ±0.110 ±1.9 ±2.0 ±1.9 ±2.0 ±0.004 ±1.60 Table 15: Results on QM9 dataset (11 tasks). Each experiment is repeated over 3 random seeds. The mean and the standard deviation is reported. The best average result is marked in bold. The task specific metrics and the average performance drop ∆m% are reported. G Limitations Our theoretical analysis assumes the exact computation of the polar factor, whereas our imple- mentation uses a Newton–Schulz approximation. In practice, the approximation error is small, we therefore omit this error from the current analysis and leave its precise theoretical characterization to future work. 43