Adaptive Online Mirror Descent for Tchebycheff Scalarization in Multi-Objective Learning
Authors: Meitong Liu
Xiaoyuan Zhang
Chulin Xie
Kate Donahue
Han Zhao
Venue: Accepted by TMLR ()

Abstract: Multi-objective learning (MOL) aims to learn under multiple potentially conflicting objectives and strike a proper balance. While recent preference-guided MOL methods often rely on additional optimization objectives or constraints, we consider the classic Tchebycheff scalarization (TCH) that naturally allows for locating solutions with user-specified trade-offs. Due to its minimax formulation, directly optimizing TCH often leads to training oscillation and stagnation. In light of this limitation, we propose an adaptive online mirror descent algorithm for TCH, called (Ada)OMD-TCH. One of our main ingredients is an adaptive online-to-batch conversion that significantly improves solution optimality over traditional conversion in practice while maintaining the same theoretical convergence guarantees. We show that (Ada)OMD-TCH achieves a convergence rate of $\mathcal O(\sqrt{\log m/T})$, where $m$ is the number of objectives and $T$ is the number of rounds, providing a tighter dependency on $m$ in the offline setting compared to existing work. Empirically, we demonstrate on both synthetic problems and federated learning tasks that (Ada)OMD-TCH effectively smooths the training process and yields preference-guided, specific, diverse, and fair solutions.

Published in Transactions on Machine Learning Research (03/2026)
Adaptive Online Mirror Descent for
Tchebycheff Scalarization in Multi-Objective Learning
Meitong Liu
meitongs @illinois.eo
University of Blinois Urbana- Champaign The University of Hong Kong
Xiaoyuan Zhang
City University of Hong Kong
Chulin Xie
chulinz:2:iliioiss.. edu
University of Ilinoii Urbana- Channaaa
Kate Donahue
kpd@iilinois. edu
University of Mlinois Triana-Champpnte
Han Zhao
honchao@illimois.oooo edu
University of Iliinois Urbena- Channa-g
Reviewed on OpenReview: https: opwnrevvee.e...e....mmmmm net/ forum? id=M
Abstract
Multi-objective learning (MOL) aims to learn under multiple potentially conflicting objectives and strike proper balance. While recent preference-guided MOL methods often rely on additional optimization objectives or constraints, we consider the classic Tehebycheff scalarization (TCH) that naturally allows for locating solutions with user-specified tradc-offs. Due ils minimax formulation, directly optimizing TCH often leads to training oscillation and stagnation. In light of this limitation, we propose an adaptive online mirror descent algorithm for TCH, called (AHH)OMD-TCH. One of main ingredients is adaptive online-to-batch conversion that significantly improves solution optimality over traditional conversion in practice while maintaining the same theoretical convergence guarantees. We show that (Ada)OMD-TH) mumber of objectives and T is the number of rounds, providing a tighter dependency on m the oflline setting compared to existing work. Empirically, we demonstrate on both synthetic problems and federated learning tasks that (Ad))OMD-TCC effectively smooths the training process and yields preference-guidel specific, diverse, and fair solutions.
achieves a convergence rate of O (V m/T), where m is the
1 Introduction
Multi-objective learning (MOL) fundamental problem various domains, including multi-task learning (MTL) (Caruana) 1997,, federated learning (FL) (McMahan al.) 2017b), and drug discovery (Xie al., 2021). These problems often involve conflicting objectives, such MTL tasks with different label distributions and FL clients with heterogeneous local data, making it infeasible to find single solution that optimizes all objectives simultancously. Consoquently, MOL methods identify solutions on the Pareto Front (PF), where any improvement. in one objective necessitales a compromise in another (Miettinen) 1998). Moreover, being able to locate specific Pareto optimal (PO) solutions with desired trade-offs is particularly helpful for decision makers with their preferences, such as a uniform preference for fairness or weighted one prioritize certain objectives. This motivates the development of preference-guie guuidedd MOL methods (Lin al. 2019 Mahapatra)
& Rajan 2020 Kamani et. al.) 2021 Momma et. al. 2022 Chen et. al. 2024b).

---

Published in Transactions on Machine Learning Research (03/2026)
Table 1: Comparison of (Ada)OMD-TCH with previous OMD-based methods.
Method
Applied preference Ouline-to-batch conversion OMD instance for À
Convergence rate
AFL MMhrri et al.
2019
Uniform
Uniform avg.
PGD
Olym/T)
ALMO
Cortes et
2020
GroupDRO
Sagawa et a
2020
Uniform
Uniform avg.
BG
O(my/ log m/T)
MTcessMiT I.
He
2024
OMD-TCH (Ours)
Uniform avg. Adaptive avg.
PGD: Olyy Olym// m EG: O( log m/T)
AdaOMD-TCH (Ours)
Diverse
PGD or EG
MOL methods can be categorized into several lines. One classic line is evolutionary algorithms (Deb et al. 2002: Zhang & Li. 2007 Schaffer] 2014), but they often suffer from slow convergence due to the use of zeroth-order optimization oracles. Recently, gradient-based methods have gained increasing attention for their scalability in deep learning (Chen et al. 2025). Gradient manépulation methods, represented by the Multiple Gradient Descent Algorithm (MGDA), aim to find descent direction by resolving gradient conflicts (Fliege & Svaiter 2000; Désidéri 2012). However, they lack the ability to precisely locate desired PO solution. methods adopt additional optimization objectives constraints to move iterates closer to the PF and the specified preference simultancously (Mahapatra &
To overcome this limitation, recent preference-gusee
Rajan 2020 Chen et al. 2024b), which often requires solving subprograms and thus induces more complexity. Another line of methods to tackle MOL. is scalarization techniques, which reduce multiple objectives to a scalar function (Miettinen 1998). Linear scalarization has been widely used for its simplicity, yet is incapable of finding solutions on the non-convex part of the PF (Hu et al.) 2024). Morcover, for given preference, the solution found by LS depends on the shape of the PF (Boyd & Vandenberghe 2004) and thus does not conform to strict trade-off. In contrast, Tohebycheff scalarization overcomes both drawbacks it is able to recover the full PF and calibrate the precise quantitative relation among objectives (Ehrgott 2005
making it natural choice for weference-guided MOL. Nevertheless, due to its non-smooth nature, direct optimization often suffers from training oscillation and stagnation (Mahapatra & Rajan 2021
Given its stated advantages, this paper aims to build upon Tehebycheff scalarization (TCH) to solve preference-guided MOL. To overcome its drawback mentioned above, inspired by the literature on online learning Nemirovskij & Yudin 1983 Hazan et al., 2016),, we propose an adaptive solver for TCH using online mirror descent (OMD), named (Ada JCH-THHH that bypasses the unstable non-smooth formulation. One of our main technical ingredients is novel adaptive online-to-bale botch conversion scheme, yielding AdaOMD-TCH, iterates and outputs reweighted average for offline/bated batch learning.
that adaptively discards This scheme is motivated by the poor solution optimality of OMD-TCH using the traditional online-to-batch conversion, which uniformly averages all iterates as the final output.
Theoretically, we prove that (Ada)OMD-TCH converges to the optimal solution of the original TCH problem, i.e., the PO solution with given trado-off, at rate of O(Vlog m/TT) O(ym/T), depending the OMD instance, in the stochastic, offlne/batte setting, where is the number of objectives and T is the number of rounds. Our O(ylog (T) bound reveals tighter dependency on m for offline learning compared to previous works (Sagawa et al. 22200] He et al. 2024). Empirically, we demonstrate on seven synthetic problems and federated learning tasks that (1) OMD-)OH effectively stabilizes the training process as opposed to directly optimizing TCH, (2) AdaOMD-TCH significantly improves solution optimality over OMD-TCH, while retaining the same thcoretical convergence properties, and (3) (Ada)OMD-TCH is able to locate the specified and diverse solutions, serving as a competitive preference-guided MOL method.
Beyond the technical contributions, work contributes to conceptually connecting and unifying different applications in machine lcarning litorature that admit the same problem structure, including agnostic federated learning (AFL) MMohri el al. 2019), agnostic multi-objective learning ( (ALMO) (Cortes et al., 2020), group distributionally robust optimization (GroupDRO) (Sagawa et al. 2020 and robust multi-tast learning (EXCess.MTI. (He et al., (024), , among many others. Despite their distinct application scenarios, the underlying minimax formulation adopted these works is essentially a special case of Tchebycheff scalarization under a uniform preference. By allowing for general weighted preferences, we unify and extend these methods into
2

---

Published in Transactions on Machine Learning Research (03/2026)
generalized framework, and contribute (1) novel adaptive muline-tobbttdn conversion scheme that boosts solution optimality without affecting convergence guarantees, (2) a theoretical iteration complexity with optimal dependence on the number of objectives for the offline setting, and (3) empirical evidence of the framework as a competitive preference-guided MOL method, as summarized in Table !
2
Preliminaries
Given a pasitive int we use [n] for the set ( and An for the (n - )-dimensional simplex {a E IR" i== a; = 1, 2 O, Vij.
Notation.
2.1 Multi-objective learning
MOL aims to tackle the vector-optimization problem: min f(0) (ni where O C Rd
9EB
is the feasible region and ft Rd + R are m differentiable objective functions. Generally, objectives confictt with each hther so that no single solution is optimal for every objective. We are instead interested in Pareto optimal (PO) solutions (Miettinen, 1998
Definition 2.1 (SStrict) Pareto dominance).. For two solutions 0,, 02 E O, 0, dominates 02, denoted as 01 1 02 (slightly misusing the notation), if f01) I f((02) for all E [m]] and f,(0)) < ff(0)) for some E [m]. If f(,) <((02) for all E [m], 0, strictly dominates 02, denoted as 0, < 02.
Definition 2.2 ((Weak) Pareto optimality). A solution l" E θ is Pareto optimal there is no E such that < 0 A solution 0' E is weakly Pareto optimal if there is no such that 0 0'.
All (weakly) Pareto optimal solutions form the (weak) Pareto optimal set, whose image in the objective space forms the (weak) Pareto Front (PF). We also define Pareto stationarity:
Definition 2.3 (Pareto stationarity). A solution 0 e is Pareto stationary if there exists a E Am such that Σ 0; (O) = 0.
Parelo stationarity is a necessary condition for optimality, and a sufficient condition if objectives are convex and every entry of a is non-zero [Mecttinn 1998).
Scalarization is a classic technique for MOL. It finds a particular PO solution by converting the vector- optimization problem into scalar one given preference and a scalarization function. Two popular methods are linear scalarization (LS) (Geoffrion 1967) and Tchebycheff scalarization (TCH) (Bowman Jr 1976
LS: min LS(0: w) = min EEB
(x):(0);
TCH: min TCH(O; w) min max (:fi(0), BEE
(1)
#EB ielm)
where E Am is a user-defined preference vecto It controls the objective trade-off of the specific PO solution found. In particular, LS locates the PO solution where is normal vector of the PF's supporting hyperplane (Boyd & Vandenberghe 2004), while TCH enjoys the following property:
Theorem 2.4 (Informal, Ehrgott (2005)), Suppose 0% aig TCH(0: w), under mild conditions deo
w.f((Ot) (. V m
This quantitative relationship is particularly useful for preference-guided MOL-whil while the objective trade-off obtained by LS depends the problem-spocific PF's shape, TCH finds the PO solution at the intersection of the preference ray and the PF, offering more precise control. Moreover, LS fails to reach the non-convex regions of the PF Das & Dennis 1997: Hu et al. 2024), while TCH can find all (weakly) PO solutions:
The complete version of TCH is min max (x) z),, where C Rm is uadir point (i.e., f(0), vo O). When 9Ee se(m)
f(0) for all 0 0, can be set 0 and thus omitted. D 30 c O, s.t. (0) = (O),
[m]] @ 0z the only solution the TCH problem with preference When met, TCH gives the PO solution with the minimum possible maximum weighted objective, When met, the solution may weakly PO and the equality Theorem may hold.
3

---

Published in Transactions on Machine Learning Research (03/2026)
Theorem 2.5 (Choo & Atkins (1983). A feasible solution 0 O is weakly Pareto optimal if and only if it is a solution to a Tchebycheff scalarization problem given some w.
Being able to precisely control objective trade-offs and recover the complete PF, TCH is a natural choice for preference-guided MOL. However, its practicability is limited by training instability and stagnation due to the non-smooth formulation that optimizes only the worst objective at cach step (Mahapatra & Rajan 2020
2.2 Online learning algorithms
Online lcarning refers to scenarios where data arrives in a stream rather than fixed dataset (Zinkevich 2003). The defining characteristic is that the current optimal solution may no longer be optinal after new data is presented. This process can be modeled as a game between a player and an advensary: in each round t E (1.....)) T) the player outputs a solution x(1) E X based on past data and the adversary responds with a function g(() : X + IK that incurs a loss g(0) (x))). The goal of the player is to minimize the regret w.r.t. the best solution in hindsight: Regret(T') = Ei= (x(())
Ei (x). Online algorithms can also be applicd to offline/batell learning scenarios with an online-to-batel conversion that calculates deterministic solution from iterates {x(")
-inn min XEX
Jt=1, which conforms to convergence guarantee transformed
from the regret guarantee. The classic conversion is uniform averaging: + x(t), which ensures a diminishing optimization error w.r.t. T given sublinear regret bound (Cesa- Bianchi et al. 2004
Online mirror descent is fundamental online learning algorithm, commonly favored for its generaliz- able regret guarantees on decision sets with constrained geometries, as well as practically stable update trajectories [eemiovskii & Yudin 1983 Hazan et al. 2016). Its general update rule is:
arg min (Vel* (x(1) x) + 1 B Bx; (x)), XEX
(1+1) =
(2)
where (+-)) denotes the inner product, 1j is the step size, and By the Bregman divergence induced by a convex function &b X + R. With different choices of v Equation (2) can be instantiated into different forms. With de being the 1-2 norm and the negative entropy, we have Projected Gradient Descent (PGD) and Exponentiated Gradient (EG), respectively:
J exp (-1) (00) (x(1)))
PGD: x (1+1) = =Ilx -V00
xt ((+1) EG:
(3)
Σ/ 22 exp (1(((((0((()1))
where Nx: : Rd + X is projection function to the feasible domain of x.
3 (Ada)OMD-TCH
We now present our main methods. Section 3.1 formulates the unified framework for solving TCH via OMD.
Scction 3.2 introduces the adaptive online-to-batch conversion and its algorithm implementation, AdaOMD- TCH. Section 3.3 provides the convergence analysis and compares it with previous results. Section 3.4 discusses the conceptual differences between (Ada)OMD-ToC and other (preference-guiie guided) MOL methods.
3.1 OMD-TCH: unified framework
(1. following Juditsky et al (001)), we perform a key equivalent transformation: min max ()) min max Σm X (w)). As such, the Φ
Formulation. To solve the general TCH problem in Equation
#EB se/m]
inner maximization problem reformulated over a continuous simplex rather than a discrete set, thereby smoothing the one-hot selection. In the following, we use the notation L(O, A; w) = En > (w)J((O)).
The transformed problem can be interpreted as a zero-sum game between two players, O and X, who attempt to minimize and maximize shared objective L(O, X: w), respectively. This adversarial relationship makes optimization for each player an online learning task - in 0's view, À is the adversary and (())((0): w) is the time-varying loss function, and vice versa for player A. This dual problem can be solved by applying OMD to 0 and À separately. For 0 setting e(t) L( 7())) w). we derive the PGD update from Equation 3):
4

---

Published in Transactions on Machine Learning Research (03/2026)
0 ((+11) -ll 0
110
w (
(4)
Algorithm 1 OMD-TCH
1: Input: Number of rounds T, step sizes
When θ is unconstrained, PGD reduces gradient descent. For À Am: both PGD and EG applicable. Setting ( L(0 ::),, we have from Equation
and TT, (0) ( (__,...
for round == 1,... T do
3: Evaluate f(((()), (((((t))
Vi E [m]
4: Compute A (141) by PGD
or EG
PGD: ( -m (Λ00 + JA TAwwffOl f(OW))
5: Compute 0 (1+11 by PGD
(5)
6: end for
EG: X ((+1) 2 exp (1
7: Output: 0 - (
(6)
Σj= A1 exp (,xm;,
Note that the signs of the gradient terms are flipped for A's maximization goal. See full steps in Algorithm
D
Analysis. The update rule (4) for 0 involves gradients of all objectives, weighted by the a priori preference
vector w and the dynamic A. By (5) or 6 is iteratively updated such that larger weights are assigned objectives with larger accumulated losses. As such, OMD-TCH smooths out the one-hot update by incorporating all objectives while prioritizing the undertrained ones. As shown later, it converges to the solution of the original TCH problem, i..., the PO point with the specified tradc-off as in Theorem 2.4
Discussion. In various scenarios requiring fairness robustness, many methods adopt minimax objective and apply different instances of OMD solvers. For example, Mohri et al. (2019) used the PGD instance for A to encourage equal performance across clients in federated learning. Cortes et al. (020)) extended this to multi-objective learning. Sagawa et al. (2020) focused on optimizing the worst group performance for better distributional robustness, and He et al. (2024) tackled multi-task learning, using excess risks as objectives to penalize noise-contaminated tasks, both using EG for A. Essentially, these methods solve the special case of TCH with a uniform w, with its validity grounded by Theorem 2.4 However, whether OMD solvers remain effective for diverse trade-offs is left unexplored, which is critical for complete PF traversal preferenco-guided MOL. We unify this line by OMD-TCH and provide thcoretical and experimental results that support its application as competitive preference-guided MOL method.
3.2 Adaptive online-to-bated conversion
Like the previous methods discussed above, Algorithm adopts the traditional online-to-batch conversion that outputs the uniformly averaged solution 0. Although it enjoys a convergence guarantee, we challenge whether the final output should involve every iterate, especially those dominated by new ones as training proceeds. Indeed, OMD-TCH suffers from poor solution optimality, i.e., low overall performance, as observed in our experiments. Motivated by this concern, we propose an adaptive conversion that selectively excludes suboptimal iterates and carefully reweighs the others, retaining the same convergence guarantees and significantly improving solution optimality over the traditional conversion in practice.
Key idea. The final output of the adaptive conversion can be expressed as:
1
Σ T-)
T
with the following properties:
p = (0(r), E [T] 7l E [7] s.t. (()) ~ )())} is the set of iterates not dominated by any other, which we call trajectory PO iterates.
} is constructed follows:
1. Assign each iterate (()) unit weight of 1. For each ( & P, distribute its unit weight among (0(T) EPI (()) 0(0), i.e., the trajectory PO iterates that dominate (())
By this redistribution, have Eooee 7+ =T, which ensures the correct scale of θ.
5

---

Published in Transactions on Machine Learning Research (03/2026)
Feasible Region 0
t=2
T T=
Y
B
g(t)
0
0
6
013
0143
(
15
6
Pareto Froml
(19)
((9)
(a)
(b)
(c)
(d)
(e)
Figure 1: A sample run of AdaOMD-TCH. (a) ( is added to p(1) with a unit weight of 71 = 1.
(b) ((2) = l( is discarded with its weight transferred o()) (c) Ø 3 o()) is added to p(3) with its unit weight plus those of g()) o()) is discarded. (d) g(4) is a new trajectory optimal iterate and added to p(4)
with 7/4 = (e) The final output 0 is a weighted average of iterates in p(4)
In short, A excludes a large number of insufficiently trained iterates by being a weighted average of trajectory PO iterates only, with each onc's weight inherited from suboptimal iterates it dominates. The conversion is "adaptive" in the sense that P and {7>} adapt to the actual searching trajectory, rather than being fixed in advance. We show that i achieves the same iteration complexity as 0 in Section 3.3 and demonstrate its empirical superiority in Section 4
Algorithm implementation. We now introduce AdaOMD-TCH that outputs 0, as summarized in Al- gorithm 2 The key steps are from lines 4 to 20, where we dynamically maintain a set p(O, the trajectory PO iterates up to round i, and their weights 700). Specifically, each new candidate ((0) is handled by three cases:
A Algorithm 2 AdaOMD-TCH
1: Input: Number of rounds T, step sizes ne and vix
((0), X ( mn! 1 _ p(l)) =0(0) = 0.
2: for round t = 1, 1,.., -T do
3: Evaluate f:(0()), Vf((((()), for all i [m].
4:
Update p(() and 7(1) // adaptive conversion
A (((-) E p(r-i) ((() = g
Tf ( is dominated by some elements in p((-1) (A 0, line 6), directly discard (line 7) and equally split its unit weight to the dominating elements (lines 8 to 10).
5:
6:
if A # 0 then
p(t) x- p(t-1), (0) +- g (t-1)
7:
8:
for g(T) E do
If (()) dominates some elements in 1(t-1) (B * 0. line 15), discard the suboptimal elements (lines 17, 18) and add g(t) to p(t) (line 12) with its unit weight plus weights inherited from the discarded (lines 13, 16).
9:
7 + 77 + ল
10:
end for
11:
else
12:
p(t) p(t-1) u (
13:
(0) + (1-1) U (/(0) = 1}.
14:
B + (0( EEEE
Epp p((t-) 0 3 0
If (())) is not dominated by nor dominating any element in p((-1), it is new temporary trajectory PO iterate; add it to the set with a unit weight of 1 (lines 12, 13).
15:
if B 0 then
(6) +1 + + +Z L (1)
(()
16:
77
17:
p(t) < p(() \B.
(() + 7((") (ott (9)
Figure ! provides example illustration. The afore- mentioned properties can be easily checked: when the algorithm finishes, p(T)= = P; the construction of } happens at each step, where we assign a unit weight to the new iterate and reallocate the weights of iterates that become suboptimal.
18:
180)
19:
end if
20:
end if
21: Calculate ((++1) and g(++1) as in OMD-TCH.
22:
end for
Output: 0- 7 I= 1r g(r)))
23:
Complexity analysis. The memory complexity of AdaOMD-TCH is determined by the instantaneous size of p(t, In practice, most elements in the current optimal set are soon dominated and replaced by new iterates as training proceeds. Hence, p(t) is often sufficiently small, which is also our motivation to dynamically maintain p(o) and 7((), instead of deriving them after saving all iterates. The time complexity mainly depends on the efficiency of querying, insertion, and deletion on p(t), With advanced data structures such as k-d trees, such operations can be optimized to logarithmic complexity w.r.t. the sot size on average. In our experiments, we implement naive traversal and already observe minimal overhead, again, due to the small size of p(() in practice.
6

---

Published in Transactions on Machine Learning Research (03/2026)
3.3 Theoretical convergence guarantees
This section analyzes the convergence rate of (Ada) for offine/batch learning, where the training dataset for each objective remains fixed. We adopt assumptions commonly used in the convergence analysis
for OMD-based methods (Mohri et al.] 2019 Cortes et al. 2020 Sagawa et al. 2020 He et al.
2024
Assumption 3.1. For all i E [ml, fi(0) is convex in 0 and bounded by U: li(0) < U, and gradients are bounded by L in the infinity norm: [[)) I L. The feasible region is bounded by Ro: |10||> S Ro.
Additionally, consider stochastic feedback and construct the stochastic gradients as follows: in each round & E [T', for each objective i E [m], sample a random batch B, from its training set and compute the stochastic gradients w.r.t. 0 and A: de Ei (() = - x(1
E(x.))e v (x,))) v))), P.
L
5e = [..., [. E(X))EB, fi(O();; (x, .J". Note that we use the d's to update and À and still use to denote the true gradient. By construction, the stochastic gradients are unbiased, and bounded under Assumption 3.1 ||0c%" I1x I L, l10e" ll U, for any t E [T].
We first present the general convergence rate using arbitrary distanco-gencratiin functions who and d/x Theorem 3.2. Suppose Assumption 3.1 holds. With ve, 122, no, and π satisfying (1) the is ne ho-strongly
conver, (2) u/ is ux-strongly convex, (3) 170- =
Do and (4) n = v STCx02, both Algorithms 1 and g 5TC,12
4px D2
converge as: with probability at least Y, 0 < <11,
20DoCoL2 NoT
20DACAU2 A*T
2
TCH w) min TCH S BEB
A(dRoL + +U) log
On the LHS, θ is O or 0 output by Algorithm 1 or constants depending on the choices of the and 1/> and potentially contain factors of the dimensions of 0 (i.e., d) and X (i.e., m), respectively. Uncertainty comes from the stochastic gradients.
respectively. On the RHS, De, Dx, Co, and CR are
Remark 3.3. Theorem 3.2 indicates that the outputs of both OMD-TCH and AdaOMD-TCH converge to the solution of the original TCH problem, i.c., a specific PO point with tradc-offs controlled by w following Theorem 2.4 Note that the convergence rate in T, O(I/VT), matches single-objective stochastic gradient descent. The cess-informative expectation bound and proof are deferred to Appendix A.I
To further reveal the dependency on d and m, one must unwrap the factors hidden in the constants and C, which depend on the specific choice of OMD instances, i.c., the choice of yss. We present two instantiated bounds where we use PGD and EG for X, respectively, and PGD for 0 in both cases. We also discuss the p-norm instance in Appendix A.2 whose bound is found to be no better than PGD or F.G.
Corollary 3.4. Suppose Assumption 3.1 holds. Using PGD for both O and X, the constants are: Hg MA 1,
Dg = 2dR2. Dx = 2, Co = d, C^ = m. Therefore, under optimal step sizes The = V
8 and 1/Λ = V 52 mI
5TL2
with probabilily at least 1 - 7, 0 < < 1, both Algorithms and converge. as
TCH( w) min (CH w) R. 9-e
2 2/10 VT Using PGD for and EG for X, the constants are:
2 log r
M(dROL +U T
(8)
VT
Corollary 3.5. Suppose Assumption 3. holds.
μe y사 =1, 1, Do 2dR2, Dx = log m, Co = d, Cx = 1. Therefore, under optimal step sizes ne = V 5TL*
8R3
Alg and /
, with probability at least 1 - 7, 0 < < both Algorithms 1 and converge as
TCH(Ô: w) - min TCH(O:)) 2v10dRoL 2 2/5vlogmu + ( log 1 dEe
(9)
VT
VT
Remark 3.6. The factor in both corollaries can be lifted if we bound the 1-2 norm of 0 and the gradients, as adopted by most previous works. Since the 1-2 norm usually scales with dimension, we bound the infinity norm to offer clearer dependency on d. Expectation bounds and proofs are provided in Appendix A.2
7

---

Published in Transactions on Machine Learning Research (03/2026)
Compared to established bounds with EG for X (Sagawa et al. 2020 He et al. 2024 Corollary 3.5 provides tighter dependency on the number of objectives m, improving from (m log m) to OVvlog m) with no stricter assumptions on objective properties. The improvement comes from a different construction of unbiased stochastic gradients based on a more common and natural sampling strategy for offline MOL problems, i.e., to sample from all, instead of one, objectives in each round. Such full sampling is adopted by most gradient-basse bbadd MOL methods (Mahapatra & Rajan, 2020 Chen et al.) 20244/b). D), and is a must for those relying on full gradient information to compute the update direction. As such, our bound reveals optimal iteration complexity better aligned with the MOL setting. We include a detailed discussion in Appendix A.3
3.4 Conceptual comparison
In this section, we compare (Ada)OMD-TCH with (1) other scalarization-based methods, (2) gradient manipulation methods, and (3) other preference- based MOL methods
Scalarization-baseed methods. We present a connection between (Ada)OMD-TCH with EG for À and smooth Tehebycheff scalarization (STCH) (Lin et al., 2024), which also bypasses the one-hot update in vanilla. TCH by leveraging the log-sum-exp technique: min STC w.) = min 1loo (Ei=l e #ee
#Ee
where μ is a scaling constant and z is a nadir point which we set to 0 for simplicity. Optimizing the
(1) ( STCH objective with gradient descent, the update rule is: @(t+1) = ((t) - E ag w; ff:((t))) where
exp(w.,,(((()))/))
Em" (x)(1)33((0))))) Compared to Equations (4) and (6), the only difference lies in a0 and A
While (0()) is solely determined by current losses, A()) incorporates historic information through ( Such "buffering" can be viewed as a smoothing technique to make X change less drastically, which can be viewed as a result of OMD's inherent property of regularizing distances between consccutive itcrates.
From another perspective, in (MDH)OM by setting y/ to 0, À becomes a static vector initialized uniformly, and the update for 0 (Equation } is equivalent to linear scalarization with preference w. (Ada)OMD-TCH) can, therefore, also be interpreted as a middle ground between LS and TCH, for which we provide an intuitive example on our synthetic experiments in Appendix B.
Gradient manipulation (GM) methods. Although (Ada)OMD-TCH, as well as STCH, uses a dynamic weight to combine objective gradients, appearing similar in form GM methods, the two streams are fundamentally different. GM methods aim to mitigate gradient conflicts in each iteration by finding a common descent direction. The Multiple Gradient Descent Algorithm (MGDA) solves for the weights that minimize the norm of the composite gradient (Désidéri 2012 Sener & Koltun 2018b. Some of its variants regularize the change of weights with momentum updates (Zhou et al. 2022] or mirror descent updates (Fernando
et al. 2023 Chen et al. 2024a), along with other conflict-resolvnng strategies (Liu et al., 2021 Yu et al., 2020]. Algorithmically, ecalarization-basee methods compute the weights based on objective values, while GM methods rely on gradient information. The major drawback of GM methods is that, although shown to converge to a Pareto stationary solution (Fliege et al.) 2019)), they do not have control over which specific PO solution is found, potentially due to their focus local gradients, but not the objective value trado-offs. As consequence, even if reweighing objectives with preferences during optimization, they are less effective in recovering specific and diverse solutions, as shown empirically in Section 4.1
Preference-guidedd methods aim to locate specific PO solutions satisfying certain preferences, enabling decision makers to select those with the most suitable trade-offs. Most of the recent approaches stem from gradient manipulation methods and thus rely on designed mochanisms to steer the trajectory, such as using the discrepancy between the current and desired trade-offs as an additional optimization objective Mahapatra
& Rajan 2020 Kamani et al.) 2021 casting preferences as optimization constraints (Lin et al. 2019 Chen
et al. 2024b). In contrast, (Od builds on the inherent properties of Tchebycheff scalarization
(Theorems 2.4 and 2.5j, offering a cleaner formulation for preferencc-guided learning. [Momma et al. (0022 also starts from TCH and aims to avoid the one-hol update. Unlike our approach, they achieve this by deriving several levels of dual problems that lead to a strategy optimizing towards Pareto stationarity and the specified preference simultancously, similar to those adopting an additional optimization objective. However, theoretical analysis on whether and how fast the method converges to the desired PO solution remains missing, while OMD-)O is guaranteed convergence with good rate.
8

---

Published in Transactions on Machine Learning Research (03/2026)
Sofff
Tur
Tur
Tix P
Trx F1
LS
(b) TCH
(c) STCH
(d) OMD-TCH
AdaOMD-TCH
7
Teddbl
Tea
84
0.4
f
(f) MGDA
(g) PMTL
(h) EXCessMTL
(i) EPO
(i)
FERERO
Figure& 2: Solutions found by different methods on VLMOP2. Each dotted ray denotes the element-wise
inverse of a PGD for X is reported for (Ada)OMD-TCH Results are averaged over three seeds.
4 Experiments
Given the theoretical guarantees for convex objectives in Section 3.3 in this section, we study the performance of TAd in non-convex experiments. We mainly invostigate three questions: (1) Can (Ada)OMD- TCH preserve the advantage of TCH in finding specific and diverse PO solutions, serving as preference-guides MOL method?
(2) Can the OMD reformulation mitigate the training oscillation and stagnation problems of vanilla TCH? (3) Is the proposed adaptive ouline-to-bated batch conversion effective in improving solution optimality over the traditional conversion? Our experiments provide affirmative evidence for all of them and also demonstrate that AdaOMD-TCH remains highly competitive when compared to other MOL methods.
4.1 Synthetic problems
This section focuses on question (1). Synthetic problems with known and visualizable Pareto Fronts provide a suitable environment for testing how well MOL methods locate specific PO solutions under diverse preferences. We verify this ability of (Ada)OMD-TOC
on seven non-convex synthotic problems, namcly
VLMOP2 (Van Veldhuizen & Lamont 1999) and F1 F6 (Lin el al. (022). For each problem, we apply ten preference vector w's evenly across the simplex. More detailed setups are deferred to Appendix B.1
Methods. Apart from (Ada)OMD-TCH. we include scalarization methods, namely linear scalarization (LS) and vanilla Tchebychelf scalarization (TCH), well the smooth TCH (STCH) (Lin et al. 2024 and ExcessMIL (He et al. 2024), another OMD-based method. We also consider typical gradient manipulation methods, including MGDA, CR-MOGM (Zhou et al. 2022), and Moco (Frnnando et al. 2023). Finally, we compare with other preference-guiee guided methods, including PMTL (Lin et al. 2019 EPO (Mahapatra 2024b). Note that some preference-guided methods discussed 2022) are omitted in the experiments due to lack of official code for fair comparison. Hyperparameter choices reported in B.1
& Rajan 2020), and FERERO (Chen et al.
earlier (Kamani et al. 2021 Momma al.
Results. Figure 2 illustrates results on VLMOP2. In the figures, each dotted ray represents the element-wise inverse of a preference vector w. Ideally, solutions should be scattered across the PF and preferably at the intersections of the rays and the PF, where the objective trade-off strictly follows the corresponding w.
As expected, LS only locates the two endpoints on the PF and completely misses the non-convex region. TCH yields diverse solutions on the exact intersections. Note that TCH performs well on these synthetic problems, but degrades drastically when applied to more complex ones, shown later. Both proposed
9

---

Published in Transactions on Machine Learning Research (03/2026)
smooth solvers for TCH, solutions of STCH and (Ada)OMD-TCH resemble those found by vanilla TCH, expected. However, ExcessMTT, although using OMD-based updates as well, does not recover TCH, which we verified is not an artifact of hyperparameters and may be caused by inaccurate estimates of excess risks.
Additionally, MGDA finds arbitrary solutions, even when objectives are reweighed by preferences. Its variants CR-MOGM and Moco show similar results, as Appendix [3.1 This exemplifies that gradient manipulation methods, without additional designs, are insufficient for preference-guiee guidded learning. Other preference-guide MOL methods yield less satisfactory solutions compared to STCH and (Ada)OMD-TCHH. PMTL does not find the exact PO solutions; EPO performs well for most trade-offs, but misses the two extreme ones; FERERO gives fairly diverse set, but is less accurate in locating the intersections.
Similar results on the other problems can be found in Appendix B. Note that all synthetic problems have non-convex objectives, and VLMOP2 has a non-convex PF. As shown, (Ada)OMD-TCC) preserves the property of TCH finding specific and diverse PO solutions and remains effective non-convex cases, which complements our theoretical analysis assuming convexily.
4.2 Federated learning
To test (Ada)OMD-TCC) TCH on real data, we consider federated learning (FL) tasks where clients with hetero- geneous local data constitute multiple objectives. First, we address questions (2) and (3) in a 10-elient FL setting focused on the faiuuess-accuracy challenge, where one aims to find the PO solution with a balanced objective trade-off. We demonstrate more stable training using OMD updates and better solution optimality through the adaptive conversion. Next, we employ a 2-client setting to compare (Ada)OMD- TCH against other preference-guided MOL methods under diverse preferences, providing further supporting evidence for question (1). Finally, benchmark our approach against wider range of FL methods in the 10-client FL fairness experiments, where AdaOMD-TCH achieves highly competitive results.
4.2.1 AdaOMD-TCH gives more stable training and better solution optimality
First, we compare (Ada)OMD-TCHH linear scalarization (LS), and the vanilla Tchebycheff scalarization (TCH), to show that OMD updates effectively stabilize the training process over TCH, and that the adaptive online-to-batch conversion significantly improves solution optimality over the traditional conversion.
Data, models, and metrics. Following the settings in Ghosh et al. (2020) and Collins et al. (2021), we simulate three scenarios of data heterogeneity with m = 10 clients, namely Rotation and Partial Class with C = 2 and classes per client, respoctively, using MNIST [Deng] 2012) and CIFAR10 (Krizhevsky Hin- ton p We train a two-layer fully connected neural network with ReLU for MNIST and ResNet18 (He et al. 2016) model for CIFAR10. The goal is to find the optimal solution with fair, uniform trade-off. We eval- uate the methods by both overall accuracy, for which we use average test accuracy. and client-level fairness, for which we use agnostic loss (Mohri et al., 2019) and ac- curney parity (Li ct al. 2019). Note that lower fairness metrics are better. Detailed setups, hyperparameters, and random seeds are reported in Appendix B.2
CIAR10 Retation
LS7xdPvg)
Tou CollegTOC AdsoiieppTO
fourd
Tast TastAAcuuscy Party
Figure 3: Examining OMD updates and the adaptive conversion. "gd" and "eg" denote using PGD and FG, respectively, for A. The training curves are plotted seed=0 to show fluctuations.
Results. As shown in Figure 3. TCH suffers from oscillations and slow convergence, with worse results in the Partial Class cases (Appendix B.2 This justifies our molivation for avoiding the one-hot update. OMD-TCH successfully stabilizes the training process and offers a fairer solution than both TCH and LS, but still converges slowly and has an overall accuracy way below L.S. Using the adaptive onlino-to-batch conversion, AdaOMD-TCH preserves only the trajectory PO iterates and thus exhibits significant improvements faster convergence, higher average accuracy, and minimal impact fairness. Table 2 presents more detailed
10

---

Published in Transactions on Machine Learning Research (03/2026)
Table 2: Comparison between OMD-TCH and AdaOMD-TCH.
Rotation
Partial Class C ==2
Partial Class C'
Method
Average
Agnostic
Accuracy Parity 4
Average
Agnostic
Accuracy
Average
Agnostic
Accuracy Parity 4
Accuracy
Loss 4
Accuracy
Loss 4
Parity 4
Accuracy
Loss 4
OMDgd-TCH
59.244
1,239
2.429
31.080
2.515
20.600
47.960
1.832
8.787
AdaOMDgd-TCC
66.218
1.148
3.592
36.765
2.372
18.422
53.422
1.664
6.823
OMDeg-TCH
59.273
1.254
2.660
34.865
2.534
22.045
48.064
1.833
8.803
AdaOMDeg-TCH
65.885
1.156
3.688
36.755
2.388
18.933
55.632
1.662
7.930
comparison between OMD-TCH and AdaOMD-TCH on CIFAR, where AdaOMD-TCH outperforms OMD- TCH in almost all cases, especially improving average accuracy to large extent. The only exception in accuracy parity is possible as the adaptive conversion is mainly designed for better optimality. These results show that (Ada)OMD-TCH stabilizes TCH training, and the adaptive conversion yields significantly better solution optimality over the traditional one.
4.2.2 (Ada)OMD-TCH TCH serves as a competitive inteerence-guider MOL method
Next, we show that (Ada)OMD-TCH remains competitive finding preference-guided,, diverse, and optimal solutions when applied more complex tasks, complementing results on the synthetic problems.
Data, metrics, and methods. To make it casier to quantify the diversity and optimality of the solutions found under multiple preferences, adopt 2-client setting where the CIFAR10 datasel is randomly and equally distributed and rotated 0 and 90 degrees, respectively, to create data discrepancy. Following previous work (Chnn et al. 2024b), we measure the hypervolumes of the solution set over three preference choices of each method, on both objective losses and accuracies. A larger hypervolume indicates a solution set that is both more diverse and more optimal. We compare (Ada) OMD-TCH with methods that are also capable of locating preference-specifie PO solutions, including LS, TCH, STCH (Lin al.. 2024). ExcessMTL (He et al., 2024 EPO |Mahapatra & Rajan 2020), and FERERO (Chen et al., 2024b).
Results. As shown in Table OMD-TCH achieves the best results, verifying its application a general preference-guider MOL method that works beyond the uniform tradc-off for fairness and robustness, as used by previous works in Table D AdaOMD-TCH achieves slightly lower hypervolumes, which can be explained by its trade-off between optimality and diversity. Specifically, by considering only the non-dominated iterates, AdaOMD-TCE gives better optimality than OMD-TCH in both overall loss (1.495 1.521) and accuracy (65.357% >> 62.533%), but relatively less diversity, which together leads to lower hypervolumes. Nevertheless, AdaOMD-TCH still yields good results, achieving the second-best. hypervolume in accuracy. Moreover, shown by the 10-client results in Table 2 the improvement in optimality of AdaOMD-TCH is much more significant under a larger clien//ojjecte base, making it generally more competitive than OMD-TCH.
4.2.3 Comparison with MOL and FL methods the 10-client fairness benchmark
Finally, we compare (Ad))OMD-TCH with more MOL as well as FL methods under the same 10-client setup as in Section 4.2.1 where one tackles the fairness-accuracy challenge by finding the solution with both higher overall accuracy and better client-level fairness. We show that AdaOMD-TCH TCH, using the adaptive conversion, yields highly competitive performance compared other methods, especially in fairness.
Methods. Apart from (Ada) we include all previously mentioned MOL methods: LS, TCH, STCH, EXcessMTL, EPO, and FERERO. Since ExcessMTL. adopts a similar OMD framework with EG for
Table 3: Hypervolumes (t) of different methods. PGD for À is reported for (Ada)
Method
TCH
STCH
EXcessMLL
EPO
FERERO
OMD-TCH
AdaOMD-TCH
Loss
0.911+-0.092
8.797+0.052 7.583++.004 6.693=0.863 0.125-0.019
7.457++0.20 0.141+0.004
6.041+#.22 0.136+0.000
9.166:10.065
7.005++0.11 106
Accuracy
0.156+00.001
0.107+0.002
0.153+0.001
0.168-10.001
0.159++0.002
11

---

Published in Transactions on Machine Learning Research (03/2026)
CIFARIO Rotation
Irogiaa
Frdeepblr
Fedti
TCH
STORTEM
Brd
rawno
Diassen
Ada aesce
Adcosbap TCM
Litkedog
geft
Propiat
Fratecblee
SEWTTEMO
Brd
reARO
Doanti
Assbcayeet
detip
Adscwetip
Figure 4: 10-client results for all methods in average accuracy (t) and agnostic loss (1).
X, our adaptive conversion is also applicable, leading to Ade We also consider fair FL methods: qFFL Lin ct al. 2019). FedFV (Wang ct al., 2021), PropFair (Zhang et al. 2022 and FedMGDA+ (Hu et al., 2022). Due to the same nature of learning under multiple objectives, many fair FL methods are equivalent to an MOL method using uniform preference. In fact, the selected methods also cover FedAvg (McMahan
et al. 2017a (LS), TERM (Li et al. 2020) (STCH), and AFL (Mohri et al. 2019 (OMDgg-TCHH).
Results. Figure | visualizes the average accuracy and agnostic loss of all methods CIFAR Rotation. AdaOMD-TCH significantly improves solution optimality over OMD-TCH in terms of overall accuracy and achieves competitive results among all methods. It also provides the best fairness in terms of agnostic loss. Similar improvements are observed between ExcessMTL and AdaExcessMTL, which verifies the wide applicability of our adaptive online-to-batch conversion. Compared other methods, AdaOMD-Tee TCH consistently outperforms qFFL and PropFair across all settings and metrics, well EPO and FERERO in most cases. Since OMDgd-TCH encapsulates AFL, the superiority of AdaOMDgd also indicates its superiority over AFL. Full results and hyperparameters are in Appendix B.2 where we also report the training time, showing that the adaptive conversion is quite light in computation.
over OMDgd-TCH
Table 4 offers a finer comparison between AdaOMD-TCH and STCH, both smooth solvers for TCH. As discussed in Section 3.4 STCH and AdaOMDeg-TCHI share similar updates, except that the dynamic objective weights in STCH are solely determined by current losses, while those AdaOMDeg- incorporate historic information. As an attempt close this gap, we apply the momentum updates proposed in Zhou et al. 2202 to STCH, which also creates "buffering" effect: (! (t-1( (1 ()))((") where a! is the original STCH weight and 8e is computable parameter. As shown in Table 4 momentum update can improve STCH, but is still outperformed by odHOMDeg-TCH in most cases. AdaOMDgd-Tone
offers even better results, achieving the best on six out of the nine metrics. Note that STCH w// momentum, AdaOMDeg-TCCH, and AdaOMDgd-TTCH all consider past losses for dynamic weights, but in different forms.
4.2.4 Ablations and extensions
Design components. In Appendix B.2 we restate in detail the roles of the design components in AdaOMD- TCH, namely Tehebycheff scalarization, OMD updates, and the adaptive online-to-batch conversion. We apply the adaptive conversion to LS and TCH, although not rigorously motivated, and examine their performance as a light ablation study. The results further demonstrate the necessity of basing Tehebycheff scalarization and applying OMD updates, as well as the wide applicability the adaptive conversion.
Table 4: Comparison between AdaOMD-TCH and STCH.
Rotation Agnostic Loss
Partial Class C 2
Partial Class C=
Method
Average
Accuracy Parity
Average Accuracy
Aguostic
Accuracy Parity
Average Accuracy
Agnostic Loes
Accuracy
Accuracy
Loss 4
Parity $
STCH
66.320 00.
1.219
4.997
35.380
2.386
19.139
55.328
1.622
7.311
STCH w/ momentum
66.422 1
1.205 1
4,800 L
35. 105
2,380
18.945
54.240
1.637
7.335
TdCOMDeg-TCH
65. 885
1.156
3,688
355
2.388
18.933
55.632
I.662
7.930
AdaOMDgd-TCH
66.218
1.148
3.592
36.765
2.372
18.422
53.422
1.664
6.823
12

---

Published in Transactions on Machine Learning Research (03/2026)
Evaluation data for iterate comparison. When determining the Pareto dominance among iterates in AdaOMD-TCH, the ideal approach is to evaluate iterates on full training data. Yet in practice, when the data is large and mini-batch updates are adopted, such full evaluations would lead to extra training time. Therefore, in our implementation, we use batch losses as estimates whenever using mini-batch updates. Nevertheless, by comparing results using (1) mini-batch estimates, (2) full training data, and (3) held-out, validation sets, respoctively, for iterate comparison, we show that the adaptive conversion is robust against different evaluation data. Details are deferred to Appendix B.2
Objectives of different scales. In our FL setting, the client losses are of similar scales, allowing for direct evaluation of preference satisfaction without other artifacts. In broader application scenarios, the objectives may be of different scales, and directly using them for OMD-TTH,, or any method that involves dynamic weight allocation based on objective values (e.g., TCH and STCH), can cause bias towards objectives of a larger scale and interfere with the original preference. In Appendix B.2 we discuss a practical ratio trick commonly adopted in such cases and show that (Ada)OMD-TCH compatible with it.
5 Conclusion
We propose (Ada)OMD-TCH) an adaptive online mirror descont algorithm for preference-guided multi- objective learning and a unified framework covering multiple previous methods for fairness and robustness. (Ad))OMDTTC MCDH preserves the power of Tchebycheff scalarization in locating specific Pareto optimal solutions and bypasses the one-hot update that leads training oscillation and stagnation. Our novel adaptive online- to-batch conversion significantly improves solution optimality over traditional conversion while retaining the same convergence guarantees. We prove that (Ada)OMD-TCC converges to the original TCH solution at a rate of Olv log m/T),, revealing an optimal dependency on m for offline learning. We use non-convex synthetic problems and federated learning tasks to show that (1) (Ada)OMD-TCC effectively stabilizes the TCH training process, (2) AdaOMD-I MCH significantly improves solution optimality over OMD-TCH, and (3) AdaOMD-TCH is a competitive preferenco-guidel MOL method that finds specific, diverse, and fair solutions.
Broader Impact Statement
This paper presents work whose goal is to advance the field of multi-objective learning, with potential applications in algorithmic fairness, distributional robustness, and multi-task learning. Given the scope of this rescarch, we do not anticipate immediate ethical concerns or direct socictal consequences.
Acknowledgments
Meitong Liu and Han Zhao are partially supported by an NSF CAREER Award No. 2442290 and a research grant from Meta Platforms, Inc. We thank Dr. Xi Lin and Prof. Qingfu Zhang for their helpful discussion on multi-objective optimization during Han Zhao's visit the City University of Hong Kong.
References
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Matheraatiaal Journal, Second Series, 33)3333773367 1967.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, (1): 175, 2003.
V Joseph Bowman Jr. On the relationship of the tchebycheff norm and the efficient frontier of multiple-criteria objectives. In Multiple Criteria Decision Making: Proceedings of a Conference Jouy-en-Jae Josass, France May 21 23, 1975, pp. 76 86. Springer, 1976.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Rich Caruana. Multitask learning. Machine learning, 28:41-75, 1997.
Nicolo Cesa-Bianchi. Alex Conconi, and Clandio Gentile. On the generalization ability of on-line learning algorithms. IEF. Transactions Information Theory, 50(9):2050-200) 2057, 2004.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Gong Chen and Mare Teboulle. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal on Oplimizalion, 3(3):538-55) -4388 1993.
Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-war way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidacee Aduances in Neural Information Processing Systems, 36, 2024a.
Lisha Chen, Saif, Yanning Shen, and Tianyi Chen. Ferero: A flexible framework for preference-guided multi-objective learning. Advances in Neural Information Processing Systems, 37:18758 18805, 2024b.
Weiyu Chen, Baijiong Lin, Xiaoyuan Zhang, Xi Lin, Han Zhao, Qingfu Zhang, and James T Kwok. Gradient- based multi-objective deep learning: Algorithms, theories, applications, and beyond. ar preprinl arXiv:2501.109/5 2025.
Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In International conference on machine learning, pp. 794 803. PMLR, 2018.
Eng Ung Choo and Derek R Atkins. Proper efficiency in nonconvex multicriteria programming. Mathematics of Operations Research, 8(3):467 470, 1983.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized lederated learning, In International conference on machine learning. PMLR, 2021.
Corinna Cortes, Mehryar Mohri, Javier Gonzalvo, and Dmitry Storcheus. Agnostic learning with multiple objectives. Advances in Newrul Information Processing Systems, 33:20485 20495, 2020.
Indraneel Das and John Demnis. closer look at drawbacks of minimizing weighted sums of objectives for parelo set generation in multicriteria optimization problems. Structural oplimization, 14:63 69, 1997.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Compulation, 6(2):182-19)) 197, 2002.
Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE signal processing magazine, 29(6)1141-142, 2012.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313331)) 2012.
Matthias Ehrgott. Multicriteria optimization, volume 491. Springer Science & Business Media, 2005.
Heshan Fernando, Han Shen, Miao Liu, Subhajit Chandhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. International Conference on Learning Representations, 2023.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, 51:479-494, 2000.
Jörg Fliege, A Ismael F Vaz, and Luis Nunes Vicente. Complexity of gradient descent for multiobjective optimization. Optimization Methods and Software, 2019.
Arthur M Geoffrion. Solving bicriterion mathematical programs. Operations Research, 15(1):39 54, 1967.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ranchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586 19597, 2020.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2 (3-4):157-322) 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEFE conference on computer vision and poltern recognition, pp. 778, 2016.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Yifei He, Shiji Zhou, Guojun Zhang, Hyokun Yun, Yi Xu, Belinda Zeng, Trishul Chilimbi, and Han Zhao. Robust multi-task learning with excess risks. In Forby-first International Conference on Machine Learning, 2024.
Yuzheng Hu, Ruicheng Xian, Qilong Wu, Qiuling Fan, Lang Yin, and Han Zhao. Revisiting scalarization in multi-task learning: A thcoretical perspective. Advances in Neurol Information Processing Systems, 2024.
Zcou Hu, Kiarash Shaloudegi, Guojun Zhang, and Yaoliang Yu. Federated learning moets multi-objoctive optimization. IEEE Transactions on Network Science and Engineering. 9(4):2039 2051, 2022.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, (1):17-58, 2011.
Mohammad Mahdi Kamani, Rana Forsati, James Wang, and Mehrdad Mahdavi. Pareto efficient fairness in supervised learning: From extraction tracing. arXiv preprint arXte:2104.01694 2021.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. arxiv preprint ar arXic:1905104999 2019.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. arXiv preprint ar Xix::2007.011 01162, 2020.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Fung-Fu Zhang, and Sam Kwong, Pareto multi-lask learning. Advances in Neural Information Processing Systems, 32, 2019.
Xi Lin, Zhiyuan Yang, Xiaoyuan Zhang, and Qingfu Zhang. Pareto set learning for expensive multi-objective optimization. Advances in neural information processing systems, 35:19231-1924 2022.
Xi Lin, Xiaoyuan Zhang, Zhiyuan Yang, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Smooth tchebycheff scalarization for multi-objective optimization. In 41st International Conference on Machine Learning, 2024.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. Advances in Neural Information Processing Systems, 34:18878 18890, 2021.
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent pareto optimization. In International Conference on Machine Learning, pp. 6397-6607. PMLR, 2020.
Debabrata Mahapatra and Vaibhav Rajan. Exact pareto optimal search for multi-task learning and multi- criteria decision decision-making. arXiv preprint arXiv:2108.008 005597 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017a.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication efficient. learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp- 1273 1282. PMLR, 2017b.
Kaisa Miettinen. Nonlinear multiobjective optimization. International Series in Operations Research & Management Science, 12, 1998.
Mchryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated lcarning. In International conference on machine learning, pp. 4615-4622 PMLR, 2019.
Michinari Momma, Chaosheng Dong, and Jia Liu. multi-objective/ ma learning framework induced by pareto stationarity. Tn International Conference on Machine Learning, pp- 15895-15907. PMT.R, 2022.
15

---

Published in Transactions on Machine Learning Research (03/2026)
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in oplimizalion. Wiley-Interscience, 1983.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Perey Liang. networks. In International Conference on Learning Representations, 2020.
Distributionally robust neural
David Schaffer. Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the first International Conference on Genetic Algorithms and Their Applications, pp. 93 100. Psychology Press, 2014.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances in Neural Information Processing Systems, 31, 2018.
David A Van Veldhuizen and Gary B Lamont. Multiobjective evolutionary algorithm test suites. In Proceedings of the 1999 ACM symposium Applied compuling, pp. 351-3511 1999.
Zheng Wang, Xiaoliang Fan, Jianzhong Qi, Chenglu Wen, Cheng Wang, and Rongshan Yu. Federated learning with fair averaging. arXiv preprint 1xX4:2204,,14987, 2021.
Yutong Xie, Chence Shi, Hao Zhou, Yuwei Yang, Weinan Zhang, Yong Yu, and Lei Li. Mars: Markov molecular sampling for multi-objective drug discovery. In International Conference on Learning Representations, 2021.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsca Finn. Gradient surgery for multi-lask learning. Advances in Neural Information Processing Systems, 33:5824 5836, 2020.
Guojum Zhang, Saber Malekmohanmmadi, Xi Chen, and Yaoliang Yu. Proportional fairness in federated learning. arXiv preprint arXiv:220e.0166) 2022.
Qingfu Zhang and Hui Li. MOEA/D /D: multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(()::122777 731, 2007.
Xiaoyuan Zhang, Liang Zhao, Yingying Yu, Xi Lin, Yifan Chen, Han Zhao, and Qingfu Zhang. Libmoon: A gradient-based multiobjective optimization library in pytorch. Advances in Neural Information Processing Systems, 2024.
Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence of stochastic multi-objective gradient manipulation and beyond. Advances in Neural Information Processing Systems, 35:38103- 1038810333815,, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
16

---

Published in Transactions on Machine Learning Research (03/2026)
A Proofs
A.1 Theorem 3.2: the corresponding expectation bound and proofs
Theorem A.1 (Expectation bound for Theorem 3.2 Suppose Assumption 3. holds. With the same choices of to, x,, n1o, and y in Theorem 3.2 both Algorithms and converges as:
20DaCoLL MOT
CAU2
E TCH(@; m)
min TCH(O;w) S
oee
PXT
where expectation is taken on the stochastic gradients, and all notations are the same as Theorem 3.2
We now prove both Theorems 3.2 and A.1 which are based on several lemmas. We first establish the key lemma that fits the proof for 0, output by our adaptive online-to-batch conversion scheme, into the same analysis framework for 0, output by the traditional conversion that uses uniform averaging. Recall that C(O, X; w) = -i d (w)])(0))
7 O(T) is the output of Algorithm Lemma A.2. Suppose Assumption 3.1 holds and Ô Eorne
iterates { and {T Then, for any X, w Am:
1 T
L( A:w) S Σ ((:)) (::)).
(10)
Proof. First, by Assumption 3.1 f:(0) is convex in 0, and hence so is C(O, w). By convexity,
1 7 Σ 7-((0()) w).
C(O,A:w) S
0CCiP
Now, to prove suffices to prove:
1 T
Σ L,0
Σ ((, T
1
(11)
In fact, this inequality naturally stems from how } are constructed through weight re-allocation, as stated in the properties of 0. To see this, we first specify some notations that describe the re-allocation:
Suppose when Algorithm 2 finishes, for each (()) & P, its unit weight is re-allocated among elements in Pt C P, with cach ((=) E P. recciving weight Ber, such that Eottep 3tr = 1.
On the other way round, for each g(+) P, its weight Tr. apart from its own unit weight, inherited from S, C P such that 1 Eomes, Bir %
In each step, the weights of some suboptimal iterates are transferred to existing iterates that dominate them. By the transitivity of Pareto dominance, when the algorithm finishes, for any g(t), & P and 0(+) E Pt, we have ((r) (1), Therefore, f((((T)) < f(()()) for all E (m], and conscquently, for any X, w E Am, we have:
(( A: A: < L(0(1) A)
With this inequality, we have for each term on the RHS of 11 where (1)) & P:
(( N:w)
Σ (l((
A;
(:: Σ 3 = 1)
0i-)
Σ
0
17

---

Published in Transactions on Machine Learning Research (03/2026)
Finally, prove 11 by:
T x RHS =
Σ C(O x: + Σ )xw)
O
Σ C(O x: + Σ
Ber Ber (a0((()),))))) ,A:))
0 BW EP D
Σ
C(O()) \: + Σ
Σ
Ber ((0 ,::))
=
OMEP diGES,
E
BIT L(O ,X:
BEPE
ES0
Σ
((
A: (: T x LHS,
0TDE
which proves
10 and hence the lemma.
Lemma A.2 provides an inequality that allows us to continue the proof for θ the same way as 0, which follows the standard analysis of minimax optimization problem. Before that, we refer to some established results. Lemma A.3 (Properties of Bregman divergence, Chen & Teboulle (1993)) Given a distance generating function X R that p-strongly convex w.r.t. a norm -I X and continuously differentiable on int X, the Bregman divergence By X int induced by vo is defined
(x: = (xx vby) - (V
Moreover, Bg has the following properties:
Non-negativity and converity: By 2 0 and is conver in the first argument. Lower bound: For any two points x E and y E int X,
(x(x; Z 1 x y|12.
Three-point identity: For any three points x, y E int X and z E X,
Bz (z; B& (x:y) (V V (x), z).
Schwarz inequality for dual norms, Boyd & Vandenberghe (2004)). Suppose || 1|x is the dual norm of norm ||- IR defined ||x||+ == max (x, Then, for any x.y X, by definition, y.lly!
Lemma A.4 (Canchy-Schwarz
y) S ||x||-|||||-
Lemma A.5 (Azuma Hoeffding inequality on martingales, Azuma 1967 ). A discrele-time stochastic process (X1, X2, Xs....) is martingale w.r.t. a fittatton (H1, H2, Hz....) if at any time t, E. [[X,]] < oc and E [Xe H1,... H--1] X,-I. Suppose a martingale satisfies that [X, X.-II S a almost surely, then, for all positive integers T and all positive reals e,
P(X Xo 2)) S exp(
Sexp(
2 2 o7
Based on Lemmas A.3 and A.4
prove another key lemma:
Lemma A.6 (Restated, Beck & Teboulle (2003)). Given arbilrary sequence (C()).... (()),, and sequence (1(1) .......,. ((()) of the same dimension that is defined as:
(++)) arg arrgmin (t vv (0) + 7he NEV
B (z)
(12)
D ((+) arg max (5()) -m(t)> 1
BB (u; (()).
(13)
DEV
n
18

---

Published in Transactions on Machine Learning Research (03/2026)
where The is constant step size, By is the Bregman divergence induced by th V I. and thv is pu- conver w.r.l. the norm || Ilu. Then, for any V,
T
E 10) v(t) -2) 1
Be (uu; (1) +
n2
(0
(14)
1/2
2414
t=1
r
or respectively, Σ (5 u - =10)) - T/u
Bur (re; (1) + 1lu
11 (0
(15)
2/12
1=1
where || || is the dual norm of lll..
Proof. Consider single term the LHS of 14
(5(0) p(0) u² = (c(0) + (ei(t((ttt
1 (xlll))))) (((t1) - u) (term A)
The
The
- [v)(((l))
1 VVrllelttt) ((+1)) - u) (Lerm B)
The
T/2
+ (1(0), vll) -((t1)) (term C).
(16)
We bound terms A and B + C, respectively. First, observe rule 12 the entire function to be minimized on the RHS is convex w.r.t. v. Then, by the optimality condition for (++1) on this convex function, we have:
(Ve (16(), v- ((0))
B (v: LeuI,, u - v(tt)))
+ The
vo)((())) (vl((()))) = (((( 1
-
w((t))) 20,
Yu E
n
T/
Hence, term A < 0. Next, apply the three-point identity in Lemma A.3 to term B:
B
- (V)) - (v((t(()))) ((+1) u)
T/e
1
(u: - B (u: B (w((+))); :(())
(17)
nh
Then, we have for term C:
1
(()) v(0) ((0)) vltt1))
x 1
(100 - (((1))) (by Lemma A.4
n/
1
- 50 + He (1ll0) - v0t2)
<
(18)
Jl 2/1n
2
Now, adding
17 and
18
B C+C= The
1 (
Ber (2; - Bus (u;x((++)) -B (2(++1) (0))
(1) 12, + He
|| (1+1)
+ 24h
2
<
1
B Bw - (u, (1+1))
+ ||5 (1,00 12..) (by Lemma A.3
n
7/u
2/11
(u; B (uu; (((1)))))))
+
nu
11,
(19)
T
2/4r
19

---

Published in Transactions on Machine Learning Research (03/2026)
Therefore, given term A I 0 and 19
have from 16
(00 u = A (B <
1
Bee (w; (w: (lt)) - Bo (w; vltttt)
+ T
|| (0.0
7/u
2/1r
Finally, by summing up both sides from t to T, we have
T
Σ (5 (()))0()) ((0) - -u) = nlu
(Bu Bui (w 2 (T+2))
+
Σ
10
24 t=1
Bed (u; (1)) f/u
T
10 (by non-negativity of B
2p
which proves (1). The maximization case in Equation 15) can be proved by the same procedure utilizing
the concavity of the function to be maximized in rule 13
Now, we ready to prove Theorems 3.2 and A.1
Proof of Theorems 3.2 and A.1 Before starting the derivation, we obtain some bounds on the norm of gradients that will be used later. Directly implied by the assumptions, we have:
VoL = Σ (())lll - (V)ll) S L,
(20)
VAC(O, = ||w f(0)ll | S.
(21)
The same upper bounds also hold for stochastic gradients. Now begin derivation. First, rewrite the LHS of 7 with C(O, w))
TCH(O: w) min TCH(O; w) max C(O, (( min max C(,, A; w)) xE
OEE
XEAm
Given that C(O, A; w) convex in O and linear X, we have:
max L(O, A; w) min max L(O,A:w) dEAm
AEAM
max C(O, A: Aw) max min C(O, A; w) (Von Neumann's theorem) XEDm
ΛE
L(O, w) min C(O, A;
max
XEDm
= _( X X w) - -((0" >:
(22)
where X = arg max L(O, w), 0" = arg min L( X; w), and X = + E A AEA..
Next, by L(O, ); w)'s convexity in 0, we have for i being 0 and respectively:
T
C(0.\':w) <
(()
X;w),,
(23)
T
[ Xi w)
1 Σ +L(((11 w: T
Σ (( x") T
1
(24)
where the second incquality in 14 is exactly Lemma A.2 With the same RHS in and 24 we are able
to continue the proof for both solutions output by the traditional uniform averaging conversion and the new adaptive conversion. Next, by L(O, X; w)'s linearity in X, we have:
T
C( λ:w)
Σ C(O ww) [=1
(25)
20

---

Published in Transactions on Machine Learning Research (03/2026)
With 23
24
and 25
we continue from
22
T
T
[( x w) - L( A: w)
C(
L ;(0" :w)
T
T 1=1
t=1
T
[(0()) x - - (0) :))
T
term
+ C(0 w) L(0", ((0) ((1)
w)
(26)
term B
Now, we bound A and B by linearity and convexity, respectively:
A = C(e()) w) (()(t) A (1) w) = (VxC()()) A 10 w). X² w) -1))
B C( (1) :)) C(0", A w) V 1 w), 07)
We can then continue from 26
1 T
(A+B B) < (V 110);), (VAC(O(),A())))) A + (Vo((0 ,A00
w)) 0()) (o0(0())(()
-00
Σ (5xC(0()
(term D1)
(,, - (x2( 10) X 200) (term E1)
+ Σ (5o (0()0)((00,)))))) w): 0(1) 0*) (term D2)
(oL( A(; 60(( 20) w), 0() -0)) (term E2).
(27)
This is the last reduction on the upper bound. After bounding the above four terms separately, we will be able to arrive at the inequalities in the theorem. All of them can be solved by invoking Lemma A.6 For D1 and D2, it is direct application. For E1 and E2, need an additional construction step.
Bounding D1. Now, for D1, recall the update rule for A:
(++1)_ arg max ( A w) A) 1 Bux (2)) AEA
By Lemma A.6 substituting ((0) = S(((t A()); w), e1 = 1 and = X3, we have:
T D1
Σ (()(( w), 1 1())
T
Bux (1))
+ JA
Σ (0x((
7A
2μ1
11x TCAU2
Dx +
(28)
7/
2pa
where yx and || || and are the constant and norm on which the strong convexity of v/> is defined, and || II*,, is the dual norm of ||
[lx. The upper bound of the norm stems from (21) at the beginning of the proof, and Cx, as well Dx constants depending the specifie choice of v/x
21

---

Published in Transactions on Machine Learning Research (03/2026)
Bounding D2. Similarly, for D2, recall the update rule for O:
o g(++)) = arg min (ōgL(0))) (4) w). ;)) 0) + - Bo (0; )
Ag
110
By Lemma
A.6. substituting ((0) = ( 1(); w), wit) = O(0) and u 0", we have:
D2- (ōo (() ( ww 00 -0)
1
vo (0; 001) +
7
( (
110
2010
1
+ Ma TCoL?.
< - Do
(29)
110
2n
Bounding E1. Next, for F1, the first argument of the inner product no longer matches the update rule for A and thus Lemma A.6 cannot be directly applied. Instead, we construct a sequence (x such that
=
w) x (+1) arg max " (x((((() ( B (x:
XEA..
1/a
Invoke Lemma A.6 on this sequence: substituting ((0) VAC(O() A() - -)x(((()) (CC( :()):)), 211) = =x(),
and u = A3, we have:
VxC(0(1) TxC:0(0,\)::)>>>>> -
- -x
S Bu (1) +
Σ |V w) 5x(( ,1(0; w)
11x
2/1x
T
< - B (A: (0)
1A
Σ
(1V2 w)lx, + ( , :10:w)]1x.) 2
2px
1=1
1
a TACAU3.
S
Dx +
(30)
7
2
Then, we have for E1:
T
E1 (V)( \0); - -22(0(() -,,C(0(),\);:,)) w' -x11
Σ
t=1
T +
(VL(( ,0; - SA 100 ()
- -((),,
(31)
where the first term is bounded by 30 Different ways to deal with the second term result in the expectation bound and the high-probability bound, respectively. First, we have by the total law of expectation:
E
( w): (xC( ((:)), (00)
T
E
V VV \( - 52 A0) - (10) |m.... 7-1
T
Σ
E
(x(1) 10, E VAC(O()) (0,000 w) 6x 7 771 //...,,,........................
(32)
Σ E (x (0) -100 _00000) .,) =0.
(33)
22

---

Published in Transactions on Machine Learning Research (03/2026)
where {me) are the random batch sampled in the past to compute stochastic gradient. Here, 322 is based the fact that both (²) and X are deterministic given 8x (xL(0(111) all deterministic given up to the (t - 1)-th random batch. The next equality (33) is based on the fact that
0(--1), and A (T which are
the stochastic gradient is an unbiased estimator of the true gradient.
Next, the key observation to obtain the high-probability bound is that X, = (V 8xC(0lT), ( w). (T) { is a martingale w.r.t. filtration {me. We can check this by definition:
( (()) - -1) - - <0
E ||el =E
E [
71:
w). (1) (()) .7......97. 70-1 7- E (V)C(((t) A :)) Sx
+ E [ m....., 7-
=0 - (same argument as
32 and 33
X
We can now bound the second term by the Azuma- Hoeff-ig inequality in Lemma A.5 Cr from:
We have the constant.
XX X = (V) A :w) 6x A( w), x), (1)) (())
- ( 10) :w) - Sxc(O ,1'); ; w)
(1
(34)
( (0); w)ll + 11 A w)ll ;
(1xx + (1A%))
$ 20 x2 = 4U,
where 34 is based on Lemma have for any positive reals E:
A.4 and that || Io is the dual norm of || ||. Then, given that Xo = 0, we
T
- - x,,, 211) se)
P(X, =
Σ V C((())
2 1 - exp( 32TU2
Let expl (PPU2) have 0 0<7< < and == 4U / 2T Therefore, we have
T Σ
()L(())) 10); w) Sx w), 100) s 4U /2Tlo8 _ - 2 1 -7y
(35)
Combining 330
31
33
and
35
we obtain the two types bounds for E1:
Dx +
E EI S
+ 0,
(36)
1
1
and with probability at least 1 - 7, 0 < 1:
Dx
T
1 7
E1
+ 4U
2T 2T log
(37)
7/X
Bounding E2. We simply go through a similar process. We explicitly present the steps for completeness.
First, construct sequence {u(0) such that
(1 (11
(0:w) 1 (++1) arg min (Vo X
:) w) )) (1) w), v) + 1
Buo (vr; ()()))
n1
23

---

Published in Transactions on Machine Learning Research (03/2026)
By Lemma A.6
we have
T
Σ VoC(0 ( w) 60L(0 ;10) w1, ((0) -0")
1
c (0'; (())
110
VoL(0()) (0000())000))))))))))))))))))))) ,(0 - -00((0)) ;
110
2p0
1=1
1
y (0" ((1))
110
(VVo ;) + ( A w)lo..)) )²
110
2110
Do +
11
T.C.
(38)
110
Then, we have for E2:
E2
Σ
V (( ,'0)w) - (,0" (10)
1=1
+
(oL(O \ w) - A w), ww) 2 -0))
0¹).
where the second term is bounded by
38 For the first term, we have:
E
V VoC(O A w) SoL(0 A w))
w), 000) - r10))
E
V VeL( 110 - A()) 0(0) w(0)) .7....,, 7h-1
T
Σ
E
v00 E VoL(O A(0) 6 A())w) ,o((0())\)))) ......,, 7-11>> //......7-111 [2(0
(39)
Σ E (010 w0) 0,000. 0.
(40)
where 1
33
is based the fact that both (()) and ()()) deterministic given )0 (t-))) w)
w ④ (f(()))) ((t-1), and (t-1), which are all deterministic given up to the (t - 1)-th random batch. And (40) is still based on the fact that the stochastic gradient is an unbiased estimator of the true
gradient. With the same argument for (39 and (40), one can check that Y, = (Var(Vo ) w)
(0(() (T); w), 0(F) - ((t) a martingale w.r.t. filtration {nc), and we have
|Y Y (VoL( (1)) w) S0C(0 A1O; w),
w), 000 (())
< VOL(O()) > 6o((0 A(0 w))o (0 - 0000
(IVoL( X ;10 w) ())a 10)
((0) w))lo)) (1000)
(0)0
2L 2dRo 4dRoL,
where the last inequality is based on |00|| S dl S dRo and the same for wt)) Then, by the Azuma- Hoeffding inequality, we have for 0 < 7 < 1:
P Σ EvooCoo x() X() (0(( X (w; 0() wli)) s 4dRoly 2T log ?
1 1-7.
Therefore, for E2, we have the two types of bounds as follows:
Do
2no TCo T,2
E E2] <
+ 0,
(41)
170
μo
24

---

Published in Transactions on Machine Learning Research (03/2026)
and with probability at least 1 - - < < <
1:
Do
2no TC
1
E2 -
+ AdRoLy
2o log
(42)
μ
Finalize. At last, we are able to assemble the bounds for terms D1, D2, E1, and E2 to bound
27 and thus
bound the convergence error. For the expectation bound, with 28 for D1, (29 for D2, for E2, we have
36 for E1 and 41
2Da
TC
2Dx
T
E
TCH(O: w)
min OC w) DE
T
110
2p
2/1
from D2 and E2
from DI and E1
When
Do 5T
and
7
Aux 5TCxU2,
we further have:
CoDo NeT
20DACAU2
E TCH(O: w)
min TCH(O;w) S DEB
which proves the expectation bound in Theorem A. For the bighprrobbillity bound, with 28 for D1, 29 for D2, 37 for E1, and 42 for E2, have with probability at least 7, < <:
2Do 77
TnoTCoL2
3Dx
TCxTUU
TCH(Ô: w) min TCH(O; w) S dee
+
+
2110
211x
T
Rd 2T 2T
+ 4U
2T log
from E2
from El
With the same optimal step sizes, we have with probability at least - 0 < <<7<<>>1 <:
20D&CoL2 No
20D
+4(dRoL + UV/ / log
1
(CH w) min TCH(O::) <
PAT
which completes the proof of Theorem 3.2
A.2 Corollaries 3.4 and 3.5 expectation bounds, proofs, and analysis on the p-norm instance
Corollary A.7 (Expectation bound for Corollary 3.4 Suppose Assumplion 3. holds. Using PGD for both O and X, with the some optimal step sizes ne and 1l as in Corollary 3.4 both Algorithms and converge as:
min TCH w) S 2/11dRoo 2/100m 8E8
TCH(O::) w)
(43)
/T
Corollary A.8 (Expectation bound for Corollary 3.5 EG for X, with the same optimal step sizes no and ny as in Corollory 3.5. both Algorithms and converge as:
Suppose Assumption
3.1 holds. Using PGD for 0 and
min TCH(O, w) 2v10dRoL + 2V5vlogmu d0
E [C)((::)
(44)
VT
VT
Proof of Corollaries 3.4 3.8 A.7 and A.8 Given the general bounds in Theorems 3.2 and A.1 the four corollaries can be casily derived by instantiating the constants associated with the specific choices of vb, namely na: μx, Do, Dx, Co, and Cx. Recall their meanings follows:
25

---

Published in Transactions on Machine Learning Research (03/2026)
ve is po-strongly convex w.r.t. norm || lll.. vix is px-strongly convex w.r.t. norm 1lx
By (00; & Do- BØ (A: & Dx-
||oo[ ; w) S Coli, |[ ; w)lk. S C2U2, with the same inequalities for the corresponding stochastic gradients, where || || denotes the dual norm.
We now discuss the cases for Projected Gradient Descent (PGD) and Exponentiated Gradient (EG), respec- tively, resulting in the corresponding terms in the four theorems. In the following, we use x to denote either or À if some property holds for both them and dim(x) for the dimension of x.
Projected Gradient Descent.
The 1-2 norm induced (xx) 2112|12 is 1-strongly convex w.r.t. || 1l2. Hence, Px
For Bx,(x"; x(!)), we have:
1 xx 11 - (|xx 112 1|x((1
(x (2)
Recall that [0 I Ro, hence, for O Rd we have (110 ||2 12) S (2 =2dRg. For
Am; we have (112*1 + || s (I + | 11 S (2) 2. Hence, Do 2d and
Dx 2.
For Cx; since the dual norm of 1-2 norm is still 1-2 norm, have for any gradient Vx,
V V (Vdim(x)
dim(x) Vxl
Given that V loc < L, VAllo S U, have Vo S dL?, / mU? The same inequalities hold for stochastic gradients. Hence, Co = d and Cx
Therefore, when applying PGD to 0, by substituting the above constants into expressions in Theorem 3.2 we
have the optimal step size no
Apo Do STC
/
/111224g 5TAT2
v
5TI2, and the first term in (8) 443
&R
99
and
44
10 HOT
20 2dR d. 12
2
1.T
VT
Similarly, when applying PGD to X, we have the optimal step size
Du STCAU
4.1.2
m7
57
and the sccond term in and 43
20D2CAU2
20
2
U2
2/100mu
MXT
1.T
VT
Exponentiated Gradient (for Am only).
The negative entropy ((A) = Σm X log A is 1-strongly convex w.r.t. || 1h2 Hence, μs 1.
For B (A+; with initialization ( mm
have:
m.
Bo, (A:;00)
Σ log
x log \i
1og
+ log m log
Hence, Dx log m.
For Cx, since the dual norm of [-1 norm is the infinity norm, we have for any gradient Vx, The same holds for the &x. Hence, CA 1.
|| x U2,
26

---

Published in Transactions on Machine Learning Research (03/2026)
Therefore, when applying EG to X, we have the optimal step size 1a
D STOxU²
Alog STUF; and the second
term in 9 and (44)
20D2CAU2
20 log m 1. 1.U
2/5
PXT
1.T
VT
Till now, the proofs for Corollaries
3.4
and A.8 are completed.
We also considered the p-norm algorithm, another mirror descent instance induced by the l-p norm. We analyzed its case and saw that it is no better than PGD or EG, as derived below.
The L-p norm induced (xx) = 1 p is (p- 1)-strongly convex w.r.t. || -lpp for < p S 2. Hence,
Nx = p 1. For (xx by definition, Bax (x) deal with the gradient of the t-p norm, consider the gradient w.r.t. the i-th element of x, i.e, Z1:
1\2 || -
1 - (V (Vx0n (x(0) I1. x - x To
2/v
2/0-1
V |xx1
1 2 Vz.
Σ
12
Σ
lzy1
10110-22. 2x.
(45)
2
2
Σッ 11 (zz)1) 2/p-1
Then, we have V x) =
>/ |r5|" = ||>|| and thus
Bax (xxxx(1))
1
||x1 13
1x 1x - (V x(1
| [| x*) + (V x 2 |1x00) x0))
2
2
2 |
12
xx 1/ - (
x 2 | 2 x*) + 1|
| 2
|xx (1) 1/ (V x | 2 x')
(46)
2
Next, we upper bound KV
1 ||x(1) 1 x²) By Lemma A.4 we have I( 1 11 x')| s
x
IIV x 1 |211/1/]" Ilps where
p + 4
= 1, i.e. q + pq. Utilizing Equation 45 we have
2/p-1
1/a
d
| x
1xx 1121/ =
Σ
|zy|
P
Σ
2/p-1
1-1/p
Σ
|20 1
Σ |2s|""
1/p
Σ |2, P
= =|xx011pp- 1|p
Therefore, we have (V x [
J3. x*)
< | 11 |x max( || (12).
Finally, continuing from Equation
46
we have
B (x": x ())
1
x
_ >|x 112 + max([|x*1]] 113 11x)) = 2 max ||x|
2
For 0, we have 2 max |10133 < 2 (dR))²
: = 2d R2.
For X, we have 2 max |사| < 2 max |AIR < 2.
Hence, Dg = 2d R3 and D> = 2.
For Cx. since the dual norm of ||
||p is || 11g s.t. 1 + 1 = 1. we have for any gradient Vx,
V = V 12 < (dim(x)
/ 1 : s dim(x) (
Hence, Co = d and CA m
27

---

Published in Transactions on Machine Learning Research (03/2026)
Therefore, using p-norm, the bounds for 0 and À respectively are:
2v R010RRLL
2v 100mm v - 1)T
and
(p 1)VT
The bound for 0 achieves the minimum value when == 2 (recall that 1 < < 2), in which case p-norm reduces to Projected Gradient Descent. For X, we can further upper bound the term by considering:
m J/ m 44 mö /9.
whose minimum value is /2e log m, obtained when q = 2 2og m. Substituting back, the optimal bound for X 1v 1//5 log mt VT which is no better than Exponentiated Gradient.
A.3 Comparison with previous results and discussion on sample complexity
In previous works adopting OMD-based methods with EG for À (Saaaa et al. 2020 He et al. 2024 the convergence rate is derived as Ommylogm// The additional m factor com compared to our bound in Corollary 3.5 is induced by their sampling one data point in each round. Recall that given the composite loss C( Ees (0) (the preference weight w omitted for simplicity), we want to build unbiased estimators for VxC(0, A) = (f. (m))) The sampling stralegy in these works is: (1) sample an objective index [m] uniformly, (2) sample one data point from the datasct of objective i, i.c., x ~ Di, and (3) construct the stochastic gradient 5xL(0, A):
(6x): mf) and (6x), 0. Vi
Here, we use da to denote 8x C(, A) for simplicity. The constant m in the non-zero entry is necessary for this stochastic gradient to be unbiased: for each entry j in 8x.
E (6x)g)
m -
x 0 x mEZDD, (0,
(0) (V
Due to the constant m, the upper bound of |o\||>o are amplified by a factor of m. This is equivalent to having U + mU in Corollaries 3.5 and A.8 and hence the additional m in these previous bounds. In contrast, our strategy samples from all objectives at each step and constructs (5x); = f((0; B,), where B, is the random batch sampled from the data of objective i. This stochastic gradient is unbiased without a coefficient of m, and thus the optimality.
Full sampling is adopted by most MOL methods, usually perform offline learning with pre-collected training set, and many gradient manipulation methods require full gradient information for conflict resolving. Therefore, our analysis provides more suitable convergence rate for OMD-basod methods for MOL.
Finally, while full sampling yields a tighter iteration complexity in the offline setting, we point out that in ouline/active/ haaiee//active/nttttout ccontinuus learning, where one desires lower sample complexity, there is no optimal strategy between the two sampling mothods. Instead, they offer different tradc-offs in the sample complexity bound:
R + m² log m + (12 m²) log
Single-objective ((1) sampling: O
2²
mR log + (mR + m) log
Full O(m) sampling: O
2
where is the optimization error and constants d, L, and are omitted. These sampling complexity bounds can be easily derived from the itcration complexity bounds and the number of samples drawn in each round. As shown, (1) sampling avoids multiplication between and RS, while ((m) sampling avoids the quadratic dependency in m.
28

---

Published in Transactions on Machine Learning Research (03/2026)
B Full experiment details and results
Our code is available at http:////ggthub..cc/muuuuuttiii
B.1 Synthetic experiments
Experiments are conducted using an open-source MOL library (Zhang al. 2024) with implemented synthetic problems and some methods. Uncovered methods are added following the corresponding official codes.
Hyperparameters and random seeds. All experiments run for 1000 epochs. Those of linear scalarization (LS),, vanilla Tchebychelf scalarization (TCH), PMTL, EPO, and FERERO use 7/0 0.01. All experiments of (Ada)OMD-TCH, STCH, ExcessMiL, MGDA, CR-MOGM, and Moco use he = 0.02. This is to ensure the same scale for updates, since there is an additional coefficient for the gradient term 0 from the dynamic weights, which is roughly of scale 0.5 given that the number of objectives is Nevertheless, we did not. observe significant differences when using either rate on the same method.
In terms of method-specific hyperparameters, all experiments of (Ada)OMD-TOQ TCH, either using PGD EG for X, well as ExcessMTL, use П = 1.0. For STCH, use μ 0.01. The momentum parameter a in CR-MOGM is computed as suggested in Corollary 1 of the original work. For Moco, the regularization constant is set as 0.01 and the step size for the dynamic weight, similar to 1J is set as 1.0. All results are averages over three random seeds, 0, 19, and 42.
Full results. Figures for all methods on all synthetic problems are presented in Figures 6 to (Ada)OMDgdd TCH stands for applying PGD to X, and "eg" for EG. Similar results as discussed in the main body are observed across different problems. Additionally, compared to the PGD instance, the EG ones sometimes less effective in recovering the exact PO solutions found by TCH. We also report hypervolume results in Table 10 where TCH achieves the best hypervolume, and AdaOMDgd-TCG ranks the second on five of the seven problems, complementing our findings in the figures.
(Ada)OMD-TCH as a middle ground between LS and TCH. To provide an intuitive illustration for this interpretation in Section 3.3, we apply OMDgd-TCH on VLMOP2 with different п)x- As shown in Figure 5 when f/x reduces near 0, the results resemble LS, and increasing it recovers the results of TCH.
B.2 Experiments on fair federated learning
Data settings. The detailed approach to simulate client data heterogeneity is follows:
Both datasets are equally and randomly split into 10 subsets for 10 clients. For MNIST, 7 subsets are not rotated, 2 subsets are rotated by 90 degrees, and subset is rotated by 180 degrees. For CIFARIO, 7 subsets are unchanged, and subsets are rotated by 180 degrees. For the 2-client preference-guides experiment, data are equally and randomly split into two subsets, each rotated by 0 and 90 degrees.
Rotation:
Partial Class with C = 2 or 5: Both datasets are first equally and randomly split into 10 subsets. For each client, C classes are randomly chosen, and the images in the corresponding subset of these classes are assigned to the elient.
LS
OMDgd-TCH
TCH
Pogan
Tagin
Nackl
0.2
02
172 0.001
11 0.1
1.0
10.0
Figure 5: An example of OMd-TTH lying between LS and TCH.
29

---

Published in Transactions on Machine Learning Research (03/2026)
Table 5: Method-specific hyperparameter values.
Best Value
Method
Hyperpazam
Atterapted Values
MNIST Rosation
MNIST Partial Class C=2
MNIST
CIFARIO
CIFARIO
CIFARIO
Class
Class Cw5
gFPL.
U.1. U.6, 1.0, 5.0. 10.0
0.1
0.1
8.1
0.1
0.1
0.1
PropFaic
M
2.0,
5.0
2.0
2.0
2.0
3.0
4.0
2.0
PoMMGDA+
0.05, 0.1, 0.5,
0.5
0.5
0.05
0.1
RxdFV
0.1, 0.2. 0.5
0.2
0.2
0.2
0.2
0.1
0.2
STCH(TERM)
0.01, 0.03, 0.1, 0.3,
1.0, 3.0, 10.0
0.01
0.01
0.01
0.01
0.00
0.03
0.
0.
0.3
1.0
1.0
0.1
0.03
0.001
OMDgL-TCH(AFL)
0.19%
0.001, 0.003, 0.01.
0.03
0.01
0.01
0.01
AdaOMDgd TCH
0.1%
0.03, 0.1, 0.3,
0.08
1.0
1.0
0.03
0.003
0.3
OMDeg-TCh
0.1gs
0.3
0.3
0.1
1.0
0.03
0.1
AdaOMDeg TCH
0.1gg
Hyperparameters and random seeds. For all MNIST experiments, the hidden layer of the fully connected neural network is of size h 200. We go through T = 300 communication rounds, with each client executing == 10 epochs of full-batch local updates in each round. For all CIFAR10 experiments, we train the ResNet 18 model for T = 45 communication rounds, with each client doing T = epoch of local update with a batch size of 100 in each round.
All methods' step sizes for model parameters are set as ne = 0.1. For other method-specific hyperparameters, we try values reported in their original paper and select the best ones that yield the smallest worst client training loss, in order to match ones listed in Table Here, 1Aλ for (Ada)OMD-TCH is reported as 0.1m,, which is what used in practical codes. This is because under a balanced tradeofT, w; = 1/m 0.1 for all objeclives/client and can be integrated into For the 2-client preference-guidee experiment, we directly use the best hyperparameter of the corresponding mothod in the CIFAR10 Rotation sctting.
methods for fair comparison. The attempted values and the best
All evaluation results are averaged over 10 random seeds: 0, 25, 37, 42, 53, 81, 119, 1010, 1201, 2003.
Machines and training time. We Linux machine with AMD EPYC 7352 24-Core Processors and eight NVIDIA RTX A6000 GPUs. Table 6 reports the training time per FL round of different methods averaged over 10 seeds. Comparing AdaOMD-TCH and OMD-TCH, AdaFxxessMMTI and ExcessMTT,, we see that the adaptive conversion docs not imposc any significant overhead. As discussed in Section 3.2 this is mainly because the small size of p(() in practice. Additionally since OMD-TCH requires strictly ly no more computation than ExcessMTL, the discrepancy between them is likely due to scheduling deviation of the servers. Therefore, most methods with small differences can be considered similar training time.
Table 6: Training time per round.
MNIST
CIFAR10
Method
Rotation
Partial Class C=2
Partial Class C=5
Rotation
Partial Class C=2
Partial Class C=5
(S(edAAvg)
0.338
0.206
0.236
9.748
2.142
6.168
qFFL.
0.591
0.181
0.482
7.823
2.123
5.450
PropFair
0.733
0.559
0.620
8.033
2,059
5.217
FeIMGDA+
1.360
0.535
0.276
7.920
2,118
3.272
FedFV
0.311
0.233
0.607
7.741
2.438
5.937
TCI
0.329
0.227
26266
8.191
1.480
3.170
STCH(TERM)
0.590
0.546
0.441
7.939
2.537
5.118
EPO
0.377
0.138
0.180
8.656
1.738
4.241
FERERO
0.462
0.227
2,000
4.492
EXCesMTIL
0.344
0.197
8.576
1.562
4.327
AdaEXcessMTL
0.1112
0.142
0.175
7,881
1.389
4.239
OMDDg-TCH(AFL)
0.365
0.206
0.266
8.042
2.420
5.273
AlaOMDgI-TCC
0.591
0.226
0.278
7.900
3,022
5.527
TCD
0.348
0.209
0.270
8.313
2,3/2
6.017
AdaOMDeg TCH
0.564
0.460
0.569
7.995
2,431
5.508
30

---

Published in Transactions on Machine Learning Research (03/2026)
Table Comparison between LS, AdaLS, TCH, AdaTCH, and AdaOMDgd-TCH.
(a) Average accuracy 1
(b) Accuracy parity +
Method
LS
AdalS
TCH
AdsTCH
AdsOMD-TCH
Meilud
LS
AdiLL
TCH
AdaTCH
AdsOMD-TTC
Rotation
66.269
66.169
62.356
65.257
66.218
Rotation
6.012
6.283
4.727
1.920
3.502
Partial Class C
38.925
38 09.095
20.935
31.150
36.765
Partial Class C 2
21.801
28,658
27.199
16.345 L
18:422
Portial Class
5
53.626
55.540
36.242
47.792
53.422
Partaal Class C 5
8.610
8.565
16.141
7.804
6.823
Full results. Figure includes the training and test curves of the maximum client loss for LS, TCH, and AddaOMMDTTCH, complementing Figure 3 in the main lext. Figure 10 includes the scalter plots of average test accuracy and test accuracy parity, also complementing Figure 8 Figure 11
visualizes the benchmark
across all methods, and Table I1 lists the corresponding numerical results.
Design components. The motivations for the three components of AdaOMD-TCH are as follows:
Tchebycheff scalarization ensures (1) recovering the non-convex PF and (2) locating solutions with specific tradc-offs (Theorem 2.4), which are important for preferenco-guided MOL and many methods fail to satisfy, such as LS and gradient manipulation methods without additional design.
OMD updates smooth out the one-hot update of TCH to avoid training oscillation and stagnation.
The adaptive conversion considers only the trajectory PO iterates to improve solution optimality over traditional conversion while retaining the theoretical convergence guarantecs.
Although the adaptive conversion designed for online algorithms such as OMD and thus does not apply, principle, to LS and TCH, we still investigate the performance of AdaLS and AdaTCH further justify the use of Tchebycheff scalarization and OMD updates.
Table 7 presents the comparison on CIFAR over 10 seeds. In terms of accuracy, the adaptive conversion does not help for LS. AdaTCH improves over TCH, but is still outperformed by AdaOMD-TCH by large amount, not addressing the unstable and slow one-hot update as effectively as OMD. Nevertheless, this improvement indicates that our proposed adaptive scheme is more broadly applicable.
In terms of fairness, AdaLS is hardly improved and is still outperformed by most TCH-based methods. This is because the adaptive conversion does not change the property of LS, i.e., LS does not aim for equal (weighted) losses like TCH. The fairness of AdaTCH is improved, but its key drawback is still the suboptimal accuracy.
In summary, AdaTCH < AdaOMD-TCH in average accuracy demonstrates the necessity of applying OMD updates, and AdaLS > most TCH methods in accuracy parity further confirms the advantage of Tchebychelf scalarization. Applying the adaptive conversion to a broader range of methods, such as TCH, may be an interesting dircction, which we leave for future studics.
Evaluation data for iterate comparison. To demonstrate the robustness of the adaptive conversion against different evaluation data, conduct an ablation the CIFAR rotation setting, where the objective values, i.e,, client losses, for dominance comparison use:
mini-batch estimates (mini): This corresponds to the current results in Table 11d
full training loss (full): Each client is evaluated on its full local training data.
held-out validation estimates (val): Since CIFAR10 does not feature validation set, we split the test set in half, using one for validation and the other for testing.
Table 8: Ablation on different evaluation data for iterate comparison.
Ada full
AdaOMDeg:TCC
Method
mini
val
mini
full
val
Avg. Accuracy
66.218
66.061
66.386
65.885
65.913
66.260
Agnostic Loss |
1.148
1.128
1.185
1.156
1.130
1.171
Accuracy Parity
3.592
3.503
4.022
3.688
3.372
3.819
31

---

Published in Transactions on Machine Learning Research (03/2026)
Table 9: Compatibility of (Ada)OMD-TCH with using objective ratios for weight updates.
Method
LS
TCH
STCH
OMDgd-TCH TdaOMDgd-TCH OMDeg-TCH
AdaOMDeg-TCH
Agnostic Ratio +
0.656
0.648
0.627
0.647
0.465
0.651
0.465
Ratio Parity $
0.087
0.066
0.068
0.024
0.043
0.029
0.042
We directly use the reported hyperparameters and seeds. As shown in Table S comparing the full and mini columns, one sees that using full training loss indeed improves agnostic loss, which is the goal of Tehebycheff scalarization, and accuracy parity. Using the validation set slightly worsens the two but increases the average accuracy. Most importantly, switching to either evaluation barely changes the relative performance of AdaOMD-TCH compared to other methods, e.g., they still achieve the best agnostic loss. This validates that the adaptive conversion is robust against different dominance comparison data.
Objectives of different scales. One practical trick to resolve the bias induced by scale differences to, when updating the dynamic weights, replace f(((()) with the ratio f(((0)) E (0, I], where f(((()) is the initial value of the i-th objective. Thereby, the weight allocation process examines not the raw objectives, but how much each has improved, aiming for a preference-sperified degree of training across objectives. This trick has been adopted by previous works to normalize excess risks (He et al. 2024 Chen et al.) 2018
To demonstrate the compatibility of our methods with this trick, we apply to TCH, STCH, and (Ada)OMD- TCH on the CIFAR rotation setting. By using the ratios, we evaluate the agnostic ratio, ie., the worst test loss ratio across clients, and the ratio parity, i.c., the standard deviation of test loss ratios. We use the current hyperparameters and seeds. As shown in Table 9 the results are consistent with our current findings. Specifically, we still have (1) TCH is better than LS, (2) OMD-TCH is often better than TCH, and (3) AdaOMD-TCH greatly improves optimality over OMD-TCH, as reflected by the smaller agnostic ratio, i.., the performance of the least-trained objective, with a slight increase in ratio parity, which is still better than other methods. This demonstrates the compatibility of our methods with the ratio trick and, thus, potcntially with different scales of objectives.
32

---

Published in Transactions on Machine Learning Research (03/2026)
Table 10: Hypervolumes of different methods on synthetic problems.
Problen
VLMOP2
F1
F2
F3
F4
F5
F6
LS
0.012:00001
0.938220.065
10005=0.0055
0.967:2000188
10002000013
1,00
0.989=0.0035
TCH
0.295=+0.000
1.011+0.009
1.021=0.009
1.015=+0.003
1.024=0.0016
1.027=0.003
1.023=00.00
STCH
0.291++0.000
0.966-+00007
0.985+0.007
0.906--0.004
1.004+0.014
1.003+0.007
1.014-0.007
OMDgd-TCH
0.289++0.001
0.970=000007
0.990=0.003
0.950+00000
0.973++0.003
0,983=0.010
1.03=00004
Ad00MDgI-TCH
0.2921100000
0.992.10.008
1.008
0.97010.001
1.006.0.0013
1.01410.010
1.015.0.004
OMDeg- TCH
0.269-+0.006
0.960 00000
0.004
0.926+000024
0.942440.13
0.962-0.016
0.977
AdoOMDeg-TCH
0.270.10.006
0.981110.009
0.00
0.94410.021
0.979:10.015
0.964_0.026
0.990=0.014
ExceseTII.
0.119.10.011
0.931 10.022
0.025
0.98610.012
0.0005
0.983 0.001
0.016
EPO
0.283:0.000
0.968=00003
0.07
0.96620.003
0.95740.014
0.963200024
0,96200.020
FERERO
0.289110.000
1010110.008
1001100001
0.9831000015
0.996.10.009
10002-0.014
0.905
MGDA
0. 0.232=0.006
0.963=0.015
0.970=0.015
0.981=0.013
0.970=#0.011
0,956=0.018
0.991=0.010
CR-MOGM
0.231::00006
0.963220.115
0.971=0.014
0.982:0.013
0.970:200114
0.968=0.017
0.90
Moco
0.256:000011
0.956+0.023
0.977=0.014
0.979 021
0. 0.992+0.088
0.981=0.022 024
0.989=0.035
PMTL
0.208=00.028
0.86320.021
0.892=0.022
0.88
0.887#0.019
0.860=0.013
0.881=00011
Table 11: Numerical results of all methods
(a) MNIST Rotation
Miled
fer Imawy
18
STATOMOTIE
Aikuag Falo
Lanaai
L37766114
(b) MNIST Partial Class C=2
Meteed
RIGH
CHINN-TO
10
01
Agusts
Acauayy Pult
(c) MNIST Partial Class C=5
Apania Jos
TO BOWEIL
Smowa d:
E 22
N
LN B3
(d) CIFARIO Rotation
Aganta Lus
1 200LB0
LISGARIS
(c) CIFARIO Partial Class C=2
Agunta
2477 aricl
(1) CIFAR1O Partial Class C=5
Pieki
590
PSDARO
Alciiiia FOR
0Miing TOM
SadVUh B ICH
30 1755
(19081185
63:3
Agueti Low
54111538
T 1310112.00
S256L2A7S
420723.11
EA0111.20
50001110
7.966L1855
33

---

Published in Transactions on Machine Learning Research (03/2026)
LS
TCH
MGDA
CR-MOGM
Moco
VLMOP2
34
FT
628
15
668
628 10
F2
648
F3
F4
P5
F66
Figure 6: Full results of LS, TCH, and gradient manipulation methods.
34

---

Published in Transactions on Machine Learning Research (03/2026)
STCH
OMDgd-TCH AdaOMDgd-Ton -CH
OMDeg-TCC TCH
AdaOMDeg-Tee TCH
VLMOP2
14
122
P3
F4
P5
321
100 121
200
428
F6
331
221 CAR
103
121
424
100
Figure 7: Full results of STCH and TAHH)O
35

---

Published in Transactions on Machine Learning Research (03/2026)
EXCessMTL
PMTL
EPO
FERERO
PAUDON
VIMOP2
06
14
E1
800 021 c8
0n 100
580 <28
1.4
F3
P4
14.
R5
6
5
F6
Figure 8: Full results of ExccssMTL and preferenco-guided MOL methods.
36

---

Published in Transactions on Machine Learning Research (03/2026)
TD1
TCH
OMByy- (C-AAR) OMMllg TEN
DMEIa TO HAFO
celira AscONCzolO-
PRU SHT LAKE
MAJOMDDATCH
LSPPedtes
LSHiedRegl
TDI
TCH
NAV 120
ONDORTCHAAF) DMtiigg
deloot TOHAFD
OMByy- RC-AAF OMINNg TEH
BMbbeg
DVDOa TO HAFD
ASSOHEyAATC
Parib, Class_C-
30seods
LSHiedReg!
TCH
TCH
ONEGATCCHAF Dittie IOM
ONDg-TTCHAAL
OHCOA-TCHAA
Oriiing RCH
MYs SMT LAKE
No:
Round
30
120
CIRRR1 Rocation
CIRAR10 Ruzation
Lillediug)
LSFedlvg)
LilledRugi
TCM
TCH
MNO SMTT
AssONGgdTO:
Adkoii beg ICH
Asscrbie I0-
AdMiiN beg
Man
Mac
Sound
Round
Roand
CITAR1O Partil
xeed-0
CITAR10 Pettial 1owees
Litledreg)
TCM
Vee togen
Mar Noc 200.
ASSONDGOTO:
Liifsttegi
10e
TCM
AANOO ICH
ASscnDey in:
CHE
TONWAL
MiDON MIDN ICH
Raud
Raand
Rzurd
CITAROO Partial Claes C-w.cCCSSaaae Ctw.----SaSaa
xeed-0
CITMR10 Pettall
Dowess
LS(eddlog)
LSitediugi
TCHI
TOI
OXIDWITCHAMN
THI DNE
TOi TOIAA
ASsCMDrOTCH
AdUCHDeatTCh
1o
Tound
Round
Bead
Figure Training and test curves of the worst client loss.
37

---

Published in Transactions on Machine Learning Research (03/2026)
MNIST Rotation
MNIST Partial, Class C+2
MNIST Partial Class Partsal_Class_ C-5
Average Accuracy
Average Page Test Accuracy
50
Test
LS(Fedfug)
LSdFes/wgg
OMDAATTCHARR.
(MDgddTCH(AFL)
CMMDg--TC((AFL)
OMDoe TCH
OMDuggTCH
OMDeg-TCK TCH
AdAOMMDgATCH
AdaaMDgd-TTH
AdsOMDggSTCH
ACSOMDeg-TCH
AdaOMDeg
AdsOMDeg-TCI
625
0.5
Test Accuracy Parity
Test Accuracy Parity
Test Accuracy Parity
CIFAR10 Rotation
CIFAR10 Partial_ Class_C C=2
CIFARIO Partial CiaiillCClass_eee Class_Cm$
LS(Fed/wg)
TCH
GMIDgS-TCHIARL CMDeg Ada DMDgATCH
Average Test Accurary
LS(FedAwg)
20
TCH
Ada OMDggDHH
OMDgd TCHAAFL) OMDeg-TCH
Test
(0Fedfug)
AdwOMDgd-TCH
TCH
AdaOMDeg-TCH TCH
OMDee
AdacMDydTTCH
AGSOMDeg-TCH
10
20
22
24
25
23
20
30
32
24
16
6- Test Accuracy Parity
Test Accuracy Parity
6-
Test Accuracy Parity
Figure 10: Scatter plots of average accuracy and accuracy parity.
38

---

Published in Transactions on Machine Learning Research (03/2026)
MNIST Rotation
Accunsy Parter
BB
+
Aprentic
-9
grn.
fropha
RedPy
STORTIIR
(Pg
Brovviiyy
evr
frophan
FadPy
2011 STORTTIRS
Big
Frestto
Exeennity
Loinatgg
eift
frophan
Festy
BPG
FentRo
Breestff
MNIST Partial_Class C-2
Class
Agrantic
1
LSitetter
froutise
FinEeo
Loinestegy
aftt
frouitse
STOHNTIMN
YCH
Firseo
Loitestogy
off
fropitate
Feorr
nead costuan COsteLL
MNIST Partial Partial_Cless_Co Cless_C-5
Accmey Perty
12
Loptestoop
drf
Fadty
STEWITRRS
Eid rExDRo beceseri
Loptestop
orft
Fratecba
Feltv
STEWITRRS
beasurtt
Add aooyy--rocen PCu
AncHetii OrDoN Tor derostteprn TDM
Loyfesdopi
orft
Pergiise
Featecbee
Feeti
bxcesorry
saut-cor coscoooatt Olto Soyyh-oooo poreettr Cov ostoisa Toi
coscesting For
on
Buaaroy Parter
S
5
1
m
EPD
Lepredtago
orft
Fropiaa
Feltu
EPD
FEARPO becrstff
dstop AssrietyofCC stsctttippPii TEH
orrt Ferpraal
Feetaal
smoee Tottr
Diceeste11
CI Partial Class C=2
Aunozte
Letreddegg
Redl'
TCH
Freetto
(sireseegi
arf
STONTTRN))
TCH
EPG
Ercessmtt
Ausinttpptoo Tor Taa
Lsinedeogi
TCH
EnD Ercevtitt
ohtrrs Coreeet (o CaltneeTo YOu dercaatorryn Tia
CIFARIO Cittal_Claas_CCo Cm5
Acuurace Purtyr
Igronte
11
-1
LSitedeeg)
dff.
ICH
iPo
Eecosulft.
Loifeddegi
ICH
Asst Costicooootttt.
Lostedlogi
Reorv
ICH STONTERS))
mP
riteee
Aeat MTT
Ostrgs wortss/ottsli Smmoootris TCM
Figure 11: Boxplots of all methods on three metrics.
39


Reviews:
[{"review_id": "0GemSDlmt5", "reviewer": "Reviewer_QyVB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies preference-guided multi-objective optimization via Tchebycheff scalarization (TCH). It reformulates TCH as a min–max game over a simplex variable and solves it with the online mirror descent (OMD) method. The primary contribution is an adaptive online-to-batch conversion that outputs a weighted average of only the trajectory Pareto-optima, with weight redistribution from dominated iterates. The paper provides convex stochastic convergence bounds and conducts experiments on synthetic MOL and federated settings. The results demonstrate the effectiveness of the proposed method.\n\nOverall, the presentation is clean, and the idea of adaptive conversion is straightforward yet highly effective. But I have some concerns.\n\n1. Alg.2 requires the comparison among different $\\theta$ to determine the Pareto dominance. Ideally, the objective values should be evaluated with full data. But in practice, these values are estimated from minibatches. I would like some clarification on the implementation details. \n2. The main convergence theorem assumes convexity, but in practice the experiment settings are nonconvex. I would like to see further discussion on this gap, or some convergence analysis in a nonconvex setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The presentation of this paper is clean, and the theoretical and experimental results demonstrate the effectiveness of the proposed method.", "audience_yn": "Yes", "audience_explanation": "The convergence analysis here assumes convexity, and it is consistent with the compared baselines in Table 1. The proposed methods in this paper yield better convergence rates.", "requested_changes": "I would like to see the following adjustments:\n\n1. Ablation where dominance comparisons are conducted using (i) full training loss, (ii) a held-out validation estimate, and (iii) minibatch estimates. As mentioned before, there are some inconsistencies between the method and implementation. \n2. Does this method apply to the varying scales of losses? I mean, from the experiments, the loss scales are similar and comparable. But in practice, loss scales can differ across tasks or clients. What is the empirical performance then?", "broader_impact_concerns": "This paper tackles multi-objective learning, which is a common problem in the real world. I have no additional concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qJZj865ZBn", "reviewer": "Reviewer_ULkm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes AdaOMD-TCH, an algorithm for multi-objective learning via Tchebycheff scalarization (TCH). To overcome the issue of non-smoothness when optimizing TCH, AdaOMD-TCH reformulates the problem as a zero-sum game between the solution $\\theta$ and the preference vector $\\lambda$. Thanks to the transformation, the inner TCH maximization becomes continuous and can be solved by Online Mirror Descent (OMD), hence the name OMD-TCH. The paper further proposes an adaptive version, AdaOMD-TCH, that applies online-to-batch and reweighs the solutions.  The paper presents a theoretical convergence analysis for the non-adaptive version. Empirically, both versions are benchmarked, which shows that the adaptive version is better, and both are competitive against the baseline approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "-\tThe paper presents a decent overview of the settings and related literature. \n-\tThe methodology is sufficiently clear and sound. There seems to be no major issue.\n-\tAlthough there is no convergence analysis for the adaptive version, the analysis for the standard version is sound.\n-\tThe empirical performance seems to be promising.\n-\tHowever, there are some issues I would like the authors to address, please see the requested changes.", "audience_yn": "Yes", "audience_explanation": "I believe researchers with online learning interest (especially preference-guided multi-objective learning) will appreciate this work.", "requested_changes": "-\tAdd some explanation on how OMD can be used for online learning problems (e.g., what makes it suitable for online settings) and why it should be used (e.g., why not other algorithms).\n-\tRegarding the transformation in Section 3.1. Is this transformation a common technique in the field, or is it proposed by the authors? It will be great if there are more explanations for this key transformation.\n-\tRegarding the adaptive version AdaOMD-TCH, it seems high-performance solutions found in early rounds (e.g., in round 1) will have much larger weights compared to high-performance ones found later (e.g., in round 100). Will this cause bias towards the early solutions and make the algorithm stuck?\n-\tThe experiment results are hard to follow because the authors use different formats to present the same metrics. For example, Figure 3 uses line plots, Table 2 is table format, and Figure 4 uses box plots – all share the same purpose of showing the accuracy and loss metrics. If there are no other purposes for this, I highly suggest converting to a single format, preferably Figure 3 (left), since it shows the performance across rounds – it would demonstrate clearly how the proposed method competes against the baselines across iterations.\n-\tFurthermore, about the experimental results, I think Figure 2 serves very little purpose (as it only shows one random run) and should be accompanied by another metric. I suggest using hypervolume (like in Table 3) to further quantify the performance. The hypervolume, as the authors also agreed, is a robust metric to quantify the performance of multi-objective problems. In fact, I think it would be best if the authors could use **line plots of hypervolume vs rounds** as the main results for all experiments, followed by tables that show the final results of each objective.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4gdou0vw8R", "reviewer": "Reviewer_ZACz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper develops methods for multi-objective learning, where there are multiple objective functions present. In particular, the paper focuses on solving the Tchebycheff scalarization version of the problem, which is formulated as a minmax problem over a (potentially non-uniformly) weighted average of the $m$ different objective functions. The paper modifies this minmax formulation by replacing the max over functions with a max over a simplex weighting of the functions. They then propose solving the problem with the minimax version of mirror descent. They also propose a new weighting scheme, different from releasing the average iterate, which they show has experimental benefit.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I don't see any major correctness or presentational issues. A more minor comment is the following.\n\n- The authors claim that in Remark 3.6 that the factor d in Corollary 3.5 could be lifted. Could the authors elaborate on how this is done? A direct approach using the l2 analysis of mirror descent/gradient descent would still leave a $\\sqrt{d}$ factor because the width of the constraint set has l_2 radius $\\sqrt{d}$.", "audience_yn": "No", "audience_explanation": "As far as the papers interest to the community, I am a bit more concerned. The proposed algorithm is simply mirror descent, and I currently don't see how this provides new insights to the community. The AdaOMD algorithm is a bit more novel, but the idea of releasing only a combination of the best iterates is also not really new. My thinking is that the most potentially interesting part for many people will be the experiments, but this is these do not seem to be the focus of the paper.", "requested_changes": "It would be great if the authors could address the following concerns:\n\n- Near the end of the introduction, the authors claim that previous works do handle non-uniform weighting, and claim they generalize these methods. Could the authors elaborate on why non-uniform weighting is difficult? It seems to be we can always push the weights into the objective function, say $f_i'(\\theta) = w_i f_i(\\theta)$. Now run an algorithm for uniform weighting using the $f_i'$ functions. Is there a reason this doesn't work?\n\n- While not entirely clear, the impression the current writing gives is that converting the problem $\\min \\max \\{w_i f_i(\\theta)}$ into a smooth problem which uses a simplex weighting is a novel step. However, reformulating the non-smooth problem into a smooth minimax problem is a classic use of minmax optimization. \n\n- The usage of ``online to batch conversion'' is a bit confusing to me. While not strictly incorrect, the algorithm the authors use would normally just be called mirror descent (not online mirror descent). Calling this an online to batch conversion feels like it adds extra steps. Could the authors clarify if this conversion is adding anything, over existing analysis? For example, see [1] Section 6.5 and 5.2.\n\n[1]:  Convex Optimization: Algorithms and Complexity, Sebastion Bubeck\n\n- Overall, can the authors provide more justification as to why their results would be of interest to the community? In particular, could the authors argue that their results are more than a direct application of classic techniques (as I've described in previous points) to the Tchebycheff scalarization problem?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)