summaries: In the standard online learning model, the aim of the learning algorithm is to minimize its cumulative regret, defined by the difference in cumulative losses between the algorithm and the best decision taken with the benefit of insight in some reference set. In the generalized model of “multi-objective” online learning, the feedback is no longer a single scalar, but a vector of losses, each defined for a distinct objective. The performance of the learning algorithm is often defined in terms of “Pareto regret”, for which each instantaneous regret is captured by the notion of Pareto Suboptimality Gap (PSG). Although multi-objective online learning has been studied in the (possibly contextual and linear) bandit setting, many questions remain open. Notably, this paper focuses on the full-information setting where a vector-valued loss function is supplied at the end of each round. Based on the Online Mirror Descent (OMD) paradigm, two versions of multi-objective OMD are provided and analyzed for the dynamic version of Pareto regret (the static version being left as an open issue). Comparative experiments for both versions are performed on several benchmarks.  The paper formulates a novel framework for multi-objective online convex optimization. The novel framework, similarly to the single-objective online convex optimization framework, can be viewed as a two players repeated game where at each round the online learner selects a point $x_t$ and the (possibly adversarial) environment selects a vector valued loss function $F_t (\cdot )$. To extend the notion of regret to the multi-objective setting at each round the suboptimality of $x_t$ is measured using the Pareto suboptimality gap (PSG). Two algorithms (OMMD-I and OMMD-II) which upper bound the extension of the dynamic regret in the multi-objective setting are designed. The two algorithms can be viewed as extensions of the min-norm method for offline multi-objective optimization in the online setting. In both algorithms a composite gradient, which is a convex combination of the descent directions for every objective, is calculated. This composite gradient is used to select, together with a Bregman reguralization, the descent direction and consequently the point $x_{t+1}$. The main difference between the two algorithms OMMD-I and OMMD-II is that in the latter the composition of the descent directions in two consecutive rounds will possibly be "more similar" (due to the regularization term $|| \lambda - \lambda_{t-1}||_1$).  1. This paper introduces the problem of multi-objective online convex optimization. 2. The authors propose to use PSG as the performance metric, and show that it is related to the dynamic regret.  3. The authors develop algorithms that enjoy sublinear multi-objective regret, and also conduct experiments to show the effectiveness of the proposed methods.  The paper studies the problem of multi-objective optimization in an online setting, where the objective functions are time-varying. An algorithm is proposed to solve this problem. The algorithm queries the gradient of all objective functions, and returns a convex combination of these gradients as the input to the mirror descent algorithm. The performance of the algorithm is measured compared to a sequence of Pareto optimal points, where a single component of the loss vector cannot be improved without causing harm to the other components. Under some set of assumptions, Theorem 1 provides an upper bound on the dynamic regret of the algorithm. 
abstractText: 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.
references.authors: Amir Beck Marc Teboulle
references.title: Mirror descent and nonlinear projected subgradient methods for convex optimization
references.venue: Operations Research Letters,
references.authors: Omar Besbes Yonatan Gur Assaf Zeevi
references.title: Non-stationary stochastic optimization
references.venue: Operations research,
references.authors: Jock A Blackard Denis J Dean
references.title: Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables
references.venue: Computers and electronics in agriculture,
references.authors: Lucas Bradstreet
references.title: The hypervolume indicator for multi-objective optimisation: calculation and use
references.venue: University of Western Australia Perth,
references.authors: Nicolò Campolongo Francesco Orabona
references.title: A closer look at temporal variability in dynamic online learning
references.venue: arXiv preprint arXiv:2102.07666,
references.authors: Nicolo Cesa-Bianchi Pierre Gaillard Gábor Lugosi Gilles Stoltz
references.title: Mirror descent meets fixed share (and feels no regret)
references.venue: arXiv preprint arXiv:1202.3323,
references.authors: Kalyanmoy Deb
references.title: Multi-objective optimization. In Search methodologies, pages 403–449
references.authors: Jean-Antoine Désidéri
references.title: Multiple-gradient descent algorithm (mgda) for multiobjective optimization
references.venue: Comptes Rendus Mathematique,
references.authors: Jörg Fliege Benar Fux Svaiter
references.title: Steepest descent methods for multicriteria optimization
references.venue: Mathematical Methods of Operations Research,
references.authors: Eric Hall Rebecca Willett
references.title: Dynamical models and tracking regret in online convex programming
references.venue: In International Conference on Machine Learning,
references.authors: Elad Hazan
references.title: Introduction to online convex optimization
references.venue: arXiv preprint arXiv:1909.05207,
references.authors: Xinyu Huang Peng Wang Xinjing Cheng Dingfu Zhou Qichuan Geng Ruigang Yang
references.title: The apolloscape open dataset for autonomous driving and its application
references.venue: IEEE transactions on pattern analysis and machine intelligence,
references.authors: Ali Jadbabaie Alexander Rakhlin Shahin Shahrampour Karthik Sridharan
references.title: Online optimization: Competing with dynamic comparators
references.venue: In Artificial Intelligence and Statistics,
references.authors: Alex Kendall Yarin Gal Roberto Cipolla
references.title: Multi-task learning using uncertainty to weigh losses for scene geometry and semantics
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Xi Lin Hui-Ling Zhen Zhenhua Li Qingfu Zhang Sam Kwong
references.title: Pareto multi-task learning
references.venue: In Thirty-third Conference on Neural Information Processing Systems (NeurIPS
references.authors: Shiyin Lu Guanghui Wang Yao Hu Lijun Zhang
references.title: Multi-objective generalized linear bandits
references.venue: arXiv preprint arXiv:1905.12879,
references.authors: Weixin Lu Yao Zhou Guowei Wan Shenhua Hou Shiyu Song
references.title: L3-net: Towards learning based lidar localization for autonomous driving
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Jiaqi Ma Zhe Zhao Xinyang Yi Jilin Chen Lichan Hong Ed H Chi
references.title: Modeling task relationships in multi-task learning with multi-gate mixture-of-experts
references.venue: In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Xiao Ma Liqin Zhao Guan Huang Zhi Wang Zelin Hu Xiaoqiang Zhu Kun Gai
references.title: Entire space multi-task model: An effective approach for estimating post-click conversion rate
references.venue: In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval,
references.authors: R Timothy Marler Jasbir S Arora
references.title: Survey of multi-objective optimization methods for engineering
references.venue: Structural and multidisciplinary optimization,
references.authors: Brendan McMahan
references.title: Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization
references.venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,
references.authors: Tadahiko Murata Hisao Ishibuchi
references.title: Moga: multi-objective genetic algorithms
references.venue: In IEEE international conference on evolutionary computation,
references.authors: Sashank J Reddi Satyen Kale Sanjiv Kumar
references.title: On the convergence of adam and beyond
references.venue: In International Conference on Learning Representations,
references.authors: Sara Sabour Nicholas Frosst Geoffrey E Hinton
references.title: Dynamic routing between capsules
references.venue: arXiv preprint arXiv:1710.09829,
references.authors: Ozan Sener Vladlen Koltun
references.title: Multi-task learning as multi-objective optimization
references.venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,
references.authors: Shahin Shahrampour Ali Jadbabaie
references.title: Distributed online optimization in dynamic environments using mirror descent
references.venue: IEEE Transactions on Automatic Control,
references.authors: Nathan Srebro Karthik Sridharan Ambuj Tewari
references.title: On the universality of online mirror descent
references.venue: arXiv preprint arXiv:1107.4080,
references.authors: Eralp Turgay Doruk Oner Cem Tekin
references.title: Multi-objective contextual bandit problem with similarity information
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Jung-Ying Wang
references.title: Application of support vector machines in bioinformatics
references.venue: Taipei: Department of Computer Science and Information Engineering,
references.authors: Tianbao Yang Lijun Zhang Rong Jin Jinfeng Yi
references.title: Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient
references.venue: In International Conference on Machine Learning,
references.authors: Tianhe Yu Saurabh Kumar Abhishek Gupta Sergey Levine Karol Hausman Chelsea Finn
references.title: Gradient surgery for multi-task learning
references.venue: Advances in Neural Information Processing Systems,
references.authors: Lijun Zhang Shiyin Lu Zhi-Hua Zhou
references.title: Adaptive online learning in dynamic environments
references.venue: arXiv preprint arXiv:1810.10815,
references.authors: Richard Zhang Daniel Golovin
references.title: Random hypervolume scalarizations for provable multiobjective black box optimization
references.venue: In International Conference on Machine Learning,
references.authors: Martin Zinkevich
references.title: Online convex programming and generalized infinitesimal gradient ascent
references.venue: In Proceedings of the 20th international conference on machine learning (icml-03),
references.authors: Eckart Zitzler Lothar Thiele
references.title: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach
references.venue: IEEE transactions on Evolutionary Computation,
references.authors: Sener Koltun Lin
references.title: 2019). Specifically, similar to (Sener and Koltun, 2018), we first consider the setting of two objectives, namely m = 2. In this case, when λ, λt−1 ∈ ∆2, the L1 regularizer ∥λ− λt−1∥1 equals to 2|λ1
references.authors: T}. Proof
references.title: Our proof is similar to the analysis of OMD in the single-objective setting
references.venue: (Srebro et al.,
sections.heading: 1 INTRODUCTION
sections.text: 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 (Désidéri, 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 (Désidéri, 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 (Désidéri, 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(V 1/3T 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.
sections.heading: 2 PRELIMINARIES
sections.text: In this section, we briefly review the necessary background knowledge of online convex optimization and multi-objective optimization.
sections.heading: 2.1 ONLINE CONVEX OPTIMIZATION
sections.text: 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 ⊂ Rn. 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.,
  RS(T ) = T∑ t=1 ft(xt)− min x∗∈X T∑ t=1 ft(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.,
  RD(T ) = T∑ t=1 ft(xt)− T∑ t=1 min x∗t∈X ft(x ∗ t ).
  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 = argmin x∈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).
sections.heading: 2.2 MULTI-OBJECTIVE OPTIMIZATION
sections.text: 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 = (h1, . . . , hm)⊤ as objectives, where m ≥ 2 and hi : 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 hi(x) ≤ hi(x′) for all i, and there exists one i such that hi(x) < hi(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 ∈ argminx∈K h1(x), is Pareto optimal. Different Pareto optimal solutions reflect different trade-offs among the objectives (Sener and Koltun, 2018; Lin et al., 2019). Definition 2 (Pareto front). (a) All Pareto optimal solutions form the Pareto set, denoted as PK(H). (b) The image of PK(H) constitutes the Pareto front, denoted as P(H) = {H(x) | x ∈ PK(H)}.
  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′′∈Q h(z′′) is directly the discrepancy measure. However, in MOO with more than one loss, for any x ∈ K, the loss gap H(x) − H(x′′), where x′′ ∈ PK(H), is a vector. 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 Rm, i.e.,
  ∆(x;K∗, H) = inf ϵ≥0 ϵ s.t. ∀x′′ ∈ K∗,∃i ∈ {1, . . . ,m}, hi(x)− ϵ < hi(x′′).
  Clearly, PSG is a distance-based discrepancy metric that motivated from a purely geometric viewpoint. In practice, the comparator set K∗ is often set to be the Pareto set PK(H) (Turgay et al., 2018). Then for any x ∈ K, its PSG is always non-negative and equals to zero if and only if x ∈ PK(H). Multiple Gradient Descent Algorithm (MGDA) is an offline first-order algorithm for MOO (Fliege and Svaiter, 2000; Désidéri, 2012). At each iteration l ∈ {1, . . . , L}, where L is the maximum number of iterations, it first computes the gradient ∇hi(xl) for each objective i ∈ {1, . . . ,m}, and then derive the composite gradient gl = ∑m i=1 λ i l∇hi(xl) 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 determination of the weights λl = (λ1l , . . . , λ m l ) for the gradient composition, which is given as
  λl = argmin λl∈∆m ∥ m∑ i=1 λil∇hi(xl)∥22,
  where ∆m = {λ ∈ Rm | λi ≥ 0, i ∈ {1, . . . ,m}, and ∑m i=1 λ i = 1} denotes the probabilistic simplex in Rm. 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. Existing works (Désidéri, 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 hi are convex functions).
sections.heading: 3 MULTI-OBJECTIVE ONLINE CONVEX OPTIMIZATION
sections.text: 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 ⊂ Rn. Then the adversary replies the decision with a vectoral loss function Ft(x) : X → Rm, where its i-th component f it (x) : X → R belongs to the i-th objective, and the learner suffers the loss Ft(xt) ∈ Rm. The goal of the learner is to generate a sequence of decisions {xt | 1 ≤ t ≤ T} so that the cumulative loss ∑T t=1 Ft(xt) can be optimized.
  Recall that, in the single-objective setting, the performance metric R(T ) = ∑T
  t=1 ft(xt) − ft(x∗t ), i.e., the regret, compares the actual decisions xt with some comparator x∗t ∈ X at each round t ∈ {1, . . . , T}. In general, there are two common types of regret which differ in the comparators, i.e., 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 ≡ x∗ ∈ argminx∈X ∑T t=1 ft(x). For the dynamic regret, the comparator x ∗ t at each round t is selected as the optimal decision w.r.t. the instantaneous loss ft at that round, i.e., x∗t ∈ argminx∈X ft(x).
  In analogy, in the multi-objective setting, we define the regret as R(T ) = ∑T
  t=1 ∆t, where the quantity ∆t at each round t compares the actual decisions xt with some comparator x∗t ∈ X . However, in general, no single decision can optimize all the objectives at the same time. Hence, it is reasonable to compare xt with all the Pareto optimal decisions that constitute a comparator set X ∗t ⊂ X . Specifically, we introduce the Pareto suboptimality gap (PSG) (Turgay et al., 2018), i.e.,
  ∆(xt;X ∗t , Ft) = inf ϵ≥0 ϵ s.t. ∀x′′ ∈ X ∗t ,∃i ∈ {1, . . . ,m}, f it (xt)− ϵ < f it (x′′). (1)
  Then the multi-objective regret can be defined as R(T ) = ∑T
  t=1 ∆(xt;X ∗t , Ft). Given the above definitions, we can formulate the multi-objective variants of the static and dynamic regret respectively, by using different comparator set X ∗t at each step. Specifically, if we set all X ∗t to be the Pareto set of the cumulative loss ∑T t=1 Ft, then we can formulate a regret metric termed the multiobjective static regret (recall that PX(F ) denotes the Pareto set of F )
  RMOS(T ) := T∑ t=1 ∆(xt;X ∗, Ft), where X ∗ = PX( T∑ t=1 Ft).
  Alternatively, if we set X ∗t to be the Pareto set of the instantaneous loss Ft at each round t, then we can give a regret metric termed the multi-objective dynamic regret
  RMOD(T ) := T∑ t=1 ∆(xt;X ∗t , Ft), where X ∗t = PX(Ft),∀t ∈ {1, . . . , 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 f it (x
  ′′),∀x′′ ∈ X ∗t . 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 X ∗t 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.,
  RMOD(T ) = sup x∗t∈X∗t ,1≤t≤T inf λ∗1 ...,λ ∗ t∈∆m T∑ t=1 (λ∗t ⊤Ft(xt)− λ∗t ⊤Ft(x ∗ t )), (2)
  where ∆m represents the probabilistic simplex in Rm.
  Remark. In the single-objective setting where m = 1, the probabilistic simplex ∆m collapses into a single point {1}. Moreover, the Pareto set X ∗t of the scalar loss function Ft : X → R reduces to the optimal set argminx∈X Ft(x). Hence we have RMOD(T ) = ∑T t=1(Ft(xt) − minx∈X Ft(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 is the reason. In RMOS, the comparator set X ∗ is the Pareto set of the cumulative loss ∑T t=1 Ft rather than the instantaneous loss Ft. Hence, at some specific round t, the actual decision xt may Pareto dominate all decisions in X ∗ w.r.t. the instantaneous Ft, and so we expect the discrepancy metric ∆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∗ ∑T t=1 max{Ft(xt)−Ft(x∗), 0}, which
  can be much looser than the static regret RS(T ) = supx∗∈X∗ ∑T
  t=1 Ft(xt)−Ft(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.
sections.heading: 4 ONLINE MIRROR MULTIPLE DESCENT
sections.text: In this section, we first present the Online Mirror Multiple Descent (OMMD) algorithm, then provide theoretical analysis for it.
sections.heading: 4.1 THE ALGORITHM
sections.text: The protocol of OMMD is given in Algorithm 1. At each round t, the learner computes the gradient for each loss ∇f it (xt), 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) = [∇f1t (xt), . . . ,∇fmt (xt)] ∈ Rn×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 η, regulariza-
  tion function R. 2: Initialize: x1 ∈ X , λ0 ∈ ∆m. 3: for t = 1, . . . , T do 4: Predict with xt and receive the vector loss function Ft : X → Rm. 5: Compute the multiple gradients ∇Ft(xt) = [∇f1t (xt), . . . ,∇fmt (xt)] ∈ Rn×m. 6: Determine the weights for the gradient composition
  λt = argmin λ∈∆m
  ∥∇Ft(xt)λ∥22; (OMMD-I) (3)
  λt = argmin λ∈∆m
  ∥∇Ft(xt)λ∥22 + α∥λ− λ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 = argmin x∈X
  η⟨gt, x⟩+BR(x, xt). (5)
  9: end for
  i.e., the min-norm method (Désidéri, 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.
sections.heading: 4.2 ANALYSIS
sections.text: 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 ⊂ Rn. Lemma 1. Suppose the diameter of the decision set X is bounded by D. Assume Ft is bounded, i.e., |f it (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
  RMOD(T ) ≤2δ T−1∑ t=1 sup x∈X |f it (x)− f it+1(x)|+ 4δFT T−1∑ t=1 ∥λt − λt+1∥1
  + η
  2 T∑ t=1 ∥∇Ft(xt)λt∥22 + γD η ⌈T δ ⌉.
  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 t=1 supx∈X |f it (x)− f it+1(x)| ≤ VT . Assumption 3 (Lipschitz continuity). For each i ∈ {1, . . . ,m}, there exists some positive and finite G such that, the i-th loss f it at each round t ∈ {1, . . . , T} is G-Lipschitz continuous w.r.t. ∥ ·∥, i.e., |f it (x)− f it (x′)| ≤ G∥x− x′∥.
  In the convex setting, Lipschitz continuity guarantees bounded gradients, i.e., ∥∇f it (x)∥∗ ≤ G for any t ∈ {1, . . . , T}, i ∈ {1, . . . ,m}, x ∈ X . We can now derive a general regret bound for OMMD. Theorem 1. Assume the step size η satisfies 4VTG2T ≤ η ≤ 4VT G2 . Then OMMD-I or OMMD-II with weights λt at each round t attains the following regret
  RMOD(T ) ≤ ηG2T
  2 +
  η
  2 T∑ t=1 (∥∇Ft(xt)λt∥22 + 8FG2T 2 VT ∥λt − λt−1∥1) + 4γDVT η2G2 .
  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 α = FG
  2T VT
  , OMMD-II adaptively selects λt to minimize the term ∥∇Ft(xt)λt∥22 + α∥λt − λ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 η = 2G ( γDVT GT ) 1/3 and α = 8FG 2T 2 VT , OMMD-II achieves the following regret
  RMOD(T ) ≤ O(V 1/3T T 2/3).
sections.heading: 5 EXPERIMENTS
sections.text: 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 (Désidéri, 2012; Sener and Koltun, 2018) to the multi-objective online setting, which has been described as OMMD-I in Algorithm 1.
sections.heading: 5.1 SIMULATION EXPERIMENTS: TRACKING THE PARETO FRONT
sections.text: In the simulation setup, the goal is to track two points ξ1t , ξ 2 t moving on the plane R2. The two points cycle along a circle with a ratius of 1, i.e., C = {ξ ∈ R2 | ∥ξ∥2 = 1}, namely, for each i ∈ {1, 2}, ξit = (cos θ i t, sin θ i t) is determined by some angle θ i t. 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 θ11 = 0 and θ21 = π/2, and iteratively generated as follows: at each round t, for each i ∈ {1, 2}, the adversary independently samples an angle δit from a Gaussian distribution N (2π/P i, 1/ √ P i), then generates the next point ξit+1 via θ i t+1 = θ i t − δit. Note that, we have Eθit+1 = θi1 + 2πt/P i, which implies that in average ξit rotates clockwise uniformly along the circle C, with a period of P i. At each round t, the learner generates a decision xt from X = {x ∈ R2 | ∥x∥2 ≤ 2}, which is a L2norm ball with a radius of 2. Then it acquires the positions of ξ1t , ξ 2 t and suffer two losses f i t (xt) = ∥xt− ξit∥2/2 for i ∈ {1, 2}. In this problem, the Pareto set of the vectoral loss ft = (f1t , f2t ) at each round t is exactly the line segment linking ξ1t and ξ 2 t , i.e., X ∗t = {λξ1t + (1 − λ)ξ2t | λ ∈ [0, 1]}. For any decision xt ∈ X , its PSG exactly equals to the squared distance between xt and the line segment. The setup and PSG measurement are summarized in Figure 1 (left plot).
  (a) simulation setup (b) runtime performance
  1 t 1
  2 t 1
  1 t
  2 t }t(xt)xt 0 2000 4000 6000 8000 10000
  # Rounds
  0.03
  0.06
  0.09
  0.12
  Av er
  ag e
  PS G
  Phase 1 Phase 2 OMMD-II min-norm lin-opt lin 1 lin 2
  Figure 1: Simulation setup and results. Left: Target points ξ1t , ξ 2 t cycle along the circle. At each round t, the Pareto set is the line segment [ξ1t , ξ 2 t ], and PSG measures the distance between xt and the line segment. Right: Performance comparison of OMMD-II and baselines.
  (a) protein (b) covtype 0 2500 5000 7500 10000 12500 # Rounds
  0.31
  0.33
  0.35
  0.37
  Av er
  ag e
  Lo ss
  OMMD-II lin-opt
  0 200000 400000 600000 # Rounds (K)
  0.14
  0.18
  0.22
  0.26
  Av er
  ag e
  Lo ss
  OMMD-II lin-opt
  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 (linopt) on protein and covtype datasets.
  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(xt)/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 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.
sections.heading: 5.2 ONLINE CONVEX EXPERIMENTS: AN APPLICATION TO ADAPTIVE REGULARIZATION
sections.text: 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 = λ2t/λ 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 σ = λ2t/λ 1 t is determined by a grid search over (λ1t , λ 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 ] lt(xt)/T where lt(xt) 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 of adaptive regularization using our online MOO technique over fixed regularization.
sections.heading: 5.3 ONLINE NON-CONVEX EXPERIMENTS: MULTI-TASK DEEP LEARNING
sections.text: 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.
sections.heading: 6 CONCLUSIONS
sections.text: 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.
sections.heading: 7 ETHICS STATEMENT
sections.text: 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.
sections.heading: 8 REPRODUCIBILITY STATEMENT
sections.text: 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.
sections.heading: APPENDIX
sections.text: 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.
sections.heading: A MORE DETAILS OF THE ALGORITHM
sections.text: 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 m = 2. In this case, when λ, λt−1 ∈ ∆2, the L1 regularizer ∥λ− λt−1∥1 equals to 2|λ1 − λ1t−1|. Then the optimization problem on λ at round t reduces to (since there are only two objectives, the superscripts of λ1 and λ1t−1 are omitted)
  min λ∈[0,1]
  ∥λg1 + (1− λ)g2∥2 + 2α|λ− λt−1|.
  Interestingly, we find that, the above problem also has an closed-form solution as below.
  Proposition 2. Set λL = (g⊤2 (g2−g1)+α)/∥g2−g1∥2, and λR = (g⊤2 (g2−g1)−α)/∥g2−g1∥2. Then the above optimization problem has a closed-form solution, i.e.,
  λ =  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]
  ∥λg1 + (1− λ)g2∥2 + 2α(λt−1 − λ),
  as well as min
  λ∈[λt−1,1] ∥λg1 + (1− λ)g2∥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.
sections.heading: B MORE DETAILS OF THEORETICAL ANALYSIS
sections.text: 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.
sections.heading: B.1 A MORE DETAILED REGRET BOUND FOR OMMD-II
sections.text: 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 η = 2G ( γDVT GT ) 1/3 and α = 8FG 2T 2 VT . Then OMMD-II attains the following regret
  RMOD(T ) ≤ ( γD
  G4 )1/3
  (VT ) 1/3
  T 1/3 T∑ t=1 inf λ∈∆m (∥∇Ft(xt)λ∥2∗ + 8FG2T 2 VT ∥λ− λt−1∥1)
  + 2(γDG2)1/3(VT ) 1/3T 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,∞).
sections.heading: B.2 REGRET BOUNDS FOR OMMD-II UNDER ARBITRARY TEMPORAL VARIABILITY
sections.text: 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. In OMMD-II, set η = min{max{ 2G ( γDVT GT ) 1/3, 4VTG2T }, 4VT G2 } and α =
  8FG2T 2
  VT . Then
  it attains the regret bound
  RMOD(T ) ≤ max{( γD
  G4 )1/3
  (VT ) 1/3
  T 1/3 T∑ t=1 inf λ∈∆m ( 8FG2T 2 VT ∥λ− λt−1∥1 + ∥∇Ft(xt)λ∥2∗ ) + 2(γDG2)1/3(VT ) 1/3T 2/3, 6VT , 3G
  2 (2γD)1/2T 1/2}.
  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. In OMMD-II, set η = min{max{ 2G ( γDVT GT ) 1/3, 4VTG2T }, 4VT G2 } and α =
  8FG2T 2
  VT . Then
  it attains the following regret
  RMOD(T ) ≤ max{O(VT 1/3T 2/3), O(VT ), O(T 1/2)}.
sections.heading: C OMITTED PROOFS
sections.text: 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.
sections.heading: C.1 PROOF OF PROPOSITION 1
sections.text: 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
  {ϵ | Ft(xt)− ϵ1 ⊁ Ft(x)}.
  Then ∆t(xt) can be evaluated via the pair-wise suboptimality gap as ∆t(xt) = supx∈PX(Ft) δt(xt, x).
  We then focus on the pair-wise gap δt(xt;x) w.r.t. any Pareto optimal decision x ∈ X ∗t ≡ PX(Ft). Since x is a Pareto optimal decision of Ft, from the definition of Pareto optimality, there must exist some i ∈ {1, . . . ,m} such that f it (xt)− f it (x) ≥ 0. The pair-wise suboptimality gap has an equivalent expression, namely,
  δt(xt;x) = min k∈{1,...,m}
  {(fkt (xt)− fkt (x))+},
  where (l)+ = max{l, 0}, l ∈ R is the truncation operator. Denote Um = {ek | 1 ≤ k ≤ m} as the set of all unit vector in Rm, then we equivalently have
  δt(xt;x) = min λ∈Um
  λ⊤(Ft(xt)− Ft(x))+.
  Note that, we here slightly abuse the truncation operator (l)+ to allow l to be a vector in Rm, which represents the vector whose i-th coordinate equals to max{li, 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 = {λ ∈ Rm | λ ≻ 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 ⊤ ∈ Um. Thus the relaxed problem is equivalent to the original problem, namely, min λ∈Um λ⊤(Ft(xt)− Ft(x))+ = inf λ∈∆m λ⊤(Ft(xt)− Ft(x))+.
  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 x∈X∗t inf λ∈∆m
  λ⊤(Ft(xt)− Ft(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 X ∗t , as shown in the following. Lemma 2. Let X ∗t be the Pareto set of Ft : X → Rm. Then for any xt ∈ X , it holds that
  sup x∈X∗ inf λ∈∆m λ⊤(Ft(xt)− Ft(x))+ = sup x∈X∗t inf λ∈∆m λ⊤(Ft(xt)− Ft(x)).
  Proof. Define the alternative ”gap” metric without the truncation operator as δ′t(xt;x) = infλ∈∆m λ
  ⊤(Ft(xt) − Ft(x)). Moreover, define the supremum of δ′t(xt;x) over x ∈ X ∗t as ∆′t(xt) = supx∈X∗t δ ′ t(xt;x). Then from the definition of truncation operator (·)+, we have δ(xt;x) ≥ δ′(xt;x) and ∆t(xt) ≥ ∆′t(xt). It then suffices to prove that, for any given xt ∈ X , there exists some certain x∗t ∈ X ∗t such that the value of δ′(xt;x∗t ) can be as large as ∆t(xt). Indeed, if this is the case, then ∆t(xt) ≤ ∆′t(xt), and hence the two quantities ∆t(xt) and ∆′t(xt) are equal. We consider the following two cases:
  (i) xt is already a Pareto optimal point of Ft, i.e., xt ∈ X ∗t . Then from the definition of PSG, we directly have ∆t(xt) = 0. Notice that δ′(xt;xt) = 0, and hence ∆t(xt) = supx∈X∗t δ
  ′(xt;x) ≥ δ′(xt;xt) = 0. Consequently, the relation ∆t(xt) ≤ ∆′t(xt) holds in this case. (ii) xt is not a Pareto optimal point of Ft, i.e., xt /∈ X ∗t . Then we have ∆t(xt) > 0. Set ϵ = ∆t(xt), and denote x∗t ∈ argmaxx∈X∗t δt(xt;x), then δt(xt;x ∗ t ) = ϵ > 0. Therefore, from the definition of δt(xt;x ∗ t ) we know that, for any i ∈ {1, . . . ,m}, we have f it (xt)− f it (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(xt) = supx∈X∗t δ ′ t(xt;x) ≥ δ′(xt;x∗t ) = δ(xt;x∗t ) = ∆t(xt). ■
  From the above lemma, the PSG measurement at round t has an equivalent form as
  ∆t(xt) = sup x∈X∗t inf λ∈∆m
  λ⊤(Ft(xt)− Ft(x)),
  and correspondingly, the multi-objective dynamic regret becomes
  RMOD(T ) = T∑ t=1 ∆t(xt) = T∑ t=1 sup x∈X∗t inf λ∈∆m λ⊤(Ft(xt)− Ft(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
  RMOD(T ) = sup x∗t∈X∗t ,1≤t≤T inf λ∗1 ...,λ ∗ t∈∆m T∑ t=1 (λ∗t ⊤Ft(xt)− λ∗t ⊤Ft(x ∗ t )),
  which proves the proposition. ■
sections.heading: C.2 PROOF OF LEMMA 1
sections.text: 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 η (BR(x ∗ t ;xt)−BR(x∗t ;xt+1)) + η 2 ∥∇Ft(xt)λt∥2∗, (6)
  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 (xt − x∗t ) = g⊤t (xt+1 − x∗t ) + g⊤t (xt − xt+1). From the first-order optimal condition of xt+1, for any x′ ∈ X , we have
  (η∇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
  η (∇R(xt+1)−∇R(xt))⊤(x∗t − xt+1) + g⊤t (xt − xt+1).
  Recall the definition of Bregman divergence BR. We can check that (also see (Beck and Teboulle, 2003))
  BR(x ∗ t , xt)−BR(x∗t , xt+1)−BR(xt+1, xt) = (∇R(xt+1)−∇R(xt))⊤(x∗t − xt+1).
  Since R is 1-strongly convex, we have BR(xt+1, xt) ≥ ∥xt+1 − xt∥2/2. Hence
  ft(xt)− ft(x∗t ) ≤ 1
  η (BR(x
  ∗ t , xt)−BR(x∗t , xt+1)−
  1 2 ∥xt+1 − xt∥2) + g⊤t (xt − xt+1).
  Moreover, from the Cauchy-Schwartz inequality we have
  g⊤t (xt − xt+1) ≤ η
  2 ∥gt∥2∗ +
  1
  2η ∥xt − xt+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 ⊤(Ft(xt)− Ft(ut)) ≤
  γ
  η T−1∑ t=1 ∥ut − ut+1∥+ 1 η BR(u1, x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗
  Proof. Summing the inequality in Lemma 3 over t ∈ {1, . . . , T}, we have T∑
  t=1
  λt ⊤(Ft(xt)− Ft(ut)) ≤ T∑ t=1 1 η (BR(ut, xt)−BR(ut, xt+1)) + ηt 2 ∥∇Ft(xt)λt∥2∗
  ≤ 1 η T−1∑ t=1 (BR(ut+1, xt+1)−BR(ut, xt+1)) + 1 η BR(u1, x1) + ηt 2 ∥∇Ft(xt)λt∥2∗.
  Recall the assumption that BR(x, z)−BR(y, z) ≤ γ∥x− y∥,∀x, y, z ∈ X . We then obtain T∑
  t=1
  λt ⊤(Ft(xt)− Ft(ut)) ≤
  1
  η T−1∑ t=1 γ∥ut − ut+1∥+ 1 η BR(u1, x1) + η 2 ∥∇Ft(xt)λt∥2∗,
  which proves the lemma. ■
  We can now return to prove Lemma 1. Notice that, for an arbitrary comparator sequence u1, . . . , uT ∈ X , the Pareto tracking regret can be decomposed as T∑
  t=1
  λt ⊤Ft(xt)− T∑ t=1 λt ⊤Ft(x ∗ t ) = T∑ t=1 λt ⊤Ft(xt)− T∑ t=1 λt ⊤Ft(ut)︸ ︷︷ ︸
  term A
  + T∑ t=1 λt ⊤Ft(ut)− T∑ t=1 λt ⊤Ft(x
  ∗ t )︸ ︷︷ ︸
  term B
  .
  We now instantiate the comparator sequence to be a piece-wise stationary sequence, i.e.,
  {u1, . . . , uT } = w ⋆ I1 , . . . , w ⋆ I1︸ ︷︷ ︸ ∆ times , . . . , w⋆I⌈ T ∆ ⌉−1 , . . . , w⋆I⌈ T ∆ ⌉−1︸ ︷︷ ︸
  ∆ times
  , w⋆I⌈ T ∆ ⌉ , . . . , w⋆I⌈ T ∆ ⌉︸ ︷︷ ︸
  (1+ T∆−⌈ T ∆ ⌉)∆ times  , which starts with w∗1 and only changes for every ∆ steps (∆ is an integer such that ∆ ≤ 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 = argminx∈X ∑ t∈Ii λt
  ⊤Ft(x), for any t ∈ Ii, i ∈ {1, . . . , ⌈T/∆⌉}. Then we can apply Lemma 4 to such comparator sequence and bound the term A as
  A ≤ γ η ⌈T/∆⌉−1∑ i=1 ∥uIi − uIi+1∥+ 1 η BR(uI1 , x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗
  ≤ γ η (⌈T ∆ ⌉ − 1)D + γD η + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗ = γD η ⌈T ∆ ⌉+ η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗.
  Notice that, the second term B measures the difference between the cumulative linearized loss of the best decisions x∗Ii regarding each interval Ii and that of the comparators {x ∗ t }. To analyze this term, we consider such difference Bi restricted to any interval Ii, i ∈ {1, . . . , ⌈T/∆⌉}:
  Bi = ∑ t∈Ii λt ⊤Ft(ut)− ∑ t∈Ii λt ⊤Ft(x ∗ t )
  = ∑ t∈Ii λt ⊤Ft(ut)− ∑ t∈Ii λpi ⊤Fpi(x ∗ pi) + ∑ t∈Ii λpi ⊤Fpi(x ∗ pi)− ∑ t∈Ii λt ⊤Ft(x ∗ t ).
  Recall our definition of ut and x∗t , then we have ∑ t∈Ii λt ⊤Ft(ut) ≤ ∑ t∈Ii λt ⊤Ft(x ∗ pi) and λpi ⊤Fpi(x ∗ pi) ≤ λpi ⊤Fpi(x ∗ t ). Hence we further have
  Bi ≤ ∑ t∈Ii λt ⊤Ft(x ∗ pi)− ∑ t∈Ii λpi ⊤Fpi(x ∗ pi) + ∑ t∈Ii λpi ⊤Fpi(x ∗ t )− ∑ t∈Ii λt ⊤Ft(x ∗ t ).
  Moreover, for any t ∈ Ii, x ∈ X , we have
  |λt⊤Ft(x)−λpi ⊤Fpi(x)| = | t−1∑ k=pi (λk+1 ⊤Fk+1(x)−λk⊤Fk(x))| ≤ qi∑ k=pi sup x∈X |λk⊤Fk(x)−λk+1⊤Fk+1(x)|.
  Recall that Ii has at most ∆ elements, we further have
  Bi ≤ 2∆ qi∑
  k=pi
  sup x∈X
  |λk⊤Fk(x)− λk+1⊤Fk+1(x)|.
  Hence the term B can be bounded as
  B = ⌈T/∆⌉∑ i=1 Bi ≤ 2∆ ⌈T/∆⌉∑ i=1 qi∑ k=pi sup x∈X |λk⊤Fk(x)− λk+1⊤Fk+1(x)|.
  From the definition of pi and qi, we further have
  B ≤ 2∆ T−1∑ t=1 sup x |λt⊤Ft(x)− λt+1⊤Ft+1(x)|
  ≤ 2∆ T−1∑ t=1 sup x (|λt⊤(Ft(x)− Ft+1(x))|+ |(λt − λt+1)⊤Ft+1(x)|).
  Combining the above two inequalities on terms A and B, we finally derive
  RMOD(T ) ≤ γ
  η ⌈T/∆⌉−1∑ i=1 ∥uIi − uIi+1∥+ 1 η BR(uI1 , x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗
  + 2∆ T−1∑ t=1 sup x∈X (|λt⊤(Ft(x)− Ft+1(x))|+ |(λt − λt+1)⊤Ft+1(x)|).
  Assume that the diameter of the decision domain X is upper bounded by some D > 0, then ∥uIi − uIi+1∥ ≤ D and BR(uI1 , x1) ≤ γ∥uI1 − x1∥ ≤ γD. Hence we have
  γ
  η ⌈T/∆⌉−1∑ i=1 ∥uIi − uIi+1∥+ 1 η BR(uI1 , x1) ≤ γD η (⌈T/∆⌉ − 1) + γD η = γD η ⌈T ∆ ⌉.
  Further assume that each loss function Ft is coordinate-wise G-Lipschitz continuous, i.e., |f it (y)− f it (x)| ≤ G∥y − x∥,∀x, y ∈ X , i ∈ {1, . . . ,m}. Without loss of generality, we suppose 0 ∈ X and f it (0) = 0,∀t ∈ {1, . . . , T}, i ∈ {1, . . . ,m}. Then for any x ∈ X , |f it (x)| ≤ GD, and consequently
  T−1∑ t=1 |(λt − λt+1)⊤Ft+1(x)| ≤ T−1∑ t=1 ∥λt − λt+1∥1∥Ft+1(x)∥∞ ≤ 2F T−1∑ t=1 ∥λt − λt+1∥1.
  It then remains to tackle the term ∑T−1
  t=1 supx∈X |λ⊤t (Ft(x)−Ft+1(x))|. To this end, we introduce the following lemma.
  Lemma 5. For OMMD with composition weights λt ∈ ∆m at each round t, it holds that
  T−1∑ t=1 sup x∈X |λt⊤(Ft(x)− Ft+1(x))| ≤ 2F (T − 1) T−1∑ t=1 ∥λt − λt+1∥1 + VT .
  Proof. Denote λ = ∑T
  k=1 λk T . We then decompose ∑T−1 t=1 supx∈X |λt ⊤(Ft(x)− Ft+1(x))| as
  T−1∑ t=1 sup x∈X |λt⊤(Ft(x)− Ft+1(x))|
  = T−1∑ t=1 sup x∈X |(λt − λ)⊤(Ft(x)− Ft+1(x)) + λ ⊤ (Ft(x)− Ft+1(x))|
  ≤ T−1∑ t=1 sup x∈X
  |(λt − λ)⊤(Ft(x)− Ft+1(x))|︸ ︷︷ ︸ term A +
  T−1∑ t=1 sup x∈X
  |λ⊤(Ft(x)− Ft+1(x))|︸ ︷︷ ︸ term B .
  Since we have assumed that |f it (x)| ≤ F for any x ∈ X , t ∈ {1, . . . , T}, i ∈ {1, . . . ,m}, it holds that |f it (x)− f it+1(x)| ≤ 2F . Consequently, we can bound the term A as
  term A = T−1∑ t=1 sup x∈X | m∑ i=1 (λit − (λ)i)(f it (x)− f it+1(x))|
  ≤ T−1∑ t=1 sup x∈X m∑ i=1 |λit − (λ)i| · |f it (x)− f it+1(x)|
  ≤ T−1∑ t=1 m∑ i=1 |λit − (λ)i| · sup x∈X |f it (x)− f it+1(x)|
  ≤ T−1∑ t=1 m∑ i=1 |λit − (λ)i| · 2F = T−1∑ t=1 2F∥λt − λ∥1,
  where λit and (λ) i represents the i-th entry of λt and λ, respectively. Also notice that for any t ∈ {1, . . . , T},
  ∥λt − λ∥1 = ∥ ∑T
  k=1 λk T
  − λt∥1 = ∥ ∑T
  k=1(λk − λt) T ∥1
  = ∥ ∑T k=1 ∑t−1 s=k(λs − λs+1)
  T ∥1 ≤ T∑ k=1 t−1∑ s=k ∥λs − λs+1 T ∥1
  ≤ T∑
  k=1 T−1∑ s=1 ∥λs − λs+1 T ∥1 = T T−1∑ s=1 ∥λs − λs+1 T ∥1 = T−1∑ s=1 ∥λs − λs+1∥1.
  Therefore, we have
  term A ≤ T−1∑ t=1 2F T−1∑ s=1 ∥λs − λs+1∥1 = 2F (T − 1) T−1∑ t=1 ∥λt − λt+1∥1.
  As for term B, we have
  term B = T−1∑ t=1 sup x∈X |λ⊤(Ft(x)− Ft+1(x))| ≤ T−1∑ t=1 sup x∈X m∑ i=1 (λ)i · |f it (x)− f it+1(x)|
  ≤ m∑ i=1 (λ)i · T−1∑ t=1 sup x∈X |f it (x)− f it+1(x)| ≤ m∑ i=1 (λ)i · VT = VT ,
  where the last inequality is derived from the assumption of temporal variability, and the last equation comes from the fact that ∑m i=1(λ) i = 1T ∑m i=1 ∑T s=1 λ i s = 1 T ∑T s=1 ∑m i=1 λ i t = 1. Combining the above bounds for term A and term B, we finally prove the lemma. ■
  Plugging the above terms into the above bound for RMOD(T ), and replace the quantity ∆ ∈ {1, . . . , T} by δ, we have
  RMOD(T ) ≤2δVT + 4δFT T−1∑ t=1 ∥λt − λt+1∥1 + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗ + γD η ⌈T δ ⌉,
  for any δ ∈ {1, . . . , T}. Note that ∑T
  t=1 supx∈X (|λt ⊤(Ft(x) − Ft+1(x))| + |(λt −
  λt+1) ⊤Ft+1(x)|) = ∑T−1 t=1 supx∈X (|λt
  ⊤(Ft(x) − Ft+1(x))| + |(λt − λt+1)⊤Ft+1(x)|), because the regret does not depend on FT+1, λT+1. We thus prove the lemma. ■
sections.heading: C.3 PROOF OF THEOREM 1
sections.text: Proof. This theorem can be directly derived from Lemma 1.
  Specifically, when 4VTG2T ≤ η ≤ 4VT G2 , we can set δ = ηG2T VT
  , which satisfies 1 ≤ δ ≤ T . Plugging it into Lemma 1 and rearranging the inequality, we can directly derive the theorem. ■
sections.heading: C.4 PROOF OF THEOREM 2
sections.text: 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 η = 2G ( γDVT GT ) 1/3. Hence this theorem can be directly derived from Theorem 3. ■
sections.heading: C.5 PROOF OF THEOREM 3
sections.text: Proof. Denote η0 = 2G ( γDVT GT ) 1/3. We consider the following three cases:
  (i) When 4VTG2T ≤ η0 ≤ 4VT G2 , we can directly apply the above lemma.
  (ii) When η0 < 4VTG2T , or equivalently VT > ( γD 8 ) 1/2GT , we have η = 4VTG2T . Set δ = 1 in Lemma 1, then it can be verified that
  RMOD(T ) ≤ 2VT + 2VT G2T T∑ t=1 (α∥λt − λt−1∥1 + ∥∇Ft(xt)λt∥2∗) + γDG2T 2 4VT
  ≤ 4VT + 2VT G2T T∑ t=1 ∥∇Ft(xt)λt−1∥2∗
  ≤ 4VT + 2VT G2T T∑ t=1 G2 = 6VT .
  (iii) When η0 > 4VTG2 , or equivalently VT < ( γD 8T ) 1/2G, we have η = 4VTG2 . Set δ = T in Lemma 1, then it can be verified that
  RPT (T ) ≤ 2TVT + 2VT G2 T∑ t=1 (α∥λt − λt−1∥1 + ∥∇Ft(xt)λt∥2∗) + γDG2 4VT
  ≤ G(2γD)1/2T 1/2 + 2VT G2 T∑ t=1 ∥∇Ft(xt)λt−1∥2∗
  ≤ G(2γD)1/2T 1/2 + 2VT G2 T∑ t=1 G2 ≤ 3G 2 (2γD)1/2T 1/2.
  Combining (i)-(iii), we prove the theorem. ■
sections.heading: C.6 PROOF OF COROLLARY 1
sections.text: 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 V 1/3T T 2/3 ≥ O(T 1/2). Moreover, since VT ≤ o(T ), we have V 1/3T 2/3 ≥ o(VT ). Therefore, the dominating term in the bound of Corollary 2 is V 1/3T 2/3, which proves the corollary. ■
sections.heading: C.7 PROOF OF COROLLARY 2
sections.text: 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 + ∥∇Ft(xt)λ∥2∗} ≤ ∥∇Ft(xt)λt−1∥2∗ ≤ (∥λt−1∥1∥∇Ft(xt)∥∞)2 ≤ G2.
  Plugging it into the bound in Theorem 3 directly proves the corollary. ■
sections.heading: D MORE DETAILS IN MULTI-OBJECTIVE STATIC REGRET
sections.text: 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 Ft and fixed weights λ ∗ at all rounds. Now the static regret takes
  RMOS(T ) := sup x∗∈X∗ inf λ∗∈∆m
  λ∗⊤( T∑ t=1 Ft(xt)− T∑ t=1 Ft(x ∗)),
  where X ∗ = PX( ∑T
  t=1 Ft). 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 t=1 Ft, i.e., X ∗ = argminx∈X Ft(x). Hence the multi-objective static regret
  takes RMOS(T ) = supx∈X∗( ∑T t=1 Ft(xt)− ∑T t=1 Ft(x ∗)) = ∑T t=1 Ft(xt)−minx∈X ∑T t=1 Ft(x), which exactly reduces to the standard static regret RS(T ) in the single-objective setting.
  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
  RMOS(T ) ≤ 2FT T−1∑ t=1 ∥λt − λt+1∥1 + 1 η BR(x ∗, x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗. (7)
  By setting η = √ 2D
  G √ T and α = 4FTη , the regret bound reduces to O( √ T ), which is sublinear w.r.t. T .
  Proof. We start from the definition of RMOS(T ). Specifically, for any λ ∈ ∆m and λ1 . . . , λT ∈ ∆m, it holds that
  RMOS(T ) = sup x∗∈X∗ inf λ∗∈∆m T∑ t=1 λ∗⊤(Ft(xt)− Ft(x∗)) ≤ sup x∗∈X∗ T∑ t=1 λ⊤(Ft(xt)− Ft(x∗))
  = T∑ t=1 ((λ⊤Ft(xt)− λt⊤Ft(xt)) + λt⊤(Ft(xt)− Ft(x∗)) + (λt⊤Ft(x∗)− λ⊤Ft(x∗)))
  ≤ T∑
  t=1
  F∥λ− λt∥1 + T∑
  t=1
  λt ⊤(Ft(xt)− Ft(x∗)) + T∑ t=1 F∥λ− λt∥1
  = 2F T∑ t=1 ∥λ− λt∥1 + T∑ t=1 λt ⊤(Ft(xt)− Ft(x∗)).
  To tackle the second term in the above inequality, we set u1 = u2 = . . . = uT = x∗ in Lemma 4, which results in
  T∑ t=1 λt ⊤(Ft(xt)− Ft(x∗)) ≤ 1 η BR(x ∗, x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗.
  To analyze the static regret for OMMD-II, we relate the first term ∑T
  t=1 ∥λ − λt∥1 with the L1 regularization in the regularized min-norm solver at each round. Specifically, we denote the average weights as λ̄ = ∑T t=1 λt/T and set λ = λ̄ in the first term. Then for any t ∈ {1, . . . , T}, we have
  ∥λ̄− λt∥1 = ∥ ∑T
  i=1(λi − λt) T
  ∥1 = ∥ ∑T i=1 ∑t−1 k=i(λk − λk+1)
  T ∥1
  ≤ T∑
  i=1 t−1∑ k=i ∥λk − λk+1 T ∥1 ≤ T∑ i=1 T−1∑ k=1 ∥λk − λk+1 T ∥1
  = T T−1∑ k=1 ∥λk − λk+1 T ∥1 = T−1∑ t=1 ∥λt − λt+1∥1.
  Consequently, the static regret can be bounded as
  RMOS(T ) ≤ 2F T∑
  t=1 T−1∑ t=1 ∥λt − λt+1∥1 + 1 η BR(x ∗, x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗
  = 2FT T−1∑ t=1 ∥λt − λt+1∥1 + 1 η BR(x ∗, x1) + η 2 T∑ t=1 ∥∇Ft(xt)λt∥2∗,
  which proves the full static regret bound. Now we prove the reduced bound. From the full bound, we equivalently have
  RMOS(T ) ≤ 1
  η BR(x
  ∗, x1) + η
  2 T∑ t=1 (∥∇Ft(xt)λt∥2∗ + 4FT η ∥λt − λt−1∥1).
  We now set λ = 4FTη in OMMD-II, and specify λt to be the composition weights generated by the algorithm at round t. Then we know that λt ∈ argminλ∈∆t ∥∇Ft(xt)λ∥ 2 ∗ + 4FT η ∥λ− λt−1∥1. In particular, we have ∥∇Ft(xt)λt∥2∗ + 4FTη ∥λt − λt−1∥1 ≤ ∥∇Ft(xt)λt−1∥ 2 ∗. Therefore, it holds that
  RMOS(T ) ≤ 1
  η BR(x
  ∗, x1) + η
  2 T∑ t=1 ∥∇Ft(xt)λt−1∥2∗.
  Utilize Assumption 1 and Assumption 3, and set η = √ 2D
  G √ T , then we have
  RMOS(T ) ≤ 1
  η BR(x
  ∗, x1) + η
  2 T∑ t=1 ∥∇Ft(xt)λt−1∥2∗ ≤ G √ 2DT,
  which proves the reduced bound. ■
  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 ∑T t=1 δ(xt;x ∗, Ft, λ ∗). Such a metric compares the generated decision xt at each round with the fixed comparator x∗ ∈ X ∗. Hence, in particular, it is able to produce a negative value when xt dominates x∗ regarding the instantaneous loss 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.
sections.heading: E DISCUSSION ON AN ALTERNATIVE METRIC BASED ON PROJECTION
sections.text: 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 ∆projt . At each round t, we project the generated decision xt onto the Pareto optimal set X ∗t , namely xproj ∈ argminx′∈X∗t ∥xt−x
  ′∥2, and then measure 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 P∗t in the loss space, the projection-based metric ∆ proj t only compares the actual loss Ft(xt) with the loss Ft(xproj) evaluated at a single comparator xproj .
  In intuition, ∆projt 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 P∗t . Moreover, for the second objective, we have f2t (xproj) > f 2 t (xt). Therefore, xproj is not a proper point to measure the Pareto suboptimality of xt regarding P∗t . Notably, measuring the Euclidean distance between Ft(xproj) and Ft(xt) is meaningless, since xproj performs even worse than xt in the second objective.
  Concretely, we consider the decision set X = {(x1, x2) | −1 ≤ x1 ≤ 0,−1 ≤ x2 ≤ 0}, which is a rectangle in R2. We assume there are two objectives, and at round t, the loss function Ft : X → R2 takes Ft(x1, x2) = ( 2x 1−x2 3 , 2x2−x1 3 ). Since Ft is a linear transformation, it is convex. The decision set X and the image set Ft(X ) are shown in Figure. It is easy to verify that, the Pareto optimal set X ∗t = {(−1, x2) | −1 ≤ x2 ≤ 0} ∪ {(x1,−1) | −1 ≤ x1 ≤ 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) = (− 23 , 1 3 ). From the plot in Figure, it is obvious that Ft(xproj) is the most remote point from Ft(xt) in the Pareto front. Moreover, regarding the second objective, f2t (xproj) > f 2 t (xt), 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 ∆t(xt) equals supx∈X∗t infλ∈∆2 λ ⊤(Ft(xt)−Ft(x)), or equivalently supx∈X∗t mini∈{1,2}(f i t (xt)− f it (x)). It is easy to verify that ∆t(xt) = 1 3 and the comparator x ∗ t attaining the supremum is (−1,−1), which we denote as xPSG. Then the compared loss Ft(xPSG) = (− 13 ,− 1 3 ), which is exactly the closest point to Ft(xt) in the Pareto front. Moreover, xPSG dominates xt. Hence, compared to the projection-based metric ∆projt 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.