Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning
Authors: Pier Giuseppe Sessa
Pierre Laforgue
Nicolò Cesa-Bianchi
Andreas Krause
Venue: NeurIPS 2023 poster (2023)
Keywords: multitask learning
confidence intervals
online learning theory
active learning
regret
TL;DR: We prove novel confidence intervals for multitask kernel regression and show their relevance in multitask online and active learning.

Abstract: Multitask learning is a powerful framework that enables one to simultaneously learn multiple related tasks by sharing information between them. Quantifying uncertainty in the estimated tasks is of pivotal importance for many downstream applications, such as online or active learning. In this work, we provide novel confidence intervals for multitask regression in the challenging agnostic setting, i.e., when neither the similarity between tasks nor the tasks' features are available to the learner. The obtained intervals do not require i.i.d. data and can be directly applied to bound the regret in online learning. Through a refined analysis of the multitask information gain, we obtain new regret guarantees that, depending on a task similarity parameter, can significantly improve over treating tasks independently. We further propose a novel online learning algorithm that achieves such improved regret without knowing this parameter in advance, i.e., automatically adapting to task similarity. As a second key application of our results, we introduce a novel multitask active learning setup where several tasks must be simultaneously optimized, but only one of them can be queried for feedback by the learner at each round. For this problem, we design a no-regret algorithm that uses our confidence intervals to decide which task should be queried. Finally, we empirically validate our bounds and algorithms on synthetic and real-world (drug discovery) data.

Multitask Learning with No Regret:
from Improved Confidence Bounds to Active Learning
Pier Giuseppe Sessa"
Pierre Laforgue" Università degli Studi di Milano pierre 1af orguuuuuiiimmmm it
ETH Zürich sessa@inf www.oeiif.ethh...cmmmm ethz.
Nicolò Cesa-Bianchi
Andreas Krause
Università degli Studi di Milano
ETH Zürich krauseaßethz.cc ch
Politecnico Milano
nicolo. cesa-bianaaaaeaee @unimi.
Abstract
Multitask learning is powerful framework that enables one to simultancously learn multiple related tasks by sharing information between them. Quantifying uncertainty in the estimated tasks is of pivotal importance for many downstream applications, such as online or active learning. In this work, we provide novel confidence intervals for multitask regression in the challenging agnostic setting, i.e., when neither the similarity between tasks nor the tasks' features are available to the learner. The obtained intervals do not require i.i.d. data and can be directly applied to bound the regret in online learning. Through a refined analysis of the multitask information gain,
obtain new regret guarantees that, depending similarity parameter, can significantly improve over treating tasks independently. We further propose a novel online learning algorithm that achieves such improved regret without knowing this parameter in advance, i.c., automatically adapting task similarity. As a second key application of our results, we introduce a novel multitask active learning setup where several tasks must be simultaneously optimized, but only one of them can be queried for feedback by the learner at each round. For this problem, we design no-regret algorithm that uses our confidence intervals to decide which task should be queried. Finally, we empirically validate our bounds and algorithms on synthetic and real-world (drug discovery) data.
task
Introduction
In many real-world applications, one often faces multiple related tasks to be solved sequentially or simultaneously. The goal of multitask learning (MTL) [4] is to leverage the similarities across the tasks to obtain more accurate and robust models. Indeed, by jointly learning multiple tasks, MTL can exploit their statistical dependencies, yielding better generalization and faster learning than treating each task independently. MTL has gained significant attention recent years, has been shown to be effective in a wide range of applications. including natural language processing, computer vision, federated learning, and drug discovery, see e.g.. [11, 19, 16, 27].
very natural model for learning across multiple tasks is the agnostic multitask (MT) regression approach of [13]. This utilizes multitask kernel that can interpolate between running N (number of tasks) independent regressions, and regressing all tasks to their common average, depending on tunable parameter. Notably, such kernel does require any knowledge neither about tasks' features
equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

taak
task 2
task
Independent
data
regression:
post. mean se(-)
contidence
task
task
task 3
true ['()
Multitask regression:
data
post. mean mn(-)
neive
improved contidence (this work)
Figure I:
Independent vs. Multitask (MT) regression. MT regression leverages data coming from multiple related tasks and can yield more accurate and more confident estimates. In this work, we show naive confidence intervals are overly conservative and provide improved ones (shaded in red).
nor about their similarity, thus finding good application in several domains. For instance, Cavallanti ct al. [5] study it for online classification, and Aesa-Bianchi et al. [6] for online convex optimization.
However, it is much less understood how to quantify the uncertainty of such MT regression, i.c., assessing confidence in the estimated tasks. In particular, also outlined by [13] as an open problem, it is important to assess their generalization error as a function of the kernel parameter. Appropriately characterizing these confidence intervals is indeed of crucial importance for a whole set of downstream applications. More concretely, multitask confidence intervals are used in online learning to inform the next decision to be made [6]. active learning- as we show next-these intervals are pivotal to deciding the most informative task to query.
In this work, we study the agnostic MT regression setup of [13], and provide new multitask confidence intervals (see Figure for a visualization) for the full range of the kernel parameter. Our intervals hold in the so-called adaptive setting, i.e., without requiring i.i.d. data, and are lighter up to /N factor than the naive ones employed in [6]. Moreover, we provide the first bounds for the information gain of MT regression and utilize them together with the derived intervals- to obtain tighter online learning guarantees. The latter depend on a task similarity parameter and can significantly improve over treating tasks independently. Additionally, we propose an adaptive no-regret algorithm that exploits task similarity without knowing this parameter in advance. Finally, we consider a novel multitask active learning setup, where tasks should be simultaneously optimized but only one of them can be queried at each round. We show that the newly derived intervals are also crucial in such setting, and provide new algorithm that ensures sublinear regret. We demonstrate the superiority of the derived intervals over previously proposed algorithms on synthetic as well as real-world drug discovery tasks.
Related work. The agnostic MT regression approach of [13] reduces the learning of N tasks to a single regression problem, as a function of the MT kernel parameter. When combined with support vector machines, it was shown effective in series of classification problems [13, 24], and since then was studied various further settings. Cavallanti al. [5], e.g., analyze mistake bounds for online MT classification algorithms as a function of the kernel parameter.
et al. [6], instead, utilize the MT kernel to prove regret bounds in online MT learning with bandit feedback. Inspired by this, [10] focuses on learning more general kernel structures from data. An important question not addressed by previous work, though, is how to properly quantify the uncertainty the obtained task estimates. This problem is well-understood in single-task learning (e.g.. [2, 25, 8)) but remains largely unexplored in MT domains. As shown in [6]. MT confidence intervals can in principle be obtained by naive application of the single-task guarantees of [2]. However, as we show in Section 2, the so-obtained intervals are extremely conservative and as a result- can hamper the MT learning performance. Our intervals are tighter by a factor up to /N w.r.t. the naive ones from [6]. yielding novel online learning regret guarantees which can provably improve over treating tasks independently.
Compared to MT online learning [5, 6], where a single task revealed to the learner each round, a series of works have considered learning multiple tasks simultaneously, i.e., taking a decision for each one of them. Dekel et al. [12], e.g., propose the use of a shared loss function to account for tasks' relatedness, Lugosi et al. [20] studies the computational tractability of taking multiple actions with joint constraints, while Cavallanti et al. [5] propose a matrix-ban based extension of the multitask Perceptron algorithm. In all of these works, however, the learner receives feedback from all the

---

tasks. In Section 4, instead, we focus on the challenging setup where only one task can be queried by the learner at each round. Hence, in addition choosing good actions, the learner faces the active learning task of assessing the most informative feedback, in order to achieve sublinear regret. Perhaps most related to ours, is the offline contextual Bayesian optimization setup [7, 18] where the goal is to compute the best strategy for each context (task) with minimal function interactions. However, unlike us, [7, 18] do not guarantee sublinear regret but provide only sample-complexity results.
Finally, we note that MT confidence intervals and regret guarantees were also recently derived by [9], albeit in different setup and regression model. Indeed, the authors of [9] focus on multi-objective optimization where they ought to learn multi-one outpur functions (each output corresponding to a task) using matrix-valued kernels. Although their setup can be related to ours, it crucially requires all tasks to be observed at each round, leading to different challenges than ours, see Appendix A.1 for details.
Notation. We use [N] (1...., N), 1N for the vector in R- full of ones. Norms of functions always taken w.r.t. the natural RKHS norm, so that we drop the subscript for simplicity of writing.
2 Improved Confidence Intervals for Multitask Kernel Regression
In this section, we introduce the MT kernel regression setting, and prove our refined confidence intervals. Of independent interest, these results are then leveraged in Sections 3 and 4 to derive novel regret bounds for online and active multitask learning. All proofs are deferred the Appendix.
2.1 Multitask Kernel Regression
Given an input space X, equipped with (single task) scalar kernel kx: X' x X + R. the goal of MT kernel regression is to jointly learn N different functions fi...., fN from X' to RR all belonging to Hkx: the RKHS associated to xx- To do so, the learner is given a set of triplets {(1,, Ys Y== consisting of measured task index i, [N], measured point F, E X, and noisy measurement y. = fü, (xx)) + E.. where Es is an independent random variable to be specified later. We can further define the multitask function frm; [N] x X + R such that (i, fi. and the multitask kernel
(ii, x), (f, z²)) - (i,
(1)
where by is kernel on the tasks. In certain cases, the latter might be given as input to the learner, either under the form of the task Gram matrix, or via task features and an assumed (e.g., linear) similarity [17]. However, in practice such information is usually not accessible to the learner. In such a case, standard agnostic approach to MT regression [5, 6, 10, 13, 24) then consists in leveraging a parameterized task kernel of the form
1 IN + b 1N1N 1 N ERNXN.
(i, = [Kmnk()) (b) wr
with Kiask (b)
Intuitively, parameter & 2 0 governs how similar the tasks are thought to be. When b = 0, we have (b) IN. such that ky 1') = owr, and the tasks are considered to be independent. When b goes +00, we have Kizs (b) = 1x1N/N and all tasks are considered to be one single common task. Any choice of b E (0, +00) corresponds to a tradeoff between these two regimes. We make this intuition explicit in Proposition (Appendix A. I). Note that all quantities depending on the kernel do by definition depend on b. We use the notation |6 to make this dependence explicit when relevant.
Given a history of measurements [(i., 2.), U V one may then estimate frl,, equivalently the {f.) N by standard kernel Ridge regression using the MT kernel k. One obtains the estimates
m4(i x: b) = k, ()) (K, AT.) Vi:t.
(3)
of 2 () = k((i, (i, x1) - x) [(,T(KKK_ + (1:) - (i,)),
(4)
where kz(i,z) ((s,,,, (i.z)) K.
[k((i,, - (is,, xxx) ( V1.t [M - and
A > 0 is some regularization parameter. Functions fr and of can be interpreted as the posterior mean and variance of corresponding Gaussian Process model, see [25, 8). In the next section, we will utilize μt and of to construct high-probability confidence intervals for the multitask function fmt
3

---

O(evoN)
Olevb)
VN +N Mo 1 1+0(V7))
naive
this work
60
80
b
Figure 2: Novel multi task confidence width wr (b) (see Theorem visualized for large and small
values of b. It improves over the naive width St. Snaive (b) by a factor of vN at and as b + +00. Problem parameters were set to B 1, 0.4, N = 20, = 4, and (b) 78 = 0 for all b.
Information gain. An important quantity when analyzing (multitask) kernel regression is the so-called (multitask) information gain:
TT (b) In - +
It can be interpreted as the reduction in uncertainty about f after having observed a given set of T datapoints. Similarly to single-task setups [25, 8], use 77 in the next sections to characterize our confidence intervals and regret bounds. Note that 77 depends on the multitask kernel through Kr, and hence on b. In Section we exploit the properties of our multitask kernel to obtain a sharper control over 7T", which is then fundamental to derive improved regret bounds.
2.2 Improved Confidence Intervals
In this section, we utilize the regression estimates obtained in Equations (3) and (4) to construct high probability confidence intervals around the unknown multitask function fr First, we assume that [|Sa]| < B for all i E [N], it is standard in single-task regression. Moreover, let Saz (1/N) Cr fi be the average task function, and define
max || l/gll/B.
Note that by definition E [0, 2]. The smaller the more similar the tasks are, the limit case being that all tasks are equal, attained at O. At the other extreme, when > 0 tasks are highly distant and ought to be learned independently. The deviation plays crucial role in the subsequent analysis.
naive confidence interval. As discussed in [6], it is possible to construct the multitask feature map v associated One may then rewrite fn1 (i, .)) = (f, (b,,, x))), where is transformed version of you which satisfies || < B / be2), see Appendices A. 1 and A.2 for details. MT regression
thus boils down to single-task regression, over the modified features (i,i, x)). and with target function f. One can then employ well-known linear regression results to obtain confidence intervals for fol Using [1, Theorem 3.11, Remark 3.13] and the definition of 7,th (b)). with probability 1 8 we have that for all / N, E [N], and X' it holds | (b) y (i, .r) S guaive (b) o b), where
Gruive (b) = BV/N1 + be?) + + 1/2 / 2 2 (b) + ln(1/8).
N(1
Note that the above confidence interval was already established in [6. Theorem 1]. As expected, depends on B, N, b, and in a decreasing fashion with respect e. However, we argue that the above naive choice can be extremely conservative. Indeed, when 6 = 0, MT regression treats tasks independently, see Proposition 2. Hence, valid confidence width from [2, 1, 8] is O(B + VYr where > is the single-task maximum information gain. Instead, noting that 7t (0) (NN see Proposition 1, the naive choice provides graive (0) = /N O(B + ) which larger by factor VN. A similar suboptimality gap of /N can also be proven when b tends to +oo. Motivated by the above observation, we derive a novel confidence width that is less conservative than S gnaive (b) for the whole range of possible kernel parameters b.
Theorem 1 (Multitask confidence intervals). Let fmt: [N] x X - such that for all i E [N], fi := (i. -) belongs to the RKHS associated to kx and [[ < B. Moreover, let bt and o, be the

---

regression estimates of Equations (3) and (4) with task kernel kr(i.j) = L (b)kk) parameter A E [1/[1+ b), 11, and noise {E-)==1 i.i.d.
Then, with probability at least 25,
[e((t x b) - (i, x> - 5,50 (b) (1)
ViEN,iE (E,N,EEN,.EEEE
3,t (b) min { (qaiiv(()) (b), gemaallb (b), gt (1)
where
gamall-b(b) (b) (31 + be)
1+ +N
+ + 1/2 22 (NV) In(N/6)),
1 1+b
(a)e)b(())) St Blageeb
Jarge.be
Bb
(b)
BV (1+ be)2
26N
+
NA7(1 6)3 1 x 22(12 V= In(1/)))
25(1 + bc)²
1+b
1
The obtained improved confidence width (b) is the minimum between three confidence widths, see Figure 2. The first one is the naive one 3am (b), obtained by standard arguments as outlined above, while 3.mall-b(() (b) and glarge-b(b)) (b) (dashed and dotted lines in Figure 2) are novel and useful for small and large values of respectively. Indeed, note that we have 3emall-bb()) (b) h-0,, O + 78 which is the expected single-task confidence width and VN smaller than /3paive (0). Similarly, as b goes to +oo we have 3 glange-(()) (b) b O(B + 2N + 22212/N) b- O(eBvb), while gepviee (b) t2 O(BBVNb). The obtained confidence width is therefore always smaller than the naive one, but also tighter by a factor VN for the extreme choices b and +00.
From technical viewpoint, (emmall-b and s.urge- are obtained by viewing MT regression as single-task regression over the inflated features (1, ) as also done in [6]. However, unlike [6], we explicitly leverage the expressions of (b(i,x: b) and Kass(() (b) as functions of b. In particular, because of the struc- ture of Kins, the regression kernel matrix a rank-one perturbation of a block diagonal matrix, a fact that we exploit, e.g., via Lemma 2. Moreover, we note that refined widths can be obtained if one has ac- cess to task specific constants B; and E,. For simplicity of exposition, we focus on uniform (over tasks) B and e. Also, a tighter data-dependent glurge-b can be utilized as outlined in Appendix A.2.2. Finally, we remark that the obtained multitask intervals do not require i.i.d. data and thus apply to the adaptive design setting where data are, e.g.. sequentially acquired by the learner, as shown in the next section.
3 New Guarantees for Multitask Online Learning
In this section, we show how the improved confidence interval established in Theorem I can be used to derive sharp regret guarantees for multitask online learning. To do we also prove novel bounds for the multitask information gain 7Tt (b). For t = 1, l, the learning protocol is as follows: nature reveals task index & [N]; the learner chooses strategy I; X' and pays (r" 22); the learner observes the noisy feedback = (is, + &s. The goal is to minimize for any horizon T the multitask regret
T!T (T)
Σ max ZE
f (it, 2))
Σ fm (ir,
(6)
In the next subsection, we provide generic algorithm to minimize (6). In particular, we show that naive choices of parameters allow to recover previous approaches with their guarantees, while using the refined confidence width Snew (b) derived in Theorem yields sigmificant improvements.
3.1 Algorithm and regret guarantees
In line with the online learning literature, our approach is based on the multitask Upper Confidence Bound, defined for any E N
ucb, x = po ()) Be(b) a. (i,
Here Br RR RR, a function which assigns a confidence width 3e(b) to each kernel parameter b. We consider the general strategy MT-UCB (see Algorithm 1) which, at each round t selects
5

---

Algorithm MT-UCB
Algorithm
Bc
Require: Domain X. kernel kx, number of tasks N, width functions (ee parameters b, A.
IGP-UCB [8]
Bemall--b
1: for t= ... do
[6]
Pt
b
2: Observe 4,
This work
Pt
N+b N46N
3: Play Ze = arg max, FEX ucb,-1 (b),
4: Observe 1/, fm (3r, + Ex.
Table Recovering previous works by
5: Update ucb.(..- based on (3),(4) and (7).
appropriate choices of Be, b, and A.
Jt arg m ucb;-1 b). As summarized in Table 1, both the strategy that runs N independent instances of IGP-UCB (one for each task), and GoB. Lin from [6] are particular cases of MT-UCB. Importantly, whenever (6) is set such that (= + (b) az(-.- (.f.-16)) 6)] is valid confidence interval for fr (.--), ), the regret of MT-UCB can be controlled through the following lemma.
Lemma 1. Suppose that X 2 (N + /) N + bN), and that for all tasks i, point x, and time t, we have f"" x ()) E [po(i, b) + (b) oe(i, ]. Then, the multitask regret of MT-UCB satisfies
(T) & (b) (b).
The main novelty of Lemma is that the right-hand side scales with 11/2, which might be chosen smaller than 1. This improvement is due the fact that multitask posterior variances smaller than (N + b)/(M (N + bN) < 1. The right-hand side also depends on the multitask information gain 1Tth (b), which is nontrivial
compute or upper bound. In the next proposition, we provide practical upper bounds of 7/7 (6), in terms of the kernel parameter and the single-task information gain 77.
Proposition 1. Ler À < 1, N 2 2, and T, 2 for all E [N]. Then, for any 2 0, we have
Nb
T
7T (b) S N
and
(T) S 7 + 2A(1 +
8(1 + b)
We can now combine Theorem 1, Lemma 1, and Proposition to obtain our main result: a bound on the multitask regret of UC- run with the confidence width Srew from Theorem and a specific A.
Theorem 2. Assume that B 1, and that MT-UCB is run with 3t 3 from Theorem 1, and (N + () bN). Let 2/e² ifT N, b 1/e² ifT 2 N and N-1/4T-1/2 and b 0 otherwise. (T) B V T (17 + In(1/5)) be the single task regret bound factorsss factors). Then, there exists universal constant C such that with probability 28 we have (up to log N factors)
achieved by IGP- (up to constant
Rm (T) = C Cin (NR (T) + cBT (V In(1/8) + cVT) RT eBTVN + + +eVNT)
The regret bound of Theorem 2 is the minimum between three bounds, obtained exploiting the three different regimes of the confidence width Srew derived in Theorem (see Figure 2). The first bound is obtained using gnew < @small-b, and shows that approach cannot be worse than independent learning. Indeed, it can be checked that, when facing N tasks, the regret of running N independent instances of IGP-UCB can be bounded by / N times the single-task regret bound of IGP-UCB, that denoted by (T)) Note however that analysis slightly differs, insofar multitask information gain, while the independent analysis uses Jensen's inequality to aggregate the individual bounds, see Appendix for details. Note finally that are able to recover this bound as 3 gemall-b tight b = 0, unlike guaive The second bound uses 3eew < 3 glarge-b and consists of two terms: the single task regret bound and an additional term that scales with the task deviation When the latter small, i.e., when tasks are similar, the dominant term R²T(T), as only one task were solved. The third bound is similar. but obtained using gnew gnaive and is useful when T > N. In
leverage the

---

contrast with the independent bound, which does not exploit the task structure, the last two bounds show that multitask learning is always beneficial when the horizon T (and thus the additional e-related term) is small. As expected, this is particularly true when the number of tasks N is large: while the independent bound increases, the second bound does not depend on N. On the other hand, one can note that the condition on e to improve over independent becomes more constraining as the horizon T increases. This suggests that the benefit of multitask may vanish with the number of available points per task, an observation which is well-known by practitioners, see e.g. [21]. As far we know, this work is the first one to provide theoretical evidence of such a phenomenon in online MT learning.
We conclude this section by comparing Theorem 2 to existing results. As already mentioned in the above discussion, independent IGP-UCE is a particular case of MT-UCB, such that we cannot be worse than the independent approach. We incidentally recover its regret bound as the first bound in the minimum of Theorem 2. Regarding GoB. Lin, since it is also a specific instance of MT-UCB (for Be Bapaiv and x = 1), Lemma allows to recover its regret bound [6, Theorem 1].
Corollary 1 (Regret of GoB. Lin [6]). For any b, the multitask regret of GoB. Lin using parameter b satisfies with probability
RThh (T) S 4,37 (b) TOVYTAOO S (BVN(L+ bE2)
+ In(1/0) ) /INF(6).
(8)
If tasks are similar, i.c. when < 1, bound (8) suggests to choose b > 0: this does not impact too much the first term, but makes 7T (6) smaller. However, we recall that the above bound instantiated with b 0 does not recover the independent bound. It is instead v vN bigger, since guaive is not tight at b = O. Hence, the Gob. Lin analysis is not sufficient to show that multitask learning improves over independent learning. Our refined analysis, which uses instead Snew. closes this gap.
3.2 Adapting to unknown task similarity
In this section, we consider the case where parameter c (i.e., a bound on the task deviation from the average, see (5)) is a-priori unknown. Despite this challenge, show that the regret bound of Theorem 2 can be approximately attained using an adaptive procedure, AdaMT-UCB (Algorithm 3), relegated to Appendix B.4 due space limitations. The proposed approach is inspired by the model selection scheme of [22, Section 7] with a few important modifications that we will outline at the end of this section. AdaMT- UCB considers a plausible set of parameters & {eI...... egg] egg) and, for each e E E, initializes an instance of the UT-UCB algorithm with parameters set according to Theorem assuming notation ueb,, to denote the upper confidence bounds constructed by MT MT-U We assume the existence of some e E such that 2 C, so that at least one of the learners is well-specifiee (i.e., its confidence bounds contain fo with high probability). Our goal is to incur a regret which grows as the regret of the learner with the smallest e such that e 2 c, since the smaller the e the smallest the regret bound (see Theorem 2), as long as is valid upper bound for Let us identify with e* such learner.
(0. 2]
e. We denote such an instance as MT-UCB(e). Moreover, we use the
At each round I, AdaMT-UCB uses learner é min &, and plays the action 24 suggested by it, i.e., the maximizer of ucb,* (ie. -). Then, all MT MT-UCB(e) learners are updated based on the observed reward. In the meantime, a misspecificcaiion test is carried out to check whether learner e, is well-specified. Such test compares the obtained cumulative reward, a lower confidence estimate on such reward according the other learners, and the believed regret of learner e,, As long the test does not trigger, the regret of learner e₁ is controlled by the believed one. Instead, if the test triggers, learner e, can be considered misspecified with high probability. As result, it gets removed from E and new epoch starts with the new set E. Let (T) denote the regret bound (Theorem 2) of learner ex had it been chosen from round O. We can state the following.
Theorem 3. Assume that there exists e E E such that e 2 E, and let M be the number of learners E E such that e < E (i.e., the number of misspecified learners in E). The regret of ACAMT-UCE satisfies with high probability (TT = 0 (VM++ +1 ITm
Clearly, the number M of misspecified learners is not known in advance but is always less than [E]. Note that when e = O. we have M = O and we recover the single task regret bound. Moreover, given p S 1, we show in Appendix B.4 that one can attain a multiplicative accuracy p over e, assuming that 2 Emin > 0, through an exponential grid with M being polylogarithmic in 1/p and 1/Emin-
7

---

Relation with the approach of [22]. Compared to [22, Section 7] wheee the goal is to adapt to an unknown features' dimension the set of learners considered AdaNT-UCB share the same dimension d. This allows us to exploit the following two novelties with respect to [22]: (1) all learners are updated from the data gathered from learner i, (Line 6 in Algorithm 3), and (2) the lower confidence bounds I, in the misspecification test (Line 8) are all computed using action 2y (i.e., the action recommended by learner it), as opposed to using the actions recommended by each learner e. Both these points are only applicable to our setting, leading to a simpler regret analysis.
4 Multitask Active Learning
The goal of the online learning setup of Section is to optimize the tasks sequentially revealed by nature. In some situations (e.g., in [20] the drug discovery problem considered in Section 5), however, we care about the performance of multiple tasks simultaneously, to eventually learn the best strategy for each of them. Moreover, we ought to do so with minimal interactions T, i.e., minimizing the queries of the function frm We capture this by the following active learning protocol.
Learning protocol and regret. At each round I, the learner: chooses strategy ( i E [N]] for each task, chooses which task i E [V] to query, and observes the noisy feedback y/ = fmh (4,, (44 + The learner's goal is to minimize the active learning regret:
T
N
T
N
RALL (T)
=
max ZEX
fTH (1,
Σ 1=1
(i,z)).
N
t=1
Compared to the online learning regret of Equation (6), the learner's performance at each round is here measured by the average reward coming from each task (as opposed to just the task presented by nature). Moreover, compared to online learning. the learner faces the additional challenge of choosing aaoossing-att at each round-frre (or informative) tasks should be queried more often to ensure AA grows sublinearly. To the best of our knowledge, the above protocol and regret notion are novel in the multitask literature.
which task information should be gathered. Intuitively, more difficult
In Algorithm 2 present MT-AL, efficient strategy that ensures sublinear active learning re- gret. Like in MT-UCB, MT-AL constructs confi- dence intervals around f and, at each round, select strategy =t arg maX ucb;-1 (i) for each task i E [N]. When it comes to se- lecting which task to query, MT-AL selects i, E arg [ - z)), i.e., the task for which the believed optimizer oi is subject to max-
Algorithm 2 AL
for i= do
o arg max ucb, - (), Vi E [N]
8. = arg max 10-10--11 (1, x()
Observe: y/ = =f (be, x² + &
Update (cb and (e(.,)) based on observations.
imal uncertainty (we use generic task-dependent widths 3i for completeness). This rule, also known as uncertainty sampling in the literature [23], intuitively makes sure the learner can control the regrets for the tasks not queried and leads to the following theorem.
Theorem 4. Suppose that for all tasks point x, and time
have that fm'(i,)) [pr(i, x) + 3t (i() Then, the MT-AL algorithm ensures the active learning regret is bounded by
T M S (1)))
where {ir} is the sequence of queried tasks and {x/() } the strategies selected for each of them.
The above bound only relies MT-AL utilizing valid intervals around futt and thus applies more broadly than our agnostic MT regression, e.g., when such intervals are constructed using a known multitask kernel & 2i, v"))))). However, Theorem shows the active learning regret heavily depends on the constructed intervals, similar to online learning. In MT-AL, these are additionally utilized for deciding which task to query at each round. When specialized our agnostic MT kernel and improved confidence, we obtain the following.
Corollary 2. Let MT-AL utilize the MT regression estimates of Eq. (3)-(4) with parameters set according to Theorem 2. Moreover, let (T)) be the bound on the online learning regret obtained in Theorem 2. Then, with high probability, have (TT < (T).
8

---

Synthetic
Drug discovery
Synthetic
Drug discovery
1007
100
90-
200
20-
30-
100
Independennt
MT-UCB, nnive (GoB Lin)
AdaMT-UCB
Unif., naive
Unaf,, improved confidence
MTS
Single MT-UCB, improved confidence
MT-AL,
MT-AL, improved confidence
AEI.VI
(a) Online learning
(b) Active learning
Figure 3: Online and active learning regrets synthetic and drug discovery MHC-I data, respectively, When utilizing the improved confidence intervals, MT-UCB and MT outperform the other baselines.
Thus, MT ensures the active learning regret is always bounded by its online learning counterpart. Moreover, the same considerations as in Theorem apply also here, regarding the benefit of multitask learning over independent single-task regression for instance.
5 Experiments
The goal of our experiments is evaluate the effectiveness of the studied MT regression, and in particular of the improved confidence intervals obtained in Section 2, both in online learning and active learning setups. We utilize the following synthetic and
data?.
We generate tasks of the form f. = (1 - 5) - f 7 5 fácy: i E [N], where F. få are random unit vectors representing common model and individual deviations. respectively. Moreover, actions consist of 10a vectors & E Rd from the sphere of radius 10. Observation noise unit normal.
Synthetic data:
Drug discovery MHC-I data [27]: The goal is to discover the peptides with maximal binding affinity to each Major Histocompatibility Complex class-I (MHC-I) allele. The dataset from [27] contains the standardized binding affinities (ICs0 values) of different peptide candidates to the MHC-I alleles (tasks). For each allele, the dataset contains ~ 1000 peptides represented as x E 1R:4 feature vectors. utilize the 5 alleles A-(0201, 0202, 0203, 2301, 2402). since they were
For our experiments, shown in [27] to share binding similarity. Note that such problem falls into our multitask active learning setup, since we would like to retrieve the best peptide for each allele minimizing the number of interactions (i.e., lab experiments). Nevertheless, we also consider its online learning analog where care about finding the best peptides for each revealed allele.
Online learning. At each round 1, a random task it E [N] is observed and point x, is selected according to the following baselines: (1) Independent, which runs N independent IGP-UCB [8] algorithms (corresponding to MT-UCB with b= 0), (2) Single, which treats all tasks to the same and runs unique single-task IGP-UCB (corresponding to MT-UCB with b +oo), (3) MT-UCB which utilizes an appropriate parameter 0 < b < oo as well as a bound on the tasks similarity (for synthetic data this can be exactly computed, while for MHC-I data Gob. Lin) or improved confidence bounds, and (4) AdaMT-UCB which is run with the same but uses the set of plausible deviations & {.1, 2. ... 1} instead of knowing the true e. For choosing b, sweep over possible values and select the best-performing one, keeping it fixed for all the baselines.
0.3) and utilizes the naive (i.e.,
Active learning. We follow the multitask active learning setup of Section 4. All baselines utilize confidence intervals from the agnostic MT regression of Section 2, where e and b are chosen as for online learning. Moreover, they all utilize the improved confidence intervals, unless otherwise specified. We compare: (1) Unif. which chooses the task i, to be queried uniformly at random (but still selects z E arg max, ucb) (i. 2)) and employs the naive or the improved confidence intervals, the offline contextual Bayesian optimization baselines (2) MTS [7] and (3) AE-LSVI [18), and (4) MT-AL which utilizes the naive or the improved confidence intervals.
code available at: https: http:/gghhi..coo///ssss/////mtmt

---

We report the cumulative regret (online and active learning, respectively) of the considered baselines in Figure 3, averaged over 5 runs. For the synthetic data, we report results for d 4, N = 5, ó 0.4, but provide full set of experiments for different parameters in Appendix D. In Appendix D) we also report the frequencies of each task being queried in our active learning experiments. In Figure 3 (a), both MT and AdaMT UCB lead to superior performance compared to the Independent and Single baselines, demonstrating the benefits of MT regression. In addition, the improved confidence intervals significantly outperform the naive ones. Moreover, we observe AdaMT-UCB achieves comparable (sometimes even better, see Appendix D) performance to MT- Indeed, instead of using conservative choice of e, the misspecification test (Line 8 of Algorithm 3) of AdaMT-UCB allows to use a smaller e and only increase it when there is evidence that the constructed intervals do not contain the true tasks. In active learning (Figure 3 (b)), we observe MT AL has significant advantage over the uniform sampling baselines and MTS, while performing comparably to AE-LSVI (both methods similar discussed in Appendix C.3). Moreover, its regret is bounded by the online learning regret of MTU conforming with Theorem 4. Importantly, the improved confidence intervals play crucial role also here and enable drastic performance improvement compared to the naive ones.
Future Directions
We believe this paper opens up several future research directions. The derived confidence intervals, as well as our analysis of the multitask information gain, heavily exploit the structure of the task Gram matrix Kussk (b), see Equation (2). However, it remains unclear whether these can be extended to more general kernels. According to the graph perspective of [13], K (b) can be seen as (b) = IN + L(b). where L(b) E N is the Laplacian matrix of clique graph with vertices [N] and edge weight b. Hence, it would be interesting to extend our results to different graph structures. Furthermore, we believe the proposed multitask confidence intervals hold potential for various related domains., c.g., to assess uncertainty in safety-critical systems [3], or to balance exploration-exploitatoon in multitask reinforcement learning [26), spam filtering [15], personalized
health [14]. In such applications, the introduced notion of active learning regret can serve as a measure of the overall sample efficiency.
Acknowledgements
This work was partially supported by ELSA (European Lighthouse on Secure and Safe Al) funded by the European Union under grant agreement No. 101070617. PL and NCB gratefully acknowledge the financial support from the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), funded by the NextGenerationEU program within the PNRR scheme (M4C2, investment 1.1), the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEUU program within the PNRR-PE-A scheme (M4C2, investment 1.3, line on Artificial Intelligence), and the EU Horizon ELL-2022-HUMANE research and innovation action under grant agreement 101 120237. project ELIAS (European Lighthouse of AI for Sustainability).
References
[1] Yadkori, Y. (2012). Online learning for linearly parametrized control problems. PhD thesis, Edmonton, Alberta, Canada.
[2] Abbasi- Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems ( (NeurIPS). 24.
[3] Camilleri, R., Wagenmaker, A., Morgenstern, J. H., Jain, L., and Jamieson, K. G. (2022). Active learning with safety constraints. Advances in Neural Information Processing Systems (NeurIPS).
[4] Caruana, R. (1997). Multitask learning. Machine learning, 28:41-75.
[5] Cavallanti, G., Cesa-Bianchi, N., and Gentile, C. (2010). Linear algorithms for online multitask classification, Journal of Machine Learning Research, 11:2901-2934.
[6] Cesa-Bianchi, N., Gentile, C., and Zappella, G. (2013). A gang of bandits. Advances Neural Information Processing Systems (NeurIPS), 26.
10

---

[7] Char, L,, Chung, Y., Neiswanger, W., Kandasamy, K. Nelson, A. O., Boyer, M.. Kolemen, E.,, and Schneider, (2019). Offline contextual bayesian optimization. Advances in Neural Information Processing Systems (NeurlPS), 32.
[8] Chowdhury, S. R. and Gopalan, A. (2017). On kemelized multi aumti-armed bandits. In International Conference on Machine Learning (ICML), page 844 853.
[9] Chowdhury, S. R. and Gopalan, A. (2021). No-regret algorithms for multi-task bayesian opti- mization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1873-1881.
[10] Ciliberto, C., Rosasco, I.,, and Villa, S. (2015). Learning multiple visual tasks while discovering their structure. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 131-139.
[1I] Collobert, R. and Weston, (2008). A unified architecture for natural language processing: Deep neural networks with multitask learning. In International Conference on Machine learning (ICML.. pages 160-167.
[12] Dekel, O., Long, P. M., and Singer, Y. (2007). Online learning of multiple tasks with a shared loss. Journal of Machine Learning Research, 8(10).
[13] Evgeniou, T., Micchelli, C. A., Pontil, M., and Shawe-Taylon Taylor, J. (2005). Learning multiple tasks with kernel methods. Journal of Machine Learning Research, 6(4).
[14] Harutyunyan, H., Khachatrian, H., Kale, D. C., Ver Steeg, G., and Galstyan, A. (2019). Multitask learning and benchmarking with clinical time series data. Scientific data, 6(1):96.
[15] Jain, G., Sharma, M., and Agarwal, B. (2019). Spam detection in social media using con- volutional and long short term memory neural network. Annals of Mathematics and Artificial Intelligence, 85(1):21-44.
[16] Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. (2021). Advances and open problems federated learning, Foundations and Trends@ in Machine Learning, 14(1-2):1-210.
[17] Krause, A. and Ong, C. (2011). Contextual Gaussian process bandit optimization. Advances in Neural Information Processing Systems (NeurIPS), 24.
[18] Li, X., Mehta, V., Kirschner, J., Char, I., Neiswanger, W., Schneider, J., Krause, A., and Bogunovic, I. (2023). Near-optimal policy identification in active reinforcement learning. Interna- tional Conference on Learning Representations (ICRL).
[19] Liu, S., Johns, E., and Davison, A. J. (2019). End-to-end multi-task learning with attention. In Proceedings of the IEEE/CVF conference computer vision and pallern recognition, pages 1871-1880.
[20] Lugosi, G., Papaspilioppolos, O., and Stoltz, G. (2009). Online multi-task learning with hard constraints. In Conference on Learning Theory (COLT).
[21] Maurer, A., Pontil, M., and Romera-Paredes, B. (2016). The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32.
[22] Pacchiano, A., Dann, C., Gentile, C., and Bartlett, L. (2020). Regret bound balancing and elimination for model selection in bandits and rl. ArXiv, abs/2012.
[23] Settles, B. (2009), Active learning literature survey. Technical report, University of Wisconsin- Madison Department of Computer Sciences.
[24] Sheldon, D. (2008). Graphical multi-task learning. Technical report, Cornell University, Ithaca, NY.
[25] Srinivas, N., Krause, A., Kakade, S., and Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning (ICML).
11

---

[26] Vithayathil Varghese N. and Mahmoud, Q. H. (2020). A survey of multi-task deep reinforcement learning. Electronics, 999):3363.
[27] Widmer, C., Toussaint, N. C., Altun, Y., and Rätsch, G. (2010). Inferring latent task structure for multitask learning by multiple kernel learning. BMC bioinformatics, 11(8))1-8.
12


Reviews:
[{"review_id": "a8whQBEzGn", "reviewer": "Reviewer_J9Sp", "summary": "The primary objective of this paper is to analyze the confidence bound of the multi-task kernel regression model and explore its application in online learning and active learning scenarios. Initially, the authors introduce a novel confidence bound, revealing distinct regimes based on task similarity. Notably, their bound proves to be tighter than a naive alternative. Leveraging this improved confidence interval, they proceed to devise online learning and active learning algorithms, providing comprehensive analyses of the confidence intervals in these contexts. In conclusion, the authors conduct empirical comparisons of their methods against existing approaches and baselines, utilizing synthetic data and drug discovery data to validate their findings.", "questions": "- Line 217 and 218: \"This suggests that the benefit of multitask may vanish with the number of available points per task, an observation which is well-known by practitioners\". Are there any relevant citations?", "limitations": "I think the empirical results are quite limited. But this limitation is not mentioned.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The analysis on the confidence interval of the multi-task kernel regression seems to be a decent addition to the related literature for adapting multi-task kernel regression to online and active learning.\n- Their analysis can provide insight into how training on different tasks can be used to help out on other relevant tasks, which seems to help understanding multi-tasks learning in general.", "weaknesses": "I think the weakness of this work lies in the empirical results.\n- The empirical results are quite limited with only one real dataset and a synthetic dataset. \n- It is mentioned that for online learning, the parameter b is selected based on sweeping over all possible values and choose the best performing one. However, I am not sure if this is possible in practice. At least, a separated validation set should be used for parameter selection. (this problem seems to be also existing in the active learning setting)\n- The empirical results for active learning are also a bit weak. According to Figure 3, it seems that the proposed algorithm could be slightly worse in some T and at best on par with existing algorithms. Are there any other benefits for adapting the proposed algorithm instead of other competitors in practice?\n- For active leaning, I believe this work could also benefit from a more detailed analysis on the how are the examples being selected with different algorithms differs from each other.\n\nminor:\n- The y-axis in Figure 3 should have labels.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the raised points, to which we would like to individually respond below.\n\\\n\\\n**W1 (empirical results on 2 datasets only).**\nWe would like to point out that our work is primarily of theoretical nature and that experiments are essentially designed to support our theoretical findings. In that respect, we believe our experimental setup provides empirical evidence to all of our following claims:\n- the novel confidence intervals derived in Theorem 1 outperform their naive counterparts (as depicted in Figures 1 and 2) and are key for effective multitask learning. This is confirmed both in our online and active learning experiments where we run baselines using the naive intervals and our improved ones. In addition, in our set of synthetic experiments (see Figure 4 in Appendix D) we observe that the higher the number of tasks $N$, the more our improved intervals outperform the naive ones. This perfectly conforms with –and experimentally verifies– our theory.\n- the algorithms we introduce (MT-UCB-improved confidence, AdaMT-UCB, MT-AL-improved confidence) outperform existing methods, including the independent single-task approach, see Figures 3 and 4.\n- AdaMT-UCB, which automatically adapts to the tasks relatedness, is at least on par (if not better) with the strategy that can access (a bound on) the tasks’ deviation $\\epsilon$, see Figures 3 (a) and 4.\n\n**W2 (selection of $b$).**\nRecall that we are in an online learning setting, in which the learner must make predictions at each time step for each new data point arriving. Hence, it is impossible to resort to a pre-existing validation set to select parameter $b$. We view $b$ as a tunable hyperparameter, similar to a tunable confidence width in standard Bayesian optimization (BO). However –unlike when tuning the width in BO– we note that our confidence intervals hold for any choice of $b$ (see, e.g., Figure 2), thus one could in principle employ more sophisticated hierarchical approaches (e.g. running experts on a grid of possible $b$) to perform as well as with the best $b$ in hindsight. We feel this is beyond the scope of our work and would have cluttered the paper. The situation is different for $\\epsilon$, which must be a valid bound on the unknown tasks’ deviations (thus potentially affecting the validity of our confidence intervals) and for which we have designed the AdaMT-UCB adaptive procedure.\n\n**W3 (weak active learning experiments).**\n**We respectfully disagree.** First, we note that the primary goal of such experiments is to show the benefits of our improved confidence intervals over the naive ones, when utilized for active learning. In that regard, we observe that “Uniform, improved confidence” and “MT-AL, improved confidence” significantly and consistently outperform “Uniform naive” and “MT-AL naive”. Moreover, when considering the other baselines MTS and AE-LSVI, we remark that they also utilize our improved confidence intervals, which are thus partly responsible for their performance. We will make sure this comes across clearly. Second, when comparing with MTS in drug discovery, we observe that MTS has quite an aggressive behavior in the first steps, securing high rewards, but then suffers *linear* regret (i.e., it fails to converge to the optimal strategy for each task). Instead, the goal of our active learning setup is to achieve *sublinear* regret (as proved in Theorem 3), which is empirically satisfied by MT-AL in both experiments. Finally, the fact that MT-AL and AE-LSVI enjoy similar performance was pretty expected (we also mention this in Line 352). Indeed, as discussed in Appendix C3, both approaches use very similar decision rules. However, unlike for MT-AL, it is an open problem to provably bound the active learning regret of AE-LSVI.\n\n**W4 (query frequencies).**\nWe have followed the reviewer’s suggestion and analyzed the frequency of each task being queried by each of the baselines. These are visible in the figures included in the attached pdf (in the general rebuttal) which we will be happy to add to the paper. In the synthetic experiments (top plot), we observe that all the active learning baselines (i.e., MT-AL, MTS, and AE-LSVI) query more often tasks 1 and 5. These are found to be the tasks with the smallest norm and consequently the smallest signal-to-noise ratio, thus requiring more learning data. In our drug-discovery experiments, unfortunately, we cannot compute such norms since we do not have access to the underlying task vectors. However, we notice that MT-AL and AE-LSVI query with slightly more frequency task-3 (corresponding to allele A-0203). Instead, MTS focuses heavily on task-1 due to its different query strategy. Indeed, unlike MT-AL and AE-LSVI which query the task with maximal uncertainty, MTS queries the task with maximal potential performance increase. This aggressive strategy may explain the observed imbalance and the regret of MTS which grows linearly (Figure 3, rightmost plot).\n\n**Minor weakness (Figure 3).** As specified in the caption of the figure, the y-axes in Figure 3 represent the regrets (online and active). We will add a label in the revision of the paper.\n\n**Question (missing reference).** We will add relevant citations. See for instance Section 5.4 in “When is Multi-task Learning Beneficial for Low-Resource Noisy Code-switched User-generated Algerian Texts?” by Adouane and Bernardy (2020).\n\\\n\\\n\\\nWe hope the above points clarified the reviewer’s doubts about our work. We are happy to provide more detailed answers based on the reviewer's feedback."}, {"review_id": "mLFJPslOwx", "reviewer": "Reviewer_EaHC", "summary": "This paper focuses on multitask learning in the agnostic setting. It provides multitask confidence intervals and novel online learning algorithm that achieves such improved regret. The paper also introduces a novel multitask active learning setup where several tasks must be simultaneously optimized but only one of them can be queried for feedback by the learner at each round. They design a no-regret algorithm that uses the confidence intervals to decide which task should be queried.", "questions": "- Can you please also add other real-world applications where multi-task active learning can be extended? This can be a part of the future work section/paragraph.", "limitations": "- I think that the main limitation is that the proposed method isn't compared directly with existing single-task methods as baselines.\n- Is it possible to have an active learning method built for single-task and apply it to all tasks in an MTL problem? How does that compare? For instance, techniques like Margin sampling or Least confidence can be easily applied to each task in an MTL problem with minimum overhead.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Theoretical analysis in this field of MTL is valuable\n- The proposed active learning problem in MTL is interesting and can be extended to other real-world applications.\n- The proposed method is thoroughly evaluated on synthetic and real-world drug discovery data.", "weaknesses": "- Although the paper is well written, I feel that it is densely pack with multiple goals. It would be a easier to understand if the paper focus more on a single concept rather than expanding it to several applications and add empirical results for each of them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our theoretical analysis and experimental evaluations. Below we address the raised points.\n\n \n> Can you please also add other real-world applications where multi-task active learning can be extended?\n\nWe agree with the reviewer’s suggestion and we will add further potential applications in the future work section. In particular, we have identified two compelling ones: *personalized health*, where one seeks to discover the best treatment for each patient, and *spam filtering*, where one seeks to obtain an accurate spam policy for each user. These are well-known applications of multitask learning but in both cases, the active learning component can play a crucial role. Indeed, our setup and approach would allow one to quickly discover the best strategy for each of the tasks (patients or email users) with minimal invasiveness.\n\n> I think that the main limitation is that the proposed method isn't compared directly with existing single-task methods as baselines.\n\n**We respectfully disagree with the reviewer.** Indeed, it is precisely the main goal of our work to show that multitask learning can be beneficial compared to single-task learning (as depicted, e.g., in Figure 1), both theoretically and experimentally as we argue below. \nIn our setup, the natural single-task baseline consists of performing $N$ independent regressions, and for each task selecting actions based on the UCB rule (this is similar to Margin or Least confident sampling, but with provable no-regret guarantees). Indeed this is the main baseline we want to compare to. We denote it as ‘Independent’ in our experiments and in what follows. \n- In terms of theory, our entire analysis in Section 3 is devoted to comparing the regret of MT-UCB with the one of ‘Independent’. In particular, the first bound in Theorem 2 is the regret of ‘Independent’, while the second and third bounds refer to multitask learning. They show that multitask learning is provably beneficial whenever the number of tasks $N$ is large and the tasks’ deviation $\\epsilon$ is small, as intuitively expected. To the best of our knowledge, we are the first to provably illustrate this phenomenon, and this is thanks to our refined confidence intervals derived in Theorem 1. In addition, by carefully selecting parameter $b$, our analysis also shows that MT-UCB always attains the minimum of all three bounds, hence being never worse than single-task learning. \n- In terms of experiments, we observe that ‘Independent’ is significantly and consistently outperformed by MT-UCB as expected from our theory.\n\n> Is it possible to have an active learning method built for single-task and apply it to all tasks in an MTL problem? How does that compare? For instance, techniques like Margin sampling or Least confidence can be easily applied to each task in an MTL problem with minimum overhead.\n\nThe reviewer is correct that such techniques can be applied independently to each task to efficiently discover their best strategies. However, we would like to remind the reviewer that our active learning setup focuses on the challenge where *only one* of the tasks can be queried at each round. In such a case, one also needs to sequentially decide *which* task is the most informative one to query.\n\\\n\\\n\\\nWe hope the above resolve the reviewer's concerns and we are happy to provide further answers if something remains unclear. \n"}, {"review_id": "1JWVLJfwq3", "reviewer": "Reviewer_kioq", "summary": "This work studies uncertainty quantification of estimated tasks in agnostic multitask regression. Through exploiting the structure of the task Gram matrix, This work proposes an improved bound on the multitask confidence interval that is tighter than a previous confidence interval [1] from by at most $\\sqrt{N}$.  With the derived interval, this work designed an online learning algorithm based on the upper confidence bound which selects the input with the largest upper confidence. This work also derives a regret bound for the online learning algorithm, showing that multitask learning is always beneficial. Moreover, this work designs a no-regret algorithm in an active learning setting, which uses confidence intervals to decide which task should be queried. This work proves that under the algorithm the active learning regret is always bounded by its online learning counterpart. To evaluate the proposed approach, this work conducts experiments on a synthetic dataset and a drug discovery dataset. In online learning, the proposed algorithm (MT-UCB) with the improved confidence interval outperforms independent learning, single-task learning, and MT-UCB with a previous bound [1]. In the setting of active learning, the proposed algorithm (MT-AL) improves over previous active learning algorithms, including MTS [2], AE-LSVI [3], and MT-AL with a previous bound [1]. \n\n [1] Cesa-Bianchi, N., Gentile, C., and Zappella, G. (2013). A gang of bandits. *Advances in Neural*\n\n*Information Processing Systems (NeurIPS)*. \n\n[2] Char, I., Chung, Y., Neiswanger, W., Kandasamy, K., Nelson, A. O., Boyer, M., Kolemen, E., and Schneider, J. (2019). Offline contextual bayesian optimization. *Advances in Neural Information Processing Systems (NeurIPS)*. \n\n[3] Li, X., Mehta, V., Kirschner, J., Char, I., Neiswanger, W., Schneider, J., Krause, A., and Bogunovic, I. (2023). Near-optimal policy identification in active reinforcement learning. *Interna- tional Conference on Learning Representations (ICRL)*.", "questions": "- What would be the effect for different hyper-parameters in the algorithm, such as $b$, $N$, and $\\delta$? \n\n- What would be the interpretation for better results of AdaMT-UCB compared to MT-UCB as shown in experiments? ", "limitations": "This work has discussed the limitations of the proposed methods. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper derives an improved confidence interval that is tighter than the naive confidence interval in multitask regression. \n- This paper designs two effective algorithms using the largest upper confidence based on the derived confidence interval for online multitask learning and active multitask learning. Moreover, this paper provides regret analysis for the proposed algorithm which is shown to be not worse than a previous regret bound.\n- This paper empirically evaluates the proposed method in synthetic and drug discovery datasets and shows the advantages of the proposed methods in terms of regrets. ", "weaknesses": "It would be better to provide more intuition of deriving the improved confidence interval. For example, provide a proof sketch of Theorem 1 in terms of leveraging the expression of $K_{task}(b)$. Moreover, it would be better to provide an explanation of notations from the previous work, such as $\\tilde{f}$ and $\\tilde{\\phi}(i,x|b)$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and suggestions. We address below the specific questions raised.\n\n\n> It would be better to provide more intuition of deriving the improved confidence interval.  For example, provide a proof sketch of Theorem 1.\n\nWe agree with the reviewer’s suggestion, we expand here on the proof sketch of Theorem 1. The computation of the confidence width typically involves the inversion of some kernel-related matrix, see e.g., (Chowdhury & Gopalan 2017, Section C). In our agnostic multitask formalism, this matrix can be written as a Kronecker rank-one perturbation of an easily invertible matrix, such that one can compute the inversion in closed form, see Equation (20). We are left with two terms: one similar to independent learning, and one due to multitask learning. An appropriate bounding of the latter, depending on the value of $b$, provides the improved bound. In particular, we bound it in two different regimes: for large $b$ and for small $b$. We will add this proof sketch after Theorem 1, and recall the used notation.\n\n\n> What would be the effect for different hyper-parameters in the algorithm, such as $b$, $N$, and $\\delta$?\n\nParameter $b$ defines the agnostic multitask kernel (Eq. (2)) used for regression and intuitively controls how much information is shared across the tasks, as opposed to learning each task independently. We give further intuition on $b$ in Proposition 2 (Appendix A.1), where we show that the choice of $b$ interpolates between running $N$ independent single-task regressions ($b=0$) and treating all tasks to be identical ($b=\\infty$).\n\nParameter $N$ refers to the number of tasks, which is a problem-dependent parameter and is not tunable; it is only used by the algorithm to define the multitask kernel Eq. (2) and the associated confidence intervals (see Theorem 1). Strictly speaking, the algorithm implementation (and performance) does not require knowing $N$, but only the number of tasks observed *so far*, which is readily available information.\n\nFinally, the confidence level $\\delta \\in (0,1)$ is utilized to tune the width $\\beta_t$ of the multitask confidence intervals, see Theorem 1. In particular, the smaller the $\\delta$ the wider the confidence intervals and the higher the probability (i.e., $1-\\delta$) with which they contain the true unknown task functions. In practice, $\\delta$ is usually set between 0.01 and 0.05. In our experiments we conservatively chose $\\delta=0.01$.\n\n\n> What would be the interpretation for better results of AdaMT-UCB compared to MT-UCB as shown in experiments?\n\nWhile MT-UCB requires an upper bound on the tasks’ deviation $\\epsilon$ (to be used for building multitask confidence intervals), AdaMT-UCB starts with a smaller value of $\\epsilon$ ($0.1$ in our experiments) and only increases it when there is evidence that the constructed intervals do not contain the true tasks. Thus, this allows AdaMT-UCB to be less conservative and potentially achieve superior performance (because the algorithm’s regret grows proportionally to the used $\\epsilon$, see Theorem 2). We have remarked on this fact in our experiments section (lines 347-350). We also believe this is a very interesting finding that can be of potential independent interest, whenever one would like to combat the use of overly conservative confidence bounds.\n\\\n\\\n\\\nWe hope the above point clarified the reviewer's concerns about the paper. We are happy to expand them further if needed.\n"}, {"review_id": "LzIY5w1A9Q", "reviewer": "Reviewer_ckqH", "summary": "This paper focuses on multi-task regression problems where they provide tighter confidence bounds that can be used to establish regret bounds in multi-task online learning and multi-task active learning. They also propose an algorithm that reduces the regret compared to previous bounds by adapting a task similarity parameter automatically. They perform regression experiments on a synthetic dataset and a drug discovery dataset (MHC-I) to show that their algorithms yield better (lower) regret than the reported baselines. ", "questions": "**Q1:** Can you elaborate on the interpretation of the expression for calculating “regret” in Eq. 6? And can you elaborate on what a “no-regret algorithm” is?\n\n**Q2:** Can the proposed confidence intervals and regret bounds be used for classification tasks? Can they be applied for deep neural networks in multi-task learning problems for both regression and classification?\n\n**Q3:** Are there any metrics other than regret  that are relevant to report in the experiments, e.g., RMSE?\n\n**Q4:** Since you are focusing in this agnostic setting where the task similarity is unknown, I am wondering if you can mention any examples or applications where the task similarity parameter $b$ is actually known? I get the feeling that $b$ is unknown in most multi-task learning problems. \n", "limitations": "No limitations are addressed as this is a theoretical work according to the authors. See Weaknesses and Questions above for limitations that I am concerned over. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The proposed confidence and regret bounds are general in the sense that they can be applied in online and active learning in the multi-task setting. At times, the paper prepares the reader what a section with a summary sentence, e.g. on L86-87 “In this section, we introduce the MT kernel regression setting, and prove our refined confidence intervals.” The multi-task active learning setting where only one of the tasks can be queried per time step is interesting.", "weaknesses": "**W1:** I am not a multi-task learning expert, however, I have to say that I find the paper hard to follow. There is a lot of inline math which makes reading less smooth. Also, most of the notation is introduced within the sections, while a separate paragraph that thoroughly describes all the notation that will come would have been of great help for the reader to go back to if necessary. Furthermore, I think the paper needs re-writing to emphasize what the main messages are to the reader in each section and paragraph. \n\n**W2:** One of the main contributions, Algorithm 3, described in Section 3.2 is placed in the Appendix, probably due to lack of space. I suggest that the Section 2 and 3 are re-written such that Algorithm 3 can fit into the main paper.   \n\n**W3:** Experiment section is very short (<1.5 pages). I believe that the paper would benefit from adding more experimental results to justify the contributions, as well as adding discussions around the results and emphasizing on the take-home messages to bring insights to the reader. \n\n**W4:** In my opinion, the scope of the paper is narrow as it only covers regression tasks in multi-task learning without touching any classification tasks. Furthermore, there are no experiments using deep neural networks which makes me doubt how relevant this paper is for the general audience at Neurips. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for going through our work. We respond below to the raised weaknesses and questions.\n\n**W1.**\nWe will use the extra page upon acceptance to introduce our notation in a separate paragraph.\n\n\n\n**W2.**\nWe will use the extra page upon acceptance to move Algorithm 3 into the main text. \n\n\n**W3.**\nWe would like to point out that our work is primarily of theoretical nature and that experiments are essentially designed to support our theoretical findings. In that respect, we believe our experimental setup provides empirical evidence to all of our following claims:\n- the novel confidence intervals derived in Theorem 1 outperform their naive counterparts (as depicted in Figures 1 and 2) and are key for effective multitask learning. This is confirmed both in our online and active learning experiments where we run baselines using the naive intervals and our improved ones. In addition, in our set of synthetic experiments (see Figure 4 in Appendix D) we observe that the higher the number of tasks $N$, the more our improved intervals outperform the naive ones. This perfectly conforms with –and experimentally verifies– our theory.\n- the algorithms we introduce (MT-UCB-improved confidence, AdaMT-UCB, MT-AL-improved confidence) outperform existing methods, including the independent single-task approach, see Figures 3 and 4.\n- AdaMT-UCB, which automatically adapts to the tasks relatedness, is at least on par (if not better) with the strategy that can access (a bound on) the tasks’ deviation $\\epsilon$, see Figures 3 (a) and 4.\n\nIn addition, following the suggestion of Reviewer J9Sp, we have performed additional analyses and interpretations for our active learning experiments reporting the frequencies of each task being queried by each of the baselines (see Figures in the pdf attached to the general rebuttal).\n\n\n**W4.**\n**We respectfully disagree.** First, regression is one of the most fundamental problems in machine learning; many ML algorithms build upon standard single-task regression and the associated confidence intervals. More recently –and among many other applications– these are used, e.g., in reinforcement learning, or in combination with deep models which provide powerful embeddings, thus enabling a whole set of downstream applications. Regarding the relevance to the venue, we would like to point out that deep learning is just one of the several topic areas at NeurIPS. Moreover, as discussed above, our experimental setup is specifically designed to support our theoretical findings and we do not need to use neural networks to do so.\n\n\n**Q1.**\nThe notion of regret typically measures the difference between the performance achieved by the learner and that of the best comparator for the considered problem. This is the de-facto metric in online learning (and not only, see e.g. [1,2,3]), where it is used to quantify the performance of sequential decision-making algorithms. The learner is said to achieve “no-regret” if its regret $R(T)$ grows sublinearly with $T$ (or equivalently $R(T)/T \\rightarrow 0$). Thus, as $T\\rightarrow \\infty$ its average performance converges to the one of the best comparator. In our multitask (MT) setting, in particular, the regret of Eq. (6) quantifies the cumulative difference between the best reward achievable for each revealed task and the reward of the strategies chosen by the learner. Thus, a no-regret MT algorithm is such that as $T\\rightarrow \\infty$ the learner discovers the best strategy for each task. \n\n[1]: Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.\n\n[2]: Agarwal, N., E. Hazan, and K. Singh (2019). \"Logarithmic regret for online control.\" Advances in Neural Information Processing Systems 32.\n\n[3]: Auer, P., Jaksch, T., & Ortner, R. (2008). Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21.\n\n\n**Q2.**\nThey only apply to regression because they exploit the fact that the prediction space is continuous. However, they can be combined with deep networks, see e.g. [4], to perform linear regression on the last layer (i.e., the deep-net provides embeddings). This is becoming popular for uncertainty quantification and online learning. \n\n​​[4] Damianou, A., & Lawrence, N. D. (2013, April). Deep Gaussian processes. In Artificial intelligence and statistics (pp. 207-215). PMLR.\n\n\n**Q3.**\nBecause our work focuses on *sequential* decision-making setups, the regret is the main relevant performance indicator to quantify the speed of learning. RMSE better applies to offline regression in the presence of train/validation splits, which is not our focus.\n\n\n\n**Q4.**\nWe would like to remind the reviewer that parameter $b$ does not correspond to the tasks’ similarity, but to a tunable modeling parameter that dictates how much information one wants to share across tasks (see, e.g. Proposition 2 in the Appendix). Indeed, our confidence intervals (and guarantees) hold true for the whole set of possible choices of $b$. However, though, some choices of $b$ perform better than others for the given problem. In Theorem 2 we have derived a theoretical choice for $b$ which optimizes the regret bound of MT-UCB up to constants. In practice, although we have tried different values and picked the best, one could run more sophisticated hierarchical approaches (e.g. based on experts) to learn the best $b$ online. We feel that this is a complementary approach beyond the scope of the paper. Note that the situation is different w.r.t. parameter $\\epsilon$, which instead *must be* a known bound on the tasks’ deviation and for which we have designed the adaptive AdaMT-UCB procedure.\n\n"}, {"review_id": "kecrL3bdte", "reviewer": "Reviewer_w9gE", "summary": "This paper proposes refined confidence intervals for multitask kernel regression and applies this to the multitask online learning setting and the multitask active learning setting. The thrust of the idea is to further exploit the structure of the task kernel (Eq (2)) where the refined confidence bound is always smaller than the existing confidence bound and tighter by a factor of sqrt of the number of tasks for the extreme cases of b=0 and b=infty, corresponding to the independent tasks or identical tasks, respectively. \n\nTwo important parameters: $b$ is the task-relatedness in the definition of the multitask kernel and $\\eps$ is the task discrepancy from the average task. \n\nThe paper studies both cases of known and unknown $\\eps$. When $\\eps$ is unknown, they use a minibatch learning idea and misspecification task to determine the smallest upper bound of $\\eps$ from the predefined search space. This only incurs an extra term of the square root of the search space cardinality. \n\nThe paper also provides empirical validations to justify their results. \n\n---------- \nUPDATE: I am raising my rating from 5 to 7 to champion this paper. I think this is a solid contribution to the multitask learning setting and I would view this paper as an (interesting) theoretical contribution, rather than a strong algorithm paper in the deep learning setting. On this ground, I think the experimental results the paper presented are sufficient for validating the usefulness of multitask learning in the settings they considered. I believe the points raised by Reviewer ckqH are important but can be largely addressable without changing the scientific merit claimed in the reviewed paper. In particular, I agree with Reviewer ckqH in that the paper should make it clear from the title and the abstract that the paper focuses on a multitask kernel setting, not a general multitask learning setting.", "questions": "- An implicit assumption is that each $f_t$ is a sample of the known $GP(k_X)$ that I feel the paper does not make it explicit enough. \n- Also the task kernel in Eq (2) driven by $b$ is a modeling choice, not an assumption because the only task relatedness assumption comes from $\\epsilon$. The author can correct me on this point if I'm wrong. Either way, whether the task kernel is an assumption or a modeling choice should be made explicitly to the readers. \n- Line 211: $N >= T$ instead? \n- Line 248 - 250 about the misspecification test: the intuition behind why this test works should be explained further (I know what the test means but its current explanation is not very helpful to all readers). \n- The regret notion in Section 4 looks weird to me. Isn't $i_t$ instead of $i$ in the second term of the regret notion? Because the learner actively queries a task, thus, the goodness of the queried tasks should be included in the regret. \n- The second and third bound in Theorem 2 is definitely helpful when $\\epsilon = 0$. In which other regimes they are also helpful? and which are not?", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- a new refined confidence bound that is tighter than the naive bound by exploiting the structure of multitask kernel. This result is neat. \n- a comprehensive study where they apply to various learning settings and provide empirical results", "weaknesses": "- some of the writing is not clear but improbable \n- the notion of regret in section 4 looks weird", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for raising these questions, which we address below.\n\n> An implicit assumption is that each $f_t$  is a sample of the known $GP(k_X)$  that I feel the paper does not make it explicit enough.\n\nIn this work, we take a frequentist interpretation and assume the tasks$ f_i$ are fixed (but unknown) functions in the reproducing kernel Hilbert space of a known kernel $k_x$. We mention such an assumption at the beginning of Section 2.1. This is the frequentist analog of the Gaussian process assumption mentioned by the reviewer (see, e.g., [Srinivas et al. 2010] where both Bayesian and frequentist interpretations are compared), and allows one to learn such functions via kernel regression.\n\n\n> Also the task kernel in Eq (2) driven by $b$ is a modeling choice, not an assumption because the only task relatedness assumption comes from $\\epsilon$. The author can correct me on this point if I'm wrong. Either way, whether the task kernel is an assumption or a modeling choice should be made explicitly to the readers.\n\nThe reviewer is perfectly correct about the task kernel in Eq. (2) being a modeling choice (and not an assumption) and indeed it is what allows one to exploit the benefits of multitask learning. The choice of $b$ can interpolate between single-task and all-tasks regression (as we show in Proposition 2 in Appendix A.1). Indeed, the derived intervals (see, e.g., Figure 2) are a function of the parameter $b$ that one decides to use. We will make sure it comes across clearly. In Theorem 2 –in particular– we suggest a possible theoretical choice for $b$ (as a function of $N$, $T$, and $\\epsilon$) which leads to the derived online learning regret bounds.\n\n\n> Line 211: $N \\ge T$ instead?\n\nNote that the second bound in Theorem 2 grows with $T^{3/2}$, while the third bound with $T\\sqrt{N}$. Thus, the latter is beneficial (i.e., smaller) when $N \\leq T$.\n\n\n> Line 248 - 250 about the misspecification test: the intuition behind why this test works should be explained further.\n\nWe acknowledge that the intuition and the role of the misspecification test can be explained further. Upon acceptance, we would use the extra page to move the AdaMT-UCB algorithm (currently in Appendix) to the main text and provide extra intuition about the test.\n\n\n> The regret notion in Section 4 looks weird to me. Isn't $i_t$ instead of $i$ in the second term of the regret notion? Because the learner actively queries a task, thus, the goodness of the queried tasks should be included in the regret.\n\nThe fact that the active learning regret of Section 4 depends on all tasks $i$ and *not* exclusively on the queried one $i_t$ is precisely what makes it different and more challenging than the standard online learning regret of Eq. (6). Indeed if in online learning we only care about the task which is revealed at each round (i.e., $i_t$), in active learning we care *simultaneously* about all the tasks (hence, the regret depends on all $i \\in [N]$ at each round) and face the additional challenge of deciding which task to query to learn them as fast as possible. If the regret were only dependent on the queried task $i_t$, then a trivial good strategy would be to always query the ``easiest” one, yielding a small regret but not learning the other $N-1$ tasks. We hope this clarifies the reviewer’s perplexity.\n\n> The second and third bound in Theorem 2 is definitely helpful when $\\epsilon = 0$. In which other regimes they are also helpful? and which are not?\n\nCompared to the first bound (which corresponds to independent learning), the second and third bounds in Theorem 2 refer to multitask learning. As hinted by the reviewer, they are always beneficial for $\\epsilon=0$ (i.e. when tasks are all identical) but when $\\epsilon>0$ their benefit generally depends on the interplay among the number of tasks $N$, the horizon $T$, and $\\epsilon$ itself. As discussed after Theorem 2, for a given $\\epsilon$ the benefit of such bounds degrades as $T$ increases (large data regimes) or when the number of tasks $N$ is small. Moreover, note that the second bound does not depend *at all* on $N$. Thus, for any $\\epsilon$ and $T$ there exists a number of tasks $N$ above which multitask learning is beneficial. Finally, we remark that the particular choice of $b$ derived in Theorem 2 allows MT-UCB to always attain *the minimum* of such three bounds and thus it can never be worse than independent learning.\n\\\n\\\n\\\nWe hope the above points address the reviewer’s concerns and we are happy to provide additional insights if needed.\n"}]

Author rebuttal:
We thank all the reviewers for going through our work and providing insightful suggestions and comments. 
We have addressed each of the reviews individually, hoping that most of the reviewer’s concerns are resolved. 

We are happy to provide additional insights and details based on the reviewers’ feedback.

The attached *.pdf refers to the additional details inquired by Reviewer J9Sp. 
 


Meta-review: Based on the reviews and the responses, the reviewers are in broad agreement that:

- The paper makes a solid theoretical contribution on constructing confidence intervals for multi-task kernel regression
- This paper empirically evaluates the proposed method in synthetic and drug discovery datasets

In the discussion phase, Reviewer w9gE and Reviewer J9Sp championed this paper due to its solid theoretical contributions. However they also acknowledged Reviewer ckqH's presentation suggestion that the paper should make it clear from the title and the abstract that the paper focuses on an online multitask kernel regression setting, not a general multitask learning setting. Please take this into account in the camera-ready revision.
Decision: Accept (poster)