Multitask Online Mirror Descent
Authors: Nicolò Cesa-Bianchi
Pierre Laforgue
Andrea Paudice
Massimiliano Pontil
Venue: Accepted by TMLR ()

Abstract: We introduce and analyze MT-OMD, a multitask generalization of Online Mirror Descent (OMD) which operates by sharing updates between tasks. We prove that the regret of MT-OMD is of order $\sqrt{1 + \sigma^2(N-1)}\sqrt{T}$, where $\sigma^2$ is the task variance according to the geometry induced by the regularizer, $N$ is the number of tasks, and $T$ is the time horizon. Whenever tasks are similar, that is $\sigma^2 \le 1$, our method improves upon the $\sqrt{NT}$ bound obtained by running independent OMDs on each task. We further provide a matching lower bound, and show that our multitask extensions of Online Gradient Descent and Exponentiated Gradient, two major instances of OMD, enjoy closed-form updates, making them easy to use in practice. Finally, we present experiments which support our theoretical findings.

Published in Transactions on Machine Learning Research (09/2022)
Multitask Online Mirror Descent
Nicolò Cesa-Bianchi
nicolo.css.-iiscchhiemmmn...
Deportment of Computer Science, University of Milan, Italy
Pierre Laforgue
dierre.laforgueeuunimn.. it
Department of Computer Science, University of Milan, Italy
Andrea Paudice
andrea. andrea. Pettraa.pruuiiceeuumiiii
Deportment of Computer Science, University of Milan, Italy Istituto Italiano di Tecnologia, Genova, Italy
Massimiliano Pontil
massimiliano pttpiiimmooooott@.....
Istituto Italiono di Tecnologia, Genova, Italy University College London, United Kingdom
Reviewed on OpenReview: https: // openreview. net/
met/ forum? id- zuRX9kkKs
Abstract
We introduce and analyze MT-OMD, a multitask generalization of Online Mirror Descent (OMD) which operates by sharing updates between tasks. We prove that the regret of MT-OMD is of order /I+ d2 1)VT, where o² is the task variance according the geometry induced by the regularizer, N is the number of tasks, and T is the time horizon. Whenever tasks are similar, that is o² < 1, our method improves upon the VNT bound obtained by running independent OMDs on each task. We further provide a matching lower bound, and show that our multitask extensions of Online Gradient Descent and Exponentiated Gradient, two major instances of OMD, enjoy closed-form updates, making Ihem easy to use in practice. Finally, we present experiments which support our theoretical findings.
1 Introduction
In multitask learning (Caruana, 1997), one faces set of lasks lo solve, and tries to leverage their similarities learn faster. Task similarity is often formalized in terms of Euclidean distances among the best performing models for cach task, Evgeniou & Pontil (2004) for an example. However, in online convex optimization, and Online Mirror Descent (OMD) in particular, it is well known that using different geometries to measure distances in the model space can bring substantial advantages - see, e.g., Hazan (2016); Orabona (2019). For instance, when the model space is the probability simplex in Rd, running OMD with the KL divergence (corresponding to an entropic regularizer) allows one to learn at rate depending only logarithmically on d. It thus natural to investigate to what extent measuring task similarities using geometries that are possibly non-Euclidcan could improve the analysis of online multitask learning. From an application perspective, typical online multitask scenarios include federated learning applications for mobile users (e.g., personalized recommendation or health monitoring) for smart homes (e.g., energy consumption prediction), mobile sensor networks for environmental monitoring, or even networked weather forecasting. These scenarios fit well with online learning, as new data is being generated all the time, and require different losses and decision sets, motivating the design of a general framework.
In this work, we introduce MT-OMD, a multitask genoralization of OMD which applics to any strongly convex regularizer. We present regret analysis establishing that MT-OMD outperforms OMD (run independently each task) whenever tasks are similar according to the geometry induced by the regularizer. Our work

---

Published in Transactions on Machine Learning Research (09/2022)
builds on the multitask extension of the Perceptron algorithm developed in Cavallanti et al. (2010), where prior knowledge about task similarities is expressed through symmetric positive definite interaction matrix A. Typically, A= = 1+ + L, where L is the Laplacian of task relatedness graph with adjacency matrix W. The authors then show that the number of mistakes depends on Σ, ||ull + Eng Wiy Wyyllu; - Uy 12, where cach u, denotes the best model for lask i. This expression can be seen as a measure of task dispersion with respect. to matrix W and norm I| 122. The Euclidean norm appears because the Perceptron is an instance of OMD for the hinge loss with the Euclidean regularizer, so that distances in the model space are measured through the corresponding Bregman divergence, which is the Euclidean squared norm.
For an arbitrary strongly convex regularizer v the regret of OMD is controlled by a Bregman divergence and a term inversely proportional to the curvature of the regularizer. The key challenge we face is how to extend the OMD regularizer to the multitask setting so that the dispersion term captures task similarities. A natural strategy would be to choose regularizer whose Bregman divergence features En, Wey B (u,, Uy). Although this mimics the Euclidean dispersion term of the Perceptron, the associated regularizer has a small curvature, compromising the divergence-curvatuure balance which, as we said, controls the regret. Observing that the Perceptron's 's dispersion term can be rewritten ||A|/2u||, where A is a block version (across tasks) of A and u is the concatenation of the reference vectors u4 our solution consists in using the regularizer 2b (A1/2. .), where ab is the compound version of any base regularizer & defined on the model space. While exhibiting the right curvature, this regularizer has still the drawback that A might be outside the domain of tb. To get around this dilficulty, we introduce notion of variance aligned with the geometry induced by v, such that the corresponding Bregman divergence B& (AAl/2u, u,, A 1/2b) is always defined for sets of tasks with small variance. We then show that the Bregman divergence can be upper bounded in terms of the task variance o², and by tuning appropriately the matrix we obtain a regret bound for MT-OMD that scales as /1 + 2N - 1). In contrast, the regret of independent OMD scales as VN, highlighting the ad advantage brought by MT-OMD when tasks have a small variance. We stress that this improvement is independent of the chosen regularizer, thereby offering a substantial acceleration in wide range of scenarios. To keep the exposition simple, we first work with a fixed and known a². We then show an extension of MT-OMD that does not require any prior knowledge on the task similarity. The rest of the paper is organized as follows. In Section 2, we introduce the multitask online learning problem and describe MT-OMD, our multitask extension to solve it. In Section 3, we derive a regret analysis for MT-OMD, which highlights its advantage when tasks are similar. Section devoted to algorithmic implementations, and Section 5 to experiments.
Related work. Starting from the seminal work by Caruana (1997), multitask learning has been intensively studied for more than two decades, see Zhang & Yang (2021) for recent survey. Similarly to Cavallanti et al. (2010), our work is inspired by the Laplacian multitask framework of Evgeniou et al. (2005). This framework has been extended to kernel-based learning (Sheldon, 2008), kernel-based unsupervised learning (Gu et al., 2011), canlextual bandits (Cesa- (Cesa-Bianchi et al., 2013), spectral clustering (Yang et al., 2014), stratified model learning (Tuck et al., 2021), and, more recently, federated learning (Dinh et al., 2021). See also Herbster & Lever (2009) for different applications of Laplacians in online learning. A multitask version of OMD has been previously proposed by Kakade et al. (2012). Their approach, unlike ours, is cast in terms of matrix learning, and uses group norms and Schatten p-norm regularizers. Their bounds scale with the diameter of the model space according to these norms (as opposed to scaling with the task variance, in our analysis). Moreover, their learning bias is limited to the choice of the matrix norm regularizer and does not explicitly include a notion of task similarity matrix. Abernethy et al. (2007); Dekel et al. (2007) investigate different. multitask extensions of online learning, see also Alquier et al. (2017); Finn et al. (2019); Balcan et al. (2019); Denevi et al. (2019) for related extensions to meta-learning. Some online multitask applications are studied in Pillonetto et al. (2008); Li et al. (2014; 2019), but without providing any regret analyses. Saha et al. (2011); Zhang et al. (2018) extend the results of Cavallanti et al. (2010) to dynamically updated interaction matrices. However, no regret bounds are provided. Murugesan et al. (2016) look at distributed online classification and prove regret bounds, but they are not applicable in our asynchronous model. Other approaches for learning task similarities include Zhang& & Yeung (2010); Pentina & Lampert (2017); Shui et al. (2019). We finally note the recent work by Boursier et al. (2022), which establishes multitask learning guarantees with trace norm regularization when the number of samples per task is small, and that by Laforgue et al. (2022), which learns jointly the tasks and their structure, but only with the Euclidean regularizer and under the assumption that the task activations are stochastic.
2

---

Published in Transactions on Machine Learning Research (09/2022)
Although asynchronous multitask setting is identical to that of Cavallanti et al. (2010), emphasize that our work extends theirs much beyond the fact. that we consider arbitrary convex losses instead of just the hinge loss. Algorithmically, MT-OMD generalizes the Multitask Perceptron in much the same way OMD generalizes the standard Perceptron. From a technical point of view, Theorem 1 in Cavallanti et al. (2010) is a direct consequence of the Kernel Perceptron Theorem, and is therefore limited to Euclidean geometries. Instead, our work provides a complete analysis of all regularizers of the form (A1/2.) Although Cavallanti et al. (2010) also contains a -on-Euclidean p-norm extension of the Multitask Perceptron, we point out that their extension is based on regularizer of the form || This is different from MT-OMD for p-norms, which instead uses >; (A [|. As a consequence, their bound is worse than ours (see Appendix C for technical details), does not feature any variance term, and does not specialize to the Euclidean case when p 2. Note that our analysis on the simplex is also completely novel as far we know.
2 Multitask Online Learning
We now describe the multitask online learning problem, and introduce our approach to solve it. We use a cooperative and asynchronous multiagent formalism: the online algorithm is run in distributed fashion by communicating agents, that however make predictions al different time steps.
Problem formulation and reminders on OMD. We consider an online convex optimization setting with a set of N E N agents, each learning a possibly different task on a common convex decision set V C Rd. At each time step t = 2,, some agent is S N makes a prediction It E V for its task, incurs loss (xxx), and observes subgradient of & at It, where l is a convex loss function. We say that is is the active agent at time L. Both the sequence i1, 12. of active agents and the sequence (1 f.. of convex losses are chosen adversarially and hidden from the agents. Note that the algorithm we propose is deterministic, such that 4 might be indifferently chosen before 2t is predicted (oblivious adversary) or after. Our goal is to minimize the multitask regret, which is defined as the sum of the individual regrets
N
T
N inf uEV
RT
Σ le(xx)) inf WEV
Σ 8: 4=t
((())
= Σ
(
Σ 1=1
Σ :1
(1)
f:
A natural idea to minimize Equation (1) is to run N independent OMDs, one for each agent. Recall that OMD refers to a family of algorithms, typically used to minimize a regret of the form E, (xx)) - infwev E, 4u),, for any sequence of proper convex loss functions 4. An instance of OMD is parametorized by a A-strongly convex regularizer sb: Rd + R, and has the update rule
T++1 = arg min (M:.t, + (x,, øEV
(2)
where Sr E IR is a subgradient of 6, at point x,, Bx v) = - (V)())) x -) denotes the Bregman divergence associated to eb and n7 > 0 is a tunable learning rate. Standard results allow to bound the regret achieved by the sequence of iterates produced by OMD. For a fixed n and any initial point x1 E V, we have (Orabona, 2019, Thcorem 6.8) that for all u V
T Σ 4(x)) - (1) Belux21
Σ 1 7 22
"
with ||- ||. the dual norm of the norm with respect which & is strongly convex (see Definition 4 in the Appendix). The choice of the regularizer vo shapes the above bound through the quantities (v, and l|sell.. When & = Yll I1ž, we have Be(r, v) -1100= - v1ll. -1- = ||- ll,, A 1 and the algorithm is called Online Gradient Descent (OGD). However, depending on the problem, different choice of the regularizer might better captures the underlying geometry. A well-known example is Exponentiated Gradient (EG), an instance of OMD in which V is the probability simplex in Rd, such that V= A = {x E R Σ, -, = 1}. EG uses the negative entropy regularizer >> Σ, In(ry), and assuming that 1 blo S Tyg, one achieves bounds of order OTT dl)d), while OGD yields bounds of order (TT VdT). We emphasize that our cooperative
3

---

Published in Transactions on Machine Learning Research (09/2022)
extension adapts to several types of regularizers, and can therefore exploit these improvements with respect to the dependence on d, see Proposition 8. Let C' be generie constant such that CvT bounds the regret incurred by the chosen OMD (e.g., C²= L, or C' = v above). Then, by Jensen's inequality the multitask regret of N independent OMDs satisfies
N R Σ CVTSSOVNT,
(4)
lii = i} denotes the number of times agent i was active. Our goal is to show that introducing commmication between the agents may significantly improve Equation (4) with respect to the dependence on N.
where 7; Li
A multitask extension. We now describe our multitask OMD approach. To gain some insights on it, we first focus on OGD. For i N and t < T, let Vi, E IRd denote the prediction maintained by agent at time step t. By completing the square in Equation (2) for db = th == šlll 112, the independent OGDs updates can be rewritten for all i < N and such that it = d:
(5) where HyllI-1 denotes the projection operator onto the convex set V according to the norm ||- that is [y (x) arg min || - yll- Our analysis relies on compound represenlations, that we explain next. We use bold notation to refer to compound vectors, such that for u1,..., uN Rd, the compound vector is = [u...... uv] E R Nd. For i S N, we use (f)) refer the 7th block of u, such that a u, in the above example. So 2t is the compound vector of the ( such that I = x("), and the multitask regret rewrites as RT(u) = (
F1,4+ I (2 m.9:).
le (u).t) For any set V c Rdd let == veN c R.dd denote the compound set such that u E V is equivalent to u E V for all i is N. Equipped with this notation, the independent OGD updates Equation (5) rewrite as
x++1 = II
IIv. lla (z)
mig:).
(6)
with gt E Rd such that gi gt for i = i, and Ogd otherwise. In other words, only the active agent has a non-zero gradient and therefore makes an update. Our goal is to incorporate communication into this independent. update. To that end, we consider the general idea of sharing updates by considering (sub) gradients of the form A where A-1 E I Ndx Nd is a shorteut notation for A- & La and A RNNN is any symmetric positive definite interaction matrix. Note that A is parameter of the algorithm playing the role of learning bias. While our central result (Theorem 1) holds for any choice of A, our more specialized bounds (see Propositions 5 to 8) apply to a parameterized family of matrices A. A simple computation shows that ()))) = A, gt. Thus, every agent makes an update proportional to A, at each time step t. In other words, the active agent (the only one to suffer loss) shares its update with the other agents. Results in Section are proved by designing a matrix A (or equivalently A) such that A captures the similarity between tasks and 4. Intuitively, the active agent i, should share its update (gradient) with another agent to the extent their respective tasks are similar. Overall, denoting by |Julaar = Vu Mu the Mahalanobis norm of u, the MT-OGD update writes
L411 = ITV.1-I1 (T. A 9t)
In comparison to Equation (6), the need for changing the norm in the projection, although unclear at first sight, can be explained in multiple ways. First, it is key to the analysis, as we see in the proof of Theorem 1. Second, it can be interpreted as another way of exchanging information between agents, see Remark 1. Finally, note that update Equation (7) can be decomposed as
Le+1 = arg min (nigr, x) + wERNd
++511 =11l0 | - xx 11.1
(8)
1 x T 12a
0141 = arg min
_
4

---

Published in Transactions on Machine Learning Research (09/2022)
showing that it is natural to keep the same norm in both updates. Most importantly, what Equation (8) tells us, is that the MT-OGD update rule is actually OMD update- see e.g., (Orabona, 2019, Section 6.4) with regularizer a + I| = Eh ( (A)/2z). This provides natural path for extending our multitask approach to any regularizer. Given a base regularizer Φ: R + R. the compound regularizer ab is given by 1b: a E R.Nd + Ei= v(x(()) \i=)(((0)). When there exists a function Φ: R - l such that vxxx) = E; ((zy), the compound regularizer is the natural extension of vi to R Note, however, that the relationship be more complex, e.g,, when (xx)= = || Using regularizer 1b (A11/2 (A)/2 .), whose associate divergence is By aA A Al/2x'), the MT-OMD update thus reads
E++1 = arg min (nig.. x) + B (A A
(9)
=EV
Clearly, if 1/ E'ace we recover the MT-OGD update. Observe also that whenever = IN. MT-OMD is equivalent to independent OMDs. We conclude this exposition with a remark shedding light on the way MT-OMD introduces communication between agents.
Remark 1 (Communication mechanism in MT-OMD). Denoting y: = A2, Equation (9) rewrites
11+1 = A-12 arg min vEAV?((V)
( gr, y) + (y.
(10)
The two occurrences of A-1/2 reveal that agents communicate in two distinct ways: one through the shared update (the innermost occurrence of A-1/2), and one through computing the final prediction F441 as a linear combination of the solution the optimization problem. Multiplying Equation (10) by A//2, MT-OMD can also be seen as standord OMD on the tronsformed iterate yt-
3 Regret Analysis
We now provide a regret analysis for MT-OMD. We start with a general theorem presenting two bounds, for constant and time-varying learning rates. These results are then instantiated to different types of regularizer and variance in Propositions 2 to 8. The main difficulty to characterize the strong convexity of 2b (A112, see Lemmas 11 and 12 in the Appendix. Throughout the section, V Rd convex set of comparators, and (4e)T1 is a sequence of proper convex loss functions chosen by the adversary. Note that all technical proofs can be found in Appendix A.
Theorem 1. Let vb Rd + R be X-strongly convez with respect to norm Il on V, let A E RNNN be symmetric posilive defonile, and set æ, V. Then, MT-OMD with th == produces sequence of ilerates (x:)i= such that for all u V, Rr(u) is bounded by
B 12 1122m)
T
max A
1
Σ
11
(11)
I
2X
1=1
Moreover, for any sequence of nonincreasing learning rates (ne) MT-OMD produces a sequence of ilerates (#:)²= such that for all u E V, RT(u) () is bounded by
B (A A x2/xx)
max EST
+
max A
Σ
1l
(12)
Y/r
SN
21
3.1 Multitask Online Gradient Descent
For & = -1111113 A A= TN (independent updates), unit-norm reference vectors (n()),, I.g-Lipschitz losses, and σ1 0, bound Equation (11) becomes: ND² /2n 1TTL3/2 /2. Choosing 17 =
we recover the DL,VNT NT bound of Equation (4). Our goal is to design interaction matrices A that make Equation (11) smaller. In the absence of additional assumptions on the set of comparators, it is however impossible to get a systematic improvement: the bound a sum of two terms, and introducing interactions typically roduces one term but increases the other. To get around this difficulty, we introduce simple condition on the task similarity, that allows us to control the increase of B (A 12 A 1/2xx) for a carefully designed class of interaction matrices.
5

---

Published in Transactions on Machine Learning Research (09/2022)
Definition 1. Let || ||: Rd - R be any norm, and ū (1/N) Ex= u for any u E R We define the
variance of w.r.t. || as
N 1 ū
Vari-n (u) N
t=1
Let D = =suPuev |2ll, and > O. The companators with variance smaller than o² o²D² are denoted by
= = V: Vari- (u) S <DDD².
(13)
For sets of comparators of the form Equation (13), we show that MT-OGD achieves significant improvements over its independent counterpart. The rationale behind this gain is fairly natural: the tasks associated with comparators in Equation (13) are similar due to the variance constraint, so that communication indeed helps. Note that condition Equation (13) does not enforce any restriction on the norms of the individual u((,, and is much more complex than simple rescaling of the feasible set by o². For instance, one could imagine task vectors highly concentrated around some vector uo, whose norm is D: the individual norms are close to D, but the task variance is small. This is precisely the construction used in the separation result (Proposition 4). As MT-OMD leverages the additional information of the task variance (unavailable in the independent case), it is expected that an improvement should be possible. The problems of how to use this extra information and what improvement can be achieved through are addressed in the rest of this section. To that end, we first assume o² to be known. This assumption can be seen as a learning bias, analog to the knowledge of the diameter D in standard OGD bounds. In Scction 3.4, we then detail a Hedge- based extension of MT-OGD that does not require the knowledge of o² and only suffers an additional regret of order vTllg N.
The class of interaction matrices consider is defined as follows. Let L IN I1 We consider matrices of the form A(b) IN + LL, where b 2 0 quantifies the magnitude of the communication. For more intuition about this choice, see Section 3.4. We can now state a first result highlighting the advantage brought by MT-OGD,
= 1 D = supxev |æ]],, and a S. Assume that 1106(())12 S Ly for all t S T Proposition 2. Let + =
and any E V. Set b = N, x1 0, and n DV/(NN + 1)(1 (N 1)02) VL. Then, MT-OGD produces sequence of iterates (xt) such that for all u E Vii-l2.0
Ri S
(14)
Proof sketch. With vi = 11l 112, and 0 = 0, we have 2 (A(b)1/2u, 1 ||u|| +6N 1) 11a (w), which is smaller than N D + NN)) Then, it is easy to check that [A(b)-1] Substituting these values into Equation (11), we obtain
(1+6JN for all is N.
6+N
ND + +
TT b+N
Rr( <
+
8
27
2 (1+ b)N
(1-b (1+b) (b+N)T
ND Finally, set 77 Lg V
and b b N.
Thus, MT-OGD enjoys a / 1 dependence, which is smaller than VN when tasks have a variance smaller than 1. When a = (all tasks are equal), MT-OGD scales as if there were only one task. When o 2 1, the analysis suggests choose b 0, i.e., A = IN, and one recovers the performance of independent OGDs. Note that the additional /2 factor in Equation (14) can be removed for limit cases through better optimization in b: the bound obtained in the proof actually reads (F with F(0) 1 and F(1) N. However, the function F lacks of interpretability outside of the limit cases (for details see Appendix A.2) motivating our choice to present the looser but more interpretable bound Equation (14). For a large N, we have /I + dN - 1) x oVN. The improvement brought by MT-OGD is thus roughly proportional to the square root of the task variance. From now on, we refer this gain as the multitask acceleration. This improvement achieved by MT-OGI is actually optimal up constants, as revealed by the following lower bound, which is only 1/4 of Equation (14).
6

---

Published in Transactions on Machine Learning Research (09/2022)
Proposition 3. Under the conditions of Proposition 2, the regret of any algorithm satisfies
sup (T( 2 1 uc 12-
Another way to gain intuition about Equation (14) is compare to the lower bound for OGD considering independent tasks (IT-OGD). The following separation result shows that MT-OGD may strictly improve over IT-OGD.
Proposition 4. Let d 2 9, N 2d, and to be tuned later. Then, there ewists Villla. such that
v - 2T
R
OGD- (u) 2
Proposition 2 then yields that for any o²
.N 16
18NN
R4
OGD
(w)) >> Rt R PT--00 OGD
(u).
3.2 Extension to any Norm Regularizers
A natural question is: can the multitask acceleration be achieved with other regularizers? Indeed, the proof of Proposition 2 crucially relies on the fact that the Bregman divergence can be exactly expressed in terms of | and VarjHia (u). In the following proposition, we show that such an improvement is also possible for all regularizers of the form Ill 112, for arbitrary norms || |l, up to an additional multiplicative constant. A crucial application is the use of the p-norm on the probability simplex, which is known to exhibit a logarithmic dependence in d for a well-chosen p.
Proposition 5. Let 11. 11: Rd + R be any norm, t = 11ll 113, D = sup ||=||, and 1. Assume that [1)6(x))|+ S T.g for all T, IVV. Set b N, 21 = and rj = DVN((N + 1)(1 + (N /) VT Then, MT-OMD produces a sequence of iterates (2x)7=1 such that for all u e Vi
(u) S
1JVST.
In particular, for d 2 and V A, choosing || = 11 1lps for p 2 21 d/dd/mlnd 1), and assuming that. [x))( Lgg it holds for all u E 11l111..
RT(u)= S
1JV16e Tlnd.
In comparison, under the same assumptions, bound Equation (14) would write as:
1)V2Td.
Projecting onto V,. Propositions 2 and 5 reveal that whenever tasks are similar (i.e., whenever E Va), then using the regularizer (2A2/2) with A * IN accelerates the convergence. However, this is not the only way to leverage the small variance condition. For instance, one may also use this information to directly project onto V, V, by considering the update
Et+1 arg min (ng.. + A. zeV,
(15)
Although not necessary in general (Propositions 2 and show that communicating the gradients is sufficient to get an improvement), this refinement presents several advantages. First, il might be simpler to compute in practice, see Section 4. Second, it allows for adaptive learning rates, that preserve the guarantees while being independent from the horizon T (Proposition 6). Finally, allows derive L bounds with the multitask acceleration for smooth loss functions (Proposition 7). Results are stated for arbitrary norms, but bounds sharper by factor can be obtained for ||2-

---

Published in Transactions on Machine Learning Research (09/2022)
Proposition 6. Let || 11: I² + R be any norm, 2 = I12, D suPsev ||]|| and a S 1. Set b N, and
1h = DVNNN++ 1)(1 + (N - 1)o 119:112)
Then, Equation (15) produces a sequence of iterates
(x)) such that for all 1i
T
1/2
Rr(u)= S $8DV1+ 1)
Σ
11
Proposition 7. Let || 1|: 12:12==2 IR be any norm, 11 - 113, D sup |||||, and o S 1. Assume that the l are M-smooth, i.c., [Vb{(x) (b)(y) S M - yll for all t < T, and any 2. E V. Set b and as in Proposition 6. Then, update Equation (15) produces a sequence of ilerates (x+) such that for all u E VI-Il.
T M
Rí (u) 1 1) 2MD 1)+
M4 (((uli))
Remark 2 (Strongly convex and exp-concave losses). Another popular assumption to derive improved regret bounds is to consider strongly convez or erp-concove losses. Recall that a function f is said to be a-cap-concave if exp(-of) is concave (for instance, the logistic loss of linear predictor with norm bounded by U and unit- norm impuls is regret bounds of order I, see e.g., (Orabona, 2019, Corollary 7.24 and Section 7.10). We highlight that a simple adaptation of the single task analysis is not enough to exhábit a multitash acceleration in these cases. Indeed, the cornerstone of our analysis to leverage the compound representation, in which the interactions are more easily analyzed. On the other hand, the strong converity or erp-coneavily of the losses provide sharper control on the instantaneous regret that depends on the norm of the active predictor ceffictor/cone /comparator only, but cannot be extended to the compound framework. Another way to look at the problem is to recall that FTRL deals with strongly conver losses by choosing 1/ =0 This means ub = ab(22/2.) = O, such that MT-FTRL is equivalent to independent FTRL and no multitask improcement can be achieved.
In this content, slandard single lask algorithms achieve improved
3.3 Regularizers on the Simplex
As seen in Propositions 2 to 7, MT-OMD induces a multitask acceleration a wide range of settings, involving different regularizers (Euclidean norm, p-norms) and various kind of loss functions (Lipschitz continuous, smooth continuous gradients). This systematic gain suggests that multitask acceleration essent derives from our approach, and is completely orthogonal to the improvements achievable by choosing the regularizer appropriately. Bounds combining both benefits are actually derived in the second claim of Proposition 5. However, all regularizers studied so far share crucial feature: they are defined on the entire space Rd. As consequence, the divergence B& (A Al/2x)) is always well defined, which might not. be true in general, for instance when the comparator set studied is the probability simplex A. A workaround consists in assigning the value +o0 to the Bregman divergence whenever either of the arguments is outside of the compound simplex A A The choice of the interaction matrix A then becomes critical to prevent the bound from exploding, and calls for a new definition of the variance. Indeed, note that for i < N we have (A (A())=/2u)(() = /1 b (0) + (1-v1 b)ū. If all () are equal (say to un E A), then all (A(b)2/2u)() are also equal to uo and A(b) E A. However, if they are different, by definition of ū, for all < d, there exists S such that u/" S uj. Then, for large enough, /1 + b u + (1 - v1 + b)ū, becomes negative, and (2))) is out of the simplex. Luckily, the maximum acceptable value for b can be easily deduced from the following variance definition.
Definition 2. Let u E IRd For all j S d, let
max
max S uj and
min NN
Then, with the convention 0/0 = 0 we define
max
u
Vara (u) max
jdd
re! maax
8

---

Published in Transactions on Machine Learning Research (09/2022)
and for any o S 1
A, = (uE A: Vara(u) S o²).
Equipped with this new variance definition, Proposition 8. Let 1p : A + I be A-strongly convex w.r.t. norm || ll. and such that there exist x² E A and C' C'++0 such that for all x E A, By(xxx)) S C. Let a S 1, and assume that [[āl((z)]]- I Lg for all and = N MT-OMD produces a sequence of iterates (x:)7=1 such that for all u E A.
now analyze regularizers defined on the simplex.
t S T and z E A. b= = (1- - (1-o2)/o² 21 === =I."...,,.'""
NYT. Then,
Br(u)= S Ly 1 2CT/X.
For the negative entropy we have x² o'=1/d and Ind. With subgradients satisfying [1)(()))loo S Lg obloin
Rr(u)= - -f
Proposition 8 shows that the multitask acceleration is not an artifact of the Euclidean geometry, but rather a general feature of MT-OMD, as long as the variance definition is aligned with the geometry of the problem.
3.4 Adaptivity to the Task Variance
Most of the results we presented so far require the knowledge of the lask variance o². We now present an Hedge-based extension of MT-OMD, denoted Hedge-MTTOMMD, that does not require any prior information on o². First, note that for o² 2 I, MT-OMD becomes equivalent to independent OMDs. A simple approach consists then in using Hedge- see, c.g., (Orabona, 2019, Section 6.8)-over over a set of experts, each running an instance of MT-OMD with different. value of o² chosen on uniform grid of the interval [0, 1]. We show that Medge-MTT-GDD only suffers additional regret of order vT log N against MT-OGD run with the exact knowledge of V-r
Thcorem 9. Let D = sup ||0||,, and assume that [ I Lg for all alltsp ST, x VEV. Then, for all u E the regret of Madge-MT-OGD is bounded by
DLg 2 + v log N + /mmn (aa), N V2T.
Variance definition and choice of A. Note that we have (N - Va = N Ee, || (:10~~(11 u0 =
u' Lu, where L = IN 11 11T/N /N is the Laplacian of the weighted clique graph over (I...., N), with edges of 1/N. A natural extension then consists in considering variances of the form
Var 1a (u)
Σ W Wo - L +==1
for any adjacency matrix W and its Laplacian LW, For instance, if we expect lasks to be concentrated in clusters, it natural to consider Wij = () and ub) (are thought to) belong to the same cluster, and 0 otherwise. This local version is interesting, as it allows to satisfy the variance condition with a smaller o, which improves the MT-OMD regret bound. Note that the proof of Theorem 1 can be readily adapted this definition by considering the class of interaction matrices (A(b) = IN + bT."). The bound however features which depends on W in nontrivial way and requires case by case analysis, preventing from stating general result for an arbitrary W. Considering even more general matrices A, i.c., that do not write as IN + ,L, suffers from the same problem (one then also needs to compute Bys (A A, A1/2v) on a case by case basis), and does not enjoy anymore the variance interpretation seen above. Furthermore, note that Proposition is obtained by minimizing Equation (11) with respect to A. For matrices of the form A(b), this tradeoff only depends on b, and is thus much easier to solve than for general matrices. Finally, we stress that local variances can be similarly considered on the simplex. Instead of involving the global umax the variance formula then features for each task/ /ooe local maximum (respectively minimum) over its neighbours.
maxig N/ [A(6)-
Note that Hedge-MT-OOe computes the loss subgradient arbitrary points (correspanding to the expert's predictions).
9

---

Published in Transactions on Machine Learning Research (09/2022)
3.5 Additional Remarks
We conclude this section with two additional results. The first one draws an interesting connection between our multitask framework and the notion of dynamic regret, while the second emphasizes on the importance of the asynchronous nature of the activations.
Remark 3 (Connection to dynamic regret). Note that our online mullitask selling can be viewed special case of dynamic regret, where each comparator u, in the sequence of comparators u1 U2.... belongs to an unknown set {u',..., "'y3 of known cardinality N. Moreover, at the beginning of each time step t, the learner is told the inder i E (1....,NY of the comparator 4y against which the regret is measured at time L. As a consequence, any algorithm for dynamic regrel minimization can be used in our selling. In the Euclidean case, the optimal dynamic regret bound is of order vD² + DVrVT, where D is the Euclidean diameter of the decision space and VT = =Ei=1 || uell2- In order to facilitate the comparison to our bound /D2 + D2(N - 1)02/TT let assume that the sequence of adversarial activations such that in # i and that all pairs of distinct elements in "ui....,ux? appear with the same frequency as consecutive comparators ut, 44+1- Let Py = Ei= |11+11 - well3- We have
Pr Σ
1
|u411
uell
T N(N
Σ itj
1/
2T
1
||44 - u2
2T D2
1)
N(N 1) izj
2
such that our upper bound is at most
Pr D + - 1)02VI D2 (N
N-1
D2
VT $ D2+ DVIVT,
27
2T
which is beller as soon as T N-1
We finally derive a regret bound in the case where several agents are active at each time step.
Proposition 10. Consider the setting of Proposition 2, but assume now that at each time step t a subset of agents A C fI,...,,' NJ,, of cardinality -Al==10 p, is chosen by the adversary and asked to make predictions. Recall that in this case the regret of an independent approach is of order DL Then, MT-OMB run with b = vpN and =-dn==Na INNDDII+ (N L3/L p)T produces sequence of iterates (æ,)²= such that for all u E VIilla.
Rr(u) S DT p) p212
Note that for p= 1, we recover eractly Proposition 2.
Proposition 10 highlights that having asynchronous activations is critical: the more active agents at a single time step, i.e., the bigger p, the bigger /1 + O
+ /3/2, i.e., the smaller the multitask acceleration. In the extreme case where p = N, our multitask framework reduces to standard online convex optimization problem, with diameter vND and gradients with Euclidean norms bounded by vNL. Lg. Standard lower bounds then of order NDL vT, confirming that no multitask acceleration is possible.
4 Algorithms
We now show that MT-OGD and MT-EG enjoy closed-form updates, making them easy to implement. Note that the MT-OGD derivation is valid for any matrix positive definite, while MT-FG requires -12/2 to be stochastic. This is verified by matrices of the form A Iy + L (Lemma 13).
MT-OGD. Let V {u Rd: ||ul|2 D}, and I 1. Recall that V Vaa {u E Nd. /ull2,> S D), and VIH = (u E V: Varj (u) & d²). Solving the first equation in Equation (8), we obtain that the iterate Øt+1 produced by MT-OGD is the solution to
min { [| A 9: #ERNa
|01|2,00 S SD).
10

---

Published in Transactions on Machine Learning Research (09/2022)
However, computing this update is made difficult by the discrepancy between the norms used in the objective and the constraint. A simple work around consists in considering the minimization over the Mahalanobis ball VA = {u E RRvd; ||ulla < (1+ b instead. It is easy to check that Villa. C VA, so that every result derived in Section for MT-OGD remains valid (only the fact that comparators and iterates are in VA is actually used). With the substitution ye = A the MT-OGD update then rewrites (see Appendix B.1 for
technical details)
1/2 Dt+1 Proj yr 7 A gt. ((++b23)ND
(16)
where 7r) min (1, و a. Note that Equation (16) can be easily turned back into an update on by making the inverse substitution. In practice however, 2 is only computed to make the predictions. The pseudo-code of the algorithm is given in Algorithm 1.
Algorithm MT-OGD
input: A positive definite matrix A R RNV (interaction matrix), o² > 0 (task variance), D > 0 (comparators set diameter), 1/t > 0 (learning-rate schedule)
initialization: A A @ Ia E IR Ndx 31 0, y/ 11//2x1
1: Compute A and 1/1/2
2: for time sleps / = 1, 1...... do
3: Compute compound prediction Dt = A 1
4: Activate agent is and predict (()
5: Get E @l(x,) and compute
6: Compute U1+1 min {
V(++o2)ND
(y: 19:-1144 11)2g:) A-1/22
I - 9/
end for
MT-EG. Using Equation (8) with A1/2 MT-FG reads
Ut+1 arg min VERNA
(nA 9t, 8) + B U:),
9t+1 arg min (3.
(17)
AEAL/2(A)
where 2b is the compound negative entropy regularizer such that (bxx) = Σ Σd === z In ()) One can
show (see Appendix B.2 for details) that the update can be rewritten for all i S N and j s
(8) Diti. Vi.
(0)
exp (11
-1/2 Mes - -1)
(6)
yetij Σl= Bet1A
Combining both equations, we finally obtain
(1) Vi
-nA 1/2 ge.
Veti,
(18)
Σl Vikk -nA 96.6
(3)
Update Equation (18) enjoys natural interpretation. Each block ( is operating an individual standard EG update, but with gradient A, 11/2 9t- When A = IN, only the active block is updated. Otherwise, the update of block i is proportional to A -12/ that quantifies the similarity between tasks and i, The pseudo-code of the algorithm given in Algorithm 2. Although this work only focuses on OMD for clarity, note that considering Setoowtto-Regulaiizee Leaeredd-Laee--seeee soc, c.g., (Orabona, 2019, Scction 7) with & = (A41/2 would yield similar bounds. This would allow, for instance, the use of time-varying learning rates with entropic regularization.
11

---

Published in Transactions on Machine Learning Research (09/2022)
Algorithm 2 MT-EG
input: A positive definite matrix A RNNN (interaction matrix), > 0 (learning-rate) initialization: A = A @ Ia E R Ndx Nd 21 = 1/d E R Nd 1: Compute A and A-1/2
y1 = A 1/1221
2: for time sleps ( .... do
3: Compute compound prediction 2t- A y
4: Activate agent and predict 22(1)
5: Get 9i E al(x)) and compute 9: 1/. 24 SLS
Compute Vit1.
Vi E [V], Vj [d]
Σn vil
01.
end for
5 Experiments
In this section, we empirically compare the performance of Hedge-MTTOGD/BE against two natural alternatives: an independent-task approach (TT-OGD/EG) where the agents do not communicate, and a Single-task approach (ST-OGD/EG) where a single model is learned and shared by all agents. Note that both IT and ST approaches are special cases of MT-OMD, obtained respectively with the choices = (i.e., o² 2 1), or b= +o0 (i.e., d² 0). In Appendix D we report an additional experiment where we empirically validate the dependence of the performance of MT-OGD on the task variance.
Online Gradient Descent. For this experiment, we use the Lenk dataset (Lenk et al., 1996; Argyriou et al., 2007). It consists of 2880 computer ratings in the range (1,2,...,10) made by 180 individuals (the tasks) on the basis of 14 binary features. Each computer is rated on discrete scale from 0 to 10, expressing the likelihood of an individual buying that computer. We run Hedge- MTdge-MT-OGDD using the clique interaction matrix A = (1 N) - 11T and the square loss. For all algorithms, the value of 17 is set according to the optimal thcoretical value, see Proposition 2. In Hedgo-MT-OGD, the variance o² learned in set of experts uniformly spaced over [0. For simplicity, we use D 1 and compute the resulting Lipschitz constant accordingly. Results are reported in Figure 1(a).
Exponentiated Gradient. For our sccond experiment, we consider EMNIST, a classification dataset consisting of 62 classes (images of digits, small and capital letters). To speed up computation, we reduced the number of features from 784 down to 10 through a standard dimensionality reduction method. We created 61 binary classification tasks by considering the digit class against each other class. To each task, we assigned 10 examples (5 positive, 5 negative) randomly chosen from the set of examples for that task. We considered the linear logistic regression and ran Hedge-MT-EG with the parameterized clique interaction matrix A(b) (1 T) b11 b11T/N /N. The value of is set according to the thcoretical value (that depends o², see Proposition 8), while o² is learned in set of 5 experts uniformly spaced over [0, 1]. For all algorithms, the value of 17 is set according to the optimal theoretical values. Results are reported in Figure 1(b).
6 Conclusion
We introduced and analyzed MT-OMD, multitask extension of OMD whose regret is shown to improve the task variance, expressed in terms of the geometry induced by the regularizer, decreases. We provided a unifying analysis and a single algorithm that explains when multitask acceleration possible based on the current geometry, and how to achieve it. Natural and interesting directions for future research include: (1) analyzing the multitask acceleration in combination with other propertics, such as strongly convex losses, and (2) designing and analyzing an extension of MT-OMD that is adaptive to the best interaction matrix.
References
Jacob Abernethy, Peter Bartlett, and Alexander Rakhlin. Multitask learning with expert advice. In Proceedinds of the 20th International Conference on Computational Learning Theory, pp. 484-498, 2007.
12

---

Published in Transactions on Machine Learning Research (09/2022)
80000
ST-OGD
400
ST-EG
CGD
EG
Hedge-MT-OGD
Hedge-MTT
60000
300
40000
200
20000
100
0-
0
500
1000
1500
2000
3000
100
200
400
500
600
Lenk (OGD, cumulative square loss)
(b) EMNIST (EG, cumulative logistic loss)
Figure Comparison between multitask (MT), independent-task (IT), and single-task (ST) OGD and EG the Lenk and EMNTST datasets. We plot the cumulative losses against time. Lenk is known to work well in multi-task settings, and indeed Hedge-MTT-OGD performs significantly better than both baselines. On the other hand, EMNIST has a variance significantly higher than Lenk. However, even in this unfavorable scenario, Medge-MT-EG is still outperforming the baselines, though by a small margin.
Gotz Alefeld and Norbert Schneider. On square roots of m-matriccs. Linear Algebra and its Applications, 42: 119 132, 1982.
Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret bounds for lifelong learning. In Proceedinds of the 20th International Conference Artificial Intelligence and Statistics, pp. 261 269, 2017.
Andreas Argyriou, Charles Micchelli, Massimiliano Pontil, and Yiming Ying. A spectral regularization framework for multi-task structure learning. In Proceedings of the 20th Annual Conference on Neural Information Processing Systems, pp. 25 32, 2007.
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient-based meta-learning. In Proceedinds of the 36th International Conference Machine Learning, pp. 424-44444 433, 2019.
Heinz H. Bauschke and Patrick L. Combettes. Conver analysis and monotone operator theory in Hilbert spaces. Springer, 2011.
Etienne Boursier, Mikhail Konobeev, and Nicolas Flammarion. Trace norm regularization for multi-task learning with scarce data. arXiv preprint arXiv:2202.00742, 2022.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2004.
Rich Caruana. Multitask learning. Machine Learning, 28(1):41-75) 1997.
Giovanni Cavallanti, Nicolò Cesa-Bianchi, and Claudio Gentile. Linear algorithms for online multitask classification. Journal of Machine Learning Research, 11:2901-2934, 2010.
Nicolò Cesa-Bianchh, Claudio Gentile, and Giovanni Zappella. A gang of bandits. In Proceedings of the 26th Annual Conference Neurol Information Processing Systems, pp. 737 745-745,20 2013.
Nicolò Cosa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Ofer Dekel, Philip M Long, and Yoram Singer. Online learning of multiple tasks with a shared loss. Journal of Machine Learning Research, 8(10):2233 2264, 2007.
13

---

Published in Transactions on Machine Learning Research (09/2022)
Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. In Proceedings of the 32th Anaual Conference on Advances in Neural Informalion Processing Systems 32,
meta-learning.
pp. 13089 13099, 2019.
Canh T Dinh, Tung T Vu, Nguyen H Tran, Minh N Dao, and Hongyu Zhang. Fedu: A unified framework for federated multi-task learning with Laplacian regularization. arXiv preprint urXiv:2102.0714 07148, 2021.
Theodoros Evgeniou and Massimiliano Pontil. Regularized multi-task learning. In Proceedings of the 10th
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 109 117, 2004.
Thcodoros Evgeniou, Charles Micchelli, and Massimiliano Pontil. Learning multiple tasks with kernel methods. Journal of Machine Learning Research, 6(4):615 637, 2005.
Chelsca Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In Proceedings of the 36th International Conference on Machine Learning, pp. 1920- 2019.
Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning. 53(3):265-298) 2003.
Adam J Grove, Nick Littlestone, and Dale Schuurmans. General convergence results for linear discriminant updates. In Proceedings 10th Annual Conference on Computational Learning Theory, pp. 171-183, 1997.
Quanquan Gu, Zhenhui Li, and Jiawei Han. Learning a kernel for multi-task clustering, In Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 368-373, 2011.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Oplimization, 2(3-4): 157-325, 2016.
Mark Herbster and Guy Lever. Predicting the labelling of a graph via minimum p-seminorm interpolation. In Proceedings of the 22nd Conference Learning Theory, 2009.
Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Regularization techniques for learning with matrices. Journal of Machine Learning Research, 13(1:11865 1890, 2012.
Pierre Laforgue, Andrea Della Vecchia, Nicolò Cesa-Bianchi, and Lorenzo Rosasco. Adatask: Adaptive multitask online learning. arXiv preprint or drXiv:2205.15802, 2022.
Peter J Lenk, Wayne S DeSarbo, Paul E Green, and Martin R Young. Hierarchical bayes conjoint analysis: Recovery of partworth heterogeneity from reduced experimental designs. Marketing Science, 15(2):173 191, 1996.
Guangxia Li, Steven CH Hoi, Kuiyu Chang, Wenting Liu, and Ramesh Jain. Collaborative online multitask learning. IEEE Transactions on Knowledge and Data Engineering, 26(8):1866-138) 1876, 2014.
Rui Li, Fenglong Ma, Wenjun Jiang, and Jing Gao. Online federated multitask learning. In Proceedings of the 7th IEFE International Conference on Big Data, pp. 215-20 215-220, 2019.
Keerthiram Murugesan, Hanxiao Liu, Jaime Carbonell, and Yiming Yang. Adaptive smoothed online multi- task learning. In Proceedings of the 29th Annual Conference on Advances Neural Information Processing Systems, pp. 4296 4304, 2016.
Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv: 19213 2019.
Anastasia Pentina and Christoph H Lampert. Multi-task learning with labeled and unlabeled tasks. In Proceedings of the 94th International Conference on Machine Learning, pp. 2807-2816, 2017.
Gianluigi Pillonetto, Francesco Dimuzzo, and Giuseppe De Nicolao. Bayesian online multitask learning of gaussian processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(2):193-206 2008.
Avishck Saha, Piyush Rai, Hal Daumé, Suresh Venkatasubrammnian, et al. Online learning of multiple tasks and their relationships. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 643 651, 2011.
14

---

Published in Transactions on Machine Learning Research (09/2022)
Shai Shalev-Shwarte Online learning: Theory, algorithms, and applications. PhD thesis, The Hebrew Universily of Jerusalem, 2007., 2007.
Daniel Sheldon. Graphical multi-task learning. Technical report, Computing and Information Science Technical Reports, Cornell University, 2008.
Changjian Shui, Mahdieh Abbasi, Louis-Famile Robitaille, Boyu Wang, and Christian Gagné. A principled approach for learning task similarity multitask learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3446-3452, 2019.
Suvrit Sra. Fast projections onto mixed-norm balls with applications. Data Mining and Knowledge Discovery, 25(2):358 377, 2012.
Jonathan Tuck, Shane Barratt, and Stephen Boyd. A distributed method for fitting Laplacian regularized stratified models. Journal of Machine Learning Research, 22(60):: 37, 2021.
Yang Yang, Zhigang Ma, Yi Yang, Feiping Nie, and Heng Tao Shen. Multitask spectral clustering by exploring intertask correlation. IEEE Transactions on Cybernetics, 45(5):1083 1094,, 2014.
Chi Zhang, Peilin Zhao, Shuji Hao, Yeng Chai Soh, Bu Sung Lee, Chunyan Miao, and Steven CH Hoi. Distributed multi-task classification: a decentralized online learning approach. Machine Learning, 107(4): 727 747, 2018.
Yu Zhang and Qiang Yang. A survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering, 2021.
Yu Zhang and Dit Yan Yeung. A convex formulation for learning task relationships in multi-task learning. In Proceedings of the 26th Conference on Uncertointy in Artificial Intelligence, pp. 733, 2010.
15

---

Published in Transactions on Machine Learning Research (09/2022)
A
Technical Proofs
In this Appendix are gathered all the technical proofs of the results stated in the article. First, we provide notation table recalling the most important notation used along the paper.
Notation TEN N N deN N
Mcaning
Time horizon
Number of lasks
Dimension of single reference vectors
" E IR, for I
Reference vector (best model) for task
u = [Ui,..., uN] E Rdd
Compound reference vector
( E Rd
Block the compound vector u (= Us here)
" (1/N) E, (()
Average reference vector
Vari.1 (w) (1/(N - -1)-11) 1)) 11((0 u||²
Variance of the reference vectors w.r.t. norm || Generic set of comparators for single task Half diameter of V w.r.t. norm || Generic set of compound comparators Comparators in V with small variance
V R"
D = suPEEv |ull
V {u E R.dd vi < N, u EV}
VI lhe = {u E V: Var (u) S D²)
/ min minisN (1)
uj
Minimum (among tasks) of component S d Maximum (among tasks) of component j S d Variance aligned with the probability simplex Probability simplex in Rd Compound probability simplex Comparators in A with small variance
(5)
max maxisN u
Vara (u) = maxisa(1 - u min /u max)s
A = {u E R E3 Ug 1
A {u E RRNd, vi S N, (1) EA}
A
= EuE A: (ars(u) I ooa}
E RN
Vector filled with 1's Identity matrix of dimension N Generic interaction matrix Parameterized interaction matrix
IN E RNNN
A E N
A(b) +1+ 11 -
A = @ Ta E NdxNN
Block version (Kronecker product with Ta) of A Block version of A(b)
A(t) = A(b)= & la
Ft. E Rd, for i is N and t T
Prediction maintained by agent i at time t Compound predictions maintained at time Active agent at time (chosen by the adversary)
Vt FIII...,,NN.. E Rdd
4 E N
4: Fd +
Loss function at time (chosen by the adversary)
9: = (2( lit))
E Rdd
Subgradient of & at point x
9: = [0,..., 0.0000..... O..... ........)
Nd
Compound subgradient (null outside block i,)
v: V + R
Generic base regularizer
Bu: V x V V-+ +
Bregman divergence induced by +b
v: u Rd + Σ, ()
Compound regularizer
3 (A1222
Regularizer of interest.
Table 1: Notation Table.
A.1 Proof of Theorem 1
The first important building block of our proof consists in characterizing the strong convexity of & (Lemma 11). To that end, need to introduce the following definition and notation about norms.
16

---

Published in Transactions on Machine Learning Research (09/2022)
Definition 3. Let Le Rd + R, and and EN - R be two norms. We define the mized norm ll Il-l IR I as follows?. For all a: E R&Nd, || is given by the N' norm of the T&N vector composed of the N norms of the blocks ( Formally, it reads
Væ E RR
| N" (((e)))))...(((()))
When N || ll and N' |l. lo. for p.g too], one recovers the standard lp.g mixed norm. We use the following shortcut notation
Ia = =1 11--11-- and IIx = || Il
Let E II-I:: R be any norm, and M E ma** be a symmetric positive definite matria. We define the Mahalanobis version of || |l. denoted || Ilas, as
Vx E: R
| = ||M
Notice that for -1-11=11 11- 1l,, we recover the standard Mahalanobis norm such that || Vx MMr, For simplicily, and when it is clear from the conterl, we use the shorleut nolation
|| - 1| = || 11,,
We are now equipped to establish the strong convexity of ub.
Lemma 11. Assume that the base regularizer th: Rd - IR is A-strongly convex with respect to some norm -I Then, the associated compound regularizer vp is X-strongly convex with respect to the Mahalanobis mized norm 1.1.A.
Proof. First, notice that for every a RR it holds
H H₂(x)) 1/2 (A 1/2
where Hœ) Ndx denotes the Hessian matrix of regularizer sb at point Moreover, due to the definition of the compound regularizer sp: x E Nd EN (x(()), matrix Hæ( is block diagonal and given by
()()()))
0
(2)))
0
H (x)
0
Assuming that vb is X-strongly convex with respect to norm || |l. it thus holds for all æ, E Rd
H (z)
H (A)122) (A)/2 (A2/2)) A2/22)
Hy ((A1/2 (1) (A1/20) (1) (A)/2 (0)
N
Σ 11//
-=1
> ||
The second important intermediate result (Lemma 12) deals with dual norms, that we recall now.
Note that sufficient condition for |- llv.v be is that (2 .x)) (Vall (xx)). In Lemma 11 we
N || ll2, which satisfies this property.
17

---

Published in Transactions on Machine Learning Research (09/2022)
Definition 4. Let N, and I|: R I be any norm. The dual norm of || denoted || Il+, is defined
Va E R
|
sup VeR llllls
(x. 8)
Lemma 12. Let p.q tool, and p², q² their conjugates such that 1/p + 1/p" =1/q + 1/4" =1. Then it holds
(Il 1l.) = =1---1111110 1lp and (ll (le.)))) = -1
Let 8 E N, ||:1|: R* + R be any norm, and M E Rxxx be symmetric positive definite matriz. Then it holds
(l Ill)) = -1 1l.. 1.
Assume furthermore that con be decomposed into s = 81 x 82, for 81,82 N. Then, for any norm ||: R R it holds
(II- (11.111.2) = 11-111-1..2-
In particular, combining the last two results yields: (Il -1...,,,))) -II-11HH..2.4
Proof. The first result is standard in convex analysis, see e.g. Appendix A.1.6 in Boyd et al. (2004). The second result is due to Sra (2012), see Lemma 3 therein. The last two results rely on the following equality (see e.g. Example 3.27 in Boyd et al. (2004)). For any norm |l, it holds
2 -11112 2 1-1111))
(19)
where f* denotes the Fenchel-Legendre conjugate of f. defined as f*(z) = sup, ff() Bauschke Combettes (2011). Applying Equation (19) || Ilas, we get for all R
(~ (11 110))) (x) ( 113. (x)
sup VER
(I, v)
2 1vvl
{M (M-1/2 1/2 M 1/2 - | 111
sup yER
1 _11=11?
(M 1/2 (M- 2)
sup =ER*
( -11-112)) (M 1/22))
1 || 1/2 //2=| 1== (-1 11: (z))
11111122111
18

---

Published in Transactions on Machine Learning Research (09/2022)
Applying Equation (19) to || 111--1,2 we get for any Re
1 2 (I) [11111) (x) =
l1 11.1.. (x)
sup
(xz, 8)
2 |1e111 11-11.2
VER-1-2 22
(or(0) y (3))
11
sup VER
2 ==1
(1) y (0))))
sup E
b 1p) (2)(1)
1
||x0()) |1 ( Ili-1..2 (x).
2
We are now ready to prove Theorem 1. The proof follows from standard arguments to analyze OMD, combined with Lemmas 11 and 12.
Proof of Theorem 1. First, notice that the compound representation allows to write
T Rr Σ (xx)
N
inf WEV t:
Σ
4uu)=
inf weV
(((xs) le (u)())
Next, for any u E V, the convexity and sub-differentiabbiity of le implies
T - - ((( S
T
T
Σ
(g), xe - u(()))
Σ
ge T. - u.)
[=1
Now, observe that update Equation (9) actually defines an OMD on iterate Ut, for the sequence of gradients (g.)(=1 and with regularizer v Recall also that &b is >-strongly convex with respect to ||- 11.1.1...4 (Lerma 11), whose dual norm is ||- 21, (Lemma 12). Applying the standard OMD bound of Equation (3), we thus obtain that for all V and 17 it holds
T
BB 21,
Σ
g at u)
lgg. l 111.
"
2X 1=1
Then, we use that for all x. y E Nd it holds B (x, 3) = Bu (A 1/22,, A /22y) and that
A - 1/2 gt
|1.11..2 2
N
A 1/2
2
gt
N
1/2)
A 1/2) )
119.112
1=1
A A
||9: 1
max
A |1
is N
19

---

Published in Transactions on Machine Learning Research (09/2022)
Combining all arguments, we finally obtain
Rr(u) _ B& (A x))
+ max A ISN
17
11 l1
The second claim of the theorem is obtained in a similar fashion. Standard OMD results (Orabona, 2019, Theorem 6.8) give that
B
ux xc
T
Rr(u)= I max 1ST
+
nella 1...AA1.
1/
2A
1=1
Replacing (,, 2z) and 11 with By (Al/2u, x and max A l19ell? respoctively yields the desired result.
iSN
A.2 Proof of Proposition
First, is easy check that we have
11T
A(b) = (1+ - b
N
11
A(b) = v1 + IN + (1 v1 + b)
N
A(6) 1
b 11
IN +
1+b
(1+ b) N
This implies
b+ N
max
[A(B)
(20)
(1+
and
N
(
2B (A(b)//2,, A(b)
Σ
(A())1/2))
N
VI+ (1) + /1 + b)u
VI+b (u (0) -) ū 2
(1+b)
Σ
1u a||2 Σ
|| 222 6 Σ
(w()))
ū, ū.
N
(1 - u0123 + ||u11(] + b(N
Var (2)
N
ue 11 b(N - 1) Var (u)
(21)
Substituting Equation (20), Equation (21) into Equation (11), and using the definition of V Vill, we get that (T( is smaller than
lu + b(N
1a
lla ())
1 b N
(1
1/T b+
g
2m
2 (1+ 6)N
27
2 (1 (1+ (++
20

---

Published in Transactions on Machine Learning Research (09/2022)
or2 Setting = Trg (b+N)7 / ND
we get
N- 02) (b My
Rr S D
N
1+b
We now optimize on b. Let a N N o²,
the optimality condition writes
(1 + aN + 2ab" 2ab")(1+ b*) = ab") +
1 (a -N + 2ab" + abb² =0
(N 1) 1+ 1- 02
1 a
N
0²
And we have
(1 + abb))) ab")("'
+ N)
+ aN 2ab"
1+0
-N N
(1111-0~
02 N -1
N
Hence, the bound becomes F(o)) T, with
N (V1+1=0²~-1)
F(a) ((o)=1+00(0 - 1) 20 N -1
N-1
Note that
2ab* s <2/a(11a)NN-1] -
that have F(a)= < 2(1 o 1)), and the bound becomes DL, (I) value which can also be achieved directly by setting b = N above.
A.3 Proof of Proposition 3
This lower bound is proved by adapting the standard lower bound for (single-agent) Online Linear Optimization, see, e.g., (Orabona, 2019, Chapter 5). We consider linear losses, i.e., we assume that for all f. < T there cxists 9t E Rd such that (xx)) = (9,,z)) Our goal is to show that for any any sequence æ1,..., Er we can construct a sequence of losses (or equivalently of ge) such that the regret lower bounded. Recall that d is the dimension of the set V and D > 0 its radius, and let 1, Assume that N even, smaller than 2d, and for all i
N/23, let
w (2 1)
VN 1)/N Doc;
and
w (2)
VN - 1)/N
where (ed)ga is the canonical basis of Rdd It is easy to check that |l & D, and that Var(w) o² D²D2 D2 such that E VI Assume that N divides T, and that the agents are activated in cyclic fashion, ie.. i, 1 1+ mod N. We introduce the family of gradient vectors
9t = C(/NN
(1) 1|2
(22)
where 61...., CryN are valued in 1-1,1), with exact values to be determined later on. Indeed, we show that for any sequence of predictions, there exists a choice of 61,-.., such that the regret is lower bounded. To that end, we use the fact that for any function F: (-1,1]7/N + R, and any probability distribution P with support in (-1,1}, we have
F(c) 2 E Eca [Fe)).
sup <E(-1,1)T/X
21

---

Published in Transactions on Machine Learning Research (09/2022)
In particular, choose P to be the Rademacher distribution, such that Pfc -1} = Pfc 1} = 1/2. and all expectations are now understood to be taken with respect to this distribution. Note that we have l S Lg and [ = 0, for all t. Given any sequence 21..... TT, we can use gradients Equation (22) and obtain
sup ET/N
RT 2 Eg
Σ
gt, x 61)
min
Σ (ges (t))
(ges
Wc u-ll.12
T
Lg
(2olte) 2e(1i))
= Eg
uEVI 1-120
max
CTt/N]
|
Lg L
T
Ee
max
CT/NN (TANN
ea en(to)
DovN
1112.10
t=1
T/N
Lg Lg N
Be
max
(w,,un u)
DovN -1
V
7=1
2 L
T/N
Ee
max
Σ
E (2w
DoyN- -1
uet
}
T=1
T/N
2 DL - 1) E
Σ C
(23)
DLg σV N
2 2
(24)
where in Equation (23) we used ||l1| 2 (N 1)DPo² and in Equation (24) we used the Khintchine inequality, see, e.g., (ianahi & Lugosi, 2006, Lemma 8.2). We now combine this lower bound with the one obtained by choosing & for all and applying the standard single-agent lower bound DL. /2T, see, e.g., (Orabona, D
2019, Theorem 5.1). Combining these two bounds, obtain that the regret is lower bounded by
DLg /2T max (1,oVN DLg V2T(L
1 +2 -
(DL
11V27).
which is only 1/4 of the upper bound Equation (14). Hence, with knowledge of o², there is no algorithm with better multitask acceleration than MT-OMD, up to constant factors.
A.4 Proof of Proposition
Consider the following setting. Let N = 2d, a < 1, uh E Rdd be such that ||vollž = 0², and set for all i S d:
(2--1) = 2 V(N - 1)/Noe,, and w (2: = 24 +u + V(N 11)NNee
where (ei)isa is the canonical basis of Rdd, It is easy to check that || 2 1 - 20 for all i S N, and that Vari-1a (1) o². Then, standard lower bound for OGD (Orabona, 2019, Theorem 5.1) applied to the N individual independent OGDs of IT-OGD with linear losses, unit-norm loss gradients, and eyclic activations such that T: = T/N, gives that
N
V2T, 2
/2(1 20²)NT
RlT OTT-OGD
4
((1-202)N
This lower bound is strictly greater than the MT-OGD upper bound Equation (14) as soon as of - 1), equivalently soon o²
4
N-16
18N-16
22

---

Published in Transactions on Machine Learning Research (09/2022)
A.5 Proof of Proposition 5
As discussed in the main body, the analysis for general norms is made more complex by the fact that Equation (21) does not hold with equality anymore. Instead, a series of approximations leveraging the properties of norms is required. Indeod, for any norm || and regularizer & = 21l -11,111, holds
2B (A(b) 12 u, A(6) =
Σ
N
(A())
)00
N
Σ
V1+b b (0 + vI+
Σ
ū + 1 + (1(() w\|l
N
2 2 + (1 + b) Σ [1(00 mz
$ 2 2ND + +(N
1)Var))
SNDD² 1+ N 1 N
0²)
(25)
In comparison Equation (21), the bound is thus multiplied by 4. The rest of the proof (Le.. the optimization in 17 and b) is similar that of Proposition 2, and we obtain that for all u E Vi- it holds:
(u) S DL
11V8T
An interesting use case unlocked by the previous result is the use of the p-norm (for p E [1, 2)) on the the probability simplex A {ar R4: Σ, xy 11. Indeed, by a careful Luning of p one can derive bounds scaling as vlnd, instead of d for OGD. Interestingly, this improvement is orthogonal to our multitask acceleration, so that it is possible to benefit from both. Recall that regularizer 111 11 is (p 1) strongly convex with respect to || ll (Shalev-Shwartz, 2007, Lemma 17), and that the dual norm of || 1pp is || ll., with g such that 1/p + 1/9 = 1. Consider V= A, and loss functions such that /geloo I Loc for all gi E dl((x), x E A. One can check that 11 S 1. d2/9 Then, substituting Equation (25) into Equation (11) and using the previous remark, we get that for all u E A 11l1pp. holds
RT(u) <
2ND (1+ N
1
7 (1+ 2(p - 1) +
b+N
TI 2/1
7
1'i9
11+D-=1 (2) N) 1 1+b
< 2D
T
Vp-
with the choice 7 = 2ND
T23,0770. Hence, the bound obtained is the product of two terms, one depending only on b, the other only on p. We can thus optimize independently. The term in is the same as in previous proofs, we can reuse the analysis made for Proposition 2. The term in d is the same as in the original proof Grove al. (1997); Gentile (2003), and the optimization is thus similar. We repeat it here for completeness. One has d' d II vq - I4 < /qd By differentiating with respect to g, the last term minimized for q = 2 21 d, with a value of 22 In d. The final bound obtained is
(1+6)(160 b+N
(p-1)
L Lo 2N 16v16e Tlnd.
We conclude with few remarks. First, in order to ensure that 2 2 (we need S 2), we may assume that d 2 3. Second, note that the improvement on the dependence with respect to comes at the price of stronger variance condition, as we have Var (u) S Vari- (u) for all p SS 2. If one is interested in a condition independent from (indeed p depends on q. which depends on d), the variance with respect || ||2 can be used. Finally, note that have used D supzea ||ا|| supzea | =
7
23

---

Published in Transactions on Machine Learning Research (09/2022)
A.6 Proof of Proposition 6
This proposition builds upon the second claim of Theorem 1. We start by detailing the proof for the specific choice -| = lll. Observe that for 1p = All 1 and all a E ViH-la. we have
B (A x1 = 1l 2 S |
| S2ND2
(1
N (1+b~~107
N 0²)
Substituting into Equation (12), obtain
2ND (1+ (1+b 62)
+ N
T
(r(u)= v
1/
2(1 b)
b+ N
D
T
(1 b)
217
2 1=1
with D AN (1+0)
Using 7tt
v2D
ND,
2 (1+6
(Orabona, 2019,
b+N
(b+ Σ:=1 1g.11
2
2imi
110: 1B
Lemma 4.13) gives
b+ V2D RT(u)= S (1+b)N
(b N) (1 (1+b 1-1 02)
1 s PV
l
(26)
1
Choosing b == N concludes the proof. In comparison Proposition (and assuming that l1gel12 S Lg), the bound multiplied by v8. One v2 multiplication is due to the choice of Tit while the other v multiplication comes from the upper bound max,st B& (A1/2u, A Al/²x;), which is 4 times bigger than the upper bound of Be 1/2,,, 1/)2)). The proof for any norm follows the same path. The only difference is on bounding max;sT B, B (A A Al)²x;,, which 4 times bigger than the same quantity for the Euclidean case, see Equation (25). Therefore, an additional v = 2 factor is added.
A.7 Proof of Proposition
Using Equation (26) with 6 = N, the smoothness of the losses gives
T
(u( S 4D 1/
M Σ (((l)t))
Using Lemma 4.20 Orabona (2019), we obtain
Rr(u) 80V1++ AMDDV++02(N
M Σ (ulitt)
As for Proposition 6, the claim for general losses is obtained by multiplying the bound by
A.8 Proof of Proposition 8
Let æ1 [x" ,".,,,"],,, and observe that A(b) 21. Then, for all u E A such that A(b) E A we
have
N = Σ By -) (1) ,0,x') $ NC. 1=1
By (A A(b)-/2m = B (A(b))/2,,z)
(27)
24

---

Published in Transactions on Machine Learning Research (09/2022)
Plugging Equation (27) into Equation (11), we obtain for all A:
NC
17b N) 21(1 + b)N TE - Lg
2b N Ab+1 CT
Rr(u) S
(28)
where we have set Ig V 16+NYT The next natural question is how to choose by As bound Equation (28)
2ML+66C
is decreasing b, one is encouraged to choose b as large as possible. However, recall that Equation (27)
requires A(b)1/2u to be in A. So the optimal choice is 6" max 2 0: A(b) A}. This value
unfortunately depends on u and cannot be used uniformly over A. However, the variance condition for A.
allows to choose global b, we show now. Let E A.. Recall that for all s N we have
(A(b)
(1)
vI (
blu.
We have to check that these vectors are in the simplex for all i S N. There are two conditions that vector æ should verify be in the simplex
( 1 1 and
(ii)
Vj S d.
It is immediate to see that the first condition is always satisfied. To analyze the second condition, we recall the following notation from Definition 2
Vj S d,
max u
min u i
Now, let S d. A sufficient condition for (ii) to hold for every (A(b) u (1)
i S N, is
v1+bbuy unin + vI
v1+ b) bax
Or, equivalently,
u
max
5
max
u
min
Since this condition must hold for every j j d, the overall condition is
max
1 o² 2²
b
< min 35d
G² -
max
min
This condition is quite intuitive. If all best models are equal, 4 = u for all j S d, one can choose = +00, and achieves a bound independent. from N. On the contrary, there exists j s d such that max = 1 and wn = 0, i..., two different corners are linked, then b= 0 is the only possible choice, and a NN dependence is unavoidable. Finally, with b (1 o²)/0² 2 0, bound Equation (28) becomes
- -N
A.9 Proof of Theorem 9
Let 6 > 0, and consider the covering C, = {s, 2s,..., 1}, of cardinality 1/e. Let u E V, we want to derive an upper bound of the regret achieved by the best expert in C. against u. First, assume that Var (u) I 1, and let σ2 = inf(= C.: Var (u) 2). Note that by definition we have Var/-1a (u) I 52 < Var Ila (u) Now, let us bound the regret of MT-OGD run with 0² o², Recall that for any fixed learning rate 7, the regret of MT-OGD is bounded by
N (N Var -12 (w))
TL2
ND (N- - 1)02)
TL
+1
g
<
+
(29)
27
N
2m
N
25

---

Published in Transactions on Machine Learning Research (09/2022)
1+(N-1)02 MT-OGD run with o² = o² uses 7 T,y regret is upper bounded by
ND
/
Plugging this into Equation (29), get that the
2T
DL,
< D (1+ v Var (u) + VEN V2T
-Dgg 1+ V min (Varj-ia( + VEN V2T.
(30)
On the other hand, if Var |H|1 (u) 2 1, we know that MT-OGD ru with x² -==1 is equivalent to independent OGDs and has regret bounded by
DL S DLg [1 V EN 2T
DLg 1 v min {Var llla (u),, N + VeN V2T
(31)
Combining Equation (30) and Equation (31), we know that in any case the best expert C. has always a regret against smaller than
DLg 1+ v min (a (u), 11 N + VEN V2T
(32)
Let us now compute the regret of Hedge-MT-OGI against the best expert in C.. By the analysis of Hedge with linear combination of the experts, we know that it is bounded by (Orabona, 2019):
v2 L. T
(33)
where Loo is an upper bound of the infinity norm of the gradients received by Hedge. The latter are equal to the vectors of losses incurred by the different experts at each time step. With finear(ized) losses, and denoting by x,
expert the prediction of one expert at time step t, we have
le (xxxperty = -(9 expert) ) (gt, vt
1z 2
expert,((t)) S 19:112 || expert, 11 S DLg.
Hence, Loo $ DLg. Now, for any u E V, the regret of Hedge-MT-OGG against u upper bounded by the sum of: (1) the regret of Hedge with respect to the best expert in C,, that upper bounded by Equation (33), and (2) the regret of the best expert in Cg against u, that is upper bounded by Equation (32). Summing the two upper bounds and setting 1/N yields the desired result.
A.10 Proof of Proposition 10
Let (Lr,))EEA, be the losses associated to the active agents at times step t. For MT-OMD run with matrix & 11 for b 2 0, and constant learning rate > O, we have N
A = A(b) = (1 bN
Rr(u)=
ΣV
Σ
(x,( (e,(((())
t=1 iEAt
T
u1 Au
1)
Σ
1
2n
2
1=1
ND (1 + 1 N 1
N
g
A 1
(34)
2m
1=1
26

---

Published in Transactions on Machine Learning Research (09/2022)
where 9: E RRNd is the compound gradient vector with non-zero blocks at the indices present in A.. Recall We have
that A(b)-1= IN +
14b N
11 =
Σ A. (9
"
Σ EA 11 Σ
(gi)
iEAt
i#jEAt
b
b
$
+ + 1)
L
(1 b)N
(1 b)N
ply pb N
(1N
Substituting into equation 34 and setting b vpN, we have
(1) - ND + T - 1))
TL P(1 + p)
21
N
Setting 1 I, VT [+vpo"(N-1) p(I+p)
ND
we finally get
S -N 1312
B Derivation of the Algorithms
In this appendix we gather all the technical details about the algorithms.
B.1 Details on MT-OGD
With the change of feasible set, F++1 produced by MT-OGD is the solution to
|| 7 -1 9: =ellaa>
min w
s.t.
| S (1 + NN2
or again
||A2 xz 1/p A 112 g: A 1/2 112
min aERNd
|/ x < (1 + bo N
s.t.
Introducing the notation y: = 1/2 mt, the update on the y: 's writes
Vi+1 Proj y: 1112
1/2 gr, v (1 + b1bb))NDD
B.2 Details on MT-EG
N
(6)
Recall that for the negative entropy regularizer we have BB( y)
(
In
x
Expliciting the
i=
5=1
y
objective function of the first update, obtain
1/2 ge, 4) + B y:) (nA 11/2
n
A
1/2
Jr.j
yj (3)
+ y
(8)
In
(1)
f=1
Vi.j
27

---

Published in Transactions on Machine Learning Research (09/2022)
For all S N and d, differentiating with respect to y and setting the gradient to 0 we get
(i)
y Det1 = vio exp (- (., 1/2 96. -1).
(35)
We focus on the second updateBquation (17). The constraint y E (A) rewrites A A-1/2y E A, equivalently
N,
1 (A-1/2y)
1,
1/2 (1)
Vi S N, j S d,
0.
We introduce matrix Y R Nxd such that YιS yi (k)
Then it holds for all i S N
1 (A-1/2y) (1)
Σ
(A-1/22)
(1)
d Σ [A-1//3)]
[A-1/281]]
1=1
=1k=
1=1
Hence, using that 1-1 is stochastic, the first constraint rewrites
A-1/211 = = - Y1=1 = Vis,, 1 1 =1.
(36)
Similarly, the second constraint reads:
Wk S i [A-1/2y] kj 20.
(37)
The Lagrangian associated to Problem Equation (17) writes
4)
Akj [A-1/2|]
Σ T (0) -1)
kj
j=1
y V1+
k=1j=1
Y3
N
d
N
Yi ln
ΣΣ
Anj
M:Yo 1 μ.
V:41J
with A Nxd and μ R.V. the Lagrange multipliers associated to constraints Equation (37) and Equation (36) respectively. For all i & N, j d, differentiating with respect to Yij and setting the gradient to 0 yields
[yitt]] = yit = Ditl.j [A-1/>A] -1 -1-1
(38)
Furthermore, the complementary slacknoss writes for all S N and j s
Aij A=/(A-12 ij 0.
However, Equation (38) gives [Y(44)]
ij > 0, and matrix 1/2 is stochastic (see Lemma 13), so we have [A [A-1/2y((+ > 0, and consequently Asj = 0. Then
VitiJ Ditlij e ---1
Using 1 yi41 1, we get e -4-1 1/(E/
j=1 3 81.1))) ).
Substituting Equation (35) we get for all i S N
(5)
DitiJ
viti. Ed= Det1k
(i) -yA 1/2 g6
> d
Ve
(1) nn
1/2 g1
Yij e A 1/2 gu.
(1)
Σ k= Yo.ko e - 91.
28

---

Published in Transactions on Machine Learning Research (09/2022)
Lemma 13. Let A = IN + L,, where L is the Laplacian metrix associated to any weighted undirected gruph on (J.....N.. Then A-1 and A-1/2 are (doubly) stochastic malrices.
Proof. It is immodiate to see from the definition of A that A-1 and A-1/2 are both symmetric and satisfy A-11 = A-1/21 = I. remains to check that their entries are nonnegative. To that end, we use that inverses of M-matrices are entrywise nonnegative. Matrix A is a non-singular M-matrix, as its off-diagonal entries are noupositive (i.e., A is Z-matrix) and its eigenvalues are positive. As consequence, A also M-matrin (Alefeld & Schneider, 1982, Theorem 4), which concludes the proof.
]
C Technical Comparison to Cavallanti et al. (2010)
First, we would like to remind the reader that, unlike Cavallanti et al. (2010): (i) we tackle any subdifferentiable loss function, and not only the hinge loss for classification, (ii) we address any strongly convex regularizer, and not only the squared Euclidean norm, (zi)) our proofs provide clear insights on the regularizer's behaviour, and are not just black box applications of the Kernel Perceptron Theorem, (iv) we provide (matching) lower bounds, (v) we develop what we believe is the correct generalization to p-norms, see technical details below, (vi) provide unifying framework and general analysis that allow to deal with non-Fuelidean geometries the simplex, (vii we are adaptive to the task variance o².
About the p-norm extension, the two regularizers used in Cavallanti et al. (2010) and this paper are fundamentally different, as they write respectively
N (b())= = A and v( = Σ (00
A first advantage of our method that we recover the Euclidean framework by setting p = 2, which not the case for the regularizer used in Cavallanti et al. (2010). This makes us believe that we propose the right way to address p-norms, and that a general theory of multitask acceleration worth developing to avoid misinterpretations of this kind. A second advantage is that our bounds have a much better dependence with respect to the task variance o² and the number of tasks N. Recall that after several approximations, see Appendix A.5, our bound for p-norms on the simplex features the variance term
VN - 1)o² < + VNo,
(39)
where d² is an upper bound of the task variance according to || Il, such that
1 Vari-l (u)
Σ ( -ull s o².
On the other hand, the bound of Theorem 6 in Cavallanti et al. (2010) features the variance term
Aulli
1
Σ
N
NN+ NN
N
N
(1 || + +N -
20
N
N
11+
Σ
1
kml
N
S1
N
77
<1+No.
(40)
29

---

Published in Transactions on Machine Learning Research (09/2022)
From Equations (39) and (40), it is clear that our bounds exhibit much better dependence with respect to o² and N. We further highlight that the bound of Theorem 6 in Cavallanti et al. (2010) contains an extra term which is the square of Equation (40), without being multiplied by any time-related quantity though.
D Additional Experiment
We report the results of synthetic experiment where we plot the multitask regret of MT-OGD against the standard deviation a of the reference vectors. Specifically, we consider a regression problem in R² with respect to the square loss. We set D = and generate N = 4 tasks defining the reference vectors as in the proof of Proposition (soc Appendix A.3), so that the task variance set to the desired value. Each task consists of sequence of 10 losses, so that T 40. The losses for the i-th task are generated by first sampling and then computing its label as y (u()) .r) + e, where is
instance from the unit sphere centered independent Gaussian noise with variance 0.1 and truncated in [-1, 1]. We plot the final multitask regret Rr averaged over 30 runs. MT-OGD is tuned with the optimal parameter choices for b and according to the theory. Results are shown in Figure 2. As expected, the regret of MT-OGD increases linearly with a, as suggested by the upper bound Equation (14) and the lower bound Proposition 3. For the sake of comparison, we also benchmark IT-OGD and report its best average performance. The switch in performance occurs slightly before 1, which also expected as, aside from the dependence in Ø, the bounds for MT-OGD scales with /2T (instead of /T for IT- IT-OGD) and thus slightly worse for = 1.
5
4
Regret
MT-OGD
IT-OGD
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0
Figure 2: Multitask regret Ry of MT-OGD and IT-OGD for T 40 against the standard deviation a.
30


Reviews:
[{"review_id": "q5qzQ2Ftiq", "reviewer": "Reviewer_vFPH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### Strengths\n\n1. This paper comes up with a novel setting of multitask online learning.\n1. With a matching upper and lower bound, this paper almost settles their multitask online learning problem.\n2. Experimental results matches theoretical results. Importantly, the authors verified the dependency on the $\\sigma^2$ parameter.\n3. The paper is generally well-organized and the writing is good. I did not find typo.\n4. The paper provides a summary of notations and symbols in the Appendix, which facilitates readers.\n\n### Weakness\n\n1. Mirror descent is a framework of algorithms. Its main feature is that it covers analyses for different regularizers, in particular the KL divergence regularizer. However, the authors seem not to mention if the algorithm could work for KL regularizers.\n2. The formulation only requires one agent to select $x_t$, and is allowed to select agent adversarially. I personally think this may require more motivation, because in multitask bandit learning literature, I usually see settings where all agents are required to play.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis paper initiates the study of multitask online learning problem. Here, $N$ agents are online-learning $N$ different tasks. The agents and the environment interact for $T$ time steps in total. At each time step $t \\in [T]$, the environment can pick an agent $i_t$ and require it to make a prediction $x_t$, the environment then chooses a convex loss function $\\ell_t$. The agent $i_t$ incurs a loss $\\ell_t(x_t)$ and observes a subgradient $\\nabla \\ell_t(x_t)$. The goal is to minimize the multitask regret, defined as the sum of individual regret. Naively running $N$ independent OMD would result in $O(\\sqrt{NT})$ regret. In this paper, the authors show that by communication across agents, the regret could be reduced to $O(\\sqrt{1 + \\sigma^2(N-1)} \\sqrt{T})$, where $\\sigma^2$ is the sample variance of the ground truth of all agents. \n\nFurthermore, this paper proves a matching lower bound, showing that the results are near-optimal. This paper begins with an algorithm that only works with known $\\sigma^2$ and $\\ell_2$ regularizer, while they further generalize to $\\ell_p$ norm regularizers. This paper also provides experiments on synthetic and real-world datasets to cooroborate their theoretical results.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "\n1. Prop. 3: could you state $D$ and $L_g$ more precisely? I'm assuming the values are the same as in Prop. 2. \n2. Setting: could you make it more clear on whether the environment selects $\\ell_t$ after seeing $x_t$?\n", "broader_impact_concerns": "This paper is mainly theoretical and I don't see any potential negative ethical impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ji3tJ7InnF", "reviewer": "Reviewer_vbu3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. This paper formulates a general paradigm for mullti-task OCO, which is an important and well-motivated problem;\n2. The proposed algorithm successfully achieves a tighter regret bound wrt the number of tasks when the tasks are similar (in the sense that the variance sigma of the compators are is small). To my knowledge, the idea of adapting to the variance of u is novel and interesting. \n3. The authors did a thorough work for the proposed problem, and studied various extensions, which are mentioned in the summary above. \n\nWeakness:\n1. The vanilla algorithm requires to know sigma as a prior knowledge. Although the authors propose a hedge version of the algorithm which is agnostic to sigma, there is an extra root(logN T) factor, which exists even if sigma is 0. \n2. Currently the configuration of A is fixed before the learning process, which means that it cannot adapt to the data like Adagrad or Adam. \n3. It would be great if the authors could extend the proposed algorithm to adapt to other types of loss functions such as exp-concave and strongly convex functions. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. This paper develops a general framework for multitask online convex optimization;\n2. The authors propose a variant of OMD that can adapt to the variance of the compartors of different tasks;\n3. The authors also consider several extensions, including a matching lower bound, measuring the variances with different norms, and how to deal with the case where the parameter of variance is agnostic;\n4. Experimental results on real-world data demonstrate the effectiveness of the proposed method. \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. It seems to me that the regret defined in this paper (eq. 1) is related to dynamic regret and adaptive regret in online convex optimization. Indeed, for example, minimizing dynamic regret can be considered as doing T tasks, and the algorithm for dynamic regret can adapt to the change of comparators (V_T=\\sum_{t=1}^T ||u_{t+1}-u_{t}||). It would be great if the authors could add more discussion to this. On the other hand, I was wondering if the proposed algorithm can also be used for minimizing dynamic regret and obtain a simga-dependant bound? \n\n2. To make the paper more easier to read, it would be better if the authors could write down the pudo-code for the algorithm more explicitly, using \\begin{algorithm} \\end{algorithm}. ", "broader_impact_concerns": "This is a theoretical paper and does not have any ethical concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UnnteSRIqG", "reviewer": "Reviewer_mLuu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \nThis paper is very well written. The introduction of the multitask extension of the OGD method is intuitive and the different interpretations (8)-(10) of the MT-OGD update (7) make it easier for the reader to understand the derivation. \nI find the result of this paper novel and timely: In federate learning, it is crucial to provide the justification of the necessity of collaboration since sharing information with others inevitably causes privacy issue and should only be conducted when there are actual benefits. I believe this work provides a solid stepping stone for analyzing the federated learning case.\nThe obtained theoretical improvement, coined multitask acceleration, is intuitive and the authors provide a complete picture on how such an improvement can be extended to general norm regularizer and Bregman divergence cases. \nFinally, the author also provided a variant of MT-OMD which is adaptive to the task variance parameter which is critical from a practical consideration. \n\nWeakness:\nI do not have much to complain about this paper and believe it can be readily accepted in the current status.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a multitask generalization of the online mirror descent method, which is able to exploit the correlation between tasks, by sharing updates between tasks. Specifically, the authors derive the MT-OGD method by introducing a interaction matrix in the standard OGD method and show that with a particular choice of the interaction, MT-OGD enjoys a multitask acceleration under the assumption that the variance of the reference vectors is small. While the above result is derived for the Euclidean regularization, the authors show that similar results can be obtained in general norm regularizer and Bregman divergence settings. Finally, a Hedge-based extension of MT-OMD is proposed which adaptive to the task variance parameter with the regret increased by only a small additional factor. The authors show that MT-OGD and MT-EG can be carried out efficiently and conduct simple experiments to validate their theoretical results empirically.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I do not have much to complain about this paper and believe it can be readily accepted in the current status.", "broader_impact_concerns": "This work may be a good starting point to provably show that the collaboration in FL is actually beneficial to users, which, in the first place, is the incentive of sharing private information.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper got overall positive reviews and all reviewers voted for acceptance.
I think this paper is well within the scope of TMLR and should be accepted.
Decision: Accept (poster)