# MULTI-OBJECTIVE ONLINE LEARNING

**Anonymous authors**
Paper under double-blind review

ABSTRACT

This paper presents a systematic study of multi-objective online learning. We
first formulate the framework of Multi-Objective Online Convex Optimization,
which encompasses a novel multi-objective dynamic regret in the unconstrained
max-min form. We show that it is equivalent to the regret commonly used in the
zero-order multi-objective bandit setting and overcomes the problem that the latter is hard to optimize via first-order gradient-based methods. Then we propose
the Online Mirror Multiple Descent algorithm with two variants, which computes
the composite gradient using either the vanilla min-norm solver or a newly designed L1-regularized min-norm solver. We further derive regret bounds of both
variants and show that the L1-regularized variant enjoys a lower bound. Extensive
experiments demonstrate the effectiveness of the proposed algorithm and verify
the theoretical advantage of the L1-regularized variant.

1 INTRODUCTION

Traditional optimization methods for machine learning are usually designed to optimize a single
objective. However, in many real-world machine learning applications, we are often required to
optimize multiple correlated objectives simultaneously. For example, in autonomous driving (Huang
et al., 2019; Lu et al., 2019b), the self-driving vehicle needs to learn to solve multiple tasks such as
self-localization and object identification at the same time. In online advertising (Ma et al., 2018a;b),
the advertiser aims to choose the exposure of items to different users so that both the Click-Through
Rate (CTR) and the Post-Click Conversion Rate (CVR) are maximized simultaneously. In many
multi-objective scenarios, the objectives may conflict with each other (Kendall et al., 2018). Hence,
there may not exist any single solution that optimizes all the objectives simultaneously. For example,
in the online advertising scenario, merely optimizing either CVR or CTR will incur the degradation
of performance of the other (Ma et al., 2018a;b).

Multi-objective optimization (MOO) (Marler and Arora, 2004; Deb, 2014) is concerned with optimizing multiple conflicting objectives simultaneously. Many different approaches for MOO have
been proposed, which include evolutionary methods (Murata et al., 1995; Zitzler and Thiele, 1999),
scalarization methods (Fliege and Svaiter, 2000) and gradient-based iterative methods (D´esid´eri,
2012). Recently, due to the great success of training multi-task deep neural networks, the first-order
gradient-based iterative methods, i.e., Multiple Gradient Descent Algorithm (MGDA) and its variants, have regained a significant amount of research interest (Sener and Koltun, 2018; Lin et al.,
2019; Yu et al., 2020). These methods compute a composite gradient based on the gradient information of all the individual objectives and then apply the composite gradient to model update.
The determination of the composite gradient is based on a min-norm solver (D´esid´eri, 2012) which
yields the common descent direction of all the objectives.

However, compared to the increasingly wide application prospect, the first-order gradient-based
iterative algorithms are relatively understudied, especially for the online learning setting. Multiobjective online learning is very important due to reasons in two main aspects. First, due to the data
explosion in many real-world scenarios such as various web applications, making in-time prediction
requires to perform online learning. Second, the theoretical investigation will lay a solid foundation
for the design of new optimizers of multi-task deep neural networks, such as multi-objective Adam.

In this paper, we conduct a systematic study of multi-objective online learning. To begin with,
we first formulate the framework of Multi-Objective Online Convex Optimization (MO-OCO). The
biggest challenge in the design of MO-OCO is the derivation of an appropriate regret definition in


-----

the multi-objective setting. Since the multiple objectives form a vector space, we need a discrepancy
metric to scalarize the loss vector. Specifically, we adopt the Pareto suboptimality gap (PSG), which
is a distance-based discrepancy metric extensively used in multi-objective bandits (Turgay et al.,
2018; Lu et al., 2019a). Then analogously to the single-objective online setting, we define the
multi-objective static regret and the multi-objective dynamic regret. However, since PSG is a metric
motivated purely from the geometric view, it is intrinsically difficult to directly optimize using firstorder gradient-based iterative methods. To remedy this problem, for the multi-objective dynamic
regret, via a highly non-trivial transformation, we derive its equivalent regret in the unconstrained
max-min form, which is much easier to optimize. Unfortunately, we further show that such an
equivalence does not hold for the multi-objective static regret since PSG always yields non-negative
measurements. Hence, in this paper, we mainly focus on studying the multi-objective dynamic regret
and leave the complete treatment of its static counterpart as an open problem.

Based on the proposed MO-OCO framework, we develop the Online Mirror Multiple Descent
(OMMD) algorithm. The key module of OMMD is the gradient composition scheme, which utilizes the information of all the individual gradients to compute a composite gradient that tends to
descend all the losses simultaneously. By directly applying the min-norm solver (D´esid´eri, 2012) in
the offline setting to determine the composition weights, we give the first variant of OMMD termed
as OMMD-I. However, the min-norm solver only uses the instantaneous gradients and ignores the
historical information, which can be very unstable in the online setting where the losses and the gradients at different rounds can vary wildly. To make the learning process more stable, we introduce a
carefully designed L1-regularizer to the vanilla min-norm solver, which results in the second variant
of OMMD, namely OMMD-II.

We then give the theoretical analysis of the proposed OMMD algorithm. Specifically, we derive a
non-trivial dynamic regret bound of OMMD-II, which includes that of OMMD-I as a special case.
The dynamic regret bound is in the same order O(VT[1][/][3]T [2][/][3]), where T is the time horizon and VT
is the temporal variability at T, as that of its single-objective counterpart(Zhang et al., 2018). We
further show that the regret bound of OMMD-II is lower than that of OMMD-I.

To evaluate the effectiveness of our proposed algorithm, we conduct extensive experiments using
both simulation datasets and real-world datasets. Specifically, we first design simulation experiments to verify the capability of OMMD-II to track the dynamic online data streams. Then we successfully realize adaptive regularization for online learning using our MO-OCO formalism, which
demonstrates the effectiveness of OMMD-II in the convex setting. We further conduct online multitask learning experiments with deep neural networks, the results of which show that both OMMD-I
and OMMD-II are effective in the non-convex setting. Moreover, in both simulation and multi-task
deep experiments, OMMD-II yields better performance than OMMD-I, which verifies the theoretical superiority of the regularized min-norm method over the vanilla min-norm method.

In summary, in this paper, we give the first systematic study of multi-objective online learning,
which includes novel framework, algorithm design and theoretical analysis. We believe that our
paper paves the way for future research on multiple-objective optimization and multi-task learning.

2 PRELIMINARIES

In this section, we briefly review the necessary background knowledge of online convex optimization
and multi-objective optimization.

2.1 ONLINE CONVEX OPTIMIZATION

**Online Convex Optimization (OCO) (Zinkevich, 2003; Hazan, 2019) is the most commonly**
adopted framework for designing online learning algorithms. It can be viewed as a structured repeated game between a learner and an adversary. At each round t ∈{1, . . ., T _}, the learner is_
required to generate a decision xt from a convex compact set X ⊂ R[n]. Then the adversary replies
the learner with a convex function ft : X → R and the learner suffers the loss ft(xt). The goal of
the learner is to minimize the regret with respect to the best fixed decision in hindsight, i.e.,


_ft(x[∗])._
_t=1_

X


_RS(T_ ) =


_ft(xt)_ min
_−_ _x[∗]_
_t=1_ _∈X_

X


-----

Note that the above regret is the static regret (Hall and Willett, 2013), which compares the learner’s
cumulative loss with that of a fixed decision. There is another version of regret, namely the dynamic
**regret (Hall and Willett, 2013; Zhang et al., 2018), which compares the learner’s cumulative loss**
with that of a sequence of changing decisions, i.e.,

_T_ _T_

_RD(T_ ) = _ft(xt)_ min _t_ [)][.]

_t=1_ _−_ _t=1_ _x[∗]t_ _[∈X][ f][t][(][x][∗]_

X X

Any meaningful regret is required to be sublinear in T, i.e., limT →∞ _RS/D(T_ )/T = 0, which
implies that when T is large enough, the learner can perform as well as the best fixed decision in
hindsight (for static regret) or the changing optimal decisions at each round (for dynamic regret).

**Online Mirror Descent (OMD) (Hazan, 2019) is a classic first-order online learning algorithm. At**
each round t ∈{1, . . ., T _}, OMD yields its decision using the following formula_
_xt+1 = arg minx∈X_ _η⟨∇ft(xt), x⟩_ + BR(x, xt),

where η is the step size, R : X → R is the regularization function, and BR(x, x[′]) = R(x) −
_R(x[′]) −⟨∇R(x[′]), x −_ _x[′]⟩_ is the Bregman divergence induced from R. As a generic algorithm, by
instantiating different regularization functions, OMD can induce two important algorithms, i.e., Online Gradient Descent (Zinkevich, 2003) and Online Exponentiated Gradient (Hazan, 2019). Several
papers work on the dynamic regret of online mirror descent (Jadbabaie et al., 2015; Shahrampour
and Jadbabaie, 2017).

2.2 MULTI-OBJECTIVE OPTIMIZATION

**Multiple-objective optimization (MOO) is concerned with solving the problems of optimizing**
multiple objective functions simultaneously (Zitzler and Thiele, 1999; Sener and Koltun, 2018). In
general, since different objectives may conflict with each other, there is no single solution that can
optimize all the objectives at the same time. Instead, MOO seeks to find solutions that achieve Pareto
optimality. In the following, we exposit Pareto optimality and related definitions more formally
using a vector-valued loss H = (h[1], . . ., h[m])[⊤] as objectives, where m ≥ 2 and h[i] : K → R,
_i ∈{1, . . ., m}, K ⊂_ R, is the i-th loss function.
**Definition 1 (Pareto optimality). (a) For any two solutions x, x[′]** _∈K, we say that x dominates_
_x[′], denoted as x ≺_ _x[′]_ _or x[′]_ _≻_ _x, if h[i](x) ≤_ _h[i](x[′]) for all i, and there exists one i such that_
_h[i](x) < h[i](x[′]); otherwise, we say that x does not dominate x[′], denoted as x ⊀_ _x[′]_ _or x[′]_ ⊁ _x._
**_(b) A solution x[∗]_** _∈K is called Pareto optimal if it is not dominated by any other solution in K._

There may exist multiple Pareto optimal solutions. For example, it is easy to show that the optimizer
of any single objective, say, x[∗]1 _x_ _[h][1][(][x][)][, is Pareto optimal. Different Pareto optimal]_
solutions reflect different trade-offs among the objectives (Sener and Koltun, 2018; Lin et al., 2019).[∈] [arg min] _∈K_
**Definition 2 (Pareto front). (a) All Pareto optimal solutions form the Pareto set, denoted as** (H).
_PK_
**_(b) The image of_** (H) constitutes the Pareto front, denoted as (H) = _H(x)_ _x_ (H) _._
_PK_ _P_ _{_ _|_ _∈PK_ _}_

Now that we’ve established the notion of optimality in MOO, we proceed to introduce the metrics
that measure the discrepancy of an arbitrary solution x ∈K from being optimal. Recall that, in the
single-objective setting with merely one loss function h : Q → R, where Q ⊂ R, for any z ∈Q,
the loss gap h(z) minz[′′] _h(z[′′]) is directly the discrepancy measure. However, in MOO with_
_−_ _∈Q_
more than one loss, for any x, the loss gap H(x) _H(x[′′]), where x[′′]_ (H), is a vector.
_∈K_ _−_ _∈PK_
Intuitionally, the desired discrepancy metric shall scalarize the vector-valued loss gap and yield
the value 0 for any Pareto optimal solution. In general, there are two commonly used discrepancy
metrics in MOO, namely Pareto suboptimality gap (PSG) (Turgay et al., 2018) and Hypervolume
(HV) (Bradstreet, 2011). As HV is a volume-based metric, it is very difficult to optimize or analyze
via iterative algorithms (Zhang and Golovin, 2020). Hence in this paper, we adopt PSG, which has
been extensively used in multi-objective bandits (Turgay et al., 2018; Lu et al., 2019a).
**Definition 3 (Pareto suboptimality gap). For any x ∈K, the Pareto suboptimality gap to a given**
_comparator set K[∗]_ _⊂K, denoted as ∆(x; K[∗], H), is defined as the minimal scalar ϵ ≥_ 0 that needs
_to be subtracted from all entries of H(x), such that H(x) −_ _ϵ1 is not dominated by any point in K[∗],_
_where 1 denotes the all-one vector in R[m], i.e.,_
∆(x; _, H) = inf_
_K[∗]_ _ϵ_ 0 _[ϵ s.t.][ ∀][x][′′][ ∈K][∗][,][ ∃][i][ ∈{][1][, . . ., m][}][, h][i][(][x][)][ −]_ _[ϵ < h][i][(][x][′′][)][.]_
_≥_


-----

Clearly, PSG is a distance-based discrepancy metric that motivated from a purely geometric viewpoint. In practice, the comparator set is often set to be the Pareto set (H) (Turgay et al., 2018).
_K[∗]_ _PK_
Then for any x, its PSG is always non-negative and equals to zero if and only if x (H).
_∈K_ _∈PK_

**Multiple Gradient Descent Algorithm (MGDA) is an offline first-order algorithm for MOO**
(Fliege and Svaiter, 2000; D´esid´eri, 2012). At each iteration l ∈{1, . . ., L}, where L is the maximum number of iterations, it first computes the gradient _h[i](xl) for each objective i_ 1, . . ., m,
_∇_ _∈{_ _}_
and then derive the composite gradient gl = _i=1_ _[λ]l[i][∇][h][i][(][x][l][)][ as the convex combination of these]_
multiple gradients; it applies the composite gradient to execute the gradient descent step to update
the decision, i.e., xl+1 = xl _ηgl, where η is the step size. The core module of MGDA is the_

[P][m]
determination of the weights λ −l = (λ[1]l _[, . . ., λ]l[m][)][ for the gradient composition, which is given as]_

_m_

_λl = arg minλl∈∆m_ _∥_ _i=1_ _λ[i]l[∇][h][i][(][x][l][)][∥][2]2[,]_

X

where ∆m = {λ ∈ R[m] _| λ[i]_ _≥_ 0, i ∈{1, . . ., m}, and _i=1_ _[λ][i][ = 1][}][ denotes the probabilistic]_
simplex in R[m]. This is a min-norm solver which finds the weights in the simplex that yields the
minimum L2 norm of the composite gradient. Thus MGDA is also called the min-norm method.

[P][m]
Existing works (D´esid´eri, 2012; Sener and Koltun, 2018) have shown that MGDA is guaranteed
to decrease all the objectives simultaneously until it reaches a Pareto optimal decision (under the
convex setting where all h[i] are convex functions).

3 MULTI-OBJECTIVE ONLINE CONVEX OPTIMIZATION

In this section, we formally formulate the framework of multi-objective optimization in the online
setting, termed Multi-Objective Online Convex Optimization (MO-OCO).

We tailor the famous online convex optimization (OCO) framework to the multi-objective setting,
which can be viewed as a repeated game between an online learner and the adversarial environment.
At each round t ∈{1, . . ., T _}, the learner generates a decision xt from a given convex compact_
decision set X ⊂ R[n]. Then the adversary replies the decision with a vectoral loss function Ft(x) :
_X →_ R[m], where its i-th component ft[i][(][x][) :][ X →] [R][ belongs to the][ i][-th objective, and the learner]
suffers the loss Ft(xt) ∈ R[m]. The goal of the learner is to generate a sequence of decisions {xt |
1 ≤ _t ≤_ _T_ _} so that the cumulative loss_ _t=1_ _[F][t][(][x][t][)][ can be optimized.]_

Recall that, in the single-objective setting, the performance metric R(T ) = _t=1_ _[f][t][(][x][t][)][ −]_ _[f][t][(][x]t[∗][)][,]_

[P][T]

i.e., the regret, compares the actual decisions1, . . ., T . In general, there are two common types of regret which differ in the comparators, i.e., xt with some comparator x[∗]t _[∈X][ at each round][ t][ ∈]_
_{_ _}_ [P][T]
the static regret and the dynamic regret. For the static regret, all comparators x[∗]t _[,][ ∀][t][ ∈{][1][, . . ., T]_ _[}]_
are identically set as the fixed optimal decision x[∗] w.r.t. all losses in hindsight, i.e., x[∗]t
_T_ _[≡]_ _[x][∗]_ _[∈]_
arg minx _t=1_ _[f][t][(][x][)][. For the dynamic regret, the comparator][ x]t[∗]_ [at each round][ t][ is selected as]
_∈X_
the optimal decision w.r.t. the instantaneous loss ft at that round, i.e., x[∗]t _x_ _[f][t][(][x][)][.]_
P _[∈]_ [arg min] _∈X_

In analogy, in the multi-objective setting, we define the regret as R(T ) = _t=1_ [∆][t][, where the]
However, in general, no single decision can optimize all the objectives at the same time. Hence, itquantity ∆t at each round t compares the actual decisions xt with some comparator x[∗]t _[∈X]_ [.]

[P][T]
is reasonable to compare xt with all the Pareto optimal decisions that constitute a comparator set
_Xt[∗]_ _[⊂X]_ [. Specifically, we introduce the Pareto suboptimality gap (PSG) (Turgay et al., 2018), i.e.,]

∆(xt; Xt[∗][, F][t][) = inf]ϵ 0 _[ϵ s.t.][ ∀][x][′′][ ∈X]t[ ∗][,][ ∃][i][ ∈{][1][, . . ., m][}][, f][ i]t_ [(][x][t][)][ −] _[ϵ < f]t[ i][(][x][′′][)][.]_ (1)
_≥_

Then the multi-objective regret can be defined as R(T ) = _t=1_ [∆(][x][t][;][ X][ ∗]t _[, F][t][)][. Given the above]_
definitions, we can formulate the multi-objective variants of the static and dynamic regret respectively, by using different comparator set Xt[∗] [at each step. Specifically, if we set all][P][T] _[ X][ ∗]t_ [to be the]
Pareto set of the cumulative loss _t=1_ _[F][t][, then we can formulate a regret metric termed the][ multi-]_
_objective static regret (recall that_ _X_ (F ) denotes the Pareto set of F )
_P_

[P]T _[T]_ _T_

_RMOS(T_ ) := ∆(xt; _, Ft),_ where = _X_ ( _Ft)._

_X_ _[∗]_ _X_ _[∗]_ _P_
_t=1_ _t=1_

X X


-----

Alternatively, if we set Xt[∗] [to be the Pareto set of the instantaneous loss][ F][t] [at each round][ t][, then we]
can give a regret metric termed the multi-objective dynamic regret


∆(xt; Xt[∗][, F][t][)][,] where Xt[∗] [=][ P][X] [(][F][t][)][,][ ∀][t][ ∈{][1][, . . ., T] _[}][.]_
_t=1_

X


_RMOD(T_ ) :=


Recall that, PSG is a zero-order metric motivated in a purely geometric sense, namely, its calculation
can be viewed as a constrained minimization problem (1) with an unknown boundary ft[i][(][x][′′][)][,][ ∀][x][′′][ ∈]
_Xt[∗][. Hence, it is intrinsically complex to design a first-order algorithm to optimize PSG given its]_
unknown constraints, not to mention the regret analysis.

Surprisingly, specific to the multi-objective dynamic regret RMOD, we can transform it into an unconstrained max-min form as follows. The derivation utilizes Pareto optimality of Xt[∗] [and is highly]
non-trivial, which is given in the appendix due to the space limit. The equivalent form is closely
related to the dynamic regret, as it recovers the dynamic regret defined for λt⊤Ft, t 1, . . ., T
_∈{_ _}_
if we determine λt at each round t ∈{1, . . ., T _} beforehand. Moreover, it exactly reduces to the_
standard dynamic regret RD in the single-objective setting.
**Proposition 1. The multi-objective dynamic regret has an equivalent form, i.e.,**


(λ[∗]t _⊤Ft(xt) −_ _λ∗t_ _⊤Ft(x∗t_ [))][,] (2)
_t=1_

X


_RMOD(T_ ) = sup inf
_x[∗]t_ _[∈X][ ∗]t_ _[,][1][≤][t][≤][T]_ _λ[∗]1_ _[...,λ]t[∗][∈][∆][m]_


_where ∆m represents the probabilistic simplex in R[m]._

**Remark. In the single-objective setting where m = 1, the probabilistic simplex ∆m collapses into**
a single point {1}. Moreover, the Pareto set Xt[∗] [of the scalar loss function][ F][t] [:][ X →] [R][ reduces to]
the optimal set arg minx _Ft(x). Hence we have RMOD(T_ ) = _t=1[(][F][t][(][x][t][)][ −]_ [min][x][∈X][ F][t][(][x][))][,]
_∈X_
which is exactly the dynamic regret RD(T ) in the standard online setting.

Unfortunately, for the multi-objective static regret RMOS, such a correspondence does not exist. Here[P][T]
is the reason. In RMOS, the comparator set X _[∗]_ is the Pareto set of the cumulative loss _t=1_ _[F][t][ rather]_
than the instantaneous loss Ft. Hence, at some specific round t, the actual decision xt may Pareto
dominate all decisions in w.r.t. the instantaneous Ft, and so we expect the discrepancy metric
_X_ _[∗]_ [P][T]
∆t to give a negative measurement. However, PSG (as well as other commonly used discrepancy
metrics such as Hypervolume) is always non-negative, so the induced RMOD is not aligned with RS.
For example, when m = 1, we have RMOS(T ) = supx∗∈X ∗ [P]t[T]=1 [max][{][F][t][(][x][t][)] _[−]_ _[F][t][(][x][∗][)][,][ 0][}][, which]_
can be much looser than the static regret RS(T ) = supx∗∈X ∗ [P]t[T]=1 _[F][t][(][x][t][)][−][F][t][(][x][∗][)][. Therefore, the]_
analysis of RMOD is intrinsically complex if we only use existing discrepancy metrics; its analysis
may require a completely new discrepancy metric ∆t that allows to give a negative measurement.

Given the limits of existing discrepancy metrics to characterize RMOS, in this paper, we mainly focus
on the dynamic variant RMOD. Indeed, the algorithm design and theoretical analysis w.r.t. RMOD are
already highly non-trivial. We will leave the analysis of RMOS for future works.

4 ONLINE MIRROR MULTIPLE DESCENT

In this section, we first present the Online Mirror Multiple Descent (OMMD) algorithm, then provide
theoretical analysis for it.

4.1 THE ALGORITHM

The protocol of OMMD is given in Algorithm 1. At each round t, the learner computes the gradient
for each loss ∇ft[i][(][x][t][)][, then determines the weights for the composition of these multiple gradients,]
and finally executes an online mirror descent step using the composite gradient. For simplicity, we
define the matrix form of the multiple gradients as ∇Ft(xt) = [∇ft[1][(][x][t][)][, . . .,][ ∇][f][ m]t [(][x][t][)]][ ∈] [R][n][×][m][.]

The core module of OMMD is the composition of the multiple gradients. In intuition, the composite
gradient gt shall elaborately utilize the information of all the individual gradient. As illustrated in
Preliminary (see the MGDA part), in the offline setting, there is one simple yet effective scheme,


-----

**Algorithm 1 Online Mirror Multiple Descent (OMMD)**

1: Input: Convex set X, time horizon T, regularization parameter α, learning rate η, regularization function R.

3:2: for Initialize: t = 1, . . ., T x1 ∈X do, λ0 ∈ ∆m.
4: Predict with xt and receive the vector loss function Ft : X → R[m].

5: Compute the multiple gradients ∇Ft(xt) = [∇ft[1][(][x][t][)][, . . .,][ ∇][f][ m]t [(][x][t][)]][ ∈] [R][n][×][m][.]

6: Determine the weights for the gradient composition

_λt = arg minλ∈∆m_ _∥∇Ft(xt)λ∥2[2][;]_ (OMMD-I) (3)

_λt = arg minλ∈∆m_ _∥∇Ft(xt)λ∥2[2]_ [+][ α][∥][λ][ −] _[λ][t][−][1][∥][1][.]_ (OMMD-II) (4)

7: Compute the composite gradient gt = ∇Ft(xt)λt.

8: Perform online mirror descent using the composite gradient


_xt+1 = arg minx∈X_ _η⟨gt, x⟩_ + BR(x, xt). (5)


9: end for


i.e., the min-norm method (D´esid´eri, 2012; Sener and Koltun, 2018), which computes a common
descent direction that can descend all the losses simultaneously. We directly apply it to the online
setting, which results in the first variant of OMMD, i.e., OMMD-I, as shown in Algorithm 1.

Despite its simplicity, OMMD-I may not yield optimal decisions in the online setting, since the
min-norm method is designed in the offline setting, which does not capture the characteristics of
the online setting. Specifically, the composition weights λt given by the min-norm solver are determined solely by the gradients at the instantaneous round t, regardless of the historical information.
Indeed, this makes sense in the offline setting, where the optimized loss function does not change
too much. In the online setting, however, the losses at different rounds can vary wildly and so are
the gradients consequently. Hence, directly applying the min-norm method will yield very different
_λts at different rounds, which makes the learning process unstable and even fail to converge._

To fix this issue, we propose to add a regularizer r(λ, λt−1) to the min-norm solver when determining the composition weights λt, where λt 1 denotes the composition weights at the precedent
_−_
round. Such a regularizer ensures that the new weights λt will not move too far away from the
precedent weights λt−1. In principle, r(λ, λt−1) can take many forms such as L1-norm, L2-norm
and KL divergence etc. Here we use the L1 norm since it aligns well with the simplex constraint of
_λ. This L1-regularized min-norm method results in the second variant of OMMD, i.e., OMMD-II,_
as shown in Algorithm 1. Later we will show that OMMD-II attains a lower theoretical regret bound
than OMMD-I, and it is also much more robust in experiments.

4.2 ANALYSIS

We first provide a general bound for OMMD, which is agnostic of the choice of λt at each round.
**Assumption 1 (Bregman divergence). The regularization function R is 1-strongly convex with**
_respect to a norm ∥· ∥._ _In addition, the Bregman divergence is γ-Lipschitz continuous, i.e.,_
_BR(x, z)_ _BR(y, z)_ _γ_ _x_ _y_ _,_ _x, y, z_ domR, where domR denotes the domain of the
_−_ _≤_ _∥_ _−_ _∥_ _∀_ _∈_
_regularization function R and satisfies X ⊂_ domR ⊂ R[n].
**Lemma 1. Suppose the diameter of the decision set X is bounded by D. Assume Ft is bounded,**
_i.e., |ft[i][(][x][)][| ≤]_ _[F][ for any][ x][ ∈X]_ _[, t][ ∈{][1][, . . ., T]_ _[}][, i][ ∈{][1][, . . ., m][}][. Then for any][ δ][ ∈{][1][, . . ., T]_ _[}][,]_

_OMMD-I or OMMD-II with composition weights λt at each round t attains the following regret_


_T −1_

_RMOD(T_ ) ≤2δ _xsup_ _|ft[i][(][x][)][ −]_ _[f][ i]t+1[(][x][)][|][ +][ 4][δFT]_

_t=1_ _∈X_

X


_T −1_

_λt_ _λt+1_ 1
_t=1_ _∥_ _−_ _∥_

X


+ _[η]_


_T_

_Ft(xt)λt_ 2 [+][ γD]
_∥∇_ _∥[2]_ _η_ _δ_
_t=1_

_[⌈]_ _[T]_ _[⌉][.]_

X


-----

The bound can be further simplified under the assumptions of temporal variability and Lipschitz
continuity, which are commonly used in dynamic regret analysis (Besbes et al., 2015; Yang et al.,
2016; Campolongo and Orabona, 2021).
**Assumption 2 (Temporal variability). For each i ∈{1, . . ., m}, there exists some positive and**
_finite VT such that_ _t=1_ [sup]x _t_ [(][x][)][ −] _[f][ i]t+1[(][x][)][| ≤]_ _[V][T]_ _[.]_
_∈X_ _[|][f][ i]_

**Assumption 3 (Lipschitz continuity). For each i ∈{1, . . ., m}, there exists some positive and**
_finite G such that, the[P] i[T]-th loss[ −][1]_ _ft[i]_ _[at each round][ t][ ∈{][1][, . . ., T]_ _[}][ is][ G][-Lipschitz continuous w.r.t.][ ∥·∥][,]_
_i.e., |ft[i][(][x][)][ −]_ _[f][ i]t_ [(][x][′][)][| ≤] _[G][∥][x][ −]_ _[x][′][∥][.]_

In the convex setting, Lipschitz continuity guarantees bounded gradients, i.e., ∥∇ft[i][(][x][)][∥][∗] _[≤]_ _[G][ for]_
any t ∈{1, . . ., T _}, i ∈{1, . . ., m}, x ∈X_ . We can now derive a general regret bound for OMMD.

**Theorem 1.weights λt at each round Assume the step size t attains the following regret η satisfies** _G[4][V][2][T]T_ _[≤]_ _[η][ ≤]_ [4]G[V][2][T][ . Then][ OMMD-I or OMMD-II][ with]


_RMOD(T_ )
_≤_ _[ηG]2[2][T]_


_T_

( _Ft(xt)λt_ 2 [+][ 8][FG][2][T][ 2]
_∥∇_ _∥[2]_ _VT_
_t=1_

X


+ _[η]_


_∥λt −_ _λt−1∥1) + [4]η[γD][2]G[V][2][T][ .]_


**Remark. The above theorem shows the theoretical superiority of OMMD-II over OMMD-I or**
naive linear scalarization that always uses fixed composition weights λt _λ at each round. In_
_≡_
particular, with the proper choice of α = _[F G]VT[2][T]_, OMMD-II adaptively selects λt to minimize the

term _Ft(xt)λt_ 2 [+][ α][∥][λ][t]
_∥∇_ _∥[2]_ _[−]_ _[λ][t][−][1][∥][1][. This term will become larger with any other choice of][ λ][t][.]_

Finally, specific to OMMD-II, we have the following regret bound. Note that, this bound actually
relies on the assumption that Ω(1) _VT_ _o(T_ ), which is implicitly assumed in other works for
dynamic online learning (Besbes et al., 2015; Yang et al., 2016; Campolongo and Orabona, 2021). ≤ _≤_
We also extend the bound to arbitrary value of VT 0 (see Corollary 2 in the appendix).
_≥_

**Corollary 1. With η =** _G[2]_ [(][ γD]GT[V][T] [)][1][/][3][ and][ α][ =][ 8][F G]VT[2][T][ 2] _, OMMD-II achieves the following regret_

_RMOD(T_ ) _O(VT[1][/][3]T_ [2][/][3]).
_≤_


5 EXPERIMENTS

In this section, we conduct extensive simulation and real-world experiments to evaluate the effectiveness of our proposed algorithm. In our experiments, we mainly compare our proposed OMMD-II
with two baseline algorithms: (i) linear optimal (lin-opt) performs single-objective online learning
using the linearized loss λ[⊤]F at each round t, where the linearization weights λ is fixed and decided
by a grid search on ∆m; note that, it is equivalent to using a fixed composition weight λt = λ in
OMMD. (ii) min-norm extends the famous min-norm method (D´esid´eri, 2012; Sener and Koltun,
2018) to the multi-objective online setting, which has been described as OMMD-I in Algorithm 1.

5.1 SIMULATION EXPERIMENTS: TRACKING THE PARETO FRONT

In the simulation setup, the goal is to track two points ξt[1][, ξ]t[2] [moving on the plane][ R][2][. The two points]
cycle along a circle with a ratius of 1, i.e., C = {ξ ∈ R[2] _| ∥ξ∥2 = 1}, namely, for each i ∈{1, 2},_
_ξt[i]_ [= (cos][ θ]t[i][,][ sin][ θ]t[i][)][ is determined by some angle][ θ]t[i][. For each][ i][ ∈{][1][,][ 2][}][, we set a positive integer][ P][ i]
as the rotating period, which is unknown to the learner. The two points are initialized by θ1[1] [= 0][ and]
_θ1[2]_ [=][ π/][2][, and iteratively generated as follows: at each round][ t][, for each][ i][ ∈{][1][,][ 2][}][, the adversary]
independently samples an angle δt[i] [from a Gaussian distribution][ N] [(2][π/P][ i][,][ 1][/]√P _[i]), then generates_

that in averagethe next point ξ ξt[i]t[i]+1[rotates clockwise uniformly along the circle][via][ θ]t[i]+1 [=][ θ]t[i] _[−]_ _[δ]t[i][. Note that, we have][ E][ C][θ]t[i][, with a period of]+1_ [=][ θ]1[i] [+ 2][πt/P][ P][ i][ i][, which implies][.]

norm ball with a radius of 2. Then it acquires the positions ofAt each round t, the learner generates a decision xt from X = ξ {t[1]x[, ξ] ∈t[2]R[and suffer two losses][2] _| ∥x∥2 ≤_ 2}, which is a[ f][ i]t [(][x][t] L[) =]2For any decisionsegment. The setup and PSG measurement are summarized in Figure 1 (left plot).∥roundxt − tξt[i] is exactly the line segment linking[∥][2][/][2][ for][ i] x[ ∈{]t ∈X[1][,][ 2], its PSG exactly equals to the squared distance between[}][. In this problem, the Pareto set of the vectoral loss] ξt[1] [and][ ξ]t[2][, i.e.,][ X][ ∗]t [=][ {][λξ]t[1] [+ (1][ −][ f][t][λ][= (][)][ξ] xt[2][f]t[ 1]t[|] and the line[ λ][, f][ ∈][ 2]t [)][ at each][[0][,][ 1]][}][.]


-----

|t(xt) } xt|t2|
|---|---|

|Col1|OMMD-II min-norm|
|---|---|
|Phase 1|Phase 2 lin-opt lin 1 lin 2|
|2000|4000 6000 8000 1000|


0.37 OMMD-II 0.26 OMMD-II

lin-opt lin-opt

0.35 0.22

0.33 0.18

Average Loss Average Loss

0.31 0.14

0 2500 5000 7500 10000 12500 0 200000 400000 600000

# Rounds # Rounds (K)

(a) protein (b) covtype


t1 1 t1 0.12 Phase 1 Phase 2 OMMD-IImin-normlin-opt

0.09 lin 1lin 2

## }xt t[(][x]t[)] t2 1 Average PSG 0.06

0.03

t2 0 2000 4000 6000 8000 10000

# Rounds

(a) simulation setup (b) runtime performance


Figure 2: Results to verify the effectiveness of
adaptive regularization using OMMD-II in realworld online classification tasks. The two plots
compare the performance of adaptive regularization (OMMD-II) and fixed regularization (lin_opt) on protein and covtype datasets._


Figure 1: Simulation setup and results. Left: Target points ξt[1][, ξ]t[2] [cycle along the circle. At each]
round t, the Pareto set is the line segment [ξt[1][, ξ]t[2][]][,]
and PSG measures the distance between xt and
the line segment. Right: Performance comparison of OMMD-II and baselines.


In our experiments, we set T = 10, 000. To simulate the adversarial dynamic change, we further
set P [1] = 10, P [2] = 20 for the first T1 = 3, 000 rounds, and P [1] = 20, P [2] = 10 for the remaining
_T2 = 7, 000 rounds. As our goal is the track the Pareto front, we adopt the average PSG, namely_

_t_ [T ] [∆][t][(][x][t][)][/T] [, as the performance metric. Accompanying the][ lin-opt][ baseline, we also consider]
_∈_
its two variants: lin-1 which sets λ as the optimal weights for the first T1 rounds, and lin-2 which

P

set λ to be optimal regarding the last T2 rounds. The learning rates η in all algorithms and the
regularization parameter α in OMMD-II are set as what the corresponding theories suggest.

Figure 1 (right plot) shows the performance of all the examined algorithms. From the results, we
observe that OMMD-II achieves the lowest PSG, showing its ability to track the Pareto front; meanwhile, min-norm appears very unstable in the dynamic setting, even worse than linear scalarization.
In particular, by comparing OMMD-II and lin-1, we find that linear scalarization with carefully
selected weights may attain performance comparable to our algorithm during some certain phase;
however, in the dynamic setting where the pattern drifts over time, the performance of linear scalarization may become very unstable or even drop severely, while our algorithm is much more robust.

5.2 ONLINE CONVEX EXPERIMENTS: AN APPLICATION TO ADAPTIVE REGULARIZATION

In many real-world online applications, regularization is often applied to avoid overfitting. A most
common way is to add a regularization term r(x) to the loss ft(x) in each round, and optimize the
regularized loss ft(x) + σr(x) instead (McMahan, 2011). The strength σ of regularization is often
treated as a hyperparameter that needs to be decided carefully beforehand, e.g., via a grid search.
The formalism of multi-objective online learning provides an another way to realize regularization.
Since r(x) often measures the complexity of x, it can be viewed as the second objective to be
optimized. Specifically, by constructing a vectoral loss Ft(x) = (ft(x), r(x)) in each round, we can
cast the regularized online learning into a two-objective online optimization problem. Compared to
the previous approach with a fixed strength σ, in our approach, the strength is implied by the weights
in gradient composition, namely σt = λ[2]t _[/λ][1]t_ [, which is adaptive at each round][ t][.]

We run experiments on two online benchmark datasets. (i) protein: A bioinformatics dataset for
protein type classification (Wang, 2002), which has 17 thousand instances with 357 features. (ii)
_covtype: A biological dataset collected from a non-stationary environment, whose goal is to predict_
the cover type of forests at a particular location (Blackard and Dean, 1999), which has 50 thousand
instances with 54 features. For both classification tasks, we use the logistic loss as the first objective,
and the squared L2-norm of model parameters (i.e., the L2-regularizer) as the second objective.

In the experiments, we adopt L2-norm balls as the decision set and set the diameter K = 10. For
OMMD-II, the parameter α is simply set as 0.2. For fixed regularization, the strength σ = λ[2]t _[/λ][1]t_ [is]
determined by a grid search over (λ[1]t _[, λ][2]t_ [)][ ∈] [∆][2][, and we denote this method as][ lin-opt][. Moreover, for]
both OMMD-II and lin-opt, learning rates η are decided via a grid search over {0.1, 0.2, . . ., 2.0}.

Since the ultimate goal of regularization is to enhance predictive performance, we adopt the average
of cumulative loss, namely _t_ [T ] _[l][t][(][x][t][)][/T][ where][ l][t][(][x][t][)][ is the classification loss at round][ t][, as the]_

_∈_
performance metric. The performance of both algorithms are reported in Figure 2. The results show
that OMMD-II attains lower loss than lin-opt in all the examined tasks, which shows the superiority

[P]

of adaptive regularization using our online MOO technique over fixed regularization.


-----

|Col1|Col2|Col3|
|---|---|---|
||OMMD-II min-norm lin (0.5,0.5) lin (.75,.25)|OMMD-II min-norm lin (0.5,0.5) lin (.75,.25)|
|0 (c|20000 40000 60 # Rounds ) Task L, Test Loss||
|OMMD-II min-norm lin (0.5,0.5) lin (.75,.25)||OMMD-II min-norm lin (0.5,0.5) lin (.75,.25)|


Figure 3: Results to verify the effectiveness of OMMD-II for online deep learning. The plots show

OMMD-II OMMD-II OMMD-II

1.2 min-norm 1.0 min-norm 1.2 min-norm

1.0 lin (0.5,0.5)lin (.75,.25) 0.8 lin (0.5,0.5)lin (.75,.25) 1.0 lin (0.5,0.5)lin (.75,.25)

Average Loss 0.8 Training Loss 0.6 Test Loss 0.8

0.6 0.6

0 20000 40000 60000 0 20000 40000 60000 0 20000 40000 60000

# Rounds # Rounds # Rounds

(a) Task L, Average Cumulative Loss (b) Task L, Training Loss (c) Task L, Test Loss

1.4

1.4 OMMD-II OMMD-II OMMD-II

1.2 min-norm 1.2 min-norm 1.2 min-norm

lin (0.5,0.5) 1.0 lin (0.5,0.5) lin (0.5,0.5)

1.0 lin (.75,.25) lin (.75,.25) 1.0 lin (.75,.25)

0.8 Test Loss

Average Loss 0.8 Training Loss

0.8

0.6 0.6

0 20000 40000 60000 0 20000 40000 60000 0 20000 40000 60000

# Rounds # Rounds # Rounds

(d) Task R, Average Cumulative Loss (e) Task R, Training Loss (f) Task R, Test Loss

the average cumulative loss, training loss and test loss for both tasks (task L/R) on MultiMNIST.

5.3 ONLINE NON-CONVEX EXPERIMENTS: MULTI-TASK DEEP LEARNING

Finally, we evaluate OMMD-II in the online non-convex setting. We choose to use the MultiMNIST
dataset (Sabour et al., 2017), which is a multi-objective version of the famous MNIST dataset for
image classification and commonly used in deep multi-task learning (Sener and Koltun, 2018; Lin
et al., 2019). In MultiMNIST, each sample is constructed by putting a random image at the top-left
and another image at the bottom-right. Our goal to classify the digit on the top-left (task L) and to
classify the digit on the bottom-right (task R) at the same time.

We follow Sener and Koltun (2018)’s setup and adopt the LeNet architecture. For linear scalarization, we consider two choices of weights, namely (0.5, 0.5) and (0.75, 0.25). For all the examined
algorithms, the learning rates η are selected via a grid search over {0.0001, 0.001, 0.01, 0.1}. For
OMMD-II, the parameter α is set according to our theory. Note that, in online experiments, the sample arrives one after another in a sequential manner, which is different from stochastic optimization
where sample batches are randomly sampled from the whole training set (Sener and Koltun, 2018).

Figure 3 compares the average cumulative loss, training loss and test loss of all the examined algorithms for both tasks. Note that, the first metric is typically used in online experiments and the
last two are commonly used in stochastic experiments (Reddi et al., 2018). The results show that
OMMD-II outperforms OMMD-I (min-norm) and linear scalarization (lin) in all metrics, which
shows that our proposed algorithm is also effective in the online non-convex setting.

6 CONCLUSIONS

In this paper, we conduct a systematic study of multi-objective optimization in the online setting. We
first formulate the framework of Multi-Objective Online Convex Optimization. Then we devise the
Online Mirror Multiple Descent algorithm, which is the first gradient-based multi-objective online
learning algorithm and has a special design when tailoring multiple gradient algorithm to online
learning, namely regularized min-norm solver. Theoretically, we provide the first paradigm of regret
analysis for multi-objective online convex optimization. We finally conduct extensive experiments
to demonstrate the effectiveness of our proposed algorithm. Future works may include developing a
framework based on the Hypervolume metric, or giving an analysis of multi-objective static regret.

7 ETHICS STATEMENT

As a study on a general learning problem, our work will not incur ethical issues by itself. However,
ethical issues may arise if our learning method is improperly applied to some application fields - just
as any other general learning method if it is misused.


-----

8 REPRODUCIBILITY STATEMENT

For every theoretical statement in our paper (including proposition, lemma, theorem and corollary),
we give a detailed proof in Appendix C. The codes to reproduce our empirical results are provided
in the supplementary materials.

REFERENCES

Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for
convex optimization. Operations Research Letters, 31(3):167–175, 2003.

Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations
_research, 63(5):1227–1244, 2015._

Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and
_electronics in agriculture, 24(3):131–151, 1999._

Lucas Bradstreet. The hypervolume indicator for multi-objective optimisation: calculation and use.
University of Western Australia Perth, 2011.

Nicol`o Campolongo and Francesco Orabona. A closer look at temporal variability in dynamic online
learning. arXiv preprint arXiv:2102.07666, 2021.

Nicolo Cesa-Bianchi, Pierre Gaillard, G´abor Lugosi, and Gilles Stoltz. Mirror descent meets fixed
share (and feels no regret). arXiv preprint arXiv:1202.3323, 2012.

Kalyanmoy Deb. Multi-objective optimization. In Search methodologies, pages 403–449. Springer,
2014.

Jean-Antoine D´esid´eri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization.
_Comptes Rendus Mathematique, 350(5-6):313–318, 2012._

J¨org Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathe_matical Methods of Operations Research, 51(3):479–494, 2000._

Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex programming. In International Conference on Machine Learning, pages 579–587. PMLR, 2013.

Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv:1909.05207, 2019.

Xinyu Huang, Peng Wang, Xinjing Cheng, Dingfu Zhou, Qichuan Geng, and Ruigang Yang. The
apolloscape open dataset for autonomous driving and its application. IEEE transactions on pat_tern analysis and machine intelligence, 42(10):2702–2719, 2019._

Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398–
406, 2015.

Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses
for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision
_and pattern recognition, pages 7482–7491, 2018._

Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong. Pareto multi-task learning. In
_Thirty-third Conference on Neural Information Processing Systems (NeurIPS 2019), 2019._

Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Multi-objective generalized linear bandits.
_arXiv preprint arXiv:1905.12879, 2019a._

Weixin Lu, Yao Zhou, Guowei Wan, Shenhua Hou, and Shiyu Song. L3-net: Towards learning
based lidar localization for autonomous driving. In Proceedings of the IEEE/CVF Conference on
_Computer Vision and Pattern Recognition, pages 6389–6398, 2019b._


-----

Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi. Modeling task relationships in multi-task learning with multi-gate mixture-of-experts. In Proceedings of the 24th ACM
_SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1930–1939,_
2018a.

Xiao Ma, Liqin Zhao, Guan Huang, Zhi Wang, Zelin Hu, Xiaoqiang Zhu, and Kun Gai. Entire
space multi-task model: An effective approach for estimating post-click conversion rate. In The
_41st International ACM SIGIR Conference on Research & Development in Information Retrieval,_
pages 1137–1140, 2018b.

R Timothy Marler and Jasbir S Arora. Survey of multi-objective optimization methods for engineering. Structural and multidisciplinary optimization, 26(6):369–395, 2004.

Brendan McMahan. Follow-the-regularized-leader and mirror descent: Equivalence theorems and
l1 regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelli_gence and Statistics, pages 525–533. JMLR Workshop and Conference Proceedings, 2011._

Tadahiko Murata, Hisao Ishibuchi, et al. Moga: multi-objective genetic algorithms. In IEEE inter_national conference on evolutionary computation, volume 1, pages 289–294, 1995._

Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In
_International Conference on Learning Representations, 2018._

Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. arXiv
_preprint arXiv:1710.09829, 2017._

Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. In Proceedings
_of the 32nd International Conference on Neural Information Processing Systems, pages 525–536,_
2018.

Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments
using mirror descent. IEEE Transactions on Automatic Control, 63(3):714–725, 2017.

Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent.
_arXiv preprint arXiv:1107.4080, 2011._

Eralp Turgay, Doruk Oner, and Cem Tekin. Multi-objective contextual bandit problem with similarity information. In International Conference on Artificial Intelligence and Statistics, pages
1673–1681. PMLR, 2018.

Jung-Ying Wang. Application of support vector machines in bioinformatics. Taipei: Department of
_Computer Science and Information Engineering, National Taiwan University, 2002._

Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal
dynamic regret of online learning with true and noisy gradient. In International Conference on
_Machine Learning, pages 449–457. PMLR, 2016._

Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn.
Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems,
33, 2020.

Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments.
_arXiv preprint arXiv:1810.10815, 2018._

Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multiobjective black box optimization. In International Conference on Machine Learning, pages
11096–11105. PMLR, 2020.

Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In
_Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936,_
2003.

Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: a comparative case study
and the strength pareto approach. IEEE transactions on Evolutionary Computation, 3(4):257–
271, 1999.


-----

APPENDIX

The appendix is organized as follows. Appendix A provides more details of OMMD, including a
discussion on the lazy version of mirror descent and how to efficiently compute the composition
weights for the regularized min-norm solver. Appendix B supplements the theoretical results with
more general regret bounds for arbitrary temporal variability VT [0, ); such a general setting
is often not considered in a typical analysis of dynamic online learning (Besbes et al., 2015; Zhang ∈ _∞_
et al., 2018), but we believe that adding such general bounds will make the analysis more selfcontained. Appendix C provides detailed proofs of all theoretical claims in this work, which have
been omitted in our main paper due to the space limit.

A MORE DETAILS OF THE ALGORITHM

In this section, we provide more details to help better understand the design of OMMD.

First, we note that, our proposed OMMD is actually based on the agile version of online mirror
descent (Hazan, 2019), where the updated model directly moves to its projecting point onto the
decision set at each round. However, we can easily make an analogy and devise a lazy version of
OMMD. Specifically, we only need to use a lazy projection operation in the mirror descent step with
the composite gradient instead of the agile projection operation (line 7 in Algorithm 1). Note that,
the analysis of the lazy version is very similar to that of the agile version (Hazan, 2019).

Next, we show that, when calculating the weights λt for gradient composition, our regularized minnorm solver only need very light computation, just as the original min-norm solver in stochastic
optimization (Sener and Koltun, 2018; Lin et al., 2019). Specifically, similar to (Sener and Koltun,
2018), we first consider the setting of two objectives, namely∆2, the L1 regularizer _λ_ _λt_ 1 1 equals to 2 _λ[1]_ _λ[1]t_ 1[|][. Then the optimization problem on] m = 2. In this case, when λ, λt−[ λ]1 ∈[ at]
_∥_ _−_ _−_ _∥_ _|_ _−_ _−_
round t reduces to (since there are only two objectives, the superscripts of λ[1] and λ[1]t 1 [are omitted)]
_−_

min
_λ∈[0,1]_ _[∥][λg][1][ + (1][ −]_ _[λ][)][g][2][∥][2][ + 2][α][|][λ][ −]_ _[λ][t][−][1][|][.]_

Interestingly, we find that, the above problem also has an closed-form solution as below.

**Proposition 2. Set λL = (g2[⊤][(][g][2]** [= (][g]2[⊤][(][g][2]
_Then the above optimization problem has a closed-form solution, i.e.,[−]_ _[g][1][)+]_ _[α][)][/][∥][g][2]_ _[−]_ _[g][1][∥][2][, and][ λ][R]_ _[−]_ _[g][1][)]_ _[−]_ _[α][)][/][∥][g][2]_ _[−]_ _[g][1][∥][2][.]_


max{0, λL}, _λL ≤_ _λt−1;_
min{1, λR}, _λR ≥_ _λt−1;_
_λt−1,_ _otherwise._


_λ =_


_Proof. We solve the following two quadratic sub-problems respectively, namely,_

min
_λ∈[0,λt−1]_ _[∥][λg][1][ + (1][ −]_ _[λ][)][g][2][∥][2][ + 2][α][(][λ][t][−][1][ −]_ _[λ][)][,]_

as well as
min
_λ∈[λt−1,1]_ _[∥][λg][1][ + (1][ −]_ _[λ][)][g][2][∥][2][ + 2][α][(][λ][ −]_ _[λ][t][−][1][)][.]_

The former problem produces λ = max{min{λL, λt−1}, 0}, and the latter one gives λ =
max{min{λR, 1}, λt−1}. Therefore, the solution to the original optimization problem can then be
derived by comparing the optimal values of the two sub-problems, which gives the desired solution
in the proposition. ■

Now that we have derived the closed-form solution to the regularized min-norm solver with any
two gradients, in priciple, we can apply Sener and Koltun (2018)’s technique to efficiently compute
the solution to the solver with more than two gradients. Specifically, we can adopt the Frank-Wolfe
method, namely, iteratively choose a pair of gradients and update the composition weights with these
two gradients.


-----

B MORE DETAILS OF THEORETICAL ANALYSIS

In this section, we provide more details and highlight technical lemmas in theoretical analysis, which
are omitted in our main paper due to space limitation.

B.1 A MORE DETAILED REGRET BOUND FOR OMMD-II

In Corollary 1, we only give the order of OMMD-II’s regret bound w.r.t. the core factors m, T and
_VT . In the following theorem, we supplement a more detailed regret bound for OMMD-II which_
explicates the dependency of other factors on the regret. The proof is presented in Appendix C.

**Theorem 2. Set η =** _G[2]_ [(][ γD]GT[V][T] [)][1][/][3][ and][ α][ =][ 8][F G]VT[2][T][ 2] _. Then OMMD-II attains the following regret_


_RMOD(T_ ) ( _[γD]_
_≤_ _G[4][ )][1][/][3][ (][V]T[T][1][ )][/][1][3][/][3]_


_T_

inf
_t=1_ _λ∈∆m[(][∥∇][F][t][(][x][t][)][λ][∥][2]∗_ [+][ 8][FG]VT[2][T][ 2]

X


_∥λ −_ _λt−1∥1)_


+ 2(γDG[2])[1][/][3](VT )[1][/][3]T [2][/][3].

Note that, as we have discussed in our main paper, just like its simplified version Corollary 1, the
above theorem is derived under the assumption of ”regular” temporal variability, namely Ω(1) ≤
_VT_ _o(T_ ), which is implicitly assumed in other works for dynamic online learning (Besbes et al.,
2015; Yang et al., 2016; Campolongo and Orabona, 2021). To give a more general analysis, in the ≤
following subsection, we also provide strict regret bounds that are valid for arbitrary VT [0, ).
_∈_ _∞_

B.2 REGRET BOUNDS FOR OMMD-II UNDER ARBITRARY TEMPORAL VARIABILITY

We here provide a more strict regret bound for OMMD-II under arbitrary temporal variability VT

[0, ∞). Specifically, we first give a detailed regret bound in analogy to Theorem 2. The proof of this ∈
theorem is given in Appendix C.

**Theorem 3.it attains the regret bound In OMMD-II, set η = min{max{** _G[2]_ [(][ γD]GT[V][T] [)][1][/][3][,][ 4]G[V][2][T]T _[}][,][ 4]G[V][2][T][ }][ and][ α][ =][ 8][F G]VT[2][T][ 2]_ _. Then_


_T_ 8FG2T 2

inf _λ_ _λt_ 1 1 + _Ft(xt)λ_

[4][ )][1][/][3][ (][V]T[T][1][ )][/][1][3][/][3] _t=1_ _λ∈∆m_  _VT_ _∥_ _−_ _−_ _∥_ _∥∇_ _∥∗[2]_

X

3G
+ 2(γDG[2])[1][/][3](VT )[1][/][3]T [2][/][3], 6VT, 2 [(2][γD][)][1][/][2][T][ 1][/][2][}][.]


_RMOD(T_ ) max ( _[γD]_
_≤_ _{_ _G[4][ )][1][/][3][ (][V]T[T][1][ )][/][1][3][/][3]_


inf
_t=1_ _λ∈∆m_

X


The above bound can be rewritten into a simpler form, if we are only interested in its order w.r.t.
_m, T and VT, just as in Corollary 1._

**Corollary 2.it attains the following regret In OMMD-II, set η = min{max{** _G[2]_ [(][ γD]GT[V][T] [)][1][/][3][,][ 4]G[V][2][T]T _[}][,][ 4]G[V][2][T][ }][ and][ α][ =][ 8][F G]VT[2][T][ 2]_ _. Then_


1/3T 2/3), O(VT ), O(T 1/2)}.


_RMOD(T_ ) ≤ max{O(VT

OMITTED PROOFS


In this section, we provide the detailed proofs of Proposition 1, Lemma 1, Theorem 1 and Corollary
1 in our main paper as well as Theorem 2, Theorem 3 and Corollary 2 in the appendix.

C.1 PROOF OF PROPOSITION 1

_Proof. We first analyze the PSG measurement ∆t(xt) at each round t_ 1, . . ., T . Specifically,
_∈{_ _}_
for any comparator x ∈X, we first define the pair-wise suboptimality gap between decisions xt
and x, namely,
_δt(xt; x) = inf_
_ϵ_ 0[{][ϵ][ |][ F][t][(][x][t][)][ −] _[ϵ][1][ ⊁]_ _[F][t][(][x][)][}][.]_
_≥_


-----

Then ∆t(xt) can be evaluated via the pair-wise suboptimality gap as ∆t(xt) =
supx _X_ (Ft) δt(xt, x).
_∈P_

We then focus on the pair-wise gapSince x is a Pareto optimal decision of δt( Fxtt;, from the definition of Pareto optimality, there must exist x) w.r.t. any Pareto optimal decision x ∈Xt[∗] _[≡P][X]_ [(][F][t][)][.]
some i ∈{1, . . ., m} such that ft[i][(][x][t][)][ −] _[f][ i]t_ [(][x][)][ ≥] [0][.]

The pair-wise suboptimality gap has an equivalent expression, namely,

_δt(xt; x) =_ min _t_ [(][x][t][)][ −] _[f][ k]t_ [(][x][))][+][}][,]
_k∈{1,...,m}[{][(][f][ k]_

whereset of all unit vector in (l)+ = max{l, 0 R}, l[m] ∈, then we equivalently haveR is the truncation operator. Denote Um = {ek | 1 ≤ _k ≤_ _m} as the_

_δt(xt; x) = min_
_λ_ _m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][+][.]_
_∈U_

Note that, we here slightly abuse the truncation operator (l)+ to allow l to be a vector in R[m], which
represents the vector whose i-th coordinate equals to max{l[i], 0} for any i ∈{1, . . ., m}.

Now the calculation of δt(xt; x) becomes a minimization problem over λ ∈Um. Since Um is
a discrete set, we can apply a linear relaxation trick. Specifically, we now turn to minimize the
quantity p(λ) = λ[⊤](Ft(xt) − _Ft(x))+ over the convex curvature of Um, which is exactly the_
probability simplex ∆m = {λ ∈ R[m] _| λ ≻_ **0, ∥λ∥1 = 1}. Note that, Um contains all vertexes of**
∆m. Since inf _λ_ ∆m p(λ) is a linear optimization problem, the minimal point λ[∗]t _⊤_ must be a vertex
_∈_
of the simplex, i.e., λ[∗]t _⊤_ _m. Thus the relaxed problem is equivalent to the original problem,_
_∈U_
namely,
min inf
_λ_ _m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][+][ =]_ _λ_ ∆m _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][+][.]_
_∈U_ _∈_

For now, we have transformed the calculation of pair-wise suboptimality gap δt(xt; x) into a optimization problem of finding the minimal linear scalarization of (Ft(xt) _Ft(x))+. Hence, the PSG_
_−_
at each round t can be expressed as

∆t(xt) = sup inf
_x∈Xt[∗]_ _λ∈∆m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][+][.]_

In the above expression, the existence of truncation operator (·)+ will incur irregularity (i.e., nonlinearity) when we try to optimize the loss Ft. Suprisingly, we find that such operator can be
**dropped when we compute ∆t(xt) w.r.t. the Pareto set Xt[∗][, as shown in the following.]**

**Lemma 2. Let Xt[∗]** _[be the Pareto set of][ F][t]_ [:][ X →] [R][m][. Then for any][ x][t] _[∈X]_ _[, it holds that]_

sup inf
_x∈X_ _[∗]_ _λ∈[inf]∆m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][+][ = sup]x∈Xt[∗]_ _λ∈∆m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][.]_

_Proof. Define the alternative ”gap” metric without the truncation operator as δt[′][(][x][t][;][ x][)]_ =
inf _λ∈∆m λ[⊤](Ft(xt) −_ _Ft(x))._ Moreover, define the supremum of δt[′][(][x][t][;][ x][)][ over][ x][ ∈X]t[ ∗] [as]
∆[′]t[(][x][t][) = sup]x∈Xt[∗] _[δ]t[′][(][x][t][;][ x][)][.]_ Then from the definition of truncation operator (·)+, we have
_δ(xt; x) ≥_ _δ[′](xt; x) and ∆t(xt) ≥_ ∆[′]t[(][x][t][)][.]

It then suffices to prove that, for any givenvalue of δ[′](xt; x[∗]t [)][ can be as large as][ ∆][t][(][x] x[t][)]t[. Indeed, if this is the case, then] ∈X, there exists some certain[ ∆] x[∗]t[t][(][∈X][x][t][)][ ≤]t[ ∗] [such that the][∆]t[′] [(][x][t][)][, and]
hence the two quantities ∆t(xt) and ∆[′]t[(][x][t][)][ are equal. We consider the following two cases:]

(i)directly have xt is already a Pareto optimal point of ∆t(xt) = 0. Notice that δ[′]( Fxtt;, i.e., xt) = 0 xt ∈X, and hencet[∗][. Then from the definition of PSG, we] ∆t(xt) = supx∈X ∗t _[δ][′][(][x][t][;][ x][)][ ≥]_
_δ[′](xt; xt) = 0. Consequently, the relation ∆t(xt) ≤_ ∆[′]t[(][x][t][)][ holds in this case.]

(ii) xt is not a Pareto optimal point of Ft, i.e., xt /∈Xt[∗][. Then we have][ ∆][t][(][x][t][)][ >][ 0][. Set][ ϵ][ = ∆][t][(][x][t][)][,]
and denote x[∗]t _[∈]_ [arg max]x∈Xt[∗] _[δ][t][(][x][t][;][ x][)][, then][ δ][t][(][x][t][;][ x]t[∗][) =][ ϵ >][ 0][. Therefore, from the definition of]_
_δt(xt; x[∗]t_ [)][ we know that, for any][ i][ ∈{][1][, . . ., m][}][, we have][ f][ i]t [(][x][t][)][ −] _[f][ i]t_ [(][x][∗]t [)][ ≥] _[ϵ][. Thus all entries of]_
_Ft(xt) −_ _Ft(x[∗]) are positive, and we have (Ft(xt) −_ _Ft(x[∗]))+ = Ft(xt) −_ _Ft(x[∗]). Consequently,_
we have ∆[′]t[(][x][t][) = sup]x∈Xt[∗] _[δ]t[′][(][x][t][;][ x][)][ ≥]_ _[δ][′][(][x][t][;][ x][∗]t_ [) =][ δ][(][x][t][;][ x]t[∗][) = ∆][t][(][x][t][)][.] ■


-----

From the above lemma, the PSG measurement at round t has an equivalent form as

∆t(xt) = sup inf
_x∈Xt[∗]_ _λ∈∆m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][,]_

and correspondingly, the multi-objective dynamic regret becomes


sup inf
_t=1_ _x∈Xt[∗]_ _λ∈∆m_ _[λ][⊤][(][F][t][(][x][t][)][ −]_ _[F][t][(][x][))][.]_

X


_RMOD(T_ ) =


∆t(xt) =
_t=1_

X


Since the time horizon T is finite, we can first swap the summation over t and the supremum over x,
then swap the summation over t and the infimum over λ. Then the multi-objective dynamic regret
further equals to

_T_

_RMOD(T_ ) = sup inf (λ[∗]t _⊤Ft(xt)_ _λ∗t_ _⊤Ft(x∗t_ [))][,]
_x[∗]t_ _[∈X][ ∗]t_ _[,][1][≤][t][≤][T]_ _λ[∗]1_ _[...,λ]t[∗][∈][∆][m]_ Xt=1 _−_

which proves the proposition. ■

C.2 PROOF OF LEMMA 1

_Proof. For OMMD whose the composition weights are λt at round t, before analyzing its regret_
bound, we first introduce two useful lemmas.

**Lemma 3. For OMD with stepsize η and loss λt⊤Ft(x), we have the following recursion**


_λt⊤Ft(xt)_ _λt⊤Ft(x∗t_ [)][ ≤] [1] _t_ [;][ x][t][)][ −] _[B][R][(][x]t[∗][;][ x][t][+1][)) +][ η]_ (6)
_−_ _η_ [(][B][R][(][x][∗] 2 _[∥∇][F][t][(][x][t][)][λ][t][∥]∗[2][,]_

_for any t ∈{1, . . ., T_ _}._

_Proof. Our proof is similar to the analysis of OMD in the single-objective setting (Srebro et al.,_
2011; Cesa-Bianchi et al., 2012). Specifically, fix ft = λt⊤Ft and gt = λt⊤Ft(xt). From the
convexity of ft, we have


_ft(xt) −_ _ft(x[∗]t_ [)][ ≤] _[g]t[⊤][(][x][t]_ _[−]_ _[x]t[∗][) =][ g]t[⊤][(][x][t][+1]_ _[−]_ _[x]t[∗][) +][ g]t[⊤][(][x][t]_ _[−]_ _[x][t][+1][)][.]_

From the first-order optimal condition of xt+1, for any x[′], we have
_∈X_

(η∇Ft(xt)λt + ∇R(xt+1) −∇R(xt))[⊤](x[′] _−_ _xt+1) ≥_ 0.

We set x[′] = x[∗]t [in the above inequality, and consequently derive]

_ft(xt)_ _ft(x[∗]t_ [)][ ≤] [1] _t_ _t_ [(][x][t]
_−_ _η_ [(][∇][R][(][x][t][+1][)][ −∇][R][(][x][t][))][⊤][(][x][∗] _[−]_ _[x][t][+1][) +][ g][⊤]_ _[−]_ _[x][t][+1][)][.]_


Recall the definition of Bregman divergence BR. We can check that (also see (Beck and Teboulle,
2003))

_BR(x[∗]t_ _[, x][t][)][ −]_ _[B][R][(][x]t[∗][, x][t][+1][)][ −]_ _[B][R][(][x][t][+1][, x][t][) = (][∇][R][(][x][t][+1][)][ −∇][R][(][x][t][))][⊤][(][x]t[∗]_ _[−]_ _[x][t][+1][)][.]_

Since R is 1-strongly convex, we have BR(xt+1, xt) _xt+1_ _xt_ _/2. Hence_
_≥∥_ _−_ _∥[2]_

_ft(xt)_ _ft(x[∗]t_ [)][ ≤] [1] _t_ _[, x][t][)][ −]_ _[B][R][(][x]t[∗][, x][t][+1][)][ −]_ [1] _t_ [(][x][t]
_−_ _η_ [(][B][R][(][x][∗] 2 _[∥][x][t][+1][ −]_ _[x][t][∥][2][) +][ g][⊤]_ _[−]_ _[x][t][+1][)][.]_


Moreover, from the Cauchy-Schwartz inequality we have

_gt[⊤][(][x][t]_ _[−]_ _[x][t][+1][)][ ≤]_ _[η]2_ _[∥][g][t][∥]∗[2]_ [+ 1]2η

_[∥][x][t][ −]_ _[x][t][+1][∥][2][.]_

Combining the above two inequalities, we can prove the lemma.


**Lemma 4. For an arbitrary comparator sequence u1, . . ., uT ∈X** _, we have_

_T_ _T −1_ _T_

_t=1_ _λt⊤(Ft(xt) −_ _Ft(ut)) ≤_ _[γ]η_ _t=1_ _∥ut −_ _ut+1∥_ + η [1] _[B][R][(][u][1][, x][1][) +][ η]2_ _t=1_ _∥∇Ft(xt)λt∥∗[2]_

X X X


-----

_Proof. Summing the inequality in Lemma 3 over t ∈{1, . . ., T_ _}, we have_


1
_η_ [(][B][R][(][u][t][, x][t][)][ −] _[B][R][(][u][t][, x][t][+1][)) +][ η]2[t]_ _∗_

_[∥∇][F][t][(][x][t][)][λ][t][∥][2]_


_λt⊤(Ft(xt)_ _Ft(ut))_
_−_ _≤_
_t=1_

X


_t=1_


_T −1_

_≤_ _η[1]_ (BR(ut+1, xt+1) − _BR(ut, xt+1)) + η [1]_ _[B][R][(][u][1][, x][1][) +][ η]2[t]_ _∗[.]_

_t=1_

_[∥∇][F][t][(][x][t][)][λ][t][∥][2]_

X


Recall the assumption that BR(x, z) _BR(y, z)_ _γ_ _x_ _y_ _,_ _x, y, z_ . We then obtain
_−_ _≤_ _∥_ _−_ _∥_ _∀_ _∈X_

_T_ _T −1_

_t=1_ _λt⊤(Ft(xt) −_ _Ft(ut)) ≤_ _η[1]_ _t=1_ _γ∥ut −_ _ut+1∥_ + η [1] _[B][R][(][u][1][, x][1][) +][ η]2_ _[∥∇][F][t][(][x][t][)][λ][t][∥]∗[2][,]_

X X

which proves the lemma. ■

We can now return to prove Lemma 1. Notice that, for an arbitrary comparator sequence
_u1, . . ., uT_, the Pareto tracking regret can be decomposed as
_∈X_


_λt⊤Ft(xt)_
_−_
_t=1_

X


_λt⊤Ft(xt) −_ _λt⊤Ft(x∗t_ [) =] _λt⊤Ft(xt) −_ _λt⊤Ft(ut)_ + _λt⊤Ft(ut) −_ _λt⊤Ft(x∗t_ [)]
_t=1_ _t=1_ _t=1_ _t=1_ _t=1_ _t=1_

X X X X X X

term A term B

We now instantiate the comparator sequence to be a piece-wise stationary sequence, i.e.,

| {z } | {z }


_λt⊤Ft(x∗t_ [) =]
_t=1_

X


_u1, . . ., uT_ = _w[⋆]1_ _[, . . ., w][⋆]1_ _, . . ., w[⋆]_ _T_ _T_ _, w[⋆]_ _T_ _T_ _,_
_{_ _}_  _I_ ∆ times _I_ _I⌈_ ∆ _[⌉−][1]_ _[, . . ., w]I[⋆]⌈_ ∆ _[⌉−][1]_ _I⌈_ ∆ _[⌉]_ _[, . . ., w]I[⋆]⌈_ ∆ _[⌉]_ 

∆ times (1+ ∆[T] _[−⌈]_ ∆[T] _[⌉][)∆]_ [times]

which starts with w1[∗] [and only changes for every]| {z } | [ ∆] [steps (]{z [∆] [is an integer such that]} | {z [ ∆] _[≤]}[T]_ [). More]
specifically, for any i ∈{1, . . ., ⌈T/∆⌉}, denote pi = (i − 1)∆+ 1 and qi = i∆, and then
_Ii = [pi, qi] is exactly the i-th stationary piece of the comparator sequence._

For any piece i ∈{1, . . ., ⌈T/∆⌉}, we set all ut, t ∈Ii to be the best fixed decision x[⋆]Ii [regarding]
the cumulative linearized losses during interval Ii, i.e., ut ≡ _x[⋆]Ii_ [= arg min][x][∈X] _t∈Ii_ _[λ][t]⊤Ft(x),_

for any t _i, i_ 1, . . ., _T/∆_ . Then we can apply Lemma 4 to such comparator sequence and
_∈I_ _∈{_ _⌈_ _⌉}_ P
bound the term A as


_⌈T/∆⌉−1_

_A ≤_ _[γ]η_ _i=1_ _∥uIi −_ _uIi+1_ _∥_ + η [1] _[B][R][(][u][I][1]_ _[, x][1][) +][ η]2_

X


_∥∇Ft(xt)λt∥∗[2]_
_t=1_

X


_≤_ _[γ]η_ [(][⌈] ∆[T] _[⌉−]_ [1)][D][ +][ γD]η


+ _[η]_


_T_

_∥∇Ft(xt)λt∥∗[2]_ [=][ γD]η ∆ _[⌉]_ [+][ η]2
_t=1_

X _[⌈]_ _[T]_


_∥∇Ft(xt)λt∥∗[2][.]_
_t=1_

X


Notice that, the second term B measures the difference between the cumulative linearized loss of
term, we consider such differencethe best decisions x[∗]Ii [regarding each interval] Bi restricted to any interval[ I][i][ and that of the comparators] Ii, i ∈{1, . . .,[ {] ⌈[x]T/t[∗][}]∆[. To analyze this]⌉}:

_Bi =_ _λt⊤Ft(ut) −_ _λt⊤Ft(x∗t_ [)]

_tX∈Ii_ _tX∈Ii_

= _λt⊤Ft(ut) −_ _λpi_ _⊤Fpi_ (x∗pi [) +] _λpi_ _⊤Fpi_ (x∗pi [)][ −] _λt⊤Ft(x∗t_ [)][.]

_tX∈Ii_ _tX∈Ii_ _tX∈Ii_ _tX∈Ii_

Recall our definition of ut and x[∗]t [, then we have][ P]t _i_ _[λ][t]⊤Ft(ut)_ _t_ _i_ _[λ][t]⊤Ft(x∗pi_ [)][ and]

_∈I_ _≤_ [P] _∈I_

_λpi_ _⊤Fpi_ (x∗pi [)][ ≤] _[λ][p]i_ _⊤Fpi_ (x∗t [)][. Hence we further have]

_Bi ≤_ _tX∈Ii_ _λt⊤Ft(x∗pi_ [)][ −] _tX∈Ii_ _λpi_ _⊤Fpi_ (x∗pi [) +] _tX∈Ii_ _λpi_ _⊤Fpi_ (x∗t [)][ −] _tX∈Ii_ _λt⊤Ft(x∗t_ [)][.]


-----

Moreover, for any t _i, x_, we have
_∈I_ _∈X_


_t−1_

(λk+1⊤Fk+1(x) _λk⊤Fk(x))_
_−_ _| ≤_
_k=pi_

X


_qi_

sup _λk⊤Fk(x)_ _λk+1⊤Fk+1(x)_ _._
_x_ _|_ _−_ _|_
_k=pi_ _∈X_

X


_λt⊤Ft(x)_ _λpi_ _⊤Fpi_ (x) =
_|_ _−_ _|_ _|_


Recall that Ii has at most ∆ elements, we further have

_qi_


sup _λk⊤Fk(x)_ _λk+1⊤Fk+1(x)_ _._
_x_ _|_ _−_ _|_
_k=pi_ _∈X_

X


_Bi_ 2∆
_≤_


Hence the term B can be bounded as


_⌈T/∆⌉_ _⌈T/∆⌉_

_Bi_ 2∆
_i=1_ _≤_ _i=1_

X X


_qi_

sup _λk⊤Fk(x)_ _λk+1⊤Fk+1(x)_ _._
_x_ _|_ _−_ _|_
_k=pi_ _∈X_

X


_B =_


From the definition of pi and qi, we further have


_T −1_

_B_ 2∆ sup _⊤Ft(x)_ _λt+1⊤Ft+1(x)_
_≤_ _x_ _−_ _|_

_t=1_

X _[|][λ][t]_

_T −1_

2∆ sup _⊤(Ft(x)_ _Ft+1(x))_ + (λt _λt+1)⊤Ft+1(x)_ ).
_≤_ _t=1_ _x_ [(][|][λ][t] _−_ _|_ _|_ _−_ _|_

X


Combining the above two inequalities on terms A and B, we finally derive


_⌈T/∆⌉−1_

_i=1_ _∥uIi −_ _uIi+1_ _∥_ + η [1] _[B][R][(][u][I][1]_ _[, x][1][) +][ η]2_

X


_RMOD(T_ )
_≤_ _[γ]η_


_∥∇Ft(xt)λt∥∗[2]_
_t=1_

X


_T −1_

sup( _λt⊤(Ft(x)_ _Ft+1(x))_ + (λt _λt+1)⊤Ft+1(x)_ ).
_t=1_ _x∈X_ _|_ _−_ _|_ _|_ _−_ _|_

X


+ 2∆


_uAssume that the diameter of the decision domainIi+1_ _∥≤_ _D and BR(uI1_ _, x1) ≤_ _γ∥uI1 −_ _x1∥≤ XγD is upper bounded by some. Hence we have_ _D > 0, then ∥uIi −_


_⌈T/∆⌉−1_

_i=1_ _∥uIi −_ _uIi+1_ _∥_ + η [1] _[B][R][(][u][I][1]_ _[, x][1][)][ ≤]_ _[γD]η_ [(][⌈][T/][∆][⌉−] [1) +][ γD]η

X


= _[γD]_

_η_ _[⌈]_ ∆[T] _[⌉][.]_


Further assume that each loss function Ft is coordinate-wise G-Lipschitz continuous, i.e., |ft[i][(][y][)][ −]
_ft[i][(][x][)][| ≤]_ _[G][∥][y][ −]_ _[x][∥][,][ ∀][x, y][ ∈X]_ _[, i][ ∈{][1][, . . ., m][}][. Without loss of generality, we suppose][ 0][ ∈X]_
and ft[i][(0) = 0][,][ ∀][t][ ∈{][1][, . . ., T] _[}][, i][ ∈{][1][, . . ., m][}][. Then for any][ x][ ∈X]_ [,][ |][f][ i]t [(][x][)][| ≤] _[GD][, and]_
consequently


_T −1_

(λt _λt+1)[⊤]Ft+1(x)_
_t=1_ _|_ _−_ _| ≤_

X


_T −1_

_t=1_ _∥λt −_ _λt+1∥1∥Ft+1(x)∥∞_ _≤_ 2F

X


_T −1_

_λt_ _λt+1_ 1.
_t=1_ _∥_ _−_ _∥_

X


It then remains to tackle the term _t=1_ [sup]x _t_ [(][F][t][(][x][)][ −] _[F][t][+1][(][x][))][|][. To this end, we introduce]_
the following lemma. _∈X_ _[|][λ][⊤]_

[P][T][ −][1]

**Lemma 5. For OMMD with composition weights λt ∈** ∆m at each round t, it holds that


_T −1_

sup _λt⊤(Ft(x)_ _Ft+1(x))_ 2F (T 1)
_x_ _|_ _−_ _| ≤_ _−_
_t=1_ _∈X_

X


_T −1_

_t=1_ _∥λt −_ _λt+1∥1 + VT ._

X


-----

_T_

_Proof. Denote λ =_ _k=1T_ _[λ][k]_ . We then decompose _t=1_ [sup]x _⊤(Ft(x)_ _Ft+1(x))_ as

P _∈X_ _[|][λ][t]_ _−_ _|_

_T −1_

[P][T][ −][1]

sup _λt⊤(Ft(x)_ _Ft+1(x))_
_x_ _|_ _−_ _|_
_t=1_ _∈X_

X


_T −1_

= sup (λt _λ)[⊤](Ft(x)_ _Ft+1(x)) + λ⊤(Ft(x)_ _Ft+1(x))_

_t=1_ _x∈X_ _|_ _−_ _−_ _−_ _|_

X

_T −1_ _T −1_

sup (λt _λ)[⊤](Ft(x)_ _Ft+1(x))_ + sup _λ⊤(Ft(x)_ _Ft+1(x))_ _._

_≤_ _t=1_ _x∈X_ _|_ _−_ _−_ _|_ _t=1_ _x∈X_ _|_ _−_ _|_

X X

term A term B

Since we have assumed that| _|ft[i]{z[(][x][)][| ≤]_ _[F][ for any][ x][ ∈X]}_ |[, t][ ∈{][1][, . . ., T]{z[}][, i][ ∈{][1][, . . ., m]} _[}][, it holds]_
that |ft[i][(][x][)][ −] _[f][ i]t+1[(][x][)][| ≤]_ [2][F] [. Consequently, we can bound the term A as]


_T −1_

sup
_x_
_t=1_ _∈X_

X

_T −1_

sup
_x_
_t=1_ _∈X_

X


term A =


_|_ _i=1(λ[i]t_ _[−]_ [(][λ][)][i][)(][f][ i]t [(][x][)][ −] _[f][ i]t+1[(][x][))][|]_

X

_m_

_i=1_ _|λ[i]t_ _[−]_ [(][λ][)][i][| · |][f][ i]t [(][x][)][ −] _[f][ i]t+1[(][x][)][|]_

X


_T −1_

_t=1_

X

_T −1_

_t=1_

X


_i=1_ _|λ[i]t_ _[−]_ [(][λ][)][i][| ·][ sup]x∈X _|ft[i][(][x][)][ −]_ _[f][ i]t+1[(][x][)][|]_

X


_m_ _T −1_

_λ[i]t_ 2F _λt_ _λ_ 1,
_i=1_ _|_ _[−]_ [(][λ][)][i][| ·][ 2][F][ =] _t=1_ _∥_ _−_ _∥_

X X


where λ[i]t [and][ (][λ][)][i][ represents the][ i][-th entry of][ λ][t] [and][ λ][, respectively. Also notice that for any]
_t ∈{1, . . ., T_ _},_

_T_ _T_
_k=1_ _[λ][k]_ _k=1[(][λ][k][ −]_ _[λ][t][)]_
_λt_ _λ_ 1 = _λt_ 1 = 1
_∥_ _−_ _∥_ _∥_ _T_ _−_ _∥_ _∥_ _T_ _∥_
P P

_T_ _t−1_ _T_ _t−1_
_k=1_ _s=k[(][λ][s][ −]_ _[λ][s][+1][)]_
= 1 1
_∥_ P P _T_ _∥_ _≤_ _k=1_ _s=k_ _∥_ _[λ][s][ −]T[λ][s][+1]_ _∥_

X X


_T_ _T −1_

_∥_ _[λ][s][ −]T[λ][s][+1]_

_k=1_ _s=1_

X X


_T −1_

1 =

_∥_ _[λ][s][ −]T[λ][s][+1]_ _∥_
_s=1_

X


_T −1_

_λs_ _λs+1_ 1.
_s=1_ _∥_ _−_ _∥_

X


_∥1 = T_


Therefore, we have

term A ≤

As for term B, we have


_T −1_

2F

_t=1_

X


_T −1_ _T −1_

_s=1_ _∥λs −_ _λs+1∥1 = 2F_ (T − 1) _t=1_ _∥λt −_ _λt+1∥1._

X X


_T −1_

sup _λ⊤(Ft(x)_ _Ft+1(x))_
_x_ _|_ _−_ _| ≤_
_t=1_ _∈X_

X


_T −1_

sup
_x_
_t=1_ _∈X_

X


(λ)[i] _· |ft[i][(][x][)][ −]_ _[f][ i]t+1[(][x][)][|]_
_i=1_

X


term B =


_m_ _T −1_

(λ)[i] _·_ _xsup_ _|ft[i][(][x][)][ −]_ _[f][ i]t+1[(][x][)][| ≤]_
_i=1_ _t=1_ _∈X_

X X


(λ)[i] _· VT = VT,_
_i=1_

X


where the last inequality is derived from the assumption of temporal variability, and the last equation
comes from the fact that _i=1[(][λ][)][i][ =][ 1]T_ _mi=1_ _Ts=1_ _[λ]s[i]_ [=][ 1]T _Ts=1_ _mi=1_ _[λ]t[i]_ [= 1][. Combining the]

above bounds for term A and term B, we finally prove the lemma. ■

[P][m] P P P P


-----

Plugging the above terms into the above bound for RMOD(T ), and replace the quantity ∆ _∈_
_{1, . . ., T_ _} by δ, we have_

_T −1_ _T_

_RMOD(T_ ) 2δVT + 4δFT _λt_ _λt+1_ 1 + _[η]_ _Ft(xt)λt_
_≤_ _t=1_ _∥_ _−_ _∥_ 2 _t=1_ _∥∇_ _∥∗[2]_ [+][ γD]η _δ_

_[⌈]_ _[T]_ _[⌉][,]_

X X

for any δ 1, . . ., T . Note that _t=1_ [sup]x [(][|][λ][t]⊤(Ft(x) _Ft+1(x))_ + (λt
_∈_ _{_ _}_ _∈X_ _−_ _|_ _|_ _−_
_λt+1)[⊤]Ft+1(x)_ ) = _t=1_ [sup]x [(][|][λ][t]⊤(Ft(x) _Ft+1(x))_ + (λt _λt+1)⊤Ft+1(x)_ ), because
the regret does not depend on| _FT +1∈X, λT +1. We thus prove the lemma.[P][T] −_ _|_ _|_ _−_ _|_ ■

[P][T][ −][1]

C.3 PROOF OF THEOREM 1


_T −1_

_λt_ _λt+1_ 1 + _[η]_
_t=1_ _∥_ _−_ _∥_ 2

X


_RMOD(T_ ) ≤2δVT + 4δFT


_Proof. This theorem can be directly derived from Lemma 1._

Specifically, wheninto Lemma 1 and rearranging the inequality, we can directly derive the theorem.G[4][V][2][T]T _[≤]_ _[η][ ≤]_ [4]G[V][2][T][, we can set][ δ][ =][ ηG]VT[2][T] [, which satisfies][ 1][ ≤] _[δ][ ≤]_ _[T]_ [. Plugging it]■


C.4 PROOF OF THEOREM 2

_Proof. Since this theorem is a special case of its following Theorem 3 when Ω(1)_ _VT_ _o(T_ ), it
can be proved as we derive Theorem 3 in the following subsection. _≤_ _≤_

In fact, as we assume Ω(1) _VT_ _o(T_ ), in the following derivation of Theorem 3, we are
always in the case of (i). In addition, when ≤ _≤_ Ω(1) _VT_ _o(T_ ) in Theorem 3 we exactly have
_≤_ _≤_
_η =_ _G[2]_ [(][ γD]GT[V][T] [)][1][/][3][. Hence this theorem can be directly derived from Theorem 3.] ■

C.5 PROOF OF THEOREM 3


_Proof. Denote η0 =_ _G[2]_ [(][ γD]GT[V][T] [)][1][/][3][. We consider the following three cases:]

(i) When _G[4][V][2][T]T_ _[≤]_ _[η][0][ ≤]_ [4]G[V][2][T][, we can directly apply the above lemma.]

(ii) When η0 < _G[4][V][2][T]T_ [, or equivalently][ V][T][ >][ (][ γD]8 [)][1][/][2][GT] [, we have][ η][ =][ 4]G[V][2][T]T [. Set][ δ][ = 1][ in Lemma 1,]

then it can be verified that


_T_

(α _λt_ _λt_ 1 1 + _Ft(xt)λt_
_t=1_ _∥_ _−_ _−_ _∥_ _∥∇_ _∥∗[2][) +][ γDG]4VT[2][T][ 2]_

X

_T_

_∥∇Ft(xt)λt−1∥∗[2]_
_t=1_

X

_T_

_G[2]_ = 6VT .
_t=1_

X


_RMOD(T_ ) 2VT + [2][V][T]
_≤_ _G[2]T_

4VT + [2][V][T]
_≤_ _G[2]T_

4VT + [2][V][T]
_≤_ _G[2]T_


(iii) When η0 > [4]G[V][2][T][, or equivalently][ V][T][ <][ (][ γD]8T [)][1][/][2][G][, we have][ η][ =][ 4]G[V][2][T][ . Set][ δ][ =][ T][ in Lemma 1,]

then it can be verified that


_T_

(α _λt_ _λt_ 1 1 + _Ft(xt)λt_
_t=1_ _∥_ _−_ _−_ _∥_ _∥∇_ _∥∗[2][) +][ γDG]4VT_ [2]

X


_R[P T]_ (T ) 2TVT + [2][V][T]
_≤_ _G[2]_


_G(2γD)[1][/][2]T_ [1][/][2] + [2][V][T]
_≤_ _G[2]_

_G(2γD)[1][/][2]T_ [1][/][2] + [2][V][T]
_≤_ _G[2]_

Combining (i)-(iii), we prove the theorem.


_∥∇Ft(xt)λt−1∥∗[2]_
_t=1_

X

_T_

_G[2]_ _≤_ [3]2 [G] [(2][γD][)][1][/][2][T][ 1][/][2][.]
_t=1_

X


-----

C.6 PROOF OF COROLLARY 1

_Proof. Since this corollary is a special case of its following Corollary 2 when Ω(1)_ _VT_ _o(T_ ),
it can be directly derived from Corollary 2. _≤_ _≤_

Specifically, since VT Ω(1), we have VT[1][/][3]T [2][/][3] _O(T_ [1][/][2]). Moreover, since VT _o(T_ ), we
_≥_ _≥_ _≤_
have V [1][/][3]T [2][/][3] _≥_ _o(VT ). Therefore, the dominating term in the bound of Corollary 2 is V_ [1][/][3]T [2][/][3],
which proves the corollary. ■

C.7 PROOF OF COROLLARY 2

_Proof. We start from the general bound derived in Theorem 3. Specifically, in the first regret term,_
since λt is selected to minimize α∥λt − _λt−1∥1 + ∥∇Ft(xt)λt∥2[∗]_ [at each step][ t][, we further have]

min
_λ_ ∆m[{][α][∥][λ][ −] _[λ][t][−][1][∥][1][ +][ ∥∇][F][t][(][x][t][)][λ][∥][2]∗[} ≤∥∇][F][t][(][x][t][)][λ][t][−][1][∥][2]∗_ _[≤]_ [(][∥][λ][t][−][1][∥][1][∥∇][F][t][(][x][t][)][∥][∞][)][2][ ≤] _[G][2][.]_
_∈_

Plugging it into the bound in Theorem 3 directly proves the corollary. ■

D MORE DETAILS IN MULTI-OBJECTIVE STATIC REGRET

As we have discussed before, the multi-objective static regret cannot be formulated using most
existing discrepancy metrics, since these metrics always give non-negative measurements, and the
static regret based on any non-negative metric will fail to reduce to the standard static regret RS(T )
in the single-objective setting. In this section, we give a possible form of multi-objective static regret
and provide an analysis for it.

The static regret is enlightened by the equivalent form of dynamic regret derived in Proposition 1.
Recall that in Proposition 1, the comparator x[∗]t [at each round][ t][ is selected from the Pareto set][ X][ ∗]t
of the instantaneous loss Ft; in addition, the weights λ[∗]t [at each round][ t][ is generated separately. To]
derive a static version, we can use a fixed comparator x[∗] from the Pareto set X _[∗]_ of the cumulative
loss _t_ _[F][t][ and fixed weights][ λ][∗]_ [at all rounds. Now the static regret takes]

_T_ _T_

[P]

_RMOS(T_ ) := sup inf _Ft(xt)_ _Ft(x[∗])),_
_x[∗]∈X_ _[∗]_ _λ[∗]∈∆m_ _[λ][∗⊤][(]t=1_ _−_ _t=1_

X X

where X _[∗]_ = PX ([P][T]t=1 _[F][t][)][. Note that when][ m][ = 1][, the probabilistic simplex][ ∆][m][ reduces to]_
a single point {1}, and the Pareto optimal set X _[∗]_ coincides with the optimal set of the cumulative scalar loss _t=1_ _[F][t][, i.e.,][ X][ ∗]_ [= arg min]x _[F][t][(][x][)][. Hence the multi-objective static regret]_
takes RMOS(T ) = supx∈X ∗ ([P][T]t=1 _[F][t][(][x][t][)][−][P]t[T]=1∈X[F][t][(][x][∗][)) =][ P]t[T]=1_ _[F][t][(][x][t][)][−][min][x][∈X]_ _Tt=1_ _[F][t][(][x][)][,]_
which exactly reduces to the standard static regret[P][T] _RS(T_ ) in the single-objective setting.
P

Surprisingly, with proper choices of η and α, our proposed OMMD-II algorithm can still achieve
a sublinear bound w.r.t. T for the static regret, as shown in the following theorem. Note that the
derived regret bound for OMMD-II is tight w.r.t. T, since it matches the lower bound O(√T ) of the

standard static regret in the single-objective setting (Hazan, 2019).

**Theorem 4. OMMD-II with composition weights λt attains the following static regret**


_T −1_

_λt_ _λt+1_ 1 + [1]
_t=1_ _∥_ _−_ _∥_ _η [B][R][(][x][∗][, x][1][) +][ η]2_

X


_∥∇Ft(xt)λt∥∗[2][.]_ (7)
_t=1_

X

_T_ ), which is sublinear w.r.t. T _._


_RMOS(T_ ) ≤ 2FT


_By setting η =_


2D

_√T_ _[and][ α][ =][ 4][F T]η_ _[, the regret bound reduces to][ O][(]_


-----

∆Proof.m, it holds that We start from the definition of RMOS(T ). Specifically, for any λ ∈ ∆m and λ1 . . ., λT ∈


_RMOS(T_ ) = sup inf _λ[∗⊤](Ft(xt)_ _Ft(x[∗]))_ sup
_x[∗]∈X_ _[∗]_ _λ[∗]∈∆m_ _t=1_ _−_ _≤_ _x[∗]∈X_ _[∗]_

X


_λ[⊤](Ft(xt)_ _Ft(x[∗]))_
_−_
_t=1_

X


((λ[⊤]Ft(xt) _λt⊤Ft(xt)) + λt⊤(Ft(xt)_ _Ft(x∗)) + (λt⊤Ft(x∗)_ _λ⊤Ft(x∗)))_
_−_ _−_ _−_
_t=1_

X


_λt⊤(Ft(xt)_ _Ft(x∗)) +_
_−_
_t=1_

X


_F_ _∥λ −_ _λt∥1 +_
_t=1_

X


_F_ _λ_ _λt_ 1
_∥_ _−_ _∥_
_t=1_

X


_λt⊤(Ft(xt)_ _Ft(x∗))._
_−_
_t=1_

X


_∥λ −_ _λt∥1 +_
_t=1_

X


= 2F


To tackle the second term in the above inequality, we set u1 = u2 = . . . = uT = x[∗] in Lemma 4,
which results in
_T_ _T_

_λt⊤(Ft(xt) −_ _Ft(x∗)) ≤_ _η [1]_ _[B][R][(][x][∗][, x][1][) +][ η]2_ _∥∇Ft(xt)λt∥∗[2][.]_
_t=1_ _t=1_

X X

To analyze the static regret for OMMD-II, we relate the first term _t=1_
regularization in the regularized min-norm solver at each round. Specifically, we denote the average[∥][λ][ −] _[λ][t][∥][1][ with the][ L][1]_
weights as _λ[¯] =_ _t=1_ _[λ][t][/T][ and set][ λ][ = ¯]λ in the first term. Then for any[P][T] t_ 1, . . ., T, we have
_∈{_ _}_

_T_ _T_ _t−1_
_i=1[(][λ][i][ −]_ _[λ][t][)]_ _i=1_ _k=i[(][λ][k][ −]_ _[λ][k][+1][)]_

[P]λ[T] _λt_ 1 = 1 = 1

_∥[¯] −_ _∥_ _∥_ _T_ _∥_ _∥_ _T_ _∥_
P P P

_T_ _t−1_ _T_ _T −1_

1 1

_≤_ _i=1_ _k=i_ _∥_ _[λ][k][ −]T[λ][k][+1]_ _∥_ _≤_ _i=1_ _k=1_ _∥_ _[λ][k][ −]T[λ][k][+1]_ _∥_

X X X X


_T −1_

_∥_ _[λ][k][ −]T[λ][k][+1]_
_k=1_

X


_T −1_

_λt_ _λt+1_ 1.
_t=1_ _∥_ _−_ _∥_

X


= T


_∥1 =_


Consequently, the static regret can be bounded as


_T −1_

_λt_ _λt+1_ 1 + [1]
_t=1_ _∥_ _−_ _∥_ _η [B][R][(][x][∗][, x][1][) +][ η]2_

X


_∥∇Ft(xt)λt∥∗[2]_
_t=1_

X


_RMOS(T_ ) ≤ 2F


_t=1_


_T −1_

_λt_ _λt+1_ 1 + [1]
_t=1_ _∥_ _−_ _∥_ _η [B][R][(][x][∗][, x][1][) +][ η]2_

X


_∥∇Ft(xt)λt∥∗[2][,]_
_t=1_

X


= 2FT


which proves the full static regret bound. Now we prove the reduced bound. From the full bound,
we equivalently have


_RMOS(T_ ) ≤ _η [1]_ _[B][R][(][x][∗][, x][1][) +][ η]2_


_T_

(∥∇Ft(xt)λt∥∗[2] [+ 4][FT]η
_t=1_

X


_∥λt −_ _λt−1∥1)._


We now set λ = [4][F T]η in OMMD-II, and specify λt to be the composition weights generated by the

algorithm at round t. Then we know that λt ∈ arg minλ∈∆t ∥∇Ft(xt)λ∥∗[2] [+][ 4][F T]η _[∥][λ][ −]_ _[λ][t][−][1][∥][1][. In]_

particular, we havethat _∥∇Ft(xt)λt∥∗[2]_ [+][ 4][F T]η _[∥][λ][t][ −]_ _[λ][t][−][1][∥][1][ ≤∥∇][F][t][(][x][t][)][λ][t][−][1][∥]∗[2][. Therefore, it holds]_


_RMOS(T_ ) ≤ _η [1]_ _[B][R][(][x][∗][, x][1][) +][ η]2_

Utilize Assumption 1 and Assumption 3, and set η =


_∥∇Ft(xt)λt−1∥∗[2][.]_
_t=1_

X

_G√√2DT_ [, then we have]


_RMOS(T_ ) ≤ _η [1]_ _[B][R][(][x][∗][, x][1][) +][ η]2_

which proves the reduced bound.


_∥∇Ft(xt)λt−1∥∗[2]_ _[≤]_ _[G]_
_t=1_

X


2DT,


-----

𝐹! [𝑥]%&'(

𝑥%&'( = (−1, 0) 𝑥! = 𝐹! 𝑥! = 0, 0

𝐹! [𝑥]"#$

2𝑥[)] −𝑥[*]
𝐹! [𝑥][)][, 𝑥][*][ =], [2𝑥][*][ −𝑥][)]

3 3

𝒫!∗

𝑥"#$ = (−1, −1) 𝒳!∗


Figure 4: Illustration of an example in which the projection-based metric ∆[proj]t fails to measure the
Pareto optimality of the generated decision xt. The light blue area and the orange area represent the
decision set and its image set Ft( ), respectively. The blue line segments constitute the Pareto
_X_ _X_
optimal set Xt[∗][. The red line segments constitute the Pareto front][ P]t[∗][. As shown in the plot, in this]
example, the projection-based metric ∆[proj]t compares Ft(xt) with the farthest point Ft(xproj) in
the Pareto front; the comparator xproj does not even dominate xt. In contrast, PSG compares Ft(xt)
with the nearest point Ft(xP SG) in the Pareto front; the comparator xP SG indeed dominates xt.

Note that the newly introduced static regret is no longer based on PSG. It can be understood as induced from a new discrepancy metric δ(xt; x[∗], Ft, λ[∗]) = (λ[∗])[⊤](Ft(xt) _Ft(x[∗])), where λ[∗]_ ∆m.
We thus have RMOS(T ) = supx∗∈X ∗ inf _λ∗∈∆m_ _Tt=1_ _[δ][(][x][t][;][ x][∗][, F][t][, λ][∗][)][. Such a metric compares the]−_ _∈_
able to produce a negative value whengenerated decision xt at each round with the fixed comparator xt dominatesP _x[∗]_ regarding the instantaneous loss x[∗] _∈X_ _[∗]. Hence, in particular, it is Ft, making_
it a general extension of PSG. Although this property is desired in the definition of static regret, it is
rarely utilized in the discrepancy metrics in multi-objective optimization. Thus it looks a bit strange
as a Pareto suboptimality metric and hence its physical meaning needs to be justified further. Besides, there are undoubtedly many other possible ways to define such metrics. Therefore, regarding
the multi-objective static regret, much work remains to be done in the future. We hope our initial
attempt paves the way for future research.

E DISCUSSION ON AN ALTERNATIVE METRIC BASED ON PROJECTION

In this section, we discuss an alternative discrepancy metric based on projection onto the Pareto
optimal set. Then we explain why it is unsuitable to measure the Pareto suboptimality in some
cases.

The metric is formulated as follows, which we term ∆[proj]t . At each round t, we project the generated
decision xt onto the Pareto optimal set Xt[∗][, namely][ x][proj] _[∈]_ [arg min]x[′]∈Xt[∗] _[∥][x][t]_ _[−][x][′][∥][2][, and then mea-]_
sure the Euclidean distance between Ft(xt) and Ft(xproj), i.e., ∆[proj]t (xt) = _Ft(xt)_ _Ft(xproj)_ 2.
_∥_ _−_ _∥_
Different from the PSG metric ∆t that directly measures the distance between the actual loss Ft(xt)
and the entire Pareto front Pt[∗] [in the loss space, the projection-based metric][ ∆]t[proj] only compares
the actual loss Ft(xt) with the loss Ft(xproj) evaluated at a single comparator xproj.

In intuition, ∆[proj]t ignores the landscape of the Pareto front, since the choice of xproj only depends
on the Pareto set, whose structure in the decision domain does not necessarily align with the landscape of the Pareto front in the loss space. Therefore, the comparator xproj may not be a good point
to measure the Pareto suboptimality of xt in the loss space. In comparison, PSG directly compares


-----

_Ft(xt) with the entire Pareto front, thus is always able to measure the Pareto suboptimality of the_
generated decision xt.

In the following, we provide an example in the two-objective convex setting to corroborate this
point. In our example, the loss Ft(xproj) induced by the projected decision xproj is actually the
most remote point from Ft(xt) in the Pareto front Pt[∗][. Moreover, for the second objective, we have]
_ft[2][(][x][proj][)][ > f][ 2]t_ [(][x][t][)][. Therefore,][ x][proj] [is not a proper point to measure the Pareto suboptimality]
of xt regarding Pt[∗][. Notably, measuring the Euclidean distance between][ F][t][(][x][proj][)][ and][ F][t][(][x][t][)][ is]
meaningless, since xproj performs even worse than xt in the second objective.

Concretely, we consider the decision set X = {(x[1], x[2]) | −1 ≤ _x[1]_ _≤_ 0, −1 ≤ _x[2]_ _≤_ 0}, which is a
rectangle in R[2]. We assume there are two objectives, and at round t, the loss function Ft : X → R[2]

takes Ft(x[1], x[2]) = ( [2][x][1]3[−][x][2] _,_ [2][x][2]3[−][x][1] ). Since Ft is a linear transformation, it is convex. The decision

set and the image set Ft( ) are shown in Figure. It is easy to verify that, the Pareto optimal
_X_ _X_
set Xt[∗] [=][ {][(][−][1][, x][2][)][ | −][1][ ≤] _[x][2][ ≤]_ [0][} ∪{][(][x][1][,][ −][1)][ | −][1][ ≤] _[x][1][ ≤]_ [0][}][, which consists of two]
line segments. We assume the generated decision xt = (0, 0) at this round t, which incurs the
loss Ft(xt) = (0, 0). Then the projection of xt on the Pareto set is xproj = (−1, 0) or (0, −1).
Due to symmetry, we only consider xproj = (−1, 0), then the loss evaluated at the comparator is
_Ft(xproj) = (−_ [2]3 _[,][ 1]3_ [)][. From the plot in Figure, it is obvious that][ F][t][(][x][proj][)][ is the most remote point]

from Ft(xt) in the Pareto front. Moreover, regarding the second objective, ft[2][(][x][proj][)][ > f][ 2]t [(][x][t][)][,]
which means xproj does not even dominate xt.

As a comparison, we also investigate PSG in the above example. Recall that, in Proposition 1, PSG
_f∆t[i]t[(]([x]x[))]t)[. It is easy to verify that] equals supx∈X ∗t_ [inf] _[λ][∈][∆][2][ λ][ ∆][⊤][t][(][(][F][x][t][t][(][) =][x][t][)][−]13[F][t][and the comparator][(][x][))][, or equivalently][ x][ sup]t[∗]_ [attaining the supremum is][x][∈X][ ∗]t [min][i][∈{][1][,][2][}][(][f][ i]t [(][x][t][)][−]
(−1, −1), which we denote as xP SG. Then the compared loss Ft(xP SG) = (− [1]3 _[,][ −]_ [1]3 [)][, which]

is exactly the closest point to Ft(xt) in the Pareto front. Moreover, xP SG dominates xt. Hence,
compared to the projection-based metric ∆[proj]t that compares Ft(xt) with the most remote point
in the Pareto front, PSG is obviously more reasonable to measure the Pareto suboptimality in the
multi-objective setting.


-----

