Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates

Preprint

G EOMETRY-AWARE M ULTI -O BJECTIVE O PTIMIZA TION : N ORM -C ONSTRAINED O RACLES WITH E N TROPIC W EIGHT U PDATES

arXiv:2610.13773v1 [math.OC] 9 Oct 2026

El Mahdi Chayti, Alireza Mirrokni, Martin Jaggi Machine Learning and Optimization Laboratory (MLO), EPFL

A BSTRACT Multiple-gradient descent is typically formulated in Euclidean geometry, whereas matrix-aware optimizers use directions induced by other norms. We analyze a single-loop multi-objective method combining a norm-constrained linear minimization oracle with entropic updates of task weights. For any finite-dimensional norm pair, we establish an O(T −1/2 ) ergodic stationarity rate in the deterministic setting, deriving the required trajectory gradient bound from smoothness and lower-boundedness in the unregularized case. With stochastic gradients and a bounded-gradient assumption, one persistent blended-gradient momentum buffer yields an O(T −1/4 ) rate whose leading term has no explicit dependence on the number of tasks. We also establish static regret for the inner weighting objective on arbitrary bounded gradient sequences and, with entropy regularization and a weight floor, iteration-wise inner-gap control after burn-in while retaining ergodic stationarity, conditional on a trajectory gradient bound. The optimal blended gradient can be nonunique in spectral and sign geometries, motivating a selectionindependent inner gap. Our analysis extends the spectral construction studied by concurrent MOON to general norms. Experiments compare the method with existing multi-task optimizers and examine its oracle, weighting, and momentum choices.

1

I NTRODUCTION

Many learning problems optimize several objectives at once: a shared backbone serving segmentation and depth, a language model balancing helpfulness against safety. Writing f1 , . . . , fK : Rd → R for the losses, one seeks a point that cannot be improved on one objective without degrading another: a Pareto-optimal point. Pareto stationarity is a first-order necessary condition for such optimality. A standard algorithm targeting this condition is multiple gradient descent (Désidéri, 2012; Fliege & Svaiter, 2000; Sener & Koltun, 2018): choose the convex combination of task gradients with smallest norm, w⋆ (x) ∈ arg min ∥∇F (x)w∥2 ,

∇F (x)w :=

w∈∆K

K X

wi ∇fi (x),

(1)

i=1

and step along −∇F (x)w⋆ (x), the conflict-avoidant direction that minimizes maxi ⟨∇fi (x), d⟩ + 1 2 2 ∥d∥2 . A large literature refines the weighting (Yu et al., 2020; Chen et al., 2020; Liu et al., 2021; Navon et al., 2022; Liu et al., 2023; Ban & Ji, 2024) and proves rates for stochastic variants (Liu & Vicente, 2021; Zhou et al., 2022; Fernando et al., 2023; Chen et al., 2024; Xiao et al., 2023; Zhang et al., 2025). Two choices in (1) are Euclidean by inheritance. The parameter update is steepest descent in ℓ2 , whereas a network’s parameters are matrices with their own scales; optimizers that take an LMO step in an operator norm, as in Muon (Jordan et al., 2024), Scion (Pethick et al., 2025) and the duality view of Bernstein & Newhouse (2024; 2025); Large et al. (2024), have improved large-scale training performance (Liu et al., 2025). These methods are single-objective; concurrent MOON (Zhou et al., 2026) brings the spectral constructionpto MOO. The weight update lives on the simplex, where entropic mirror descent gives an O(M log K/T ) regret bound under an ℓ∞ subgradient bound M , 1

Preprint

p compared with the O(M K/T ) bound obtained by converting that same bound to ℓ2 for Euclidean projected descent (Nemirovsky & Yudin, 1983; Beck & Teboulle, 2003; Bubeck, 2015). The closest methods already use elements of this construction. MSMD (Yang et al., 2024) uses entropic mirror descent on the weights with a Euclidean direction variable and a double loop. MOON (Zhou et al., 2026) combines a spectral-norm oracle with logit-based task weighting and establishes the same deterministic and stochastic rate exponents. Our contribution is a general-norm analysis, a derived deterministic trajectory gradient bound, and refinements for blended momentum and inner-problem tracking. P • General-norm deterministic convergence. Theorem 4.4 gives T1 t ∥∇F (xt )wt ∥∗ ≤ p √ √ ( 2∆L + M log K/2)/ T . For the unregularized, unclipped method, Lemma 4.3 derives √ M = O( L∆ log K) from smoothness and lower-boundedness, yielding O(L∆ log2 K/ϵ2 ) iterations without a separate gradient-bound assumption. Each iteration uses K task-gradient evaluations, one oracle call, and one entropic weight update. • Stochastic convergence with one persistent buffer. Under a trajectory gradient bound, Theorem 4.9 gives O(ϵ−4 ) iterations with momentum on the blended gradient. A weighted-average bound on noisy weight increments keeps explicit K dependence out of the leading T −1/4 term; lower-order terms retain linear K dependence under bounded variance, replaced by log K under a stronger tail assumption (Corollary D.4). • Selection-independent inner optimality and iteration-wise tracking. The optimal blended gradient can be nonunique in the Muon and Signum geometries (Proposition 3.1), motivating the inner gap. Theorem 4.5 gives static regret on arbitrary bounded gradient sequences. Average gap and regret are also bounded by the blended-gradient residual, so alone they do not distinguish adaptation from a converged scalarization; with regularization, clipping and a trajectory gradient bound, Theorem 5.1 instead controls the inner gap at every iteration after a Õ(M 4 log2 K/ϵ4 ) burn-in while retaining ergodic stationarity, in any norm but with a non-competitive exponent.

2

R ELATED WORK

Geometry-aware optimizers. Non-Euclidean steepest descent is classical (Nesterov, 2012; Carlson et al., 2015); the current line begins with Bernstein & Newhouse (2024) and Muon (Jordan et al., 2024). Pethick et al. (2025) give the LMO formulation we build on, with O(n−1/4 ) stochastic rates and layer-wise norm and radius choices; Bernstein & Newhouse (2025); Large et al. (2024) develop the duality view; Liu et al. (2025); Riabinin et al. (2025) address scaling, and Yang et al. (2021; 2023) hyperparameter transfer. All are single-objective. Stochastic MGDA. Liu & Vicente (2021) give the first stochastic multi-gradient method; Zhou et al. (2022) show naive stochastic gradient manipulation need not converge; Fernando et al. (2023) fix the bias with a tracking variable; Chen et al. (2024) show a three-way trade-off between optimization, generalization and conflict avoidance; Xiao et al. (2023) add a direction-oriented regularizer. Zhang et al. (2025) analyze MGDA under generalized smoothness with no gradient bound, obtaining O(ϵ−2 ) and O(ϵ−4 ) for average CA distance and O(ϵ−11 ), O(ϵ−17 ) for iteration-wise CA distance; these are our reference point. All are Euclidean with projected weights. The two closest methods. MSMD (Yang et al., 2024) solves the MGDA saddle problem by stochastic mirror descent with the negative entropy on the weights, so the log K benefit of entropic weights is theirs; its direction variable is Euclidean, it is double-loop, and it assumes bounded gradients. MOON (Zhou et al., 2026) uses spectral–nuclear geometry with momentum and logit-based task weighting. Its analysis assumes bounded gradients and losses and carries polynomial dependence on the number of objectives. Our spectral specialization shares this geometric construction; our stochastic analysis evaluates the oracle at the previous buffer to decorrelate the direction from the current minibatch, and our tracking variant adds a weight floor. Practical implementations also differ in momentum, logit updates, and auxiliary optimizers, as detailed in Appendix I; the empirical comparison does not isolate a single change. Our analytical additions are the arbitrary norm pair, the derived deterministic M , comparator-dependent regret, iteration-wise inner gap, nonuniqueness analysis, and the one-buffer K argument. Conditional-gradient MOO (Assunção et al., 2021) ap2

Preprint

Primal ∥ · ∥

Dual ∥ · ∥∗

lmo(g)

Known as

ℓ2 ℓ∞ spectral

ℓ2 ℓ1 nuclear

−R g/∥g∥2 −R sign(g) −R U V ⊤ , G = U ΣV ⊤

normalized SGD Signum (Bernstein et al., 2018) Muon (Jordan et al., 2024)

Table 1: Norm-constrained oracles; Pethick et al. (2025) apply them layer-wise with per-layer radii ρℓ . plies an oracle to the constraint set, a different object. See Chen et al. (2026) for a survey and Nemirovsky & Yudin (1983); Beck & Teboulle (2003); Kivinen & Warmuth (1997); Bubeck (2015) for the entropic mirror-descent bounds we use off the shelf.

3

S ETUP

Norms and the oracle. Fix a norm ∥ · ∥ on Rd , the primal norm, measuring parameter displacements, with dual ∥g∥∗ := sup∥v∥≤1 ⟨g, v⟩ measuring gradients; Hölder’s inequality ⟨g, v⟩ ≤ ∥g∥∗ ∥v∥ holds throughout. Let B := {v : ∥v∥ ≤ R}. The linear minimization oracle is any selection lmo(g) ∈ arg min ⟨g, v⟩,

so that

∥ lmo(g)∥ ≤ R,

⟨g, lmo(g)⟩ = −R∥g∥∗ .

(2)

v∈B

The identity holds for every element of the argmin and is the only property of lmo our analysis uses; we set lmo(0) = 0, so that an exactly zero blend produces a zero parameter step. With entropy regularization, the weights can still change; the full state need not be a fixed point. Table 1 lists the instances of interest. For a network with parameter blocks x = (xℓ )ℓ the norm used in P practice is ∥x∥ := maxℓ ∥xℓ ∥(ℓ) /ρℓ , with dual ∥g∥∗ = ℓ ρℓ ∥gℓ ∥(ℓ),∗ , blockwise oracle lmo(g) = P (ρℓ lmoℓ (gℓ ))ℓ of per-block radius Rρℓ , Assumption 1 imposed in this pair, and ζ 2 ≤ ℓ ρ2ℓ ζℓ2 . The minus sign is inside the oracle: the update is xt+1 = xt + γDt with Dt = lmo(Gt ), which for the Euclidean ball is normalized gradient descent, x − γRg/∥g∥2 (Pethick et al., 2025). ⊤ MOO and, for w ∈ ∆K := {w ≥ P in a norm pair. Write P F (x) = (f1 (x), . . . , fK (x)) P 0, i wi = 1}, ∇F (x)w := i wi ∇fi (x) and F (x)w := i wi fi (x). Definition 3.1 (Stationarity, CA distance, inner gap). x is ϵ-accurate Pareto stationary if minw∈∆K ∥∇F (x)w∥∗ ≤ ϵ; w⋆ (x) denotes a minimizer and d⋆ (x) := ∇F (x)w⋆ (x). For an iterate–weight pair (xt , wt ), the CA distance is CAt := ∥∇F (xt )wt − d⋆ (xt )∥∗ and the inner gap is gapt := ∥∇F (xt )wt ∥∗ − minw∈∆K ∥∇F (xt )w∥∗ ≥ 0. By the reverse triangle inequality gapt ≤ CAt for every selection w⋆ (xt ); gapt = 0 iff wt solves the inner problem; and, unlike CAt , the gap involves no selection.

Two facts about these objects differ from the Euclidean intuition (proofs in Appendix B). Proposition 3.1 (Uniqueness of the optimal blended gradient). If the dual unit ball is strictly convex, d⋆ (x) is the same for every minimizer w⋆ (x), for every instance. If it is not, there is an instance with K = 2 in which every w ∈ ∆K is optimal and d⋆ ranges over a whole segment: take ∇f1 = a, ∇f2 = b for distinct unit vectors a, b with ∥(a + b)/2∥∗ = 1 (for ℓ1 : a = (1, 0), b = (0, 1)). Proposition 3.2 (Stationary points of fixed scalarizations are Pareto stationary). If x̄ is a firstorder stationary point of x 7→ F (x)u for a fixed u ∈ ∆K , i.e. ∇F (x̄)u = 0, then minw∈∆K ∥∇F (x̄)w∥∗ = 0, attained at w = u. Strict convexity holds for ℓp , 1 < p < ∞, and fails for ℓ1 and the nuclear norm, so in exactly the Muon and Signum geometries the CA distance can depend on the selected minimizer; our guarantees hold for any measurable selection or, better, for the selection-free gap. Throughout, K ≥ 2. To distinguish Pareto stationarity P from the residual of the weights actually used, write ψt (w) := ∥∇F (xt )w∥∗ and ST := T −1 t ψt (wt ). Directly from nonnegativity, i X 1 hX 1X gapt ≤ ST , ψt (wt ) − min ψt (u) ≤ ST . (3) u∈∆K T t T t t 3

Preprint

Algorithm 1 Entropic LMO-MGDA (with optional regularization τ ≥ 0 and clipping κ ≥ 0) Require: x0 ∈ Rd ; step sizes γ, η > 0; radius R; regularization τ ≥ 0; clipping κ ∈ [0, 1/K] 1: w0 ← (1/K, . . . , 1/K) 2: for t = 0, 1, . . . , T − 1 do 3: compute ∇fi (xt ) for i ∈ [K] ▷ K backward passes PK 4: Gt ← i=1 wt,i ∇fi (xt ); Dt ← lmo(Gt ) ▷ one oracle call, layer-wise 5: gt,i ← ⟨Dt , ∇fi (xnt )⟩ for i ∈ [K] o 6:

wt+1 ← arg min w∈∆κ K

− η⟨gt , w⟩ + ηRτ KL(w∥uK ) + KL(w∥wt )

▷ softmax then clip, (4)

7: xt+1 ← xt + γDt 8: end for

Also CAt ≤ 2ψt (wt ) in every norm; in Hilbert dual geometry, CA2t ≤ ψt (wt )2 − ψt (w⋆ (xt ))2 (Zhang et al., 2025). Thus convergence of the actual blended-gradient residual implies average-gap, average-CA, and static-regret upper bounds, including for a converged fixed scalarization. Smallness of minw ψt (w) alone does not control a separately chosen wt . The gap is useful as a selection-independent inner optimality measure, but does not certify simultaneous per-task descent for every oracle selection. Appendix B gives the saddle condition and a sign-oracle counterexample. The additional results are a comparator-dependent regret bound valid independently of outer progress (Theorem 4.5) and an every-iterate tracking guarantee after burn-in (Theorem 5.1). Assumptions. Assumption 1 (Smoothness in the norm pair). Each fi is differentiable and ∥∇fi (x) − ∇fi (y)∥∗ ≤ L∥x − y∥.
Assumption 2 (Lower bound). fi⋆ := inf x fi (x) > −∞; ∆ := maxi fi (x0 )−fi⋆ > 0 and L > 0 (if ∆ = 0 or L = 0 every gradient vanishes at x0 and there is nothing to prove; excluding these keeps M > 0 and the step sizes defined). Assumption 3 (Stochastic oracle). With Ft the history up to the computation of xt , wt , the sample ξt is independent of Ft and E[∇fi (xt ; ξt ) | Ft ] = ∇fi (xt ), E[∥∇fi (xt ; ξt )−∇fi (xt )∥22 | Ft ] ≤ σ 2 for every i (a shared minibatch across tasks is allowed). Assumption 4 (Gradient bound; stochastic setting only). maxi ∥∇fi (xt )∥∗ ≤ M a.s. along the trajectory of Algorithm 2. Assumption 3 is in ℓ2 because the √ variance recursion needs an inner product; we convert through p ζ := maxx̸=0 ∥x∥∗ /∥x∥2 (1 for ℓ2 , d for ℓ1 , min(m, n) for the nuclear norm on m×n matrices), as in Pethick et al. (2025). In the deterministic analysis M is derived, not assumed (Lemma 4.3).

4

E NTROPIC LMO-MGDA

Line 6 is entropic mirror descent on the scores gt , with an optional pull of strength τ toward the uniform weighting uK and an optional floor κ on every weight, ∆κK := {w ∈ ∆K : wi ≥ κ}. The sign is correct and counterintuitive: −gt /R is a subgradient of w 7→ ∥∇F (xt )w∥∗ at wt (Lemma A.3), so descending on it ascends in gt : a task well aligned with Dt has gt,i ≪ 0 and loses weight, while a task being harmed gains it. The closed form is a softmax followed by clipping (Lemma F.1): with ρ := ηRτ , n w1/(1+ρ) eηgt,i /(1+ρ) o t,i wt+1,i = max κ, , Zt

Zt such that

P

i wt+1,i = 1,

(4)

where Zt and the set of clipped coordinates are found by a monotone recurrence in at most K rounds (Appendix F.1). At τ = κ = 0 this is exponentiated gradient, wt+1,i ∝ wt,i eηgt,i ; the entropy regularizer shrinks the logits toward a uniform weighting, related to MOON’s logit decay (Zhou et al., 2026). The method costs K backward passes, one oracle call and one softmax per iteration (for κ > 0, Appendix F.1 gives a clipping recurrence with O(K 2 ) worst-case cost, or O(K log K) 4

Preprint

using sorting), stores the K task gradients within an iteration (the scores need Dt ), and needs no inner optimization loop. Sections 4.1–4.2 analyse τ = κ = 0; Section 5 shows that τ, κ > 0 make the weights track the inner optimum at every iterate after a burn-in, without entering the stationarity inequality. 4.1

D ETERMINISTIC ANALYSIS

Three lemmas, proved in Appendix C: the descent lemma in the norm pair turned into a one-step inequality by the oracle identity, the regularized mirror-descent bound, and a self-consistent bound on the gradients along the trajectory. Lemma 4.1 (One-step inequality). Under Assumption 1, for every w ∈ ∆K and every t, F (xt+1 )w ≤ F (xt )w − γR ∥Gt ∥∗ + γ⟨gt , w − wt ⟩ + 12 Lγ 2 R2 .

(5)

The descent −γR∥Gt ∥∗ is linear in the dual norm, not quadratic as for gradient descent; this is why our stationarity criterion is first-moment, as in Pethick et al. (2025). Lemma 4.2 (Regularized entropic mirror descent). Line 6 of Algorithm 1 satisfies, for every u ∈ ∆κK , with ρ = ηRτ and r(w) := KL(w∥uK ),
η⟨gt , u − wt ⟩ ≤ KL(u∥wt ) − (1 + ρ) KL(u∥wt+1 ) + ρ r(u) − r(wt+1 ) + 21 η 2 ∥gt ∥2∞ . (6) For u = uK the regularization terms are ≤ 0; for general u they are ≤ ρ ln K; at τ = κ = 0 this is the standard bound for every u ∈ ∆K . Lemmap4.3 (Trajectory gradient √ bound). Under√Assumptions 1–2, 1 with τ = κ = 0, √ run Algorithmp γR = 2∆/(LT ) and ηR = 2 log K/(M T ). If M ≥ 2 L∆ log K√+ 2 L∆(log K + 1) then ∥∇fi (xt )∥∗ ≤ M for all t ≤ T and i ∈ [K]. In particular M = O( L∆ log K), the larger root of an explicit quadratic, suffices, with no circularity. Theorem 4.4 (Deterministic rate). Under Assumptions 1–2, run Algorithm 1 with any τ ≥ 0, κ ∈ [0, 1/K], and suppose maxi ∥∇fi (xt )∥∗ ≤ M for t < T . Then for every γ, η > 0, T −1

1 X ∆ ηRM 2 LγR ∥∇F (xt )wt ∥∗ ≤ + + , T t=0 γRT 2 2 in which neither τ , κ nor K appears. With the step sizes of Lemma 4.3, p √ T −1 2∆L + M log K/2 1 X √ , ∥∇F (xt )wt ∥∗ ≤ T t=0 T

(7)

(8)

so with t̂ ∈ arg mint<T ∥∇F (xt )wt ∥∗ the output xt̂ is ϵ-accurate Pareto
stationary, minw ∥∇F (xt̂ )w∥∗ ≤ ∥∇F (xt̂ )wt̂ ∥∗ ≤ ϵ, after T = O (∆L + M 2 log K)/ϵ2 iterations; for τ = κ = 0, M is supplied by Lemma 4.3, and substituting M 2 = O(L∆ log K) gives T = O(L∆ log2 K/ϵ2 ). No property of the primal norm beyond Assumption 1 is used. The proof compares against uK , for which KL(uK ∥w0 ) = 0 and the regularization only helps: given the same trajectory gradient bound M , τ, κ do not enter the inequality (they may change the trajectory and hence the smallest valid M ), and log K enters (8) only through η, as the price of adaptivity rather than of stationarity. Since CAt ≤ 2∥∇F (xt )wt ∥∗ by the triangle inequality, the average CA distance obeys twice (8) for every selection (Corollary C.1); equally for a fixed weighting, so this is a consistency statement, not evidence of tracking. The same stationarity bound controls the average inner gap by (3). The next result gives a comparator-dependent guarantee without requiring outer progress. Theorem 4.5 (Inner regret on bounded gradient sequences). Let At : RK → Rd , t < T , be any sequence of linear maps with maxi ∥At ei ∥∗ ≤ M , where M > 0. Start from w0√= uK and set √ ηgt,i Dt = lmo(At wt ), gt = A⊤ with ηR = 2 log K/(M T ). Then, for t Dt , and wt+1,i ∝ wt,i e every u ∈ ∆K , r T −1 T −1 1 X 1 X 2 log K ∥At wt ∥∗ ≤ ∥At u∥∗ + M . (9) T t=0 T t=0 T In particular, this holds for At = ∇F (xt ) under the conditions of (8) with τ = κ = 0. 5

Preprint

The subgradient inequality gives ∥At wt ∥∗ − ∥At u∥∗ ≤ ⟨gt , u − wt ⟩/R, and Lemma 4.2 sums the right-hand side. The proof is pathwise, allows adaptively chosen sequences, and needs neither smooth losses nor outer descent. The comparator is evaluated on the algorithm’s own trajectory; on a prescribed sequence with constant columns a, −a, a fixed e1 has regret ∥a∥∗ against the uniform weighting, which says nothing about scalarization on its own trajectory. Corollary 4.6 (Static regret to gap decomposition). Under the conditions of Theorem 4.5 with At = ∇F (xt ), r T −1 T −1 i 1 X 1 Xh 2 log K gapt ≤ M + VT , VT := min ∥∇F (xt )u∥∗ − min ∥∇F (xt )w∥∗ , u∈∆K T w∈∆K T t=0 T t=0 (10) where the comparator-variation term VT ≥ 0 is the shortfall of the best fixed weighting against the per-iterate optimum, a property of the trajectory rather than of the update. This decomposition is informative when VT is controlled. Along the trajectory covered by Theorem 4.4, (3) already gives average-gap convergence at the stationarity rate, without requiring VT → 0; one may take the smaller of the two bounds. In the Euclidean case CA2t ≤ 2M gapt , and under the uniform convexity inequality (S2) of Appendix G, CAqt ≤ (q/µ)M q−1 gapt (Remark C.1). 4.2

S TOCHASTIC ANALYSIS WITH MOMENTUM ON THE BLENDED GRADIENT

The oracle is nonlinear, so single-minibatch noise biases the direction at any fixed batch size. Averaging before the oracle call controls this error (Pethick et al., 2025); our analysis uses momentum with a horizon-dependent averaging parameter. Stochastic MGDA methods average each task gradient separately (Fernando et al., 2023; Xiao et al., 2023), storing K buffers; the alternative, which any implementation handing the MGDA direction to a momentum optimizer already uses, blends first: bt = G

K X

wt,i ∇fi (xt ; ξt,i ),

bt , Mt = (1 − α)Mt−1 + αG

Dt = lmo(Mt−1 ).

(11)

i=1

This is Algorithm 2 (Appendix D). P The tracking errorPis one vector λt := Mt − ∇F (xt )wt whose noise part is K-free √ by Jensen, E∥ i wt,i nt,i ∥22 ≤ i wt,i E∥nt,i ∥22 ≤ σ 2 (the per-task bound in Appendix E carries K). Evaluating the oracle at Mt−1 makes Dt measurable before ξt , so the score-noise cross term has zero conditional mean. The buffer chases a target moving with w√t , which moves by noisy scores; the pathwise bound ∥wt+1 − wt ∥1 ≤ 2η∥gt ∥∞ would bring in a K, and the next lemma avoids it. Lemma 4.7 (Weight increment under noisy scores). Let wt+1 be obtained from wt by line 6 of Algorithm 2. Pathwise, ∥wt+1 − wt ∥1 ≤ 2η∥gt ∥∞ . If Assumptions 3–4 hold and ηRM ≤ 12 ,   E ∥wt+1 − wt ∥1 | Ft ≤ ω := 16 ηR (M + ζσ) + 8Kη 2 R2 ζ 2 σ 2 . K appears only at second order in η: a task can move the weights by a large amount only if its noisy score is large, which has probability O(η 2 ). Lemma 4.8 (Tracking error). Under Assumptions 1–4 and ηRM ≤ 21 , splitting λt = νt + δt into noise and drift, E∥νt ∥22 ≤ σ 2 (α + (1 − α)2t ) and E∥δt ∥∗ ≤ (LγR + M ω)/α√(the x-part admits a deterministic bound since ∥xt − xt−1 ∥ ≤ γR pathwise), so E∥λt ∥∗ ≤ ζσ( α + (1 − α)t ) + (LγR + M ω)/α. Theorem 4.9 (Stochastic rate). Under Assumptions 1–4, run Algorithm 2 with T ≥ (2/M )4/3 , α = T −1/2 , γR = T −3/4 and ηR = T −3/4 /M 2 . Then T −1

1 X ∆ + 2L + 32 + 2ζσ(1 + 16/M ) C2 C3 C4 E ∥∇F (xt )wt ∥∗ ≤ + 1/2 + 3/4 + , T t=0 T T 1/4 T T

(12)

with C2 = 2ζσ, C3 = 1 + 52 L + 32(1 + ζσ/M ) + ζ 2 Kσ 2 /M 2 and C4 = 2M + 32Kζ 2 σ 2 /M 3 . Writing C1 for the numerator of the first term, the right-hand side is at most ϵ once T ≥ max{(4C1 /ϵ)4 , (4C2 /ϵ)2 , (4C3 /ϵ)4/3 , 4C4 /ϵ}; the average CA distance obeys the same bound up 6

Preprint

to a factor 2 for every measurable selection, and for t̂ uniform on {0, . . . , T − 1} drawn after the run, E minw ∥∇F (xt̂ )w∥∗ ≤ E∥∇F (xt̂ )wt̂ ∥∗ is bounded by (12). C1 is free of K; K enters C3 through the ℓ∞ error term of mirror descent on noisy scores and C4 through Lemma 4.7. The K-free requirement T ≥ (4C1 /ϵ)4 determines the count whenever C3 ≤ 16C13 /ϵ2 and C4 ≤ 64C14 /ϵ3 , i.e. for K ≲ ϵ−2 M 2 /(ζ 2 σ 2 ) as ϵ → 0. Here “K-free” means no explicit dependence with L, M, ∆, ζ, σ fixed (these can change with task scaling and norm choices). By (3), (12) also bounds the expected average inner gap. Two corollaries in Appendix D give further comparator and noise-tail bounds. Corollary D.3 bounds the stochastic inner regret against any deterministic u by (12) with ∆ → M 2 ln K, hence the average expected P 1 gap up to V̄T := minu E T t [∥∇F (xt )u∥∗ − minw ∥∇F (xt )w∥∗ ] ≥ EVT . Corollary D.4 shows that under a sub-Gaussian tail bound the linear-K terms of C3 , C4 become ln K, so every constant is polylogarithmic in K. The condition T ≥ (2/M )4/3 is ηRM ≤ 12 . The gradient bound is assumed here because Lemma 4.3’s induction controls fi along a deterministic path, whereas the stochastic one-step inequality has terms controlled only in expectation (Remark D.1). The weight step is Θ(T −3/4 /M 2 ) −1/2 rather /M ) because the latter leaves a residual Θ(M ) in the drift; this costs a factor √ than Θ(T M log K in the regret constant only (Appendix E compares with per-task tracking).

5

I TERATION - WISE INNER GAP

A per-iterate guarantee, which Zhang et al. (2025) obtain for the CA distance in the Euclidean case at O(ϵ−11 ) and O(ϵ−17 ), is stronger than an ergodic one; to track a moving target we make the inner problem strongly convex. Here τ > 0 makes ψ̃t (w) := ∥∇F (xt )w∥∗ + τ KL(w∥uK ) strongly convex with a unique minimizer pt over ∆κK , and κ > 0 keeps the divergence to that target finite; neither enters (7). The analysis uses only three norm-free facts: −gt /R is a subgradient of w 7→ ∥∇F (xt )w∥∗ , that function is M -Lipschitz in ∥ · ∥1 , and it moves by at most L∥x − x′ ∥ when x moves. Theorem 5.1 (Iteration-wise inner gap, with progress). Let Assumptions 1–2 hold and suppose maxi ∥∇fi (xt )∥∗ ≤ M along the trajectory of Algorithm 1. Fix a tracking accuracy ϵ ∈ (0, 1] with ϵ ≤ 2M and a bias accuracy β ∈ (0, ϵ], and set τ=

β , 2 ln K

κ=

β , 4M K

ηR =

ϵ2 β , 768 M 4 ln K

γR =

ϵ6 β 6 27 · 228 (2 + Λ) L M 11 K ln5 K

with Λ := ln(4M K/β). Then, for any primal norm:   4 2 2 (i) Tracking. For every t ≥ T0 := 6144 ϵM2 β 2ln K ln 24Mϵ2ln K : ∥wt − pt ∥1 ≤ ϵ/(2M ) and gap(pt ) := ∥∇F (xt )pt ∥∗ − minw ∥∇F (xt )w∥∗ ≤ β, hence gapt ≤ ϵ/2 + β. With β = ϵ/2: gapt ≤ ϵ for all t ≥ T0 = Õ(M 4 ln2 K/ϵ4 ). (ii) Progress. For every T , (7) holds, and its right-hand side is at most ϵ/2 for T ≥ T1 := ⌈4∆/(γR ϵ)⌉; with β = ϵ/2, T1 = Õ(∆LM 11 K/ϵ13 ). (iii) Tail output. For T ≥ max{2T0 , T1 } and t̂ ∈ arg minT0 ≤t<T ∥∇F (xt )wt ∥∗ , the single iterate (xt̂ , wt̂ ) satisfies both ∥∇F (xt̂ )wt̂ ∥∗ ≤ ϵ, hence minw ∥∇F (xt̂ )w∥∗ ≤ ϵ, and gapt̂ ≤ ϵ/2 + β. If ϵ > 2M all conclusions are trivial. Corollary 5.2 (Iteration-wise CA distance under uniform convexity). If the dual norm satisfies (S2) with power type q and constant µ (all ℓp , Schatten-p, 1 < p < ∞; Proposition G.1), then
1/q CAt ≤ M ∥wt − pt ∥1 + (q/µ)M q−1 gap(pt ) for every selection, so Theorem 5.1 with β = q q q−1 µϵ /(q2 M ) gives CAt ≤ ϵ for t ≥ T0 ; in the Euclidean case T0 = Õ(M 6 ln2 K/ϵ6 ), T1 = 17 Õ(∆LM K/ϵ19 ). The ϵ−13 bound concerns inner gap, whereas the ϵ−11 deterministic bound of Zhang et al. (2025) concerns Euclidean CA distance under different smoothness assumptions. For the latter metric our 7

,

Preprint

Method

mIoU↑

Pix Acc↑

Abs Err↓

Rel Err↓

∆m% ↓

STL

74.11

93.44

0.0137

38.22

0.00

LS SI RLW DWA UW MGDA PCGrad GradDrop CAGrad MoCo MoDo Nash-MTL FAMO MGDA (warm) MOON

74.80 67.77 74.24 74.42 71.56 73.12 75.89 75.85 75.83 74.37 74.71 74.76 74.19 75.64 78.53

93.37 89.97 93.30 93.41 92.15 92.80 93.72 93.70 93.50 93.17 93.51 93.29 93.28 93.60 94.15

0.0188 0.0151 0.0169 0.0159 0.0191 0.0157 0.0150 0.0151 0.0145 0.0221 0.0152 0.0144 0.0154 0.0147 0.0141

42.41 34.65 47.09 41.94 38.75 36.03 45.83 43.60 35.89 81.06 44.31 33.47 30.62 47.00 31.39

11.83 3.29 11.63 6.35 11.41 2.72 6.67 5.42 -0.66 43.33 6.50 -2.01 -1.85 7.01 -5.42

Entropic LMO-MGDA (ours)

79.03

94.48

0.0136

36.29

-3.38

Table 2: Results on CityScapes dataset. The best and second-best values are highlighted in bold and underlined, respectively. The task-specific metrics and the performance drop ∆m% are reported. conversion gives Õ(ϵ−19 ), so we claim no competitive exponent. The content is an iteration-wise inner-gap guarantee with simultaneous ergodic progress and one tail-selected iterate carrying both, in any norm, conditional on the gradient bound M (a hypothesis here, unlike in Theorem 4.4; Remark F.2). The tracked object is the regularized floored target pt ; the gap to the original inner problem comes through β. Why we track the unsquared objective, unlike the Euclidean analyses, and what it costs, is explained in Remark F.1; proofs are in Appendix F.

6

E XPERIMENTS

We evaluate on Cityscapes (K = 2: segmentation and depth) and NYU-v2 (K = 3: segmentation, depth, surface normals) with the SegNet/MTAN protocol of Navon et al. (2022); Liu et al. (2023), against single-task learning (STL), linear scalarization (LS), SI, RLW, DWA and UW weighting, MGDA (cold and warm-started), PCGrad, GradDrop, CAGrad, MoCo, MoDo, Nash-MTL, FAMO and MOON. Our method is Algorithm 2 with the spectral oracle on matrix-valued parameters. Tables 2 and 3 report per-task metrics and ∆m%, the mean relative degradation against the single-task (STL) row of each table (lower is better). The reported architectures, hyperparameters, and tuning settings are in Appendix I. The dense-prediction results use one seed, averaging the final ten epochs; they do not quantify variation across independent training runs. Our step sizes and schedule were tuned on the split on which results are reported, whereas the baselines use their reference hyperparameters (Appendix I.1). On Cityscapes, our method achieves the highest segmentation scores and the lowest absolute depth error among the reported methods. MOON achieves a lower aggregate degradation, −5.42% versus −3.38%, driven by its lower relative depth error. On NYU-v2, our method achieves the lowest reported aggregate degradation, −6.80% versus −3.72% for MOON. These are descriptive comparisons from single runs. With K = 2, 3, they do not establish the predicted scaling advantage with the number of objectives, and the implementation differences do not isolate the contribution of geometry or weighting. 6.1

M ULTI MNIST: COMPARISON WITH MOON AND ABLATIONS

We follow MOON’s MultiMNIST setup (K = 2: left and right digit, small ViT). Because its dataset instance is not released, we regenerate the data and rerun each method (Appendix I.2); only withintable comparisons are meaningful. The reported mean accuracy is 90.54% for our configuration and 87.47% for MOON. Hyperparameters for our method, including the weight step, are selected on a fixed validation split drawn from MNIST-train and frozen before evaluation on MNIST-test. Every value of the η and κ grids (Tables 5, 6) gives at least 89.5%, above all baselines. The spectral 8

Preprint

Segmentation

Depth

Surface normal

Method

mIoU↑

Pix Acc↑

Abs↓

Rel↓

Mean↓

Med.↓

< 11.25 ↑

< 22.5 ↑

< 30 ↑

∆m% ↓

STL

38.77

63.98

0.6350

0.2654

25.10

19.06

30.12

57.66

69.53

0.00

LS SI RLW DWA UW MGDA PCGrad GradDrop CAGrad MoCo MoDo Nash-MTL FAMO MGDA (warm) MOON

38.13 38.59 38.45 39.57 38.48 33.79 38.79 40.37 41.61 35.47 39.41 38.18 32.57 38.41 39.88

64.83 64.57 64.61 65.19 63.88 62.12 65.08 66.04 66.95 61.76 65.82 65.39 61.67 63.76 67.30

0.5523 0.2334 0.5439 0.2339 0.5814 0.2454 0.5691 0.2399 0.5555 0.2294 0.5906 0.2398 0.5501 0.2212 0.5536 0.2353 0.5444 0.2251 0.5808 0.2328 0.5353 0.2225 0.5575 0.2325 0.5411 0.2220 0.5813 0.2453 0.4951 0.2152

27.79 27.57 27.83 27.40 27.47 24.47 27.18 27.97 25.75 31.21 25.54 25.12 25.16 28.13 25.50

23.56 23.43 23.46 22.87 23.38 18.65 22.74 23.76 20.79 27.97 20.08 19.85 19.25 24.03 20.02

23.03 22.81 23.20 24.26 23.18 31.28 24.10 22.78 27.44 15.31 28.57 29.13 30.18 21.43 29.44

48.23 48.45 48.51 49.61 48.60 58.50 49.93 47.97 53.99 39.38 55.34 55.97 57.16 47.24 55.34

61.64 62.18 61.81 62.81 62.29 70.28 63.36 61.39 66.85 54.01 67.78 68.48 69.10 61.13 67.71

6.76 6.32 7.53 5.37 6.23 -1.33 4.23 6.39 -1.18 18.38 -1.96 -1.48 -1.00 9.15 -3.72

Entropic LMO-MGDA (ours)

42.71

68.07

0.5075 0.2129

23.76

19.18

30.27

57.34

69.60

-6.80

Table 3: Results on NYU-v2 dataset. The best and second-best values are highlighted in bold and underlined, respectively. The task-specific metrics and the performance drop ∆m% are reported.

Method

Left↑ Right↑ Avg.↑

MGDA MGDA + Muon FAMO FAMO + Muon Muon (LS) MOON

83.63 84.48 85.24 87.28 87.45 86.87

85.13 86.43 87.29 88.02 88.04 88.06

84.38 85.45 86.27 87.65 87.75 87.47

Entropic LMO-MGDA (Ours) 89.86

91.23

90.54

Component Variant

Avg.↑

Gap↓

Oracle

ℓ2 sign spectral

49.59 89.01 90.54

0.55 6.38 0.90

Weights

entropic projected

90.54 90.51

0.90 0.97

Momentum blended per-task none

90.54 90.16 81.68

0.90 1.41 1.65

Step η

10−5 to 10−3 89.5–90.5 0.29–1.97

Table 4: MultiMNIST with a ViT backbone. Left: test accuracy (%), mean over three seeds on the same regenerated data. Best and second-best values are shown in bold and underlined. Right: fixed-hyperparameter substitutions with the final encoder-only inner gap, in each oracle’s dual norm (not comparable across oracle rows). Details in Appendix I.2.

oracle is best under the fixed step sizes used in the ablation, removing momentum reduces accuracy by 8.86 points, and entropic and projected weights give similar means at K = 2; these are fixedhyperparameter substitutions, not separately tuned comparisons.

7

C ONCLUSION

We analyzed a single-loop entropic-LMO method for multi-objective optimization in arbitrary norm pairs: O(ϵ−2 ) deterministic stationarity with a derived gradient bound, O(ϵ−4 ) stochastic stationarity with one persistent buffer and no explicit K in the leading term, static regret of the weights on bounded gradient sequences, and, with regularization and clipping, iteration-wise inner-gap control after burn-in. The inner gap avoids the minimizer-selection dependence of CA distance in spectral and sign geometries. It does not by itself certify simultaneous descent, and its average, like average static regret, is already controlled by the actual blended-gradient residual. The distinct tracking conclusion is the every-iterate guarantee after burn-in, not average-gap convergence alone. Several limitations remain. Appendix H tolerates fixed relative oracle error for deterministic stationarity and average gap, but not yet for the stochastic or iteration-wise guarantees. The gradient bound is derived only in the deterministic unregularized case, and the tracking exponents are not competitive with Euclidean CA-distance results. Experiments have K ≤ 3 and τ = κ = 0, so they do not test many-objective scaling or regularized tracking. 9

Preprint

AI USE STATEMENT We used a large language model as an assistant for restructuring and editing the manuscript, checking and tightening proofs, drafting parts of the experiment code, and suggesting related work. The authors verified all such output. The research ideas, the method, and the main results are the authors’ own, and the authors take full responsibility for the content of this work. R EPRODUCIBILITY STATEMENT All theoretical results are stated together with their assumptions (Assumptions 1–4), and complete proofs are in Appendices A–H: the structural results in Appendix B, the deterministic analysis in Appendix C, the stochastic analysis in Appendix D, the iteration-wise analysis in Appendix F, the uniform-convexity conversions in Appendix G and the inexact-oracle analysis in Appendix H; explicit constants are given throughout. The method is fully specified by Algorithms 1 and 2, the closed-form weight update (4) and the clipping recurrence of Algorithm 3. Appendix I describes the architectures, data construction, reported hyperparameters and tuning grids, seed counts, validation splits, reporting protocol, ablations, and empirical encoder-only gap. The ∆m% values are computed from the per-task metrics with the reference values given there. An anonymous implementation of all methods and experiments is available at https://anonymous.4open.science/ r/LMO-MOO-D648/.

R EFERENCES P. B. Assunção, O. P. Ferreira, and L. F. Prudente. Conditional gradient method for multiobjective optimization. Computational Optimization and Applications, 78:741–768, 2021. Keith Ball, Eric A. Carlen, and Elliott H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Inventiones Mathematicae, 115:463–482, 1994. Hao Ban and Kaiyi Ji. Fair resource allocation in multi-task learning. In International Conference on Machine Learning (ICML), 2024. Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167–175, 2003. Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology. arXiv:2409.20325, 2024. Jeremy Bernstein and Laker Newhouse. Modular duality in deep learning. In International Conference on Machine Learning (ICML), 2025. Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International Conference on Machine Learning (ICML), 2018. Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231–357, 2015. David Carlson, Volkan Cevher, and Lawrence Carin. Stochastic spectral descent for restricted Boltzmann machines. In Artificial Intelligence and Statistics (AISTATS), 2015. Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multiobjective learning: Optimization, generalization and conflict-avoidance. Journal of Machine Learning Research, 25:1–53, 2024. Weiyu Chen, Baijiong Lin, Xiaoyuan Zhang, Xi Lin, Han Zhao, Qingfu Zhang, and James Kwok. Gradient-based multi-objective deep learning: Algorithms, theories, applications, and beyond. Transactions on Machine Learning Research, 2026. ISSN 2835-8856. URL https: //openreview.net/forum?id=eCUcXXH3PS. Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong, Henrik Kretzschmar, Yuning Chai, and Dragomir Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout. In Advances in Neural Information Processing Systems (NeurIPS), 2020. 10

Preprint

Jean-Antoine Désidéri. Multiple-gradient descent algorithm (MGDA) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313–318, 2012. 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 International Conference on Learning Representations (ICLR), 2023. Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479–494, 2000. Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks. https: //kellerjordan.github.io/posts/muon/, 2024. Jyrki Kivinen and Manfred K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1):1–63, 1997. Tim Large, Yang Liu, Minyoung Huh, Hyojin Bahng, Phillip Isola, and Jeremy Bernstein. Scalable optimization in the modular norm. In Advances in Neural Information Processing Systems (NeurIPS), 2024. Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021. Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. FAMO: Fast adaptive multitask optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2023. Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, et al. Muon is scalable for LLM training. arXiv:2502.16982 [cs.LG], 2025. Suyun Liu and Luis Nunes Vicente. The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning. Annals of Operations Research, 2021. Charles A. McCarthy. cp . Israel Journal of Mathematics, 5:249–271, 1967. Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi-task learning as a bargaining game. In International Conference on Machine Learning (ICML), 2022. Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983. Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341–362, 2012. Thomas Pethick, Wanyun Xie, Kimon Antonakopoulos, Zhenyu Zhu, Antonio Silveti-Falls, and Volkan Cevher. Training deep learning models with norm-constrained LMOs. In International Conference on Machine Learning (ICML), 2025. Artem Riabinin, Egor Shulgin, Kaja Gruntkowska, and Peter Richtárik. Gluon: Making Muon and Scion great again (bridging theory and practice of lmo-based optimizers for llms). arXiv:2505.13416 [cs.LG], 2025. Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018. Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171–176, 1958. Peiyao Xiao, Hao Ban, and Kaiyi Ji. Direction-oriented multi-objective learning: Simple and provable stochastic algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 11

Preprint

Greg Yang, Edward J. Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao. Tensor programs V: Tuning large neural networks via zero-shot hyperparameter transfer. In Advances in Neural Information Processing Systems (NeurIPS), 2021. Greg Yang, James B. Simon, and Jeremy Bernstein. A spectral condition for feature learning. arXiv:2310.17813 [cs.LG], 2023. Linxi Yang, Liping Tang, Jiahao Lv, Yuehong He, and Xinmin Yang. Mirror descent method for stochastic multi-objective optimization. arXiv:2410.06632, 2024. Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020. Qi Zhang, Peiyao Xiao, Shaofeng Zou, and Kaiyi Ji. MGDA converges under generalized smoothness, provably. In International Conference on Learning Representations (ICLR), 2025. Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence of stochastic multi-objective gradient manipulation and beyond. In Advances in Neural Information Processing Systems (NeurIPS), 2022. Shiji Zhou, Kunlin Lyu, Lei Zhang, Ruodong Wang, and Yifan Sun. MOON: Multi-objective orthonormalized updates for multitask learning. arXiv:2608.11749, 2026.

12

Preprint

A

P RELIMINARIES FOR THE PROOFS

Throughout, ∥ · ∥ is the primal norm on Rd , ∥ · ∥∗ its dual, B = P{v : ∥v∥ ≤ R}, and lmo is as in (2). We write A := ∇F (x) for the linear map RK → Rd , Aw = i wi ∇fi (x), and A⊤ for its adjoint, so (A⊤ d)i = ⟨∇fi (x), d⟩. We record three elementary facts. Lemma A.1 (Descent lemma in a norm pair). Under Assumption 1, for all x, y ∈ Rd and each i, fi (y) ≤ fi (x) + ⟨∇fi (x), y − x⟩ + L2 ∥y − x∥2 . Proof. By the fundamental theorem of calculus along the segment, Z 1 ⟨∇fi (x + t(y − x)) − ∇fi (x), y − x⟩ dt. fi (y) − fi (x) − ⟨∇fi (x), y − x⟩ = 0

Applying Hölder’s inequality ⟨g, v⟩ ≤ ∥g∥∗ ∥v∥ and then Assumption 1 with ∥(x + t(y − x)) − x∥ = t∥y − x∥, Z 1 Z 1 ∥∇fi (x + t(y − x)) − ∇fi (x)∥∗ ∥y − x∥ dt ≤ Lt∥y − x∥2 dt = L2 ∥y − x∥2 . ≤ 0

0

Lemma A.2 (Gradient bound from the function value). Under Assumptions 1–2, ∥∇fi (x)∥2∗ ≤
⋆ 2L fi (x) − fi for all x and i. Proof. If ∇fi (x) = 0 there is nothing to prove, so assume ∇fi (x) ̸= 0. Since Rd is finitedimensional the primal unit ball is compact, so the supremum defining ∥∇fi (x)∥∗ is attained: there is v with ∥v∥ = 1 and ⟨∇fi (x), v⟩ = −∥∇fi (x)∥∗ (negate a maximizer). For s > 0, Lemma A.1 applied at y = x + sv gives fi⋆ ≤ fi (x + sv) ≤ fi (x) − s ∥∇fi (x)∥∗ + L2 s2 . Minimizing the right-hand side over s > 0 at s = ∥∇fi (x)∥∗ /L yields fi⋆ ≤ fi (x) − ∥∇fi (x)∥2∗ /(2L), which rearranges to the claim. Lemma A.3 (Subgradient of the weight objective). Fix x and let ψ(w) := ∥Aw∥∗ on RK . For every d ∈ lmo(Aw) we have −A⊤ d/R ∈ ∂ψ(w); componentwise, −g/R ∈ ∂ψ(w) where gi = ⟨d, ∇fi (x)⟩. Proof. Because B = −B is symmetric, the dual norm is the support function ∥h∥∗ = R1 maxv∈B ⟨h, v⟩, which is convex with ∂∥ · ∥∗ (h) = R1 arg maxv∈B ⟨h, v⟩ = − R1 arg minv∈B ⟨h, v⟩ = − R1 lmo(h). The chain rule for the composition of a convex function with a linear map gives A⊤ ∂∥ · ∥∗ (Aw) ⊆ ∂ψ(w), whence the claim. Lemma A.3 justifies the sign in line 6 of Algorithm 1: since −gt /R is a subgradient of ψ at wt , a mirror-descent step minimizing ψ moves along −η(−gt /R), i.e. along +ηgt after absorbing R into η. Note that the lemma holds for every element of lmo(Aw), so no selection rule is needed for our analysis.

B

S TRUCTURAL PROPERTIES OF THE CA DIRECTION

Proof of Proposition 3.1. The set S = {Aw : w ∈ ∆K } = conv{∇f1 (x), . . . , ∇fK (x)} is convex and compact. Let m := minh∈S ∥h∥∗ and suppose g1 , g2 ∈ S both attain m with g1 ̸= g2 . If m = 0 then g1 = g2 = 0, a contradiction; so m > 0. Then g1 /m and g2 /m are distinct points of the +g2 2 dual unit sphere, and strict convexity of the dual unit ball gives ∥ g12m ∥∗ < 1, i.e. ∥ g1 +g 2 ∥∗ < m. g1 +g2 But 2 ∈ S by convexity, contradicting minimality of m. Hence the minimizing value Aw⋆ is unique. For the converse, suppose the dual unit ball is not strictly convex: there are distinct a, b with ∥a∥∗ = ∥b∥∗ = 1 and ∥m∥∗ = 1 for m := (a + b)/2. Let φ be a norming functional at m, i.e. φ(m) = 1 and |φ(y)| ≤ ∥y∥∗ for all y (it exists by compactness of the primal unit ball, since ∥m∥∗ = 13

Preprint

max∥v∥≤1 ⟨m, v⟩). Then φ(a) ≤ 1, φ(b) ≤ 1 and 12 (φ(a) + φ(b)) = φ(m) = 1 force φ(a) = φ(b) = 1, so for every θ ∈ [0, 1],
1 = φ θa + (1 − θ)b ≤ ∥θa + (1 − θ)b∥∗ ≤ θ∥a∥∗ + (1 − θ)∥b∥∗ = 1, and the whole segment [a, b] lies on the unit sphere. Take K = 2 with ∇f1 (x) = a, ∇f2 (x) = b: then ∥Aw∥∗ = 1 for every w ∈ ∆K , every w is optimal, and Aw⋆ ranges over [a, b]. For ∥ · ∥∗ = ℓ1 one may take a = (1, 0), b = (0, 1); for the nuclear norm, a = E11 , b = E22 . Hence strict convexity of the dual ball is necessary and sufficient for the optimal blended gradient to be unique in every instance. P Proof of Proposition 3.2. The function x 7→ F (x)u = i ui fi (x) is differentiable with gradient ∇F (x)u, so first-order stationarity is ∇F (x̄)u = 0 (a minimizer is a special case), and then minw∈∆K ∥∇F (x̄)w∥∗ ≤ ∥∇F (x̄)u∥∗ = 0, attained at w = u. We now record the selection criterion mentioned in Section 3. Let Φx (w, d) = ⟨∇F (x)w, d⟩ on ∆K × B. Since mind∈B Φx (w, d) = −R∥∇F (x)w∥∗ by definition of the dual norm, Sion’s minimax theorem (Sion, 1958) gives max min Φx (w, d) = min max Φx (w, d) = −R min ∥∇F (x)w∥∗ ,

w∈∆K d∈B

d∈B w∈∆K

w∈∆K

(13)

so the CA problem is maxw mind Φx , with w the maximizing and d the minimizing player. Proposition B.1 (When the oracle output is conflict-avoidant). Fix x, let w ∈ ∆K , G = ∇F (x)w, and let D ∈ lmo(G) with gi = ⟨∇fi (x), D⟩. Then (w, D) is a saddle point of Φx on ∆K × B if and only if max gi = −R ∥G∥∗ . (14) i∈[K]

When (14) holds, every objective improves by at least R∥G∥∗ along D, which by (13) is the optimal guaranteed worst-case improvement over B. If ∥·∥∗ is differentiable at G then lmo(G) is a singleton and (14) holds automatically for any minimizer w of ψ; if not, (14) can fail for some elements of lmo(G). Proof. D ∈ lmo(G) is exactly the statement that D minimizes Φx (w, ·) over B. The remaining saddle condition is that w maximizes Φx (·, D) = ⟨g, ·⟩ over ∆K , i.e. that w is supported on arg maxi gi , i.e. that ⟨g, w⟩ = maxi gi . Since ⟨g, w⟩ = ⟨∇F (x)w, D⟩ = ⟨G, D⟩ = −R∥G∥∗ by (2), this is (14). Under (14) we get −gi ≥ R∥G∥∗ for every i, which is the stated improvement. If ∥ · ∥∗ is differentiable at G then ∂∥ · ∥∗ (G) is a singleton, so by Lemma A.3 ∂ψ(w) = {−g/R} and first-order optimality of w on ∆K coincides with (14). For the failure, take the instance in the proof of Proposition 3.1 with w = e1 , so G = (1, 0) and lmo(G) = {(−R, d2 ) : |d2 | ≤ R}, every element of which satisfies ⟨G, v⟩ = −R = −R∥G∥1 . Here g = (−R, d2 ) and (14) reads max(−R, d2 ) = −R, forcing d2 = −R. The selection d2 = +R gives g2 = R > 0: the second objective is actively degraded, while the choice D = (−R, −R) improves both by R. The usual sign selection with sign(0) = 0 can also harm a task at an inner minimizer. Take R = 1, primal ℓ∞ , gradients a = (2, −1), b = (−2, 3), and w = (1/2, 1/2). Then Aw = (0, 1) and ∥A(q, 1−q)∥1 = |4q−2|+|3−4q| ≥ 1 for all q ∈ [0, 1], with equality at q = 1/2. Thus the inner gap is zero, but D = − sign(Aw) = (0, −1) gives ⟨a, D⟩ = 1 > 0. These gradients occur at the origin for the lower-bounded smooth quadratics f1 (x) = 12 ∥x∥22 + ⟨a, x⟩ and f2 (x) = 21 ∥x∥22 + ⟨b, x⟩. Inner optimality therefore does not alone certify per-task descent, even for a conventional oracle selection. We stress that Theorem 4.4 and Theorem 4.9 do not require (14). The reason is that the mirrordescent bound (6) holds for an arbitrary vector gt , and by Lemma A.3 every element of lmo(Gt ) produces a valid subgradient; the only property of Dt used elsewhere is the identity ⟨Gt , Dt ⟩ = −R∥Gt ∥∗ , which likewise holds for every element. Selection therefore affects the per-iteration guarantee of Proposition B.1, not the average-case rates. 14

Preprint

C

P ROOFS FOR THE DETERMINISTIC SETTING

Proof of Lemma 4.1. Fix wP ∈ ∆K . Multiplying Lemma A.1 (with y = xt+1 , x = xt ) by wi ≥ 0 and summing over i, using i wi = 1 for the quadratic term, F (xt+1 )w ≤ F (xt )w + ⟨∇F (xt )w, xt+1 − xt ⟩ + L2 ∥xt+1 − xt ∥2 . By line 7 of Algorithm 1, xt+1 − xt = γDt with ∥Dt ∥ ≤ R, so the last term is at most 12 Lγ 2 R2 . For the inner product, decompose ∇F (xt )w = Gt + ∇F (xt )(w − wt ) and use (2): X ⟨∇F (xt )w, Dt ⟩ = ⟨Gt , Dt ⟩ + (wi − wt,i )⟨∇fi (xt ), Dt ⟩ = −R∥Gt ∥∗ + ⟨gt , w − wt ⟩. i

P Proof of Lemma 4.2. Let Φ(w) = i wi ln wi with ∇Φ(w) = (1 + ln wi )i , whose Bregman divergence is DΦ (u, v) = KL(u∥v) for u ∈ ∆K and v in the relative interior (with 0 ln 0 = 0). Write C := ∆κK and h(w) := −η⟨gt , w⟩ + ρ r(w) + KL(w∥wt ), ρ = ηRτ, so that wt+1 = arg minC h. Both r = KL(·∥uK ) and KL(·∥wt ) have Bregman divergence KL(u∥v) with respect to themselves, and the linear term contributes nothing, so h is (1+ρ)-strongly convex relative to Φ: for all u ∈ ∆K and v in the relative interior, h(u) = h(v) + ⟨∇h(v), u − v⟩ + (1 + ρ) KL(u∥v).

(15)

The function h is differentiable at wt+1 : if κ > 0, every point of C has all coordinates at least κ > 0, so h is differentiable on all of C, including at points with some wi = κ (where the clipped solution may well lie); if κ = 0, the minimizer has all coordinates positive because ∂i KL(w∥wt ) = ln(wi /wt,i ) + 1 → −∞ as wi ↓ 0 while wt has positive coordinates. Hence first-order optimality over the convex set C gives ⟨∇h(wt+1 ), u − wt+1 ⟩ ≥ 0 for all u ∈ C. Hence, by (15) at v = wt+1 , h(u) ≥ h(wt+1 ) + (1 + ρ) KL(u∥wt+1 )

(u ∈ C).

Expanding h on both sides and rearranging,
η⟨gt , u − wt+1 ⟩ ≤ KL(u∥wt ) − (1 + ρ) KL(u∥wt+1 ) − KL(wt+1 ∥wt ) + ρ r(u) − r(wt+1 ) , (16) with equality when κ = 0, since then C = ∆K and ∇h(wt+1 ) is a multiple of 1, orthogonal to u − wt+1 . Next, split ⟨gt , u − wt ⟩ = ⟨gt , u − wt+1 ⟩ + ⟨gt , wt+1 − wt ⟩ and bound the second term by Hölder, Young’s inequality ab ≤ 21 a2 + 21 b2 and Pinsker’s inequality ∥p − q∥21 ≤ 2 KL(p∥q): η⟨gt , wt+1 −wt ⟩ ≤ η∥gt ∥∞ ∥wt+1 −wt ∥1 ≤ 12 η 2 ∥gt ∥2∞ + 12 ∥wt+1 −wt ∥21 ≤ 12 η 2 ∥gt ∥2∞ +KL(wt+1 ∥wt ). (17) Adding (16) and (17), the terms ± KL(wt+1 ∥wt ) cancel and we obtain (6). The claims about u = uK and general u follow from r(uK ) = 0, r ≥ 0 and r ≤ ln K on ∆K . At τ = κ = 0 we have ρ = 0 and C = ∆K , and (16) is the three-point identity η⟨gt , u − wt+1 ⟩ = KL(u∥wt ) − KL(u∥wt+1 ) − KL(wt+1 ∥wt ) of exponentiated gradient; the iterates then stay in the relative interior since w0 is uniform and the update multiplies by positive factors, so (6) holds for every u ∈ ∆K , including the vertices u = ei used in Lemma 4.3. Proof of Lemma 4.3. Set γ̄ := γR = C :=

p √ √ 2∆/(LT ) and η̄ := ηR = 2 ln K/(M T ), and define γ̄ ln K T γ̄ η̄M 2 T Lγ̄ 2 + + . η̄ 2 2

Substituting the step sizes, γ̄ ln K =M η̄ so C = 2M

p

q

∆ ln K L ,

T γ̄ η̄M 2 =M 2

q

∆ ln K L ,

T Lγ̄ 2 = ∆, 2

(18)

∆ ln K/L + ∆.

We prove by induction on t that ∥∇fi (xt )∥∗ ≤ M for all i.

√ Base case. By Assumption √ 2 and Lemma √ A.2, ∥∇fi (x0 )∥∗ ≤ 2L∆. Since K ≥ 2 we have 4 ln K ≥ 4 ln 2 > 2, so 2 L∆ ln K ≥ 2L∆ and the hypothesis on M gives ∥∇fi (x0 )∥∗ ≤ M . 15

Preprint

Inductive step. Suppose ∥∇fi (xs )∥∗ ≤ M for all i and all s ≤ t. Then ∥gs ∥∞ ≤ maxi ∥Ds ∥∥∇fi (xs )∥∗ ≤ RM for s ≤ t by Hölder. Apply Lemma 4.1 with w = ei and add γ/η times (6) with u = ei ; summing over s = 0, . . . , t and using KL(ei ∥w0 ) = ln K, KL(ei ∥wt+1 ) ≥ 0 and t + 1 ≤ T , fi (xt+1 ) − fi (x0 ) ≤ −γ̄

t X

∥Gs ∥∗ +

s=0

γ̄ ln K T γ̄ η̄M 2 T Lγ̄ 2 + + ≤ C, η̄ 2 2

⋆ where p we dropped the non-positive first sum. Hence fi (xt+1 ) − fi ≤ ∆ + C = 2∆ + 2M ∆ ln K/L, and Lemma A.2 gives q   √ K ∥∇fi (xt+1 )∥2∗ ≤ 2L 2∆ + 2M ∆ ln = 4L∆ + 4M L∆ ln K. L

√ It therefore suffices that M 2 ≥ 4L∆ + 4M L∆ ln K, i.e. that M be at least the positive root of √ M 2 − 4 L∆ ln K M − 4L∆ = 0, namely p √ √ √ M ≥ 2 L∆ ln K + 4L∆ ln K + 4L∆ = 2 L∆ ln K + 2 L∆(ln K + 1), √ which is the hypothesis. This closes the induction and shows M = O( L∆ ln K) suffices. Note that M is defined by an explicit formula in L, ∆, K only, so the step sizes are well defined and there is no circularity. Proof of Theorem 4.4. Take the uniform comparator u = uK , which lies in ∆κK for every κ ≤ 1/K. Adding Lemma 4.1 with w = uK to γ/η times (6) with u = uK gives, for each t, using r(uK ) = 0, r(wt+1 ) ≥ 0 and (1 + ρ) KL ≥ KL,  γη γ Lγ 2 R2 F (xt+1 )uK ≤ F (xt )uK − γR∥Gt ∥∗ + . KL(uK ∥wt ) − KL(uK ∥wt+1 ) + ∥gt ∥2∞ + η 2 2 By hypothesis (or by Lemma 4.3 when τ = κ = 0), ∥gt ∥∞ ≤ RM for all t < T . Summing over t = 0, . . . , T − 1, telescoping the divergences, and using KL(uK ∥w0 ) = 0 (as w0 = uK ) and KL(uK ∥wT ) ≥ 0, F (xT )uK − F (x0 )uK ≤ −γR

T −1 X

∥Gt ∥∗ +

t=0 1 K

T Lγ 2 R2 T γηR2 M 2 + . 2 2

⋆ Moreover F (x0 )uK − F (xT )uK ≤ Rearranging i (fi (x0 ) − fi ) ≤ ∆ by Assumption 2. p and dividing by γRT gives (7); neither τp , κ nor K has entered. With p γ̄ = γR = 2∆/(LT ) the first and third terms of (7) are each ∆L/(2T ), summing to 2∆L/T ; with η̄ = ηR = p √ √ 2 ln K/(M T ) √ the second isp M ln K/(2T ). Adding gives (8). The right-hand side of (8) is at p √ 2 2 most ϵ once T ≥ ( 2∆L + M ln K/2) /ϵ , and ( 2∆L + M ln K/2)2 ≤ 4∆L + M 2 ln K, so T = ⌈(4∆L + M 2 ln K)/ϵ2 ⌉ iterations suffice. Every step used only Assumptions 1–2 and the identity (2); no property of ∥ · ∥ beyond being a norm was invoked. √ P Corollary C.1 (Average CA distance). Under the conditions of (8), T1 t CAt ≤ 2 2∆L + p
√ M log K/2 / T for every measurable selection w⋆ (xt ).

P

Proof of Corollary C.1. Let w⋆ (xt ) be any minimizer of w 7→ ∥∇F (xt )w∥∗ over ∆K . By the triangle inequality and then optimality, CAt = ∥∇F (xt )wt −∇F (xt )w⋆ (xt )∥∗ ≤ ∥∇F (xt )wt ∥∗ +∥∇F (xt )w⋆ (xt )∥∗ ≤ 2∥∇F (xt )wt ∥∗ . Averaging over t and applying Theorem 4.4 gives the claim. Only the triangle inequality and the optimality of w⋆ were used, so the bound is valid simultaneously for every measurable selection; in particular it does not presuppose the uniqueness of ∇F (xt )w⋆ (xt ) discussed in Proposition 3.1. Remark C.1. In a Hilbert dual norm the constant 2 can be removed: the first-order optimality condition for w⋆ gives ⟨∇F w⋆ , ∇F wt − ∇F w⋆ ⟩ ≥ 0, whence ∥∇F wt − ∇F w⋆ ∥2∗ ≤ ∥∇F wt ∥2∗ − ∥∇F w⋆ ∥2∗ ≤ ∥∇F wt ∥2∗ . This is the argument used in the Euclidean literature. It 16

Preprint

relies on the parallelogram identity and is unavailable for a general dual norm, which is why we state Corollary C.1 with the triangle inequality instead. The same identity gives the conversion used in Corollary 4.6: writing a = ∥∇F wt ∥∗ and b = ∥∇F w⋆ ∥∗ , CA2t ≤ a2 − b2 = (a + b)(a − b) ≤ 2M gapt , since a, b ≤ M along the trajectory (Lemma 4.3) and a − b = gapt . More generally, if the dual norm satisfies (S2) with power type q, then with w⋆ minimizing φq (∇F w) over ∆K (the same minimizers as ∥∇F w∥∗ ), first-order optimality and (S2) give µq CAqt ≤ φq (∇F wt ) − φq (∇F w⋆ ) = 1 q q q−1 (a − b) ≤ M q−1 gapt , i.e. CAqt ≤ (q/µ)M q−1 gapt . The direct inequaliq (a − b ) ≤ a ties gapt ≤ ∥∇F (xt )wt ∥∗ and CAt ≤ 2∥∇F (xt )wt ∥∗ imply average-gap and average-CA convergence whenever the actual blended-gradient residual converges in average. This includes a fixed scalarization on its own convergent trajectory. Corollary 4.6 gives an additional comparatordependent decomposition; it is not needed to infer average-gap convergence from Theorem 4.4. Proof of Theorem 4.5. Fix u ∈ ∆K and write ψt (w) := ∥At w∥∗ . The support-function argument of Lemma A.3 applies to any linear map At , with d = Dt ∈ lmo(Gt ) and Gt = At wt . Thus −gt /R is a subgradient of ψt at wt . The subgradient inequality ψt (u) ≥ ψt (wt ) + ⟨−gt /R, u − wt ⟩ rearranges to 1 ψt (wt ) − ψt (u) ≤ ⟨gt , u − wt ⟩ for every t. (19) R Summing (6) at τ = κ = 0 over t = 0, . . . , T − 1, telescoping and dropping − KL(u∥wT ) ≤ 0, η

T −1 X

⟨gt , u − wt ⟩ ≤ KL(u∥w0 ) +

t=0

T −1

η2 X η 2 T R2 M 2 ∥gt ∥2∞ ≤ ln K + , 2 t=0 2

using KL(u∥w0 ) ≤ ln K for uniform w0 and ∥gt ∥∞ ≤ RM from the column bound maxi ∥At ei ∥∗ ≤ M and Hölder’s inequality. Combining with (19) and dividing by RT , r T −1  1 X ln K ηRM 2 2 ln K ψt (wt ) − ψt (u) ≤ + =M , T t=0 ηRT 2 T √ √ the last equality by the choice ηR = 2 ln K/(M T ), as in the proof of Theorem 4.4. P This is (9). Since it holds for every u ∈ ∆K , it holds in particular for a minimizer of u 7→ T1 t ψt (u) (which exists: each ψt is continuous and ∆K is compact), the best fixed weighting in hindsight. The argument used Lemma A.3, Lemma 4.2 and the bound ∥gt ∥∞ ≤ RM only. Hence it holds for arbitrary bounded matrix sequences, including sequences depending on preceding iterates; no outer progress is needed. Proof of Corollary 4.6. Write ψt (w) = ∥∇F (xt )w∥∗ . For any u ∈ ∆K and any t, by definition of the gap, i   h gapt = ψt (wt ) − ψt (u) + ψt (u) − min ψt (w) . w∈∆K

Average over t and apply (9) to the first bracket: r i 1 Xh 1X 2 ln K gapt ≤ M + ψt (u) − min ψt (w) w T t T T t

for every u ∈ ∆K .

The second sum is a continuous function of u on the compact set ∆K and is non-negative termwise; minimizing over u gives VT and hence (10). If some ū minimizes ψt for every t then each bracket vanishes at u = ū and VT = 0. The Euclidean conversion CA2t ≤ 2M gapt is the remark preceding P P p √ 1 1 this proof; averaging and using the concavity of · (Jensen), T t CAt ≤ T t 2M gapt ≤ q P 2M · T1 t gapt .

D

P ROOFS FOR THE STOCHASTIC SETTING

Only one vector of dimension d is carried between iterations. The convention α0 = 1 removes the initialization bias of the moving average. At t = 0 the oracle is evaluated at M−1 = 0; with the convention lmo(0) = 0 of Section 3 the first step is D0 = 0, and the argument below in fact allows any selection in B. 17

Preprint

Algorithm 2 Entropic LMO-MGDA with momentum on the blended gradient (τ = κ = 0) Require: x0 ; step sizes γ, η > 0; momentum α ∈ (0, 1]; radius R; horizon T 1: w0 ← (1/K, . . . , 1/K); M−1 ← 0 2: for t = 0, 1, . . . , T − 1 do 3: Dt ← lmo(Mt−1 ) ▷ oracle at the previous buffer: Dt is Ft -measurable 4: sample ξt,i and compute ∇fi (xt ; ξt,i ) for i ∈ [K] 5: gt,i ← ⟨Dt , ∇fi (xt ;ξP t,i )⟩ for i ∈ [K] ηgt,j ▷ line 6 of Algorithm 1 at τ = κ = 0 6: wt+1,i ← wt,i eηgt,i j wt,j e P bt ← b t , α0 = 1, αt = α for t ≥ 1 7: G w ∇f (x ; ξ ); M ← (1 − α )M + αt G i t t,i t t t−1 i t,i 8: xt+1 ← xt + γDt 9: end for Filtration and notation. Let Ft be the σ-algebra generated by ξ0,· , . . . , ξt−1,· (and x0 ), so that xt , wt , Mt−1 and hence Dt are Ft -measurable while the ξt,i are not. Write At := ∇F (xt ) and X b t − At wt = λt := Mt − At wt , nt := G wt,i nt,i , nt,i := ∇fi (xt ; ξt,i ) − ∇fi (xt ), i

together with the conventions λ−1 := M−1 − A0 w0 = −A0 w0 and Θ0 := 0, where for t ≥ 1 Θt := At−1 wt−1 − At wt . By Assumption 3, E[nt,i | Ft ] = 0 and E[∥nt,i ∥22 | Ft ] ≤ σ 2 ; consequently E[nt | Ft ] = 0. Since wt ∈ ∆K is Ft -measurable, the triangle inequality and Jensen’s inequality for the convex map s 7→ s2 with weights wt give h X 2 i X     wt,i ∥nt,i ∥2 Ft ≤ E ∥nt ∥22 | Ft ≤ E wt,i E ∥nt,i ∥22 | Ft ≤ σ 2 . (20) i

i

This bound is free of K and, notably, uses no independence across tasks: a shared minibatch for all K objectives is allowed. Throughout this appendix we work under Assumption 4, so that maxi ∥∇fi (xt )∥∗ ≤ M for every t, and we write ζ = maxx̸=0 ∥x∥∗ /∥x∥2 as in Section 3. D.1

T HE WEIGHT INCREMENT

The tracking analysis needs to control how far the weights move in one step. The pathwise bound (a) below is what the deterministic analysis would use; it involves ∥gt ∥∞ , √ a maximum over tasks, which in the stochastic setting contains maxi ∥nt,i ∥∗ and would introduce a K through a maximal inequality. Part (b) shows that in expectation the increment is governed by the wt -weighted average of the noise instead, with the maximum over tasks confined to a term of second order in η. Lemma P D.1 (Weight increment; restatement of Lemma 4.7). Let w ∈ ∆K , g ∈ RK , and wi′ = ηgi wi e / j wj eηgj . (a) Pathwise, ∥w′ − w∥1 ≤ 2η∥g∥∞ . (b) Suppose w, x and D with ∥D∥ ≤ R are F -measurable, gi = ⟨D, ∇fi (x)⟩ + ⟨D, ni ⟩ with maxi ∥∇fi (x)∥∗ ≤ M , E[ni | F] = 0 and E[∥ni ∥22 | F] ≤ σ 2 for each i (no independence across i required). If ηRM ≤ 21 , then   E ∥w′ − w∥1 | F ≤ ω := 16 ηR (M + ζσ) + 8Kη 2 R2 ζ 2 σ 2 . (21) Proof. (a) Take u = w in (16), which at τ = κ = 0 is the three-point identity of exponentiated gradient (with wt = w, wt+1 = w′ , gt = g). Since KL(w∥w) = 0 it reads η⟨g, w − w′ ⟩ = − KL(w∥w′ ) − KL(w′ ∥w), i.e. KL(w′ ∥w) + KL(w∥w′ ) = η⟨g, w′ − w⟩ ≤ η∥g∥∞ ∥w′ − w∥1 . Both divergences are non-negative, so KL(w′ ∥w) ≤ η∥g∥∞ ∥w′ −w∥1 . Pinsker’s inequality 12 ∥w′ − w∥21 ≤ KL(w′ ∥w) gives 21 ∥w′ − w∥21 ≤ η∥g∥∞ ∥w′ − w∥1 ; if w′ ̸= w divide by ∥w′ − w∥1 , and otherwise the claim is trivial. 18

Preprint

P P (b) Step 1: a weighted-average bound. Put bi := ηgi , ai := ebi , Z := j wj aj and b̄ := j wj bj . P ′ ′ −1 Then i wi |ai − Z|. For any constant c, since P wi − wi = wi (ai − Z)/Z, so ∥w − w∥1 = Z i wi (ai − c) = Z − c, X X X X X wi |ai − c|. wi |ai − Z| ≤ wi |ai − c| + |c − Z| = wi |ai − c| + wi (c − ai ) ≤ 2 i

i

i

b̄

i

i

Take c = e . By Jensen’s inequality for exp, Z =

P

j wj e

bj

b̄

b̄

≥ e , hence e /Z ≤ 1 and

X 2eb̄ X wi ebi −b̄ − 1 ≤ 2 wi eyi − 1 , Z i i

∥w′ − w∥1 ≤

yi := bi − b̄.

(22)

Step 2: splitting the scores. Write bi = di + νi with di := η⟨D, ∇fi (x)⟩ and νi := η⟨D, ni ⟩. By Hölder, |di | ≤ ηRM and |νi | ≤ ηR∥ni ∥∗ ≤ ηRζ∥ni ∥2 . Hence X ¯ + |νi − ν̄| ≤ 2ηRM + |νi | + |yi | ≤ |di − d| wj |νj |, j

and consequently

P

i wi |yi | ≤ 2ηRM + 2

P

i wi |νi |.

Step 3: the good event. Let A := {maxj |νj | ≤ 21 }. On A, using 2ηRM ≤ 1, every |yi | ≤ 1 + 12 + 12 = 2. Since y 7→ (ey − 1)/y is increasing on (0, 2] with value (e2 − 1)/2 < 4 at y = 2, we have |ey − 1| ≤ e|y| − 1 ≤ 4|y| for |y| ≤ 2, and (22) gives, on A, X X ∥w′ − w∥1 ≤ 8 wi |yi | ≤ 16ηRM + 16 wi |νi |. i

i

′

Off A we use the trivial bound ∥w − w∥1 ≤ 2, together with the union bound and Chebyshev’s inequality: X X X
Pr(Ac | F) ≤ Pr |νj | > 12 F ≤ 4 E[νj2 | F] ≤ 4η 2 R2 ζ 2 E[∥nj ∥22 | F] ≤ 4Kη 2 R2 ζ 2 σ 2 . j

j

j

Step 4. Combining, and using E[|νi | | F] ≤ ηRζ E[∥ni ∥2 | F] ≤ ηRζσ (Jensen), X   E ∥w′ −w∥1 | F ≤ 16ηRM +16ηRζσ wi +2 Pr(Ac | F) ≤ 16ηR(M +ζσ)+8Kη 2 R2 ζ 2 σ 2 . i

The constant 16 is not optimized. What matters is the structure of (21): the first-order term is a w-weighted average of the per-task noise, not a maximum, and the number of objectives enters only through the second-order term 8Kη 2 R2 ζ 2 σ 2 , which is what makes the leading term of Theorem 4.9 free of K apart from log K. D.2

T RACKING ERROR

Proof of Lemma 4.8. From line 7, for t ≥ 1, b t − At wt λt = (1 − α)Mt−1 + αG

= (1 − α) Mt−1 − At−1 wt−1 + (1 − α) At−1 wt−1 − At wt + αnt = (1 − α)λt−1 + (1 − α)Θt + αnt , b 0 − A0 w0 = n0 because α0 = 1. Unrolling, and λ0 = G λt = α

t t X X (1 − α)t−s+1 Θs . (1 − α)t−s ns + (1 − α)t n0 + s=1

s=1

|

{z

}

=: νt

|

{z

=: δt

(i) Drift. Split Θs according to whether x or w moved:  
Θs = As−1 − As ws−1 + As ws−1 − ws . 19

}

(23)

Preprint

For the first term, by convexity of ∥ · ∥∗ and Assumption 1, X   ∥ As−1 − As ws−1 ∥∗ ≤ ws−1,i ∥∇fi (xs−1 ) − ∇fi (xs )∥∗ ≤ L∥xs − xs−1 ∥ ≤ LγR, i

the last step because xs − xs−1 = γDs−1 with ∥Ds−1 ∥ ≤ R; this holds pathwise, for every realization of the noise, and is free of K. For the second term, by convexity and Assumption 4, ∥As (ws−1 − ws )∥∗ ≤ max ∥∇fi (xs )∥∗ ∥ws − ws−1 ∥1 ≤ M ∥ws − ws−1 ∥1 . i

The step ws−1 → ws is the update of Lemma 4.7 with F = Fs−1 , w = ws−1 , x = xs−1 , D = Ds−1 and noise ni = ns−1,i ; the hypotheses of part (b) hold by Assumptions 3 and 4 and ηRM ≤ 12 . Hence E∥ws − ws−1 ∥1 ≤ ω, and E∥Θs ∥∗ ≤ LγR + M ω =: B

(s ≥ 1),

while Θ0 = 0. Summing the geometric weights in (23), E∥δt ∥∗ ≤ B

t X B 1−α ≤ . (1 − α)t−s+1 ≤ B α α s=1

(ii) Noise. For s < s′ , ns is Fs′ -measurable and E[ns′ | Fs′ ] = 0, so E⟨ns , ns′ ⟩ = 0: the summands of νt are orthogonal in L2 . Therefore, by (20), E∥νt ∥22 = α2

t X

(1 − α)2(t−s) E∥ns ∥22 + (1 − α)2t E∥n0 ∥22

s=1

≤ σ2




α2 2t + (1 − α) ≤ σ 2 α + (1 − α)2t , 2 1 − (1 − α)

using α2 /(1 − (1 −√α)2 ) = α/(2 for α√∈ (0, 1]. Converting with ζ and applying Jensen’s √ − α) ≤ α √ inequality (EY ≤ EY 2 ) and a + b ≤ a + b, q
√ E∥νt ∥∗ ≤ ζ E∥νt ∥22 ≤ ζσ α + (1 − α)t . Combining (i) and (ii) with ∥λt ∥∗ ≤ ∥νt ∥∗ + ∥δt ∥∗ gives √

LγR + M ω (t ≥ 0), (24) α + (1 − α)t + α which is the statement of Lemma 4.8. No maximal inequality over the K tasks has been used; K enters only through the second-order term of ω. E∥λt ∥∗ ≤ ζσ

D.3

O NE - STEP INEQUALITY AND THE RATE

Lemma D.2 (Stochastic one-step inequality). Under Assumption 1, for every w ∈ ∆K and every t ≥ 0,
F (xt+1 )w ≤ F (xt )w − γR∥At wt ∥∗ + γ⟨gt , w − wt ⟩ + 2γR ∥λt−1 ∥∗ + ∥Θt ∥∗ DP E 1 2 2 −γ i (wi − wt,i ) nt,i , Dt + 2 Lγ R , with the conventions λP −1 = −A0 w0 , Θ0 = 0. The noise term is kept signed: it is bounded in absolute value by γR∥ i (wi − wt,i )nt,i ∥∗ , but what we use is that its conditional mean given Ft is zero when w is deterministic. Proof. Weighting Lemma A.1 by w exactly as in the proof of Lemma 4.1 gives F (xt+1 )w ≤ F (xt )w + γ⟨At w, Dt ⟩ + 21 Lγ 2 R2 . Write At w = At wt + At (w − wt ). First part. For t ≥ 1, Dt ∈ lmo(Mt−1 ), so by (2) and Hölder, ⟨At wt , Dt ⟩ = ⟨Mt−1 , Dt ⟩ + ⟨At wt − Mt−1 , Dt ⟩ ≤ −R∥Mt−1 ∥∗ + R∥At wt − Mt−1 ∥∗ . 20

Preprint

By the triangle inequality ∥Mt−1 ∥∗ ≥ ∥At wt ∥∗ − ∥At wt − Mt−1 ∥∗ , hence ⟨At wt , Dt ⟩ ≤ −R∥At wt ∥∗ + 2R∥At wt − Mt−1 ∥∗ . Finally At wt − Mt−1 = −(Mt−1 − At−1 wt−1 ) − (At−1 wt−1 −At wt ) = −λt−1 −Θt , and the triangle inequality gives the term 2R(∥λt−1 ∥∗ +∥Θt ∥∗ ). For t = 0, M−1 = 0 and D0 ∈ B is arbitrary, so Hölder gives ⟨A0 w0 , D0 ⟩ ≤ R∥A0 w0 ∥∗ = −R∥A0 w0 ∥∗ + 2R∥A0 w0 ∥∗ = −R∥A0 w0 ∥∗ + 2R(∥λ−1 ∥∗ + ∥Θ0 ∥∗ ) under the stated conventions. Second part. By definition, gt,i = ⟨Dt , ∇fi (xt ; ξt,i )⟩ = ⟨Dt , ∇fi (xt )⟩ + ⟨Dt , nt,i ⟩, so DX E X ⟨At (w − wt ), Dt ⟩ = (wi − wt,i )⟨∇fi (xt ), Dt ⟩ = ⟨gt , w − wt ⟩ − (wi − wt,i ) nt,i , Dt . i

i

Multiplying both parts by γ and collecting terms gives the claim. Proof of Theorem 4.9. Throughout, α = T −1/2 , γR = T −3/4 and ηR = T −3/4 /M 2 ; the hypothesis T ≥ (2/M )4/3 is exactly ηRM ≤ 21 , so Lemma D.1(b), and with it Lemma 4.8, apply. Step 1: the master inequality. Fix a deterministic u ∈ ∆K . Add Lemma D.2 with w = u to γ/η times (6) (at τ = κ = 0) with the same u; Lemma 4.2 is a deterministic statement about line 6 of Algorithm 2 and applies verbatim to the noisy scores, since its proof uses no property of gt beyond finiteness. Summing over t = 0, . . . , T − 1, telescoping the divergences, using KL(u∥wT ) ≥ 0 and F (x0 )u − F (xT )u ≤ ∆ (Assumption 2), and dividing by γRT , T −1

∆ KL(u∥w0 ) η X LγR 1 X ∥At wt ∥∗ ≤ + + ∥gt ∥2∞ + T t=0 γRT ηRT 2RT t 2 +

T −1 T −1 E
2 X 1 X DP ∥λt−1 ∥∗ + ∥Θt ∥∗ − i (ui − wt,i ) nt,i , Dt . T t=0 RT t=0

(25)

This holds pathwise. For the stationarity bound we take u = uK , so that KL(u∥w0 ) = 0 and the second term vanishes; for the regret bound of Corollary D.3 a general u is kept and KL(u∥w0 ) ≤ ln K. We now take expectations term by term. Step 2: the noise cross term vanishes. u is deterministic and wt , Dt are Ft -measurable, while E[nt,i | Ft ] = 0. By the tower property, DX E hD X Ei E (ui − wt,i )nt,i , Dt = E (ui − wt,i ) E[nt,i | Ft ], Dt = 0. i

i

This is exactly what evaluating the oracle at Mt−1 rather than Mt buys: with Dt = lmo(Mt ) the direction would depend on ξt and this term would not vanish. Step 3: the mirror-descent error term. By Hölder and Assumption 4, ∥gt ∥∞ ≤
R maxi
∥∇fi (xt ; ξt,i )∥∗ ≤ R
M + ζNt with Nt := maxi ∥nt,i ∥2 , so E∥gt ∥2∞ ≤ 2R2 M 2 + P ζ 2 ENt2 ≤ 2R2 M 2 + ζ 2 Kσ 2 , using ENt2 ≤ i E∥nt,i ∥22 ≤ Kσ 2 . Hence 
ζ 2 Kσ 2  η X . E∥gt ∥2∞ ≤ ηR M 2 + ζ 2 Kσ 2 = T −3/4 1 + 2RT t M2 This is one of the two places where K appears polynomially; both are of lower order than T −1/4 . Step 4: drift and noise terms. Let B = LγR + M ω as in the proof of Lemma 4.8. P Using ∥λ−1 ∥∗ = ∥A0 w0 ∥∗ ≤ M , Θ0 = 0, (24) for t ≥ 1 and E∥Θt ∥∗ ≤ B for t ≥ 1, together with t≥0 (1 − α)t ≤ 1/α, T −1
2M √ 2 X 2ζσ 2B E ∥λt−1 ∥∗ + ∥Θt ∥∗ ≤ + 2ζσ α + + + 2B. T t=0 T αT α With the stated step sizes,  ζσ  8Kζ 2 σ 2 −3/2 M ω = 16 T −3/4 1 + T , + M M3   ζσ 8Kζ 2 σ 2 −3/2 B = L T −3/4 + 16 T −3/4 1 + + T , M M3 21

Preprint

so that 2B/α = 2 L + 16 + 16ζσ/M T −1/4 + 16Kζ 2 σ 2 M −3 T −1 and 2B ≤ 2(L + 16 + 16ζσ/M )T −3/4 + 16Kζ 2 σ 2 M −3 T −3/2 . Step 5: collecting. Substituting into (25) after taking expectations, T −1

1 X 2ζσ ∆ + 2L + 32 + 2ζσ (1 + 16/M ) + 1/2 E∥At wt ∥∗ ≤ T t=0 T 1/4 T +

1 + 25 L + 32(1 + ζσ/M ) + ζ 2 Kσ 2 /M 2 2M + 32Kζ 2 σ 2 /M 3 + , 3/4 T T (26)

where in the last term we used T −3/2 ≤ T −1 . This is (12); setting the right-hand side to ϵ yields T = O(ϵ−4 ). The number of objectives does not enter the T −1/4 term (the comparator is uniform); the two terms carrying K polynomially are of order T −3/4 (from the ℓ∞ error term of mirror descent, Step 3) and T −1 (from the second-order part of the weight increment, Lemma D.1(b)). Step 6: the CA distance. The inequality CAt ≤ 2∥At wt ∥∗ of Corollary C.1 is pathwise P and holds for every measurable selection w⋆ (xt ), so averaging and taking expectations gives T1 t E CAt ≤ 2×(26). Finally, note that with the deterministic choice ηR = Θ(T −1/2 /M ) the term M ω/α would contain 16ηRM 2 /α = Θ(M ), which does not vanish as T → ∞; this is why the weight step size must be reduced to Θ(T −3/4 /M 2 ) in the stochastic setting. Corollary P D.3 (Stochastic inner regret). P Under the conditions of Theorem 4.9, for every u ∈ ∆K , T1 t E∥∇F (xt )wt ∥∗ ≤ T1 t E∥∇F (xt )u∥∗ plus the right-hand side of (12) with P ∆ replaced by M2 ln K; hence T1 t E gapt is bounded by the same quantity plus V̄T :=  P 1 minu∈∆K E T t ∥∇F (xt )u∥∗ − minw ∥∇F (xt )w∥∗ . Note V̄T ≥ EVT : the comparator must be deterministic for the noise cross term to vanish, so the stochastic statement is against the best fixed weighting in expectation, not against the realized hindsight minimizer. The linear-K terms in C3 , C4 are two maxima over√ tasks of noise magnitudes bounded with second moments only, and are intrinsic there (noise of size Kσ with probability 1/K makes some task an outlier at every step). A tail assumption removes them. Corollary D.4 (Polylogarithmic K under sub-Gaussian noise). Replace the variance bound in As
2 2 sumption 3 by the conditional tail bound Pr ∥∇fi (xt ; ξt )−∇fi (xt )∥2 > s | Ft ≤ 2e−s /(2σ ) for all s ≥ 0 and i. Then Theorem 4.9 holds for T 3/2 ≥ (8ζ 2 σ 2 /M 4 ) ln(4KT ) with σ → 2σ in C1 , C3 , C2 = 4ζσ +2M , ζ 2 Kσ 2 /M 2 → 2ζ 2 σ 2 (1+ln 2K)/M 2 in C3 , and C4 = 4M (Appendix D): under these conditions every displayed constant depends on K only through ln K, so T = O(ϵ−4 ) with a K-free constant for K ≤ exp(O(ϵ−2 )); Corollary D.3 holds with the same constants plus M 2 ln K. For a.s. bounded noise the constants of Theorem 4.9 are free of K. Proof of Corollary D.3. Fix a deterministic u ∈ ∆K and write ψt (w) = ∥At w∥∗ and ḡt,i := ⟨Dt , ∇fi (xt )⟩ for the noiseless scores, so that gt,i = ḡt,i + ⟨Dt , nt,i ⟩. Because Dt = lmo(Mt−1 ) is not an element of lmo(At wt ), Lemma A.3 does not apply directly; we argue from the definition of the dual norm instead. For any v ∈ ∆K , ∥Dt ∥ ≤ R gives ψt (v) = ∥At v∥∗ ≥ −⟨At v, Dt ⟩/R = −⟨ḡt , v⟩/R; at v = u this is ψt (u) ≥ −⟨ḡt , u⟩/R. For wt , the first part of the proof of Lemma D.2 gives ⟨At wt , Dt ⟩ ≤ −R∥At wt ∥∗ + 2R(∥λt−1 ∥∗ + ∥Θt ∥∗ ), i.e. ψt (wt ) ≤ −⟨ḡt , wt ⟩/R + 2(∥λt−1 ∥∗ + ∥Θt ∥∗ ). Subtracting,
1 ψt (wt ) − ψt (u) ≤ ⟨ḡt , u − wt ⟩ + 2 ∥λt−1 ∥∗ + ∥Θt ∥∗ R E
1 1 DX = ⟨gt , u − wt ⟩ − (ui − wt,i )nt,i , Dt + 2 ∥λt−1 ∥∗ + ∥Θt ∥∗ . R R i P η P 1 ln K 2 Sum over t, divide by T , bound RT t ⟨gt , u − wt ⟩ by ηRT + 2RT t ∥gt ∥∞ via (6), and take expectations. The signed noise term vanishes exactly as in Step 2 of the proof of Theorem 4.9; the remaining terms are precisely those of (25) without ∆/(γRT ) and LγR/2 but with 22

Preprint

KL(u∥w0 )/(ηRT ) ≤ ln K/(ηRT ) = M 2 ln K T −1/4 for the general comparator, and Steps 3– 5 of that proof bound the rest by (26) with ∆ removed and 2L (from 2B/α) retained. For the gap statement, fix a deterministic u ∈ ∆K and write, as in the proof of Corollary 4.6, E gapt = E[ψt (wt ) − ψt (u)] + E[ψt (u) − minw ψt (w)]; average over t, bound the first average by the regret bound just proved, and then take the minimum over deterministic u of the second average, which is V̄T . The comparator must be deterministic because Step 2 of the proof of Theorem 4.9 uses E[nt,i | P Ft ] = 0 against a Ft -measurable u − wt ; the realized hindsight minimizer u(ω) = arg minu T1 t ψt (u) depends on the whole trajectory and is not admissible. Since E minu (·) ≤ minu E(·), one has EVT ≤ V̄T , and the bound with EVT in place of V̄T is not established by this argument.

2

2

Proof of Corollary D.4. Write Xi := ∥nt,i ∥2 , so Pr(Xi > s | Ft ) ≤ 2e−s /(2σ ) . Then E[Xi2 | R∞ R∞ 2 Ft ] = 0 Pr(Xi2 > u) du ≤ 0 2e−u/(2σ ) du = 4σ 2 , so Assumption 3 holds with σ replaced by 2σ, and every step of the proofs of Lemma D.1, Lemma 4.8 and Theorem 4.9 goes through with that substitution except the two that bound a maximum over tasks. Those improve as follows. The ℓ∞ error term (Step 3). With Nt = maxi Xi and u0 := 2σ 2 ln(2K), Z ∞ Z ∞
2 2 E[Nt2 | Ft ] = Pr(Nt2 > u) du ≤ u0 + 2Ke−u/(2σ ) du = u0 +4Kσ 2 e−u0 /(2σ ) = 2σ 2 1+ln 2K , 0

u0

by the union bound. Hence E∥gt ∥2∞ ≤ 2R2 M 2 + 2ζ 2 σ 2 (1 + ln 2K) and the Step 3 term is
T −3/4 1 + 2ζ 2 σ 2 (1 + ln 2K)/M 2 . The union bound in Lemma D.1(b). Since |νj | ≤ ηRζXj , Pr(Ac | F) ≤

X j

 Pr Xj >

  1  1 ≤ 2K exp − 2 2 2 2 , 2ηRζ 8η R ζ σ

so ω = 16ηR(M + 2ζσ) + 4K exp − 1/(8η 2 R2 ζ 2 σ 2 ) , using E[Xi | F] ≤ (E[Xi2 | F])1/2 ≤ 2σ in the first term. With ηR = T −3/4 /M 2 the exponent is −M 4 T 3/2 /(8ζ 2 σ 2 ), and the hypothesis T 3/2 ≥ (8ζ 2 σ 2 /M 4 ) ln(4KT ) is exactly 4K exp(−M 4 T 3/2 /(8ζ 2 σ 2 )) ≤ 1/T . Hence in the proof of Theorem 4.9, M ω ≤ 16T −3/4 (1 + 2ζσ/M ) + M/T , so 2B/α ≤ 2(L + 16 + 32ζσ/M )T −1/4 + 2M T −1/2 and 2B ≤ 2(L + 16 + 32ζσ/M )T −3/4 + 2M/T . √ Collecting. Repeating Step 5 with σ → 2σ in the noise terms (2ζσ α → 4ζσT −1/4 , 2ζσ/(αT ) → 4ζσT −1/2 ) and the two replacements above gives the constants in the statement: C1 = ∆ + 2L + 32 + 4ζσ(1 + 16/M ), C2 = 4ζσ + 2M , C3 = 1 + 52 L + 32(1 + 2ζσ/M ) + 2ζ 2 σ 2 (1 + ln 2K)/M 2 , C4 = 2M + 2M = 4M . The requirement C3 ≤ 16C13 /ϵ2 for a K-free iteration count now reads ln(2K) ≲ ϵ−2 . For almost surely bounded noise Xi ≤ σ̂ one has Nt ≤ σ̂ and Pr(Ac ) = 0 once ηRζ σ̂ ≤ 12 , so no maximum over tasks is ever taken and the constants are those of Theorem 4.9 with σ → σ̂ and the K-terms deleted. The regret corollary adds KL(u∥w0 )/(ηRT ) ≤ M 2 ln K T −1/4 as before. Remark D.1 (On the gradient-bound assumption). Assumption 4 is used in three places: to bound the w-component of the drift (∥As (ws−1 − ws )∥∗ ≤ M ∥ws − ws−1 ∥1 ), in Lemma D.1(b), and in Step 3 above. In the deterministic setting the analogous bound is derived in Lemma 4.3 by an induction on the function values along the trajectory. That induction does not transfer to Algorithm 2: the stochastic one-step inequality contains the random terms ∥λt−1 ∥∗ and the noise cross term, which are controlled in expectation but not almost surely, so it yields a bound on Efi (xt ) and not the almost-sure gradient bound that the drift argument requires. Removing the assumption would need a stopping-time argument in the manner of Zhang et al. (2025), which we leave aside. Note that under c for all x, ξ, Assumption 4 an almost-sure bound on the stochastic gradients, ∥∇fi (x; ξ)∥∗ ≤ M c directly, since ∥∇fi (x)∥∗ = ∥Eξ ∇fi (x; ξ)∥∗ ≤ Eξ ∥∇fi (x; ξ)∥∗ by Jensen; in holds with M = M that case the assumption is not additional. 23

Preprint

E

P ER - TASK TRACKING VARIANT

For completeness we record the alternative referred to in Section 4.2; this is an upper-bound comparison of the two tracking schemes, not a convergence theorem. Track mt,i = (1 − α)mt−1,i + b t = P wt,i mt,i , Dt = lmo(G b t ), gt,i = ⟨Dt , mt,i ⟩. Writα∇fi (xt ; ξt,i ) per task and set G i ing λt,i = mt,i − ∇fi (xt ) and Λt = [λt,1 , . . . , λt,K ], the recursion for each λt,i has drift ∇fi (xt−1 ) − ∇fi (xt ) only, bounded by LγR deterministically, so no w-drift √ term appears and ηR = Θ(T −1/2 /M ) remains admissible, which gives the better constant M log K in place of P M 2 log K. The one-step inequality however involves ∥Λt wt ∥∗ = ∥ i wt,i λt,i ∥∗ , and wt is correlated with the past noise that produced λt,i : the weight update raises wt,i precisely when past scores ⟨Ds , ns,i ⟩ were those same noise vectors appear in λt,i . The Jensen argument of (20) P positive, andP bounds E∥ i wt,i λt,i ∥2 by i E[wt,i ∥λt,i ∥2 ], which is not ≤ maxi E∥λt,i ∥2 when wt and λt,i are dependent. One is left with the pathwise bound ∥Λt wt ∥∗ ≤ maxi ∥λt,i ∥∗ and a maximal inequality E max ∥νt,i ∥2 ≤

X

i

E∥νt,i ∥22

1/2

≤

√

K max E∥νt,i ∥22

i

i

1/2

,

√ √ so a factor cK = K under Assumption 3 alone (improving to O( log K) if each nt,i is subGaussian) multiplies ζσ in the leading term. The two variants therefore trade a better M -dependence against a worse K-dependence, and only the blended form has a leading term free of K under bounded variance alone. Whether cK can be removed for per-task tracking is open.

F

I TERATION - WISE INNER GAP : PROOFS FOR S ECTION 5

Throughout, ∥ · ∥ is an arbitrary norm, At := ∇F (xt ), and ft (w) := ∥At w∥∗ ,

r(w) := KL(w∥uK ),

ψ̃t := ft + τ r,

Φt := KL(pt ∥wt ),

pt := arg min ψ̃t (w), w∈∆κ K

with ∆κK = {w ∈ ∆K : wi ≥ κ}, Λ := ln(1/κ), η̄ := ηR, γ̄ := γR, ρ := η̄τ , and gapt := ft (wt ) − min∆K ft . For τ > 0, ψ̃t is strictly convex (as r is) and continuous on the compact set ∆κK , so pt exists and is unique. We use three facts about ft , valid in every norm along a trajectory with maxi ∥∇fi (xt )∥∗ ≤ M : P (F1) ft is convex and M -Lipschitz in ∥ · ∥1 on ∆K : |ft (v) − ft (w)| ≤ ∥At (v − w)∥∗ ≤ i |vi − wi |∥∇fi (xt )∥∗ ≤ M ∥v − w∥1 . (F2) ĝt := −gt /R ∈ ∂ft (wt ) (Lemma A.3), and ∥ĝt ∥∞ ≤ maxi ∥∇fi (xt )∥∗ ≤ M by Hölder. ′ ′ ′ (F3) For ∗ − ∥∇F (x )w∥∗ | ≤ ∥(∇F (x) − ∇F (x ))w∥∗ ≤ P any w ∈ ∆K and x,′ x , |∥∇F (x)w∥ ′ i wi ∥∇fi (x) − ∇fi (x )∥∗ ≤ L∥x − x ∥ (Assumption 1).

Lemma F.1 (Closed form of line 6). The minimizer in line 6 of Algorithm 1 is given by (4): 1/(1+ρ) ηgt,i /(1+ρ) wt+1,i = max{κ, ci /Zt } with ci = wt,i e and Zt > 0 the unique normalizer for P which i wt+1,i = 1 (for κ < 1/K; if κ = 1/K then wt+1 = uK ). Proof. The objective h(w) = −η⟨gt , w⟩ + ρr(w) + KL(w∥wt ) is strictly convex and differentiable on the relative interior, and the P constraints are affine, so the KKT conditions are necessary and sufficient. With multiplier ν for i wi = 1 and λi ≥ 0 for wi ≥ κ, and using ∂i r(w) = ln wi + ln K + 1, ∂i KL(w∥wt ) = ln wi − ln wt,i + 1, stationarity reads −ηgt,i + (1 + ρ) ln wi + ρ(ln K + 1) + 1 − ln wt,i − ν − λi = 0, i.e. (1 + ρ) ln wi = ln wt,i + ηgt,i + const + λi . If λi = 0 this gives wi = ci /Zt for a constant Zt ; if λi > 0 then P wi = κ, and λi ≥ 0 is equivalent to ci /Zt ≤ κ. Hence wt+1,i = max{κ, ci /Zt }. The map z 7→ i max{κ, ci /z} is continuous, non-increasing, tends to Kκ < 1 as z → ∞ and to ∞ as z → 0, and is strictly decreasing wherever its value exceeds Kκ, so Zt is unique. 24

Preprint

F.1

C OMPUTING THE CLIPPED UPDATE

Equation (4) determines wt+1 implicitly through the normalizer Zt , or equivalently through the set ⋆ S ⋆ := {i : ci /Zt < κ} of clipped coordinates. P Given S , Zt⋆is explicit: the unclipped coordinates ⋆ must carry the mass 1 − |S |κ, so Zt = i∈S / ⋆ ci /(1 − |S |κ). The clipped set is found by the following recurrence, which is the “clip, renormalize, repeat” rule stated as a fixed-point iteration. 1/(1+ρ) ηgt,i /(1+ρ) Write c = (ci )i∈[K] with ci = wt,i e > 0 and, for S ⊆ [K] with |S|κ < 1, P i∈S / ci Z(S) := . (27) 1 − |S|κ Algorithm 3 Clipped renormalization (KL projection of the softmax output onto ∆κK ) Require: c ∈ RK >0 ; κ ∈ [0, 1/K) 1: S0 ← ∅ 2: for k = 0, 1, 2, . . . do 3: Zk ← Z(Sk ) 4: Ak ← {i ∈ / Sk : ci < κZk } 5: if Ak = ∅ then return wi = κ for i ∈ Sk , 6: end if 7: Sk+1 ← Sk ∪ Ak 8: end for

▷ renormalize the unclipped coordinates, (27) ▷ coordinates that fall below the floor wi = ci /Zk for i ∈ / Sk

Lemma F.2 (Correctness and termination of Algorithm 3). Let κ ∈ [0, 1/K) and c ∈ RK >0 , and let Z ⋆ be the unique normalizer of Lemma F.1, with S ⋆ = {i : ci /Z ⋆ < κ}. Along Algorithm 3: (i) S0 ⊆ S1 ⊆ · · · ⊆ S ⋆ , and Z0 < Z1 < · · · ≤ Z ⋆ while the recurrence continues; (ii) the recurrence returns after at most |S ⋆ | + 1 ≤ K rounds, in the first round k with Ak = ∅; at that round Sk = S ⋆ and Zk = Z ⋆ , so the returned w is wt+1 of (4). (A coordinate with ci = κZ ⋆ exactly may sit in either set; the returned vector is the same.) Each round costs O(K), so the update costs O(K min{K, |S ⋆ | + 1}); sorting c once gives an O(K log K) implementation, since S ⋆ is Pa lower set in the order of c. At κ = 0 the recurrence stops after one round with S0 = ∅ and Z0 = i ci , i.e. the plain softmax. P Proof. Two facts about Z(·) are used. First, by the definition of S ⋆ and i max{κ, ci /Z ⋆ } = 1, X
ci = Z ⋆ 1 − |S ⋆ |κ , ci < κZ ⋆ (i ∈ S ⋆ ), ci ≥ κZ ⋆ (i ∈ / S ⋆ ). (28) i∈S / ⋆

Second, for S ⊆ S ⋆ , X X X ci = ci + ci ≤ Z ⋆ (1 − |S ⋆ |κ) + κZ ⋆ (|S ⋆ | − |S|) = Z ⋆ (1 − |S|κ), i∈S /

i∈S / ⋆

i∈S ⋆ \S

with strict inequality if S ̸= S ⋆ ; dividing by 1 − |S|κ > 0 gives Z(S) ≤ Z ⋆

for all S ⊆ S ⋆ ,

with equality iff S = S ⋆ .

(29)

(i) Monotonicity. We show by induction that Sk ⊆ S ⋆ . This holds for S0 = ∅. If Sk ⊆ S ⋆ then Zk = Z(Sk ) ≤ Z ⋆ by (29), so every i ∈ Ak satisfies ci < κZk ≤ κZ ⋆ , i.e. i ∈ S ⋆ ; hence Sk+1 ⊆ S ⋆ . The sets are nested by construction. For the normalizers, if Ak ̸= ∅ then, using ci < κZk for i ∈ Ak , X X
ci = Zk (1 − |Sk |κ) − ci > Zk (1 − |Sk |κ) − |Ak |κZk = Zk 1 − |Sk+1 |κ , i∈S / k+1

i∈Ak

and 1 − |Sk+1 |κ ≥ 1 − |S ⋆ |κ > 0, so Zk+1 > Zk . 25

Preprint

(ii) Termination and correctness. Since the Sk are nested subsets of S ⋆ and strictly grow while Ak ̸= ∅, the recurrence stops after at most |S ⋆ | + 1 rounds. At termination, Ak = ∅ means ci ≥ κZk for all i ∈ / Sk , while every i ∈ Sk was added at some round j < k with ci < κZj ≤ κZk by (i). Hence the returned vector satisfies wi = max{κ, ci /Zk } for every i, and it sums to 1 by the definition of Z(Sk ). It is therefore the water-filling vector of Lemma F.1 with normalizer Zk ; by the uniqueness of the normalizer proved there, Zk = Z ⋆ , and consequently Sk = S ⋆ and w = wt+1 . For the complexity claim, note that S ⋆ consists of the coordinates with the smallest ci : if ci ≤ cj and j ∈ S ⋆ then ci /Z ⋆ ≤ cj /Z ⋆ < κ. After sorting, one can scan the candidates S = {the s smallest} for s = 0, 1, . . . and stop at the first s for which the (s + 1)-st smallest c is at least κZ(S); by (29) and the argument above this is S ⋆ . At τ = κ = 0 the update is a single softmax, and for κ > 0 the recurrence typically stops after one or two rounds, so the per-iteration cost of line 6 is O(K) in practice and never more than O(K 2 ); it is negligible against the K backward passes. Remark F.1 (Why the unsquared objective). In Euclidean geometry, the squared inner objective 1 2 2 ∥∇F (xt )w∥2 is smooth. The analyses of Zhang et al. (2025) exploit this structure for iterationwise CA distance. Our oracle instead supplies a subgradient of the unsquared norm, matching the linear descent term in Lemma 4.1. In Euclidean geometry, the squared-objective gradient is ∥Gt ∥2 times the unsquared gradient when Gt ̸= 0; the latter involves normalization by ∥Gt ∥2 and is illconditioned near a zero blend. For general dual norms, nonsmoothness can also occur at nonzero blends: the ℓ1 norm is nonsmooth at vectors with zero coordinates, and the nuclear norm at rank-deficient matrices. Squaring need not remove this nonsmoothness. Our analysis therefore uses only convexity, Lipschitz continuity, and the oracle subgradient identity. It incurs the slack 2η̄ 2 M 2 per step in Lemma F.3, a Hölder-1/2 sensitivity bound, and the 1/κ factor in Lemma F.4. These bounds lead to the stated burn-in and total-horizon exponents; sharper analysis under additional norm smoothness assumptions remains open. F.2

C ONTRACTION WITH SLACK

Lemma F.3 (Contraction toward the regularized target). Suppose maxi ∥∇fi (xt )∥∗ ≤ M . For every u ∈ ∆κK ,   (1 + ρ) KL(u∥wt+1 ) ≤ KL(u∥wt ) + η̄ ψ̃t (u) − ψ̃t (wt+1 ) + 2η̄ 2 M 2 . In particular, since pt minimizes ψ̃t over ∆κK ∋ wt+1 , KL(pt ∥wt+1 ) ≤

Φt + 2η̄ 2 M 2 . 1+ρ

Proof. Start from (16) in the proof of Lemma 4.2, written with ĝt = −gt /R, so that η⟨gt , u − wt+1 ⟩ = −η̄⟨ĝt , u − wt+1 ⟩:
(1 + ρ) KL(u∥wt+1 ) ≤ KL(u∥wt ) − KL(wt+1 ∥wt ) + η̄⟨ĝt , u − wt+1 ⟩ + ρ r(u) − r(wt+1 ) . For the inner product, split u − wt+1 = (u − wt ) + (wt − wt+1 ) and use (F2): the subgradient inequality gives ⟨ĝt , u−wt ⟩ ≤ ft (u)−ft (wt ), and Hölder gives ⟨ĝt , wt −w
t+1 ⟩ ≤ M ∥wt+1 −wt ∥1 . Then, by (F1), ft (u) − ft (wt ) = ft (u) − ft (wt+1 ) + ft (wt+1 ) − ft (wt ) ≤ ft (u) − ft (wt+1 ) + M ∥wt+1 − wt ∥1 . Hence
η̄⟨ĝt , u − wt+1 ⟩ ≤ η̄ ft (u) − ft (wt+1 ) + 2η̄M ∥wt+1 − wt ∥1
≤ η̄ ft (u) − ft (wt+1 ) + 2η̄ 2 M 2 + 21 ∥wt+1 − wt ∥21 , by Young’s inequality 2ab ≤ 2a2 + 12 b2 with a = η̄M , b = ∥wt+1 − wt ∥1 . Pinsker’s inequality bounds the last term by KL(wt+1 ∥wt ), which cancels the − KL(wt+1 ∥wt ) above. Substituting and using ρ = η̄τ ,   (1 + ρ) KL(u∥wt+1 ) ≤ KL(u∥wt ) + η̄ ft (u) + τ r(u) − ft (wt+1 ) − τ r(wt+1 ) + 2η̄ 2 M 2 , which is the claim. The second statement follows from ψ̃t (pt ) ≤ ψ̃t (wt+1 ), as wt+1 ∈ ∆κK by construction. 26

Preprint

The additive slack 2η̄ 2 M 2 arises from our subgradient analysis of the potentially nonsmooth objective ft . This argument does not establish contraction without slack. Euclidean squared-objective analyses exploit additional smoothness; such smoothness is not available for every dual norm. F.3

T HE MOVING TARGET

Lemma F.4 (Sensitivity of the regularized optimum). Let p(x) := arg min∆κK {∥∇F (x)w∥∗ + τ r(w)}. For any x, x′ , r 2L∥x − x′ ∥ ′ ∥p(x) − p(x )∥1 ≤ , τ and hence, along the trajectory, X (pt,i − pt+1,i )2 2Lγ̄ χ2 (pt ∥pt+1 ) := ≤ . p τκ t+1,i i Proof. Write p = p(x), p′ = p(x′ ), ψ̃x = fx + τ r with fx = ∥∇F (x) · ∥∗ . Since fx is convex and finite, the first-order optimality condition for the convex problem min∆κK ψ̃x provides s ∈ ∂fx (p) with ⟨s+τ ∇r(p), p′ −p⟩ ≥ 0. Convexity of fx and the Bregman identity r(p′ ) = r(p)+⟨∇r(p), p′ − p⟩ + KL(p′ ∥p) give ψ̃x (p′ ) − ψ̃x (p) ≥ ⟨s + τ ∇r(p), p′ − p⟩ + τ KL(p′ ∥p) ≥ τ KL(p′ ∥p) ≥ τ2 ∥p′ − p∥21 , the last step by Pinsker. Symmetrically ψ̃x′ (p) − ψ̃x′ (p′ ) ≥ τ2 ∥p − p′ ∥21 . Adding and cancelling the identical τ r terms,     τ ∥p − p′ ∥21 ≤ fx (p′ ) − fx′ (p′ ) − fx (p) − fx′ (p) ≤ 2 sup |fx (w) − fx′ (w)| ≤ 2L∥x − x′ ∥ w∈∆K

by (F3), which givesPthe first claim. For the second, ∥xt+1 − xt ∥ ≤ γ̄, and since pt+1,i ≥ κ, χ2 (pt ∥pt+1 ) ≤ κ−1 i (pt,i − pt+1,i )2 ≤ κ−1 ∥pt − pt+1 ∥21 . This Hölder- 12 bound uses only strong convexity and the uniform closeness (F3) of fx and fx′ , so it holds in every norm. A route to stronger sensitivity estimates would require additional regularity. Even in Euclidean geometry, differentiating the unsquared objective introduces normalization by the blend norm near stationarity; general norms may also have nonzero nonsmooth points. Lemma F.5 (KL perturbation of the first argument). Let p, p′ , q ∈ ∆κK and Λ := ln(1/κ). Then p p KL(p′ ∥q) ≤ KL(p∥q) + (2 + Λ) KL(p′ ∥q) · χ2 (p∥p′ ). Proof. Fix q and let F (·) := KL(·∥q), which isPconvex with ∇F (p′ )i = ln(p′i /qi ) + 1. Convexity at p′ gives F (p′ ) − F (p) ≤ ⟨∇F (p′ ), p′ − p⟩ = i ln(p′ip /qi )(p′i − ppi′), the constant dropping because P ′ ′ pi · 1/ pi yields i (pi − pi ) = 0. Cauchy–Schwarz with the splitting X ′ 1/2  X ′ X p′ p p (pi − pi )2 1/2 p ln i (p′i − pi ) ≤ p′i ln2 i = V (p′ ∥q) χ2 (p∥p′ ). ′ q q p i i i i i i It remains to show V (p′ ∥q) ≤ (2 + Λ) KL(p′ ∥q). Put ri := p′i /qi ; since p′ , q ∈ ∆κK we have 2 ri ∈ [κ, 1/κ], r − r + 1 ≥ 0, we have P so | ln ri | ≤ Λ. Writing P ψ(r) := r ln r and d(r) := r ln P V (p′ ∥q) = i qi ψ(ri ) and, because i qi (ri − 1) = 0, also KL(p′ ∥q) = i qi d(ri ). So it suffices that ψ(r) ≤ (2 + Λ)d(r) whenever | ln r| ≤ Λ. Substituting r = es , this is es s2 ≤ (2 + Λ) (ses − es + 1) s

for |s| ≤ Λ,

(30)

s

where se − e + 1 ≥ 0 with equality only at s = 0 (both sides of (30) vanish there). We prove the stronger statement es s2 ≤ (2 + max(s, 0))(ses − es + 1) for all real s, which implies (30) since max(s, 0) ≤ Λ on [−Λ, Λ]. Case s ≥ 0. Let h(s) := (2 + s)(ses − es + 1) − es s2 . Dividing by es > 0, e−s h(s) = (2+s)(s−1+e−s )−s2 = s−2+(2+s)e−s =: k(s). Then k(0) = 0 and k ′ (s) = 1−(1+s)e−s ≥ 0 because 1 + s ≤ es . Hence k ≥ 0 on [0, ∞), i.e. h ≥ 0. 27

Preprint

Case s ≤ 0. Put u := −s ≥ 0. The claim es s2 ≤ 2(ses −es +1) reads e−u u2 ≤ 2 1−(1+u)e−u , P i.e. u2 + 2u + 2 ≤ 2eu , which holds because 2eu = 2 + 2u + u2 + j≥3 2uj /j! ≥ u2 + 2u + 2. Hence es s2 ≤ (2 + max(s, 0))(ses − es + 1) for all s, which gives (30) and therefore V (p′ ∥q) ≤ (2 + Λ) KL(p′ ∥q). F.4

T HE RECURSION , THE BIAS , AND THE PROOF OF T HEOREM 5.1

Lemma F.6 (Tracking recursion). Assume ρ = η̄τ ≤ 1 and maxi ∥∇fi (xt )∥∗ ≤ M . Then  ρ 2(2 + Λ) 2 Φt + 4η̄ 2 M 2 + Φt+1 ≤ 1 − χ (pt ∥pt+1 ). 4 ρ Proof. Apply Lemma F.5 with p = pt , p′ = pt+1p , q = wt+1 (allpin ∆κK : wt+1 by construction, 2 pt , pt+1 by definition): Φt+1 ≤ KL(p ab ≤ p t ∥wt+1 ) + (2 + Λ)Φt+1 χ . Young’s inequality p 1 2 θ 2 2 , θ = ρ/2 bounds the last term by ρ Φ a + b with a = Φ , b = (2 + Λ)χ + (2 + t+1 2 2θ 4 t+1 2 Λ)χ /ρ. Using Lemma F.3 for KL(pt ∥wt+1 ) and rearranging, 1 h Φt + 2η̄ 2 M 2 (2 + Λ)χ2 i Φt+1 ≤ + . 1 − ρ/4 1+ρ ρ For ρ ∈ (0, 1], (1−ρ/4)(1+ρ) = 1+ 34 ρ− 14 ρ2 ≥ 1+ 12 ρ, so [(1−ρ/4)(1+ρ)]−1 ≤ (1+ρ/2)−1 ≤ 1 − ρ/4, and (1 − ρ/4)−1 ≤ 2. Substituting gives the claim. Lemma F.7 (Bias of the regularized target). Suppose maxi ∥∇fi (xt )∥∗ ≤ M and κ ≤ 1/K. Then ft (pt ) − min∆K ft ≤ 2M Kκ + τ ln K. Proof. Let wt⋆ ∈ arg min∆K ft and ŵ := (1 − Kκ)wt⋆ + KκuK . Then ŵi ≥ κ and ŵ ∈ ∆K , so ŵ ∈ ∆κK ; ∥ŵ − wt⋆ ∥1 = Kκ∥uK − wt⋆ ∥1 ≤ 2Kκ; and r(ŵ) ≤ (1 − Kκ)r(wt⋆ ) ≤ ln K by convexity of r, r(uK ) = 0 and r ≤ ln K. Optimality of pt and r ≥ 0 give ft (pt ) ≤ ψ̃t (pt ) ≤ ψ̃t (ŵ) ≤ ft (ŵ) + τ ln K ≤ ft (wt⋆ ) + M ∥ŵ − wt⋆ ∥1 + τ ln K, by (F1). Proof of Theorem 5.1. We first dispose of the trivial regime: if ϵ > 2M then ft (w) ≤ M < ϵ/2 for every w ∈ ∆K , so gapt ≤ M < ϵ and ∥∇F (xt )wt ∥∗ ≤ M < ϵ for every t. Assume ϵ ≤ 2M , so also β ≤ 2M . Then κ = β/(4M K) ≤ 1/(2K) < 1/K, so ∆κK has non-empty relative interior; and ϵ2 β 2 16 ρ = η̄τ = ≤ < 1, 2 4 1536 M ln K 1536 ln2 2 so Lemma F.6 applies. Note Λ = ln(1/κ) = ln(4M K/β). (i) Tracking. Iterating Lemma F.6 with the uniform bound χ2 (pt ∥pt+1P ) ≤ 2Lγ̄/(τ κ) of Lemma F.4, from Φ0 = KL(p0 ∥uK ) ≤ ln K, and summing the geometric series j≥0 (1 − ρ/4)j = 4/ρ,   ρ t 16η̄ 2 M 2 8(2 + Λ) 2Lγ̄ ρ t 16η̄M 2 16(2 + Λ)Lγ̄ Φt ≤ 1 − ln K + + · = 1 − ln K + + . 2 4 ρ ρ τκ 4 τ η̄ 2 τ 3 κ (31) We show each of the three terms is at most ϵ2 /(24M 2 ) for t ≥ T0 . The second equals 16M 2 · ϵ2 β 2 ln K = ϵ2 /(24M 2 ) exactly. For the third, substitute η̄ 2 = ϵ4 β 2 /(7682 M 8 ln2 K), 768M 4 ln K · β 3 3 3 τ = β /(8 ln K) and κ = β/(4M K), so that η̄ 2 τ 3 κ = ϵ4 β 6 /(9·221 M 9 K ln5 K) (as 7682 ·8·4 = 9 · 216 · 25 ); then 9 · 225 (2 + Λ)LM 9 K ln5 K 9 · 225 ϵ2 ϵ2 16(2 + Λ)Lγ̄ = γ̄ = = 2 3 4 6 28 2 η̄ τ κ ϵ β 27 · 2 M 24M 2 exactly, by the choice of γ̄. For the first, (1 − ρ/4)t ≤ e−ρt/4 ≤ ϵ2 /(24M 2 ln K) once t ≥ 4 24M 2 ln K , and 4/ρ = 6144M 4 ln2 K/(ϵ2 β 2 ), so this holds for t ≥ T0 . Hence Φt ≤ ϵ2 /(8M 2 ) ρ ln ϵ2 √ for t ≥ T0 , and Pinsker gives ∥wt − pt ∥1 ≤ 2Φt ≤ ϵ/(2M ). Lemma F.7 with 2M Kκ = β/2 28

Preprint

and τ ln K = β/2 gives gap(pt ) ≤ β. Finally, by (F1), gapt = ft (wt ) − ft (pt ) + gap(pt ) ≤ M ∥wt − pt ∥1 + β ≤ ϵ/2 + β. P (ii) Progress. The bound T1 t<T ∥∇F (xt )wt ∥∗ ≤ ∆/(γ̄T ) + η̄M 2 /2 + Lγ̄/2 is (7) of Theorem 4.4, which holds for every τ ≥ 0, κ ≤ 1/K and every γ, η. It remains to check the three terms at the stated parameters. ∆/(γ̄T ) ≤ ϵ/4 for T ≥ T1 = ⌈4∆/(γ̄ϵ)⌉. Next η̄M 2 /2 = ϵ2 β/(1536M 2 ln K) ≤ ϵ/8, because ϵβ/M 2 ≤ ϵ2 /M 2 ≤ 4 ≤ 192 ln 2 ≤ 192 ln K. Finally Lγ̄/2 ≤ ϵ/8 because, using (2 + Λ)K ≥ 1, ln K ≥ ln 2 and β ≤ ϵ ≤ 2M , Lγ̄ = ϵ6 β 6 /(27 · 228 (2 + Λ)M 11 K ln5 K) ≤ ϵ (ϵ/M )11 /(27 · 228 ln5 2) ≤ ϵ 211 /(27 · 228 ln5 2) < ϵ/4. Hence the average is at most ϵ/4 + ϵ/8 + ϵ/8 = ϵ/2 for T ≥ T1 . PT −1 PT −1 (iii) Tail output. Let T ≥ max{2T0 , T1 }. By (ii), t=T0 ∥∇F (xt )wt ∥∗ ≤ t=0 ∥∇F (xt )wt ∥∗ ≤ T ϵ/2, the first inequality by non-negativity of the dropped terms. The minimum over the tail is at most its average, so ∥∇F (xt̂ )wt̂ ∥∗ ≤ (T ϵ/2)/(T − T0 ) ≤ ϵ, using T − T0 ≥ T /2. Since t̂ ≥ T0 , part (i) gives gapt̂ ≤ ϵ/2 + β, and minw ∥∇F (xt̂ )w∥∗ ≤ ∥∇F (xt̂ )wt̂ ∥∗ ≤ ϵ. With β = ϵ/2 the parameters reduce to τ = ϵ/(4 ln K), κ = ϵ/(8M K), η̄ = ϵ3 /(1536M 4 ln K), γ̄ = ϵ12 /(27 · 234 (2 + Λ)LM 11 K ln5 K) and T0 = ⌈(24576M 4 ln2 K/ϵ4 ) ln(24M 2 ln K/ϵ2 )⌉, which gives the stated orders. Proof of Corollary 5.2. By the triangle inequality, CAt ≤ ∥∇F (xt )(wt − pt )∥∗ + ∥∇F (xt )(pt − w⋆ (xt ))∥∗ . The first term is at most M ∥wt − pt ∥1 ≤ ϵ/2 for t ≥ T0 by (F1) and Theorem 5.1(i). For the second, w⋆ (xt ) minimizes φq ◦ ∇F (xt ) over ∆K (the same minimizers as ft ), so the argument of Remark C.1 applied with wt replaced by pt gives ∥∇F (xt )(pt − w⋆ (xt ))∥q∗ ≤ (q/µ)M q−1 gap(pt ) ≤ (q/µ)M q−1 β, which equals (ϵ/2)q for β = µϵq /(q2q M q−1 ). The orders of T0 and T1 follow by substituting this β into Theorem 5.1: in the Euclidean case β = ϵ2 /(8M ), so ϵ2 β 2 = ϵ6 /(64M 2 ) and ϵ6 β 6 = ϵ18 /(218 M 6 ). Remark F.2 (On the gradient bound in Theorem 5.1). Theorem 5.1 takes the trajectory gradient bound as a hypothesis, and we keep it as one: unlike Theorem 4.4 at τ = κ = 0, we do not derive it. We record what a derivation would involve. The induction of Lemma 4.3 changes in the comparator: Lemma 4.3 uses u = ei , which is not in ∆κK , so one applies (6) at êi = (1 − Kκ)ei + KκuK ∈ ∆κK and pays γ∥gs ∥∞ ∥ei − êi ∥1 ≤ 2γ̄M Kκ per step for the difference, together with the regularization term ρ ln K/η · γ = γ̄τ ln K per step from Lemma 4.2. Since τ ln K + 2M Kκ = β ≤ ϵ and T1 γ̄ ≤ 4∆/ϵ + γ̄, over T1 steps these add at most T1 γ̄ β ≤ 4∆ + γ̄ϵ to the function-value increase, so fi (xt ) − fi⋆ ≤ 5∆ + C ′ with C ′ collecting γ̄ϵ and the (much smaller) remaining terms of p 2L(5∆ + C ′ ), Lemma 4.3 at these step sizes, and Lemma A.2 converts this into ∥∇f (x )∥ ≤ i t ∗ √ ′ ′ which is below the M of Lemma 4.3 (≥ 4 L∆) once C ≤ 3∆. Verifying C ≤ 3∆ requires relating the remaining terms, which involve M , ϵ and β but not ∆, to ∆ through the explicit value of M in Lemma 4.3 and the horizon actually run, which is max{2T0 , T1 } rather than T1 . We have not carried this out, so the gradient bound remains an assumption of Theorem 5.1.

G

U NIFORM CONVEXITY OF ℓp AND S CHATTEN -p NORMS

Corollaries 4.6 and 5.2 convert a bound on the inner gap into a bound on the CA distance whenever the dual norm satisfies the following uniform convexity inequality of power type q ≥ 2 with constant µ ∈ (0, 1]: with φq := 1q ∥ · ∥q∗ , q 1 q ∥y∥∗

≥ 1q ∥y ′ ∥q∗ + ⟨∇φq (y ′ ), y − y ′ ⟩ + µq ∥y − y ′ ∥q∗

for all y, y ′ .

(S2)

(The conversion itself is in Remark C.1.) This appendix records which ℓp and Schatten-p norms satisfy (S2), and with which (q, µ). Proposition G.1. Let ∥ · ∥∗ be the ℓp norm on Rm or the Schatten-p norm on Rm×n . (i) For 1 < p ≤ 2, (S2) holds with q = 2 and µ = p − 1: the function ψp := 21 ∥ · ∥2∗ is (p − 1)strongly convex with respect to ∥ · ∥∗ . (ii) For 2 ≤ p < ∞, (S2) holds with q = p and µ = 21−p . 29

Preprint

(iii) For p > 2, (S2) fails with q = 2 for every µ > 0: the ratio Dψp (y, x)/∥y − x∥2∗ can be made arbitrarily small. For p = 1 (the ℓ1 and nuclear norms) the unit ball is not strictly convex and no inequality of the form (S2) can hold. Proof. (i) Theorem 1 of Ball et al. (1994) (optimal 2-uniform convexity) states that for 1 ≤ p ≤ 2 and all X, Y ,  ∥X + Y ∥p + ∥X − Y ∥p 2/p ∗ ∗ ≥ ∥X∥2∗ + (p − 1)∥Y ∥2∗ , (32) 2 both for ℓp (their case (a), functions in Lp ) and for Schatten-p (their case (b), matrices in Cp ). Put a−b 2/p X = a+b 2 and Y = 2 , so that X + Y = a and X − Y = b. Because 2/p ≥ 1, the map s 7→ s p
2/p ∥a∥p +∥b∥ 1 1 2 2 ∗ ∗ is convex on [0, ∞) and Jensen’s inequality gives ≤ 2 ∥a∥∗ + 2 ∥b∥∗ . Combining 2 with (32), a−b 2 a+b 2 + (p − 1) ≤ 21 ∥a∥2∗ + 12 ∥b∥2∗ for all a, b. 2 2 ∗ ∗ p−1 1 1 2 Multiplying by 12 gives ψp ( a+b 2 ) ≤ 2 ψp (a) + 2 ψp (b) − 8 ∥a − b∥∗ , which is midpoint strong convexity with modulus p − 1; for continuous functions this upgrades to strong convexity by the usual dyadic-subdivision argument, and strong convexity of ψp is (S2) with q = 2, µ = p − 1. (ii) Let ϕ := ∥ · ∥p∗ . Clarkson’s inequality for p ≥ 2 states that for all y, y ′ ,  y + y′   y − y ′  ϕ(y) + ϕ(y ′ ) ϕ . (33) +ϕ ≤ 2 2 2 For ℓp this follows coordinatewise from the scalar case, which is X p/2 + Y p/2 ≤ (X + Y )p/2 ≤ 1 a+b 2 a−b 2 1 2 p p 2 p/2 2 (|a| +|b| ) for X = ( 2 ) , Y = ( 2 ) , X +Y = 2 (a +b ), using superadditivity of s 7→ s p/2 on [0, ∞) (as p/2 ≥ 1) and then convexity of s 7→ s ; for Schatten norms (33) is McCarthy’s extension of Clarkson’s inequality to trace classes (McCarthy, 1967). Now let m := (y + y ′ )/2. Convexity of ϕ gives ⟨∇ϕ(y ′ ), m − y ′ ⟩ ≤ ϕ(m) − ϕ(y ′ ), and y − y ′ = 2(m − y ′ ), so
Dϕ (y, y ′ ) := ϕ(y) − ϕ(y ′ ) − ⟨∇ϕ(y ′ ), y − y ′ ⟩ ≥ ϕ(y) − ϕ(y ′ ) − 2 ϕ(m) − ϕ(y ′ )  y − y′  = 21−p ∥y − y ′ ∥p∗ , = ϕ(y) + ϕ(y ′ ) − 2ϕ(m) ≥ 2ϕ 2 the last inequality being (33). Dividing by p gives (S2) for φp = ϕ/p with q = p and µ = 21−p . (iii) Take x = e1 and y = e1 + te2 with t
↓ 0 (for Schatten norms, x = E11 , y = E11 + tE22 ). sign(gi )|gi |p−1 i we have ∇ψp (e1 ) = e1 , hence ⟨∇ψp (x), y − x⟩ = Since ∇ψp (g) = ∥g∥2−p p 0 and Dψp (y, x) = 12 (1 + tp )2/p − 12 = p1 tp + O(t2p ) while ∥y − x∥2p = t2 , so the ratio is 1 p−2 + O(t2p−2 ) → 0 for p > 2. Finally, if the unit ball is not strictly convex there are y ̸= y ′ pt on the unit sphere with ∥(y + y ′ )/2∥∗ = 1, and (S2) applied at y and y ′ around the midpoint forces µ = 0. The constant µ = 21−p in (ii) is not sharp (numerically the best constant for ℓp is about 0.59, 0.33 and 0.10 at p = 3, 4, 6, against 0.25, 0.125 and 0.031), but it is explicit. Statement (iii) is why the power type q = p, rather than 2, appears in Corollary 5.2 for p > 2: the unit sphere of ℓp is flatter than quadratic at the coordinate points.

H

I NEXACT ORACLES

The analysis uses the oracle only through ∥Dt ∥ ≤ R and ⟨Gt , Dt ⟩ = −R∥Gt ∥∗ . In the spectral case the polar factor is computed by a Newton–Schulz iteration and is only approximate. Suppose instead that for some ϑ ∈ [0, 1) and all t, ∥Dt ∥ ≤ (1 + ϑ)R,

⟨Gt , Dt ⟩ ≤ −(1 − ϑ)R ∥Gt ∥∗ ,

(34)

and that maxi ∥∇fi (xt )∥∗ ≤ M along the trajectory (we do not re-derive M here). Then ∥gt ∥∞ ≤ (1 + ϑ)RM , and the two places where the oracle identity enters the deterministic analysis change as follows. 30

Preprint

p Proposition H.1. Under Assumptions 1–2 and (34), with τ = κ = 0, γR = 2∆/(LT ) and √ √ ηR = 2 ln K/(M T ): p √ 2∆L + M ln K/2 1 X (1 + ϑ)2 √ , ∥∇F (xt )wt ∥∗ ≤ · T 1−ϑ T t<T r  (1 + ϑ)2 1 X 2 ln K 2ϑM ∥∇F (xt )wt ∥∗ − ∥∇F (xt )u∥∗ ≤ M + for every u ∈ ∆K . T 1−ϑ T 1−ϑ t<T

Proof. One-step inequality. The proof of Lemma 4.1 gives F (xt+1 )w ≤ F (xt )w + γ⟨At w, Dt ⟩ + 1 2 2 2 Lγ ∥Dt ∥ ; with (34), ⟨At w, Dt ⟩ = ⟨Gt , Dt ⟩+⟨gt , w−wt ⟩ ≤ −(1−ϑ)R∥Gt ∥∗ +⟨gt , w−wt ⟩ and 2 ∥Dt ∥ ≤ (1 + ϑ)2 R2 . Repeating the proof of Theorem 4.4 with u = uK and ∥gt ∥∞ ≤ (1 + ϑ)RM , h ∆ 1X ∆ ηRM 2 LγR ηRM 2 LγR i (1−ϑ) , ∥Gt ∥∗ ≤ +(1+ϑ)2 +(1+ϑ)2 ≤ (1+ϑ)2 + + T t γRT 2 2 γRT 2 2 and the step sizes give the first claim. Regret. Write ψt (w) = ∥At w∥∗ . For any u ∈ ∆K , Hölder gives ∥At u∥∗ ∥Dt ∥ ≥ −⟨At u, Dt ⟩ = −⟨gt , u⟩, hence ψt (u) ≥ −⟨gt , u⟩/((1 + ϑ)R) (trivially if the right-hand side is negative). For wt , (34) gives ψt (wt ) = ∥Gt ∥∗ ≤ −⟨Gt , Dt ⟩/((1 − ϑ)R) = −⟨gt , wt ⟩/((1 − ϑ)R). Subtracting, with a := 1/((1 − ϑ)R) and b := 1/((1 + ϑ)R), ψt (wt ) − ψt (u) ≤ −a⟨gt , wt ⟩ + b⟨gt , u⟩ = a⟨gt , u − wt ⟩ − (a − b)⟨gt , u⟩ ⟨gt , u − wt ⟩ + (a − b)(1 + ϑ)RM, ≤ (1 − ϑ)R  1  2ϑM 1 using |⟨gt , u⟩| ≤ ∥gt ∥∞ ≤ (1+ϑ)RM . Since (a−b)(1+ϑ)RM = M (1+ϑ) 1−ϑ − 1+ϑ = 1−ϑ , 2 2 2 summing and applying Lemma 4.2 as in the proof of Theorem 4.5, with ∥gt ∥∞ ≤ (1 + ϑ) R M 2 , gives the second claim. The multiplicative factor (1 + ϑ)2 /(1 − ϑ) is controlled when ϑ is bounded away from one. The second inequality has an additive floor because of the mismatch between the upper and lower oracle constants. This is a limitation of that comparator argument, not an unavoidable floor for the average gap or regret along the descent trajectory. Indeed, if BT denotes the first bound in Proposition H.1, (3) gives 1X gapt ≤ BT , T t " # X 1 X ∥At wt ∥∗ − min ∥At u∥∗ ≤ BT = O(T −1/2 ). u∈∆K T t t Thus fixed relative oracle error satisfying (34) is already tolerated for deterministic stationarity and average inner optimality. We do not extend this proposition to the stochastic or iteration-wise results. There, oracle error must be propagated through the tracking and subgradient arguments. Moreover, the error parameters of a practical Newton–Schulz implementation depend on its polynomial, normalization, coefficient schedule, numerical precision, and input spectrum. We have not established a uniform ϑ < 1 for the five-step quintic implementation used in the experiments, nor a geometric error-decay claim for that particular implementation. Relating it to the oracle assumptions and extending the stochastic and iteration-wise guarantees remain open.

I

E XPERIMENTAL DETAILS

I.1

C ITYSCAPES AND NYU- V 2

Protocol. We follow the protocol of Navon et al. (2022); Liu et al. (2023): an MTAN model on a SegNet backbone, with 200 epochs, and batch sizes 8 on Cityscapes and 2 on NYU-v2. The standard 31

Preprint

baselines use Adam with learning rate 10−4 , which is multiplied by 0.5 after epoch 100. Our method applies the oracle direction directly with step size γ, while MOON uses the released Muon+AdamW optimizer. Reported metrics are averaged over the final 10 epochs with one seed; these epochs are correlated and do not estimate variability across independent runs. The baseline rows are re-runs with the same protocol. Cityscapes has K = 2 tasks (7-class semantic segmentation, depth); NYUv2 has K = 3 (13-class segmentation, depth, surface normals). Metrics. Segmentation: mean IoU and pixel accuracy (higher is better). Depth: absolute and relative error (lower is better). Normals: mean and median angular error (lower is better) and the fraction of pixels within 11.25◦ , 22.5◦ and 30◦ (higher is better). The aggregate is n

∆m% =

100 X Mj − MSTL,j (−1)sj , n j=1 MSTL,j

over the n metrics, with sj = 1 if higher is better and 0 otherwise. For each dataset, MSTL is the corresponding single-task baseline reported in the STL row of the same table. Thus, the STL reference is (74.11, 93.44, 0.0137, 38.22) on Cityscapes and (38.77, 63.98, 0.6350, 0.2654, 25.10, 19.06, 30.12, 57.66, 69.53) on NYU-v2. Accordingly, the STL row has ∆m = 0, and all other ∆m values are computed relative to these references. Our method. We use Algorithm 2 with the spectral oracle on convolutional and linear weights (4D kernels flattened over their last three dimensions) and the Euclidean oracle on the remaining parameters. Each matrix-valued parameter tensor is treated as a unit-radius spectral-norm block, ρℓ = 1, without width- or kernel-dependent rescaling, while all scalar and vector parameters are concatenated into a single unit-radius Euclidean block. The outer model step size controls the overall update magnitude. We use seed 42 for all dense-task experiments, with momentum α = 0.1, τ = 0, and κ = 0 fixed throughout. Hyperparameter tuning uses the same non-training benchmark split on which the dense-task results are reported: the official 500-image validation split for Cityscapes and the 654-image evaluation (test) split for NYU-v2. Thus, no additional held-out validation split is used for these dense-task experiments. Short-horizon segmentation performance is used as the primary tuning criterion, subject to maintaining joint-task performance, while the final late-training schedule is selected using the final-window ∆m. For Cityscapes, we search γ ∈ {10−3 , 5 × 10−3 } and η ∈ {10−4 , 5 × 10−4 }, selecting γ = 5 × 10−3 and η = 10−4 . The final model-step schedule uses 5 × 10−3 for epochs 1–100, 2.5 × 10−3 for epochs 101–150, and 1.25 × 10−3 for epochs 151–200. For NYU-v2, we search γ ∈ {2.5 × 10−3 , 5 × 10−3 } and η ∈ {5 × 10−5 , 10−4 }, selecting γ = 2.5 × 10−3 and η = 10−4 ; the model step is reduced to 1.25 × 10−3 from epoch 101 onward. Standard baselines use their reference hyperparameters without an additional tuning grid. I.2

M ULTI MNIST

Protocol. Following (Zhou et al., 2026), we use MultiMNIST, where each example contains two MNIST digits and the two tasks are to classify the left and right digits. The digits are concatenated horizontally and, with probability 0.5, overlapped by up to 30% of their width. The resulting images are resized to 28 × 43. We generate 10,000 training examples from MNIST-train and 1,000 test examples from MNIST-test. We use a small Vision Transformer with patch size 4 and embedding dimension 16, consisting of a class token, learned positional embeddings, and 3 transformer encoder layers, each with 2 attention heads and a feed-forward dimension of 64. No dropout is used, and the shared encoder is followed by one linear classification head for each task. All methods in Table 4 are evaluated on the same generated dataset and trained for 100 epochs with batch size 256. Our method. Algorithm 2 with the unregularized, unclipped specialization of the weight update in Algorithm 1. At each iteration, we compute per-task gradients for all trainable model parameters and form their weighted aggregate. The oracle comes from the previous momentum buffer. For every parameter tensor with at least two dimensions, we flatten all but the first dimension and apply five Newton–Schulz steps. If the resulting matrix is taller than wide, we first transpose it. Writing G for this (possibly transposed) matrix, the iteration is carried out in float32, initialized as X0 = 32

Preprint

G/(∥G∥F + 10−7 ), and uses Xr+1 = aXr + b(Xr Xr⊤ )Xr + c(Xr Xr⊤ )2 Xr ,

(a, b, c) = (3.4445, −4.7750, 2.0315),

for five steps. Each matrix-valued parameter tensor is treated as a unit-radius spectral-norm block, without width- or kernel-dependent rescaling, while all scalar and vector parameters are concatenated into a single unit-radius Euclidean block. The blended momentum buffer is initialized at zero; its first update uses α0 = 1, and subsequent updates use α = 0.1. We use model step size γ = 10−3 , weight step η = 5 × 10−5 , τ = 0, and κ = 0. MOON. We use (Zhou et al., 2026)’s released implementation: the task logits are updated with Adam at learning rate 10−4 and weight decay 10−3 , Muon uses Nesterov momentum, and tasks are scored using the previous optimizer update. The data, model, number of epochs, batch size and numerical model learning rate are shared with our method. Momentum conventions, logit optimizers, weight decay, and auxiliary parameter updates differ; a common numerical learning rate need not imply a common effective update size. The comparison therefore evaluates complete implementations rather than isolating a single algorithmic component. Other baselines. MGDA and FAMO use Adam, as in MOON’s experiments; “+ Muon” replaces Adam on the encoder matrices by Muon while keeping the baseline’s task weights, and Muon (LS) uses Muon with equal weights. In all MultiMNIST runs the model learning rate is 10−3 ; MGDA uses its minimum-norm task weights, FAMO uses weight learning rate 0.025 and γ = 0.01, and the Muon variants use momentum 0.95, five Newton–Schulz steps, RMS matching 0.2, and weight decay 10−3 , with auxiliary Adam parameters using (β1 , β2 ) = (0.9, 0.95). Tuning and reporting. All hyperparameter selection is performed on a fixed 10% validation split drawn from MNIST-train using split seed 2026. The weight-step sweep evaluates η ∈ {10−5 , 5 × 10−5 , 10−4 , 5 × 10−4 , 10−3 } (Table 5), together with the other candidate configurations and schedules considered during tuning. Final candidates are evaluated over seeds 42, 43, and 44 using the mean validation accuracy over epochs 96–100. After all hyperparameters are frozen, the selected configuration is evaluated on MNIST-test. Ablations. Each ablation changes one component of our method and keeps the others, including the step sizes tuned for the spectral configuration, on three (42, 43, and 44) seeds. These are fixedhyperparameter substitutions, not comparisons of separately tuned variants. In particular, the oracle results do not establish superiority over a retuned Euclidean oracle, and the weight results do not establish equivalence of entropic and projected updates. For the oracle ablations, the sign variant uses the unit-radius ℓ∞ oracle sign(M ), while the ℓ2 variant uses the unit-radius Euclidean oracle M/∥M ∥2 on the full parameter vector. The spectral configuration follows the product geometry of the main method: each matrix-valued parameter tensor forms a unit-radius spectral-norm block, while all scalar and vector parameters are concatenated into a single unit-radius Euclidean block. No additional RMS matching or 0.2 rescaling is applied to these oracle variants. Weights: “projected” replaces the entropic step by the Euclidean projection P of wt + ηgt onto ∆κK . Momentum: “per-task” keeps one buffer mt,i per task, evaluates the oracle at i wt,i mt,i and scores with ⟨Dt , mt,i ⟩ (Appendix E); “none” evaluates the oracle at the current blended minibatch gradient. Step η: the grid above, all other settings fixed. η

10−5

5 × 10−5

10−4

5 × 10−4

10−3

Average accuracy (%) Final inner gap

90.20 1.97

90.54 0.90

90.08 0.84

89.69 0.29

89.53 1.04

Table 5: MultiMNIST: sensitivity of our method to the weight step η (spectral oracle, entropic weights, blended momentum), test accuracy averaged over three seeds. The main configuration, η = 5 × 10−5 , was selected on the validation split. Clipping. Table 6 varies the floor κ with all other settings of the main configuration fixed (η = 5 × 10−5 , τ = 0). For κ ≤ 0.48 the results coincide with the unclipped run to the reported precision, 33

Preprint

κ Avg.↑ Gap↓

0

0.48

0.49

0.495

0.4975

90.54 0.90

90.54 0.90

90.73 1.17

91.11 1.22

90.96 1.65

Table 6: Ablation of the clipping parameter κ on MultiMNIST: test accuracy and final inner gap, averaged over three seeds. so the floor essentially never binds: with this weight step the weights remain within [0.48, 0.52]. As κ approaches 1/K = 0.5 the floor forces the weights toward uniform; the mean accuracy rises slightly, to 91.11% at κ = 0.495, while the empirical inner gap grows from 0.90 to 1.65. Since κ → 1/K reduces the method to linear scalarization with the same oracle and momentum, and this configuration reaches a similar accuracy, the margin over the baselines in Table 4 cannot be attributed to the adaptive weighting at K = 2. Empirical inner-gap diagnostic. At the end of training, we compute per-task gradients of all trainable parameters on a fixed probe consisting of the first 256 training examples and report the simplex Frank–Wolfe gap of X wi ∇ℓi f (w) = i

∗

at the final task weights. Specifically, writing G(w) = exact geometry-specific polar direction, we report

P

i wi ∇ℓi and letting P (G(w)) denote the

gap = ⟨G(w), P (G(w))⟩ − min ⟨∇ℓi , P (G(w))⟩ . i

For the spectral configuration, the exact diagnostic uses the product geometry of the method: each matrix-valued parameter block has unit spectral-norm radius, whose dual contribution is the nuclear norm, while all scalar and vector parameters form a single unit-ℓ2 block. The sign oracle corresponds to a unit ℓ∞ ball over the full parameter vector and hence an entrywise ℓ1 dual norm. The ℓ2 ablation uses one unit Euclidean ball over the full parameter vector, so its dual is the global ℓ2 norm, rather than a sum of per-layer Frobenius norms. Because the underlying geometries differ, the reported gaps for different oracle variants are not on a common numerical scale. This is a fixed-minibatch diagnostic rather than the exact full-dataset inner optimization error appearing in the theoretical analysis. All reported main configurations use τ = κ = 0 and therefore do not directly test the regularized iteration-wise tracking guarantee. Code. An anonymous implementation of all methods and experiments is available at https: //anonymous.4open.science/r/LMO-MOO-D648/.

34

Related documents

• Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates#1298269
• From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization#1116266
• Multi-objective optimisation applied to industrial energy problems#456707
• MAdam: Metric-Aware Multi-Objective Adam#1232761
• Separating plane algorithms for convex optimization#429981