Improved Regret Bounds for Non-Convex Online-Within-Online Meta Learning
Authors: Jiechao Guan
Hui Xiong
Venue: ICLR 2024 poster (2024)
Keywords: meta learning theory
non-convex online meta learning
piecewise-Lipschitz/non-Lipschitz functions
regret bounds
PAC-Bayes generalization bound
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: This paper provides improved regret bounds for non-convex online-within-online meta learning and a novel PAC-Bayes bound for multi-task learning via regret analysis.

Abstract: Online-Within-Online (OWO) meta learning stands for the online multi-task learning paradigm in which both tasks and data within each task become available in a sequential order. In this work, we study the OWO meta learning of the initialization and step size of within-task online algorithms in the non-convex setting, and provide improved regret bounds under mild assumptions of loss functions. Previous work analyzing this scenario has obtained for bounded and piecewise Lipschitz functions an averaged regret bound $O((\frac{\sqrt{m}}{T^{1/4}}+\frac{(\log{m})\log{T}}{\sqrt{T}}+V)\sqrt{m})$ across $T$ tasks, with $m$ iterations per task and $V$ the task similarity. Our first contribution is to modify the existing non-convex OWO meta learning algorithm and improve the regret bound to $O((\frac{1}{T^{1/2-\alpha}}+\frac{(\log{T})^{9/2}}{T}+V)\sqrt{m})$, for any $\alpha \in (0,1/2)$. The derived bound has a faster convergence rate with respect to $T$, and guarantees a vanishing task-averaged regret with respect to $m$ (for any fixed $T$). Then, we propose a new algorithm of regret $O((\frac{\log{T}}{T}+V)\sqrt{m})$ for non-convex OWO meta learning. This regret bound exhibits a better asymptotic performance than previous ones, and holds for any bounded (not necessarily Lipschitz) loss functions. Besides the improved regret bounds, our contributions include investigating how to attain generalization bounds for statistical meta learning via regret analysis. Specifically, by online-to-batch arguments, we achieve a transfer risk bound for batch meta learning that assumes all tasks are drawn from a distribution. Moreover, by connecting multi-task generalization error with task-averaged regret, we develop for statistical multi-task learning a novel PAC-Bayes generalization error bound that involves our regret bound for OWO meta learning.

Published as a conference paper at ICLR 2024
IMPROVED REGRET BOUNDS FOR NON-CONVEX ONLINE- ONLINE-WITHINE WITHIN-ONLLNE META LEARNING
Jiechao Guan', Hui Xiong'.
AI Thrust, The Hong Kong University of Science and Technology (Guangzhou), China GGuangzhou HKUST Fok Ying Tung Research Institute, China {j (jiechaoguan, BtonghuiJehkuse edu.cn
ABSTRACT
Online-Withe Within-Online (OWO) meta learning stands for the online multi-task learning paradigm which both tasks and data within each task become available in a sequential order. In this work, we study the OWO meta learning of the initial- ization and step size of within-task online algorithms in the non-convex setting, and provide improved regret bounds under mild assumptions of loss functions. Previous work analyzing this scenario has obtained for bounded and piecewise Lipschitz functions an averaged regret bound O(( ymm + (1177
(log m)) T + V))m) /TT across tasks, with m iterations per task and the task similarity. Our first contribution is to modify the existing non-convex OWO meta learning algorith- I. and improve the regret bound to O(( + (log + V)) for any a E (0, 1/2). The derived bound has a faster convergence rate with respect to T, and guarantees a vanishing task-averaged regret with respect fixed T). Then, we propose a new algorithm of regret O(( log + V)ym) for non-convex OWO meta learning. This regret bound exhibits a better asymptot- ic performance than previous ones, and holds for any bounded (not necessarily Lipschitz) loss functions. Besides the improved regret bounds, our contributions include investigating how to attain generalization bounds for statistical meta learn- ing via regret analysis. Specifically, by anline-to-batel arguments, we achieve a transfer risk bound for batch meta learning that assumes all tasks are drawn from distribution. Moreover, by connecting multi-task generalization error with task- averaged regret, we develop for statistical multi-task learning a novel PAC-Bayes generalization error bound that involves our regret bound for OWO meta learning.
(for any
INTRODUCTION
Meta learning, also referred to as learning to learn, is multi-task learning paradigm that transfers knowledge from past tasks to the new task for fast adaptation (Thrun & Pratt 1998). Due to the advantage of reducing annotation cost and training time for novel task, meta learning has received
increasing attention over the last decade, both from practical (Finn et al.) 2017 Snell et al. 2017
Ye et al. 2020) and theoretical perspectives (Baxter 2000 Balcan et al. 2019 Chen et al.) 2020).
Traditional meta learning theory mainly investigates generalization bounds for statistical/batch meta learning (Baxter, 2000; Pentina & Lampert 2014] Maurer et al., 2016;] Guan et al.) 2022). In this setting, samples within each task are assumed be drawn from the same data distribution and pro- cessed in batch, and different tasks are drawn from the same task distribution. Recently, there emerges an interest in studying online meta learning, where tasks are observed sequentially and require real-time processing (Alquier et al.) 2017 Finn et al. 2019). According to (Denevi et al., 2019, there are two main frameworks in online meta learning setting: (1)
Within--attte (OWB) framework, where tasks are available in sequential order but the data within each task are available in one batch, see (Finn et al., 2019) Zhuang et al., 2020 Acar et al.) [202I). (2) Online- Within-Online (OWO) framework, where both tasks and data within each task are available and pro- cessed sequentially, see (Alquier et al. 2017 Denevi et al. 2019 Khodak et al. 2019 Balcan et al.
"Corresponding Author.

---

Published as a conference paper at ICLR 2024
2019 2021). The goal of this paper is to investigate the OWO meta learning of catllliizzaaio--bbeddd online optimization algorithms in the non-convex setting, and provide strong theoretical guarantees.
Initialization based online algorithms (c.g. online gradient descent (Zinkevich 2003 typically have two the parameter. OWO meta learning aims to utilize knowledge from previous tasks initialization and step size of online algorithm on novel task for fast adaptation. Recall that the metric used measure the performance of online single-task learner is the so-called regret, which is defined as the gap between cumulative loss of online learner and the cumulative loss of the best fixed strategy in hindsight, Analogously, the metric used to measure the performance of OWO meta-learner is the averaged regret across 'I' training tasks, denoted as task-averaged regret (Balcan et al. 2019p. Previous work (Balcan et al., (02T) analyzing the non-convex OWO meta learning of initialization-basee online algorithms has attained for bounded and piecewise Lipschitz. functions a /m), with m iterations per task and V the task similarity. However, this bound has two limitations: (1) For any fixed T, it cannot guarantee a vanishing regret with respect to (w..t.) m; (2) The convergence rate w.r.t. T is slow. In this work, we attempt to address the two issues and provide improved regret bounds with fine-grained analysis.
to learn: the initialization of model's parameter, and step size to update
good
task-averaged regret bound ((( ymm + (logm) log
T1/4
/T
Our first contribution is based on the modification of existing non-conver OWO meta learning al- gorithm from |Balcan et al. (202T). We improve the regret bounds of online algorithms for learning initialization and step size respectively, and combine them get the sharper task-averaged regret
bound of ((( + (log T7" mm) for any a E (0, 1/2). The derived bound has faster convergence rate w.r.t. T,, and guarantees a vanishing task-averaged regret w.r.t. m (for any fixed T). Then, we propose a new and more efficient algorithm of regret O(( loos + +V) for non-convex OWO meta learning. This regret bound exhibits better asymptotic performance than previous ones, and holds for any bounded (not necessarily Lipschitz) loss functions. Furthermore, we show how to attain generalization bounds for statistical meta learning via regret analysis. Specifically, by online- to-batch arguments, we achieve a new transfer risk bound for non-convex batch meta learning in which different tasks are drawn from task distribution. Moreover, by revealing the connection be- tween multi-task generalization error and task- avseraee regret, we develop for statistical multi-task learning novel PAC-Bayes generalization error bound that involves our improved regret bound for non-convex OWO meta learning setting. To the best of our knowledge, this is the first PAC-Baye bound for batch/online multi-task setting that imposes distribution assumption over the data per task.
T
To summarize, our contributions are four-fold fold: (1) For non-convex OWO meta learning, we improve regret bound from O(( y + (logm) m) log + V) to O((p=/2-. + (log 2/ (logr))0² + +m) (a E VT
T
10,1/2) for bounded and piecewise Lipschitz functions. (2) We design a new and efficient OWO meta learning algorithm of sharper regret bound O(( (oosT + +Vvmm for bounded (not necessarily Lipschitz) functions.
(3) We obtain new transfer risk bound for statistical meta learning via regret analysis. (4) We derive PAC-Bayes bound for multi-task learning, shedding light on proving PAC- Bayes multi-task generalization bound with the regret bound from non-convex OWO meta learning.
2 RELATED WORK
Meta Learning. In OWB meta learning setting, the meta parameter is transferred and updated sequentially across T tasks. Concretely, when encountering a training task, OWB meta learning algorithm takes the meta parameter and the training data from the task as input, and outputs model suitable for that task. The incurred loss of the task specific model over the evaluation data is denoted as the online loss on the task. The gap between the cumulative loss of updated meta parameters across T tasks and the cumulative loss of the best fixed meta parameter in hindsight is defined as the regret. Thus, the regret bound for OWB meta learning is of Ollog T") in the strongly-conver setting (see (Finn et al. 2019 Cor 2)), and of O(VT) in the convex/non-convee setting (see (Acar et al., 2021, Thm 1) and (Zhuang et al., 2020 Thm I)). These regret bounds are irrelevant to the sample size m per task, and are achieved under very strong assumptions of loss functions (e.g. including Lipschitzness, smoothness, and Hessian smoothness).
Regret Bounds for Online-
Regret Bounds for Online- Within-Online Meta Learning. OWO meta learning is more chal- lenging than OWB meta learning. Existing algorithms in OWO meta learning can be catego- rized into two groups: (1) The first group learns a common meta parameter (e.g. a feature map
2

---

Published as a conference paper at ICLR 2024
Alquier et al.) 2017) or a meta regularization function (Denevi et al. 2019 shared across T tasks and uses the meta parameter to learn specific model for each task. The averaged regret bound across m iterations and T tasks in (Alguier et al., 2017 Thm 3.1) is of O V + 1/VT). The regret bound in (Denevi et al. 2019 Thm 1) is of Olylogm/ works focus on convex OWO meta learning, and it is hard to extend their analysis (e.g. es- pecially the primal-dual technique in Denevi et al.] (2019) to the non-convex setting. (2) The second group learns the initialization and step size of online algorithms for each task, and com- bines the regrets for learning these two sepee-pprameters to obtain ultimate averaged regret across T tasks. Concretely, the task-averaged regret bound in (Khodak et al., [209 Thm 5.1) is of O(loog T/T + log T/vT + V)ym) for convex and Lipschitz functions. The bound in (Balcan ct al. 2021 Thm 3.3) is of (((vm/T// + (log m) log + V))m) for non-convex and piecewise Lipschitz functions. Our work focuses on non-convex setting, improves regret bound to ((1/T1/22 +(og T) / VT+ /m) in Theorem for piecewise L Lipschitz functions, and further obtains a sharper regret bound of O(log T/T + V)Vm) in Theorem 3 for non-Lipschitz functions.
+ 1/VT). However, both
Generalization Bounds for Statistical Meta Learning. The basic assumption in statistical meta learning theory is that all tasks are sampled from the same task distribution (Baxter 2000). Under this assumption, Guan et al. (2022) summarize existing generalization bounds for meta learning into three groups: (I) Generalization bounds based on hypothesis space complexity (c.g. covering
number based ones (Baxter 2000) and Gaussian complexity based ones (Maurer et al.; 2016 (2)
Generalization bounds based on PAC-Bayes theory (Pentina & Lampert
2014
|013] Guan & Lu
2022). (3) Generalization bounds based on algorithmic stability (Maurer 2005 Chen et al. 2020).
However, with the tool of stability analysis. Guan et al. (2022) point out that, under the statistical
task distribution assumption, the optimal generalization bound for meta learning is of O(L/vT), where T is the number of training tasks. The optimal bound is irrelevant the sample size m per task and hence is slow, indicating the limitation of task distribution assumption. Our transfer risk bound in Theorem 4 via regret analysis is different from the above generalization bounds for meta learning. Our bound of O(V2/ decreases with higher similarity among T training tasks, shedding more light on the generalization ability of meta learning models. More discussions about generalization bounds for statistical multi-task learning can be found in Section A of the Appendix.
PRELIMINARY
In online learning, an action space θ is compact subset of Rdd A loss function E: θ + R20 is called c-strroglyy convex with respect to (w.r.t)) certain norm ||- in Id if for any x, y E O we have ((x) - E(w) 2 (g, x - y) + 1| yl where g E Al(y) and ag(y) denotes the set of subgradients of f y. If & is differentiable, de denotes the set of (unique) gradient of E, i.e. O = {Ve). When a = 0, l is called convex. E is called uniformly L-Lipschitz over Q w.r.t. the norm || ll. if for any y θ, |f(x)= {(y) < L| - yll. Let P(O) be the set of all probability distributions over action space O. For any P E P()) and any loss function l, we use (p. E) = (()) for brevity when the context is clear. We use boldface letter x to denote the real vector in high-dimensional space, and a as its normalized version x/ ||=]|. We also use abbreviation [m] = 21, m.} for any integer m.
Online Learning. Vanilla online learning (also called online single-task learning setting) is always cast as a m-round optimization problem. At each round i E [m]], the online learner selects an action 8, O. Then a loss function 4 θ + R2o is revealed from the nature and the online learner suffers loss ((.)) of the chosen action 6, The quantity used to measure the performance of online learner is the so-called regret, which is the difference between the cumulative loss of chosen actions during m rounds and the cumulative loss of the best fixed action in hindsight. Detailed introduction of regret bounds for convex/non-conver online learning can be found in Section of the Appendix.
Meta Learning. In non-convex OWO meta learning setting, the online meta-learner will encounter T tasks and each task E [T] is composed of a sequence of m loss functions {fu= θ + R20)semm] Concretely, at i-th round of the (-th task, the online meta-learner selects an action O:: E θ, and then suffers the loss (oi()re), with les chosen adversarially from the nature. The regret for task t is defined as Rt.m è > Ea--o (0) minsge Dm (0). Then, the quantity to measure the performance of online meta-learner is the following task-averaged regret:
Online-Withe
T
T m
RI RT.m=
Σ 1=1
Rt.m
Ea-pu (il()li(()))))))) ((r0)--rr(()) (0))),,, where 07 E arg min BE0
Σ (n()). (1)
T
T
3

---

Published as a conference paper at ICLR 2024
If we set the probability distribution pi as Dirac measure de; that only has mass at the point 0%, can rewrite the above task-averaged regret in a concise form: Rr,, = T Σ Σx- (Pts pt, lu)- The upper bound on Rr.m is denoted as mr.m- The goal of OWO meta learning is to improve the single-task regret by leveraging information from other tasks. Formally speaking, we expect that when I is large enough, the task-averaged regret Rr.m is smaller than the single-task regret Re.m-
4 REGRET BOUNDS FOR NON-CONVEX ONLINE META LEARNING
Following previous work (Balcan et al., 2021). we study the non-convex OWO meta learning of the initialization and step size of the Exponentially Weighted Aggregation (EWA) algorithm. We first provide general framework for analyzing the regret bounds for non-convex OWO meta Learn- ing. Such framework is motivated by the form of regret upper bound of EWA (see regret bound for piecewise Lipschitz functions in Eq. (2) and regret bound for non-Lipschitz functions in Eq. D
gmm,, where b > 0, X is the step size, Pt1 E P(() the ini- tialization distribution over the action space è for task t. P E P(()) may have some dependence on the optimal action 07. VPtti,p)) 2 is the non-negative function of Pei and Pf (e.g. the diver- gence between Pei and pi ). (m)) is the term that cannot be optimized by meta learning. We then set V = minpe + ΣT pF) as the task similarity among T tasks. We will also use fe(p) = pp) for brevity when the context is clear. Using the scaling technique, the regret bound Up(p,) A) of the EWA algorithm run with initialization p E P(O) and step size x= = mbb for v > can be rewritten as an equivalent form: Ut(p, v) (e+ f.(e), /mmb+ Therefore the OWO meta learning algorithm always consists of two online sub- uub-algorithms: one is to play action over functions (p) (p, (.pppt)) pt)²) )e((-)] to determine the initialization distribution Pri for task t, determine the step size 2/- The process of utilizing {et|se(t-1) and {est= to determine the initialization distribution Pei and the step size v, for EWA algorithm on task f. can be considered as transferring knowledge from past tasks to the novel task. Combining the regret bounds for this two online sub-algorithms at- tains the following task-averaged regret bound for non-convex OWO meta learning algorithms with general functions (i.e. without boundedness, convexity or Lipschitzness assumptions of (..21.)))
A.) màde ((pn.
de
another is to play action over functions (v)
+ (
Theorem 1 Assume that the upper regret bound for each task t E [T]] has the form of Ue(p,v) (u + hale) /mb g(m). Assume we have a sub-algorithm that achieves Fr (p) regret w.r.t. any p E P(O) by setting distributions Pei on fe(p) = (p,, pi)², and another sub-algorithm that achieves mon non-increasing Hr(v) regret w.r.t any > 0 by playing actions U, > On h2(v) = ++ fe(pa) for all t t (T). Then, running the OWO meta learning algorithm (consisting of these two sub-algorithms) with the step size v mb and initialization Pe at each task for p* = arg pEP(p) Σ Se(p) the optimal initialization and V the task similaril, we get the avek-averaged regret upper bound:
T m (p:: pt S +I
(
HT(()) T
Fr(p") VT
Fr(o*), T ++2
min
.2
mb + g(m).
We need to mention that the task-averaged regret upper bound framework in Theorem is not only suitable to analyze EWA, but also applicable to any online algorithm (e.g. Follow-The-Per Perturbeedd Leader in (Suggala & Netrapalli 2020 Thm 1)) with the regret bound of form (p, (u +
Edll Vmb + g(m). In Sections 4.1 4.1 4.2 we leverage different strategies to learn initialization Pr for Lipschitz and non-Lipschitz functions. For learning the step size U, we consistently use Follow- The-Leader (FTL) algorithm, as running FTL can achieve the following logarithmic regret bound.
Proposition 1 Assume that FTL algorithm runs on the sequence of functions (he(v) v + fd(pa) hEm over the domain [0, D), where 1>2 2 maxte(T) fe(Pes), then we have the regret bound:
T
33 T
1-1 f((pa)) fo
Σ hv(( min Σ ho(l) vE(o,
Σ (a(pa)
1=1 Furthermore, for all t [T]. f((pa)
t=1
[B2 with D > B 0, then we have the logarithmic
2
regret upper bound: TT h2(1)) min Σ h,(w) < 1 (log T + 1).
4

---

Published as a conference paper at ICLR 2024
Table 1: Different task-averaged regret bounds for OWO meta learning algorithms under different assumptions of loss functions (4.)) (m.)) the number of tasks, and m is the number of iterations per task. Concretely, the task-averaged regret upper bound = (Bound I + Bound II + V) Vm, where Bound is the regret upper bound for learning the initialization, Bound II is the regret upper bound for learning the step size, V represents the task similarity among different tasks, a E (0, 1/2). The explicit form of these regret bounds and task similarities are given in Table B.1 of the Appendix.
Existing Works
Task-eve Regret
Assumptions of t
Bound
Bound II
Khodak et al.
2019
r 2
T.m (n((1s)) - ((;(
Convex & Uniformly Lipschitz
0 (1ogg
0 T vT
Balcan al. 2021
$ 2 (pes fx) (x)(
Bounded &
0 mm///
O (lozm) log T vT
Piecewise Lipschitz
Our Theorem 2
7. Mi (pec, Eua) - ((,)
Bounded & Piccewise Lipschitz
Ol O(
O (og 7)9)))
7.'
Our Theorem 3
+ Eiim - Pt. Rx)
Bounded
O L
O O(logT ((---))
4.1 REGRET BOUNDS FOR NON-CONVEX PIECEWISE LIPSCIIZZ FUNCTIONS
In this section, we let p: - R20 be an unnormalized distribution over O. For any loss function e: θ + R. (p. = ((0))())d)))) Sg p(0)d0. The update rules of Exponentially Weighted Ag- gregation (EWA) algorithm (with initialized distribution p1 and step size X) for each round i can be summarized as follows: (1) Set normalization factor P: = Jes p:(O))0; (2) Sample 0; with probabili-
ty (O,).) e:(6:); (3) Suffer (0,) and observe (-): (4) V0 O set Pi+1(0) = E X2((0) (0). We next give the formal definition of piecewise Lipschitz functions proposed by Balcan et 2018).
Pt
Definition 1 (Piecewise Lipschitzness) The sequence of random loss functions {4s] is piecewise T--lipschizz (T. > 0) that are 3-dispersed, im, Ve 2 m-3 in expectation over the randomness of the loss functions, we have Efmax 10-0' Iase
{ E [m] (((0) - (,0) > L|0 - 6 0'|12||] s Ö(em).
Piecewise Lipschitzness is a weakly Lipschitz condition, indicating that the loss functions are dis- continuous in a concentrated small region. The soft-O suppresses dependence logarithmic terms. Let {4e : θ + [0, M]]e [m] be a sequence of piecewise L-Lipschitz functions that are 3-dispersed. Let Vpp = log (Se( -m- ((0)d0/ Se p(0)d0), where ((8", c) is the c-radius ball around the minimizer 0 Then, adapting the analysis from (Balcan et al. 2021 Thm 2.1) to the M-bounded functions obtains the regret bound for EWA algorithm with the initialization fr and the step size X:
V(p,, 0*) + +Ō((L + +1m!
Σ Ea-p, (i(0)
Σ
(,(0)) S XM2 m
(2)
À
Detailed proofs of Eq. can be found in Lemma D.I Therefore, the task-similarity is defined as 22 min
p(0)a001 Σ log (a(er:.-=))PP p(0)d0. At task t, de- note O, B(0 m 0)) we need to design an algorithm to minimize the function f((p) -log( /())d0/ Ig p())dd). We borrow the idea from Balcan et al. (2021) to discretize θ and translate the minimization problem minp:---Roo fe( over the set of distributions into an on- line convex optimization problem. Concretely, at task i, define the discretization D. = (A 0 (9)) : 0 E 10, vol(A) > 0} of θ, where ! = O., 9.! O Then we use elements of these discretization to construct non-negative vectors in IR 22 for any unnor- malized distribution p O + Rzo, let p(t) RR denote the vector with entries p(() La p(0)d0 for E Dr. We will use v as the uniform measure, i.e. =()) = vol(A), and use V v(T), p =p(T) for brevity. With simple calculations, it is not difficult see that fe(p) = - log (T. p /d) Se p(0)d0) = - -log (p: p), where P = LAce.- Notice that log (p: p) is a convex optimization problem over the Dr -immeninaii sim- plex. Thus, we can use the optimal Follow- Rhhh-Reguari Leader (FTRL) algorithm with the KT.-divergence regularization to solve this problem. The regret bound is exhibited in Proposition 2
min -1 f((p)
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 Non-convex OWO meta learning algorithm for bounded piecewise Lipschitz functions.
1: Input: step size 1 for FTRL, mixture parameter y E (0, 1J, domain upper bound D; initialized distribution P11 O + Rzo and initialized step size \ = V(D2 - log llgg))/(mmm/)) for EWA.
2: for task E [T] do
3: for round i E [m]] do
4: Set Pt: Je Pti (0) and sample On with probability Pt. (0,() = pri(Ors)/uu
5: Suffer loss (fu),, observe (es()), and update Pt,s-1 = e Aefe.10) pei // EWA step
6: Sample fr with probability Ptm and obtain task-t optimum 07 E O
7: Set 1 B0)) to be the function that is in the ball [ m m=) and otherwise 0
8: Update Pt+1,1 to Pa+i(t) = arg min pall - -1.2200))))0))) (L(p]]e(t)) - 17 E.sr log (p: p).
det1 Du log (x))))
|/ meta-update step
tm
Proposition 2 Assume that FTRL algorithm with initialization i and regularization (Ilp) runs on functions (J<(Pe))C((T) over the set = =pp: ||p|| =1, 2 ) then Σ fe(p.) ) fe(p') s 2GI.///1 /7, where p" E arg min min DED 1= s((p), G² 2 <T.(p'"|E)) = D e) Et=
21=1 vol
Notice that vol(O,) = Vam 3dd where Va = r(d/2+1) is the volume of the unit ball in the d- dimensional Euclidean space, I(x+1) = (x) is the Gamma function. Then, apply Proposition to learn the step size Ue in the piecewise Lipschitz setting and choose a proper ", we attain the regret.
4/22
Proposition 3 Assume that FTL algorithm runs on the sequence of functions {Ne(v) + feloal
herr with Se(pa)) = - -log (Pi, Pn)) over the domain [0, D), where D2 vol(e) max log qvol[B.]] 2 se(pp)), any L E [T]. Denote B² = mineerr log vol(O)
Then if we set 7 = AB /To E (0, 1] with a E (0, 1/2), we have the following regret upper bound: 1)
T
he(v) lalog T + log (vol(e)/Va))
Σ
he((r)
min WE (.
4B6
For large enough T. if we set E ml /In In eem 40
Te- [)vol( /nnT] C (0, ()), we have
V4
B² > 1, and the regret bound in Proposition haa the order of O(log 222)) (see more explanations in Remark [. of the Appendix). We list the whole pseudo code of the OWO meta learning algorith- m for piecewise Lipschitz functions {Lr in Algorithm [ and achieve our first improved regret bound for this OWO meta learning algorithm by combining regret bounds Propositions 23
Theorem Under the conditions of Theorem 7 for any lask i E [T], let (lei O + [0, M) (e(mm
be a sequence of piecewise L-Liipschttz fiaiisscitzfuncttion functions that are 3-dispersed. Set a E (0,2)) let (mm)
Ö((L + 1-m then using FTRL algorithm in Proposition 2 and FTL algorithm in Proposition respectively to learn the initialization and step size in Algorithm D Obtains the regret upper bound:
RT. Sg(m) + la T+ + log (vol())/Va))) (log
B6
(KL( [D] + 2
(IL) I1) VaT2 a
+ 2v JVm..
+ +min
V.VT2-
Remark 1 Our task- averagee regret bound Um in Theorem 2 has 3 inprovements over the regret bound in (Blcan et al. 2027 Thm 3.3) that obtained under the same assumptions (see Table Z for details): (I) Our bound guarantees vanishing task-averaged regret. For any fixed T, our Ur is a vanishing bound w.rlt m (i.e. Ur.m- = =(m)). However, in (Balcan et al. 2021 Thm 3.3) the bound UT.m (m2d/2 /r1/ + (log m) log T + V)mm) is not a vanishing bound w.r.t. m since the action space dimension d 2 1. (2) Our regret bound of ((1/T)/2-a) (a E (0, 1 1/2)) for learning the initialization distribution in each task is sharper than that 0f (m//2//11// in Balcan lt al. (2021). (3) Our regret bound of O(log T)9/2 ( for learning the step size has better convergence rate than that of O m) logT TT) in Balcan et al. (2021). l). More comparisons between our regret bound and that in Balcan et al. (222)) can be found in Table B. of the Appendix.

---

Published as a conference paper at ICLR 2024
Algorithm 2 Non-convex OWO meta learning algorithm for bounded non-Lipschitz functions.
1: Input: initialized distribution P11 E (()) and learning rate d > O.
2: for task t E [T] do
3: for round i E [m do
4: Pt = arg min PEP(O) (L(pllAn) + A1 + (ee)
E
// EWA step
5: Suffer loss (prs, Exs) and observe (+)(-)
6: Update P++1,1 = E Pams A4t1
KI. Kl (l tmM.
meta-update step
4.2 REGRET BOUNDS FOR NON-CONVEX NON-LIPSCHITZ FUNCTIONS
In this section, will describe the problem with the language of measure theory. For probability distributions p; E P(O),, define the Radon-Nikodym (RN) derivative of p w.r.t. π de when is absolutely continuous w.r.t т (i.e. P < TT). If p & π. we simply set de J +00. We re- fer readers Page 247 in Yeh (0114) for more properties of RN derivative. For distribution P; m. the KL-divergence between them defined as (L(p||=) is (T = Ee- [ aggregation (EWA) algorithm (with initialization distribution f and step size X) be summa- rized as P: = arg min (EP(O) Σj= (p, E2) + /L(lll)))/A, and the posterior P: has an analytic for- m: p:(d0) exp Σド= (0)) (0)) (d0) exp( ~ Ej (0)) (d0). According (Alquier 2021 Thm 2. for any loss function 4, + M]. EWA has the following regret upper bound:
Eepu log de and the divvveegee 1]. Then the update rule at i-th round of exponentially weighted
Σ (p S XM m + KI(pllet
m
Vp E P(O).
A
Therefore, the task similarity V2 min p(()) T Ei= KT. lpp). Then, need to choose online algorithms to learn respectively the initialization PDi and step size v, in Eq. (3) of EWA on task t. For learning Pri, we choose FTL algorithm over functions {KL(pi (()Lp P1))221
yield the regret bound.
Proposition 4 Given a sequence of distributions {pi hET)) assume that FTL algorithm runs on the sequence of {KI,(p) (p)) to determine Ps iee. pe = arg min minpee(() Ei=l KT,(Elll), and further assume G 2 maxte/1] x2 (pi (le)), then we can obtain the following regret upper bound:
T Σ (L(eille) OE)
((illle)) S <G2(log T + 1).
Σ (L(Pillpa) min
t
The above logarithmic regret bound is non-trivial, since KT. (Pp)) is the functional of distribution Pa1, and it is hard to find norm in the space of distributions fr1 verify the strong-convexity or Lipschitzness of functional KL(p)llpe)) Thus, we are unable to utilize regret analysis for the (012).. Instead, we use the analytic form of the
functions over Euclidean space (Shalev-Shwarr) optimal distribution of FTL and the properties of RN derivative to get this logarithmic regret (see Section Then, applying Proposition to learn the step size achieves the following regret bound.
Proposition 5 Given sequence functions (f((pe) = KL(Pī pl) hee))r assume that there exist D2 > [ KL [Pa),, B² < minee(r] KL (Ipx)) with B O. Assume that FTL algoritlu runs on the sequence of functions (hr(w) = + f.loa) JEERTY over the domain [0, DJ. Then we have
T
T (.())) min Σ hc(v)) < ve
D
4B6 (log + +1).
If we use EWA algorithm to learn distribution oi (i.e. set =² Ptm for task t, then the above condi- tion B > 0 truly holds (see proof at the end of Section E The pseudo code of OWO meta learning algorithm with of = Pem is listed in Algorithm 2 for non-Lipschitz functions. The correspond- ing task-averaged regret upper bound is given as follow by combining results in Propositions 5 achieving the fastest convergence rate O T/T +) with respect to T in the current work.
Theorem Under the conditions of Theorem for any task t [T], let (lu O + [0, be sequence of M M-bounded functions. Let G2 maxte(T] x2 (Pillen) D2 max (T
7

---

Published as a conference paper at ICLR 2024
and min (L Ipa)) 2 B² > O. then using FTL algorithm respectively learn the initializa- tion and step size of EWA algorithm in Algorithm 2 attains the task -veraged regret upper bound:
1
Dd (log ++ + ming
(o T + 11, .2G/
log T + } +22VV
(pi pi: Exs S
T
4T
VT
T
Remark 2 Let's compare the regret bound in Theorem 3 (for bounded functions) with the bound in Theorem 2 (for bounded piecewise Lipschitz functions) and the bound in (Khodak et al. 2019 Thm 3.2) (for convex and Lipschitz functions) in Table 7 (1) In Theorem [ the regret bounds for learning the initialization and the step size are (log TT)), both of which are sharper than the corresponding regret bounds of (11/T3/2-0) and O(log ((1oTT))/2/11 in Theorem 2 Besides, Theorem3oottains improved regret bounds without piecewise Lipschitz assumption of loss functions. (2) When compared with Khodak et al.) (2019) both our regret bound and theirs for learning the initialization have the same order of (log T T/T): but our bound for learning the step size is of (log T TT),, sharper than theirs of Ollog TT) The improvement is obtained by using primal- dual technique from Shalev-Shwarzz & Kakade (2008) to analyze the strong- conve-cyyyy of functtions (b) = e + (((Pt)//) [e)()) Besides, we achieve the improved result for bounded functions, without convexity or Lipschitzness assumptions of loss functions {Et [E We further discuss the limitations of our Theorem 3 and our Algorithmm 2 in Remark B.7 and Remark H.1 respectively.
5 GENERALIZATION BOUNDS FOR META LEARNING VIA REGRET ANALYSIS
In this section, we show how to derive generalization bound for statistical meta learning via re- gret analysis. Concretely, in Section 5.1 we provide novel transfer risk bound for non-convex batch meta learning under the task distribution assumption. In Section 5.2, we yield a PAC-Bayes generalization bound for statistical multi-task learning that supposes independence between tasks.
5.1 IMPROVED TRANSFER RISK BOUNDS FOR STATISTICAL META LEARNING
In statistical meta learning, let be a probability measure over the set of all data distributions f on bounded loss functions f θ + [0, .M.. A sequence of loss function (4uhee is generated by drawing m loss functions i.i.d. from each in sequence of distributions (Je)eeT7 where each Me is regarded as random variable and is drawn i.i.d. from T. We use the cumulative informa- tion {pt, As hejry from previous T training tasks in OWO meta learning to run an online learning algorithm EWA on the novel task with loss functions (ei)ve(m) generated i.i.d. from distribution a that drawn i...d from T, to output sequence of probability distributions [p]]se]m] Using anline-to-batel arguments, we achieve the transfer risk bound for non-convex batch meta learning.
Theorem Assume that for each task E [T], there exist G2 Z max x2 (Pa)). and min (T.(pillpa)) 2 B² > O. Assume that the novel task consists of loss functions (Li (fi)se(m) itd 14, JI Lid. T, and for any optimal distribution p" over task p. there exists H > 0 such that KL(P"1I 7 Pa) S H. Then we use ( Et= Pæi, v ET KL(pt /ta/ EWA algorithm for novel task p with loss functions (Ci)vem)) output probability distribu- tions (pi)re(m). Then let p = 1
to run
m Em for the optimal distribution p² over task μ that does not dependent on {Eissetm) with probability 1 - 8 over the draw of probability distributions {M.TE
1G2 logT T
3V2 H
log 1/8 B
B EE 1E M rmpm (00 Be {(0)+M))
T' /mB
2Tm
Remark (Comparisons among different transfer risk bounds) (1) The first group of bound- holds for meta learning algorithms that learn shared representation across tasks; The bound in AAquuer et al. 2017 Thm 6.1) is O(1/ /mm T/) The bound in (Denevi et al. 2019 Cor 42) is O( O(//og m/m + 1/VT). (2) The second group holds for algorithms that learn the initialization and step size for each task: The bound in (Khodak et al.) |019 Thm 5.1) is Olog T (m/mmTT) + 1//m= + +1V/Tm). The bound in Theorem 4 log T (Tm) + 1/ /mm + 1/VTm) is slightly larger, because our work focuses non-conee setting and E.
(p)/ is not convex w.t.. v).v). However, (Khodak et al. 2019) focuses on convex loss and E. 110 0, v is convex w.r. (0,v), hence able to use Jensen mequality to get a slightly better transfer risk bound (see their Thm E.I).
8

---

Published as a conference paper at ICLR 2024
5.2 PAC- TAC-BAYES GENERALIZATION BOUNDS FOR STATISTICAL MULTI-TASK LEARNING
In statistical multi-task learning, each task & has the training dataset S, { where Zei is drawn i.i.d. from the sample space Z according the data distribution /r. We al- so suppose the independence between datasets S and Sj (i * j) drawn from different tasks. to denote the o-algebra induced by the sequence of ran- dom variables up until the end of i-round at t-th task. Formally, an online learning algorithm Im {pu) i=1 is the set of m probability distributions over the action space O For conve- nience, we abbreviate Pii = pts(( 2ay bashhe iig U {2t) (e)sis)))). A raaddom variable as- sociated to the online learning algorithm Hm is MI1.. = 1 > (Pts. Cts), where (a)
We use Fi-
Ez--,, =)] - 1/m m (10,2x). Note that MII... is a sum of normalized martingale dif- ferences since E[ C.. F. = 0. The generalization error of the action @ E θ defined as: gen(O, S2) = Ez-u, [e(0, -
mm ((0, ze:). ). In PAC-Bayes learning, for each task t, the al- gorithm Ar takes the training sample S. and a prior as input and outputs a posterior A,(S,) E P()). The generalization error of posterior (S,) is defined as ge, Si) = A. (S.))en(B S,). Then we obtain the following proposition that connects the multi-task generalization error of posteriors (A)(5)))221 in statistical multi-task learning and the task-averaged regret in OWO meta learning.
Proposition 6 Let R
T.m (p, 4)), then Ei=gen -eeg S()= R - -E
Using T. in our Theorem 3 to upper bound the task-averaged regret RT.m. and applying simple concentration inequality upper bound the sum of martingale differences E, MI,... we obtain for statistical multi-task learning a novel PAC-Bayes bound that does not appear in existing literature.
Theorem Let Ar be the statistical learning algorithm for task t E [T]. Assume that for all actions 0 E O samples E Z, E(0, z) E [0,M], M). Then, with probubility at least 1 - ō over the draw of {St)eeTT), the mulli-task generalization error of statisticul learning algorithms (Ather satisfies:
T T BemAI(S) Benni ((0
T E(0, 26) m Ee(0,
1
Ur +
2 log }
S
My
m
T'
Remark 4 We give two insights into the PAC-Bayes bound in our Theorem 5 (1) The most related
work to our bound is the PAC-Bayes bound for multi-task generalization error in PAC-Bayes meta learning theory (in the batch setting), which assumes that the priors for each task are the same and are sampled from the hyper-posterior Q. The tightest PAC-Bayes bound in this field is from z O(1/m + In (T m.). J. Such PAC-Bayes bound for batch multi-tass learning is sharper than our bound of O(V/vm + 1/VTm) in our Theorem 5 statistical multi-task learning, indicating the difficulty of online metu learning w.r.l. butch meta learning. (2) Our Proposition ofor the first time reveals the connection between multi- generalization ervor in PAC-Bayes theory and the avsk-averaged regret in non non-convex OWO meta learning. This gives promising direction of proving PAC-Bayes multi-takk generalization bounds by applying regret analysis and simple concentration inequality.
Guan & Lu 2022 Prop 3) of O(EP~~ Ei= (L(A((S))))P) + In (Tm))/(Tm)
CONCLUSION
We study the non-convex ontinn (OWO) meta learning of the initialization and step size of exponentially weighted aggregation (EWA) algorithm. We extend the averaged regret upper bound analysis to the non-convex setting, and typically propose to learn the step size with Follow- The-Leader (FTL) algorithm to guarantee the logarithmic regret. For learning the initialization, we develop two algorithms based on the type of loss functions. For piecewise Lipschitz functions, we choose Hollow-The-Reee -eee--Reeelll--eaaaaaeee achieve a sublinear regret. For non-Lipschitz functions, we utilize FTL algorithm to learn the con- tinuous initialization distribution and derive a logarithmic regret. Both strategies lead to improved regret bound for non-convex OWO meta learning. Furthermore, by online-to- taline-to-batch arguments, we yield new transfer risk bound for batch meta learning. By online-to-PAC techniques, we achieve a novel PAC-Bayes generalization bound for statistical multi-task learning, revealing promising framework of proving PAC- MAC-Bayes bounds for multi-task setting via regret analysis. Our ongoing research includes exploring the OWO meta learning of other online algorithms (e.g. Follow-The- Berturbed-Leader), and investigating whether we can obtain its optimal task-averaged regret bound.
algorithm to learn the discrete initialization distribution and

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
We would like to thank all reviewers for their constructive suggestions to improve the quality of this paper. This work was partially supported by National Natural Science Foundation of China (Grant No.92370204), Mhangzhou-HHKUSTCCG ence and Technology Planning Project of Guangdong Province(Gram No. 20.2023300000001 Ed- ucation Bureau of Guangzhou Municipality, and Guangdong Science and Technology Department.
Joint Funding Program (Grant 20.202333300088,, Sci-
REFERENCES
Durmus Alp Emre Acar, Ruizhao Zhu, and Venkatesh Saligrama. Memory efficient online meta learning. In International Conference Machine Learning (ICML), pp. 32-42, 2021.
Pierre Alquier. -on-enxonentially weighted aggregation: Regret bounds for unbounded loss func- tions. In International Conference on Machine Learning (ICMI), pp. 207-218, 2021.
Pierre Alquier. The Tien Mai, and Massimiliano Pontil. Regret bounds for lifelong learning. In International Conference Artificial Intelligence and Statistics (AISTATS), pp. 261-269, 2017.
Ron Amit and Ron Meir. Meta-leaming by adjusting priors based on extended PAC-Bayes theory. In International Conference on Machine Learning (ICML). pp. 205-214, 2018.
Rie Kubota Ando and Tong Zhang. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research (JMLR), 6:1817-1853, 2005.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm de- sign, online learning, and private optimization. In IEEE Anmual Symposium on Foundations of Computer Science (FOCS), pp. 603-614, 2018.
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning In International Conference on Machine Learning (ICML), pp. 424-433,
2019.
Maria-Florima Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to- learn non-convex lipsshise-lipschitz functions. In Advances in Neural Information Processing Systems (NeurIPS). pp. 15056-15069, 2021.
Jonathan Baxter. Learning internal representations. In Conference on Learning Theory (COLT), pp- 311-320, 1995.
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12: 149-198, 2000.
Shai Ben-David and Reba Schuller Borbely. A notion of task relatedness yielding provable multiple- task learning guarantees. Machine Learning, 73(3):273-285 -27, 2008
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Jiaxin Chen, Xiao-Ming Wu, Yanke Li, Qimai LI, Li-Ming Zhan, and Fu-Lai Chung. A closer look at the training strategy for modern meta-learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 396-406, 2020.
Giulia Denevi, Carlo Ciliberto, and Massimiliano Pontil. Online-wiitinn-nninee meta-learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 13089-13099, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning (ICML), pp. 1126-1135, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham M. Kakade, and Sergey Levine. Online meta-learning, In International Conference Machine Learning (ICML), pp. 1920-1930, 2019.
10

---

Published as a conference paper at ICLR 2024
Bela A. Frigyik, Santosh Srivastava, and Maya R. Gupta. Functional bregman divergence and bayesian estimation of distributions. IEEE Transactions on Information Theory, 54(11):5130- 5139, 2008.
Xiang Gao, Xiaobo Li, and Shuzhong Zhang. Online learning with non-convex losses and non- stationary regret. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 235-243, 2018.
Jiechao Guan and Zhiwu Lu. Fast-rate pac-bayesian generalization bounds for meta-learning. In International Conference on Machine Learning (ICML), pp. 7930-7948, 2022.
Jiechao Guan, Yong Liu, and Zhiwu Lu. Fine-grained analysis of stability and generalization for modern meta learning algorithms. In Advances in Neural Information Processing Systems (NeurIPS), pp. 18487-18500, 2022.
Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv:1909.0520730 2023.
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient-based meta- learning methods. Advances in Neural Information Processing Systems (NeurIPS), pp. 5915- 5926, 2019.
Jianhua Lin. Divergence measures based on the shannon entropy. IEEE Transactions on Information Theory, 37(1):145-151, 1991.
Tongliang Liu, Dacheng Tao, Mingli Song, and Stephen Maybank. Algorithm-dependent gen- cralization bounds for multi-task learning. IEEE Transactions Pattern Analysis and Machine Intelligence (TPAMI), 39(2):227-241, 2017.
Gábor Lugosi and Gergely Neu. caline-to-pate conversions: Generalization bounds via regret anal- ysis. arXiv preprint arXi::2305.19674 2023.
Andreas Maurer. Algorithmic stability and meta-learning Journal of Machine Learning Research (JMLR), 6:967-994, 2005.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research (JMLR), 17:81:1-81:33 2016.
Anastasia Pentina and Christoph H. Lampert. A PAC-Bayesian bound for lifelong learning. In International Conference of Machine Learning (ICML), pp. 991-999, 2014.
Anastasia Pentina and Christoph H. Lampert. Lifelong learning with non-i.i.d. tasks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1540-1548, 2015.
Shai Shalev-Shwartz. Online learning and online convex optimization. Found. Trends Mach. Learn., 4(2):107-194, 2012.
Shai Shalev-Shwartz and Sham M. Kakade. Mind the duality gap: Logarithmic regret algorithms for online optimization. Advances Neural Information Processing Systems (NeurIPS), pp- 1457-1464, 2008.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 4077-4087, 2017.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In International Conference on Algorithmic Learning Theory (ALT), pp. 845- 861. 2020.
Eiji Takimoto and Manfred K. Warmuth. The minimax strategy for gaussian density estimation. pp. In Anmual Conference Computational Learning Theory (COLT), pp. 100-106, 2000.
Sebastian Thrun and Lorien Pratt. Learning to Learn. Kluwer Academic Publishers, 1998.
Han-Jia Ye, Hexiang Hu, De-Chuan Zhan, and Fei Sha. Few-shot learning via embedding adapta- tion with set-to-set functions. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 8805-8814, 2020.
11

---

Published as a conference paper at ICLR 2024
James Yeh. Real Analysis: Theory of Measure and Integration. World Scientific, 2014.
Niloofar Yousefi, Yunwen Lei, Marius Kloft, Mansooreh Mollaghasemi, and Georgios C. Anag- nostopoulos. Local rademacher complexity-based learning guarantees for multi-task learning.
Journal of Machine Learning Research (JMLR), 19:3811-3::44 2018.
Zhenxun Zhuang, Yunlong Wang, Kezi Yu, and Songtao Lu. No-regret non-convex online meta- learning. In JEEE International Conference on Acoustics, Speech and Signal Processing (ICAS- SP), pp. 3942 3946, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference of Machine Learning (ICML), pp. 928 228-936,,20 2003.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A ADDITIONAL RELATED WORK
Online Convex Optimization. In online convex optimization (OCO) setting where the loss func- tions (4)))/m)) are convex, the regret is defined as R... - -E (:(0.) ((()), where 0" arg mingse Din ((()). The upper bound Un Ran on the regret is always called regret bound. The goal of online learner is to choose a sequence of actions {0:)ve(m) that will guar- antee the vanishing regret, i.e. Rm = o(m) or Um = o(m). In OCO problem, two fa- (FTRL). At i-th round, FTL chooses the action 0: = arg mingeo Σj=1 (0);; and FTRL selects the action 0. arg mingge Ej ( R(0), where R O + Rzo is always a strongly-convex regular- ization function like E2-norm. When xe are convex and Lipschitz, FTRL achieves optimal regret of O(ym) (see Schalev-Shwarke 2012 Thm 2. for upper bound and (Hazan 2023 Thm 3.2) for lower bound). When (4 mm) are grongly-convex. and Lipschitz, FTL. achieves optimal regret of Olog m) (see (Shalev-Shwartz & Kakade 2008 Cor 1) for upper bound and (Takimoto & Warmuth 2000, Thm 4) for lower bound). We introduce FTRL and FTL in detail because these two algorithms are utilized as the main components of our OWO meta learning algorithm in Section 4
mous algorithms are Hellow-The-Leaderr (FTL. and Bollow-The-Regularized----
Online Non-Convex Optimization. However, in online non-convex optimization setting where the loss functions {& [e(m) are non-convex, minimizing regret is more difficult than that in convex case. It has been demonstrated that all deterministic online algorithms (e.g. the aforementioned FTL and FTRL for OCO) cannot obtain vanishing regret in the non-convex setting (see (Suggala & Netrapalli, 2020 Prop 3) and (Cesa-Bianchi & Lugosi| 2006), Sect 4.1) for details). Therefore, at i-th round we need to add randomness into the algorithm, and choose the action drawn from certain probability distribution Pi E P(O). The corresponding regret is defined Rm e Σ Ee- (0) (0))),
where E arg min Em (0). If {e, fiemm are Lipschitz, using Follow- Hellow-Thhe-Pare Seerturbed-Leadee algorithm allows to achieve the optimal regret (( (see (Suggala & Netrapalli 2020 Thm 1)).
Generalization Bounds for Statistical Multi-Task Learning. Statistical multi-tas, learning refers to the multi-task setting where data within each task are assumed to be independently sampled from the same distribution. The investigation of generalization bounds for statistical multi-task learning has long history and dates back to (Baxter 1995). In the last decades, different generalization bounds are proposed for multi-task learning, mostly based on model-capacity theory: for example, the generalization bound based on covering number complexity (Ando & Zhang, 2005), the bounds based on the VC-dimension of hypothesis space (Baxter 2000 Ben-David & Borbely 2008), the bound based on Gaussian complexity (Maurer al. 2016). Apart from them, there also exist gen- eralization bounds for multi-task learning that are derived based on algorithmic stability analysis, like (Maurer 2005 Liu al.) 2017). Recent works also use localized Rademacher complexity anal- ysis to obtain improved generalization bounds (Yousefi et al. 2018). However, little literature use PAC-Bayes theory to prove bounds for multi-tast learning, except for the PAC-Bayes generaliza- tion bounds in statistical meta leaning that involves the multi-task generalization bounds (Pentina & Lampert 2014 Amit & Meir 2018 Guan & Lu/ 2022). But the PAC-Bayes multi-task generaliza- tion bounds in meta learning theory assume the priors for different training tasks are the same and are sampled from the same syper-prior distribution. Therefore, to the best of our knowledge, there is still no explicit PAC- generalization bound for standard statistical multi-task learning setting.
B EXPLICIT FORM OF REGRET BOUNDS FOR OWO META LEARNING
Remark B.1 (Limitations of the regret bound in Theorem 3 For any task t E (T), if we set the distribution pt as Dirac measure do: that only has mass I at the minimizer 0;, the regret in Theorem 3 degenerates to the regret defined in Eq. ① (iee. the regret in our Theorem Z To let (L Ilen) (where Pa1 = =1/(t11) Pt) make sense, there should exist at least one E [t-1],
such that p%, (10;)) > 0 (otherwise the RN derivative dpp /d(E:=1 1-1 P2) = co). However, the optimal actions for the past tasks may not be the optimal one for future tasks. Hence the regret bound in our Theorem 3 may be vacuous under the regret definition in Eq. [7). This also indicates some extent the limitation of the regret (defined as the gap between the cumulative loss w.n.t. { and the loss w.E.. the optimal distribution pt) and the f-divergence based regret upper bounds (which, including the f-divergence between pt and the initial distribution Prl, will become vacuous if we set pt as a Dirac measure. See more details in Allqier 2027
Thm f) WWA-type algorithm.
13

---

Published as a conference paper at ICLR 2024
Table B.I: Different task-at ass-avvraged regret bounds for OWO meta learning algorithms under difference assumptions of loss functions (4u)elr) (eeeeiimmm In these bounds, T' is the number of tasks, and m is the number of iterations per task. Concretely, the task-averaged regret upper bound = (Bound I + Bound II + v)mm + (m), where Bound I is the regret upper bound for learning the initialization, Bound II the regret upper bound for learning the step size, V/ represents
the task similarity among T different tasks. For all t [T], vol( Vaam d3 In (Khodak et al. 2019, Thm 3.2) and Theorem 3 g(m) = 0. In (Balcan
et al. 2021 Thm 3.3) and our Theorem 2 (m)) O(m1-0) We set (minn ( Frlo") .2 [=(("))) = O ("r("")) = O Frde") for all Bound in Table 1 of the
main text for brevity. In the bound Khodak at. (2019). de (0 (0a) represents the Bregman divergence between vectors Br and 9n with respect to function d.
min, 7 Li log Javer. (sser.))eee P(d0)
min, 7 Er log J -o pf (te)
ming + E d (o (00
min, 3 Σ KL(T)
Task Similarity V/2
$)
o log 7 (moxeetr KLdp llm))) )
o min (V +
(d (6:(11110))))) ))
: +
voi(es)) Keip 1ooy
o (log T'g woll ee)) F log
T (mimeepr KL (lea))
Boand
o min { (
los v
log (log
vT
1 los
PT
" (ies) log
}
Ing
o min max [lee)l
VTT vol(e)))
})
KLde" (ppwal
Kide" K 1 1loys volree })
T
x (o llaay
mnx [10; I
KL (1l) valre)
V.
Bound
78 (ea))
maxe m
71-1
o min {
O min {
V maxicm
O min
Assumptions of (&
Bounded & Piecewise Lipschitz
Bounded & Piecowise Lipschitz
Convex & Lipschitz
Bounded
+ Di (e(0n)) - 4,(0))
> (pes le) - (x100)
7 Eud le Ee) - (o))
Task- Task-Averaged Regret
# Di foa Ris
Khodak et al. 2019)
Existing Works
Balcan et al, 2021
Theorem
Our Theorem
14

---

Published as a conference paper at ICLR 2024
Remark B.2 (Our Three Technical Novelties in Deriving Improved Regret Bounds for OWO meta learning) (1) The first novelty lies in deriving improved regret bound for the online algorithm that runs over the functions {hς(v) = U + f((pa) (oooaa///rer (ee on the domain [B², D21 to learn the step size ve of EWA algorithm. Throughout the whole paper, we choose the efficient Follow- Follow-The--Laud The-Leader (FTL)
Ei = (Ei=) fe(paa)((t (=(aa/))/ttt111)) 1)) 1/2
algorithm to learn the step size vt arg min BP.
and use the primal-dual analysis from (Shalev-Shwart, & Kakade 2008 Cor I) to derive logarith- mic regret bound of Olog T). The key step in obtaining the logarithmic regret Oloo T) is to show that minserry fi(Pt) ) is strictly positive (i.e. B > 0) to guarantee the the boundedness of dh, (vx) (i.e. the Lipschitz property of h4(1) at the point vt). The positiveness of mingg(r) Se(pa) is guaranteed for piecewise Lipschitz fanctions in Proposition 3 and for non- fisschitz.uucctionss Lipschitz. functions in Proposition 5 respectively, via fineggrained estimation of the lower bound
of (t( and
B² of Se [((Pta) In contrast, existing works (Khodak et al. 2019 Prop B.2) and (Balcan et al. 2021 Cor 3.2) both choose e-FTL algorithu to optimize the functions (he(e) = u (f((p))+ (/)0 ho on the domain [0, D21 (where D² z max; fe(Pr1)) to learn the step size us, and lead to the regret O + (log T)2²), which is of ((VTTogg) T) if we set e 1 1/T1/4 and is slower than our bound. (2) The second novelty lies in deriving improved regret bound for the online algorithm that runs over the functions {f((p) = (p,, he)m in the piecewise Lipschitz case. We use Follow-The- Bipplarizzd-Leader (FTRL) algorithm to achieve the regret of O(T)/2+m), a E (0, 4), and the mixture parameter y = ma8 'T is irrelevant to the optimal p* (hence Y can be set in advance), Existing work (Balcan et al. 2027 Thm 3.2) also uses FTRL algorithm, but Balcan et al.) (202T) leverage a more complicated analysis, attaining larger regret bound (mm//TT0/7 "TT/")) Nevertheless, the choice of in (Balcan el al.) (027)) depends on the knowledge of optimal parameler p that con- tains information of training lasks, which is unfeasible in the sequential online meta learning set- ting. (3) The third novelty lies in deriving improved regret bound for the online algorithm that runs over the functions {f((p) = [p) (p)ett in the non-Lipschitz case. Obtaining regret bounds for FTL algorithm run over the functions (p [Ip) (E( is hard, because (L lee) is the functional of the probability distribution p. and thus we are unable to use traditional regret analysis (e.g. the gradient boundedness and strong convexity analysis of the functions) for the functions on Euclidean space -Swwrr) (2012). Instead, we leverage an insightful lemma from (Frigyik et al. 2008
Thm II.1) to obtain the analytic form Pei = arg min pEP(O) E KL(P?llp) = = 1-1 PT of the solution of FTL algorithm. Then, we use this analytic form, as well as the properties of RN deriva- tive to estimate the upper bound of the regret and ultimately obtain a non-trivial logarithmic regret Olog T), achieving sofar far the tightest regret bound for learning the initialization of EWA algoritium.
Remark B.3 (Comparisons between our Task-Averaged Regret Bound and the Vanilla Averaged Regret Bound for EWA Algorithm). Recall that in Theorem 3 G² Z ( x² (Ptilppa) D² 2 [T (p. (Pa)), min KT, ((pp))llp)== 2 B2, then our task-averaged regret upper bound is
m Σ (e - pt, p()
Dd (log T + +1 mmin G2 T + +1) 2G
log T + ) )+2V) VmM.
B6
VT
T
t=1
The vanilla averaged regret bound (Alquier 2021 Thm 2.1) for EWA algorithm (with the step size X = 1/(M vm) and the initialization Pei for task t) across T tasks without knowledge transfer is
T
1 T
Eirsem + KL(oilleu) vmM 1
T
(pu- pi, S T
+ Σ (lillle))) T (=1
T
t=l
1=1
We can observe that: (1) If we assume the same upper bound D2 on KL((p)1Pa)) the vanilla averaged regret bound is of O O(MmMD²) which is independent T and could not decrease with the increase T. This demonstrates that we are unable to obtain lighter regret bound for multi-task learning than that for single-task learning, if we do not share any knowledge across different tasks. (2) When T is large enough, our task-averaged regret bound is of O( D(VmMVV) ). Such regret bound typically sharper than the vanilla averaged regret bound O(mMMD²) when V << D2, i.e. when different tasks share a high degree of similarity. This indicates that, when T training tasks are similar enough, leveraging knowledge from previous tasks can achieve better theoretical guarantee than single-task learning, validating the advantages of OWO meta learning. (3) In our Theorem 3 the proposed task similarity notion 22= min, 1 HT, KL(ptllp) 1. E (L 1 Σ Pt) is actually the so-called generalized Jensen-Shannow divergence, which is always used to measure the similarity among different distributions (pi ) heery in information theory Lin 1997 Section V).
15

---

Published as a conference paper at ICLR 2024
Remark B.4 (More Discussions between our Task-Averaged Bound for OWO Meta Learning and the Task-Averaged Regret Bound obtained via Dynamic Regret Analysis). One of the anonymous Reviewers suggest we make a comparison between our task-averaged regret in Theorem and the tusk-averaged regret obtained via dynamic regret analysis: (1) First, we need to derive a task- averaged regret bound for OWO meta learning through the lens of dynamic regret analysis. Denote (0(0)= = - then the regret for OWO meta learning in our Eq.(7) can be rewritten roughly as Ei=1 F.
(e() (actually, we think we cannot rigorously rewrite the task-averaged regret as the equivalent form of dynamic regret, because we cannot write > Eo- (0) as the expectation of Φr (0) over a common distribution P P(O)), where Pt. m -.Ei
2.=ii11 Pts. Assume that
Σt= |1 - -1++lll= S Vr, then according to the latest dynamic regret bound in (Gao et al. 2018 Thm 1) (to the best of our knowledge this is the latest dynamic regret bound for non-convex online learning), the task-averaged regret is bounded by 1. >I==1
2t I Ee-p, ve(() oe(6,) S O ((<TTVVrT)
.T
0( (2) Nexi, we compare our regret O(( LoxTT via dynamic regret analysis. from 3 aspects: (i) Our regret analysis does not adopt the bounded total variation assumption (i.e. VT is a bounded constant), when compared with dynamic regret analysis. (ii) Our regret bound O((loTT + V) m)) is more informative, revealing the importance of task similarity V to the generalization of OWO meta leaning algorithm. (iii) Our task-averaged regret bound O(( ((TTTT +Vymm has a faster convergence rate w.r.l. T when compared with O (IITVE)
T +V)/m) and the regret O (ViVVe) ) obtained
T
VT
Remark B.5 (More Discussions on the Advantages of our Theorem 2 when compared with our Theorem 3 One of the anonymous Reviewers suggest we discuss more the value/advantages of the first improved regret bound when compared with the second improved regret bound. The detailed explanations between their differences lie in the following 4 aspects: (1) The first im-
proved regret bound in our Theorem 2 is not a special case of our Theorem The main rea-
son is that Theorem 2 uses V2 = miippp--R2.. p(0))0011 + Ei log (scor...-o (ttor..m=sp((0p) p(0)d0 as the similarity notion between different tasks, but Theorem 3 uses the task similarity notion v2 mm) + Σt= KT(pEllp). Besides, the task similarity in Theorem 2 is defined ac- cording to the specific property (i.e. c-radius) of the piecewise Lisschitz iuncchittfuuction, and hence is par- ticularly applicable to the piecewise-Lipschhe
setting. (2) The action-space- dicceediscretizationn technique (described in Section 4.7 to obtain the first regret bound in Theorem 2 is of independent interest. The defined task similarity in Theorem 2 also requires novel action-space citioon-ppaceddiccrtiiattttt discretizationn method to translate the minimization problem minppe fe(p) over the set of distributions into a tractable online convex optimization problem. (3) At present. the first regret bound has higher application value than the second regret bound. The Algorithm A (corrssponding to the first regret bound in our Theorem 2 can be applied in the continuum domain, but Algorithm 2 (corresponding
the second regret bound in our Theorem 3) at the current stage is still not easy to be applied in the continuum domain (see more explanations in our Remark I (4) The first improved regret is obtained under the same assumptions (i.e. piecewise Lipschitzness and bounded loss functions) as that in (Balcan) et al. 2021 Thm 3.3), via a more technical analysis. We list the improved regret our paper to make fair comparison and show rigorous improvements over existing result (Balcan et al. 2021).
Remark B.6 (The Potential Improvement Space of our Theoretical Results). According to Theo-
rem 7 we decompose the task-averaged regret bound problem into two subproblems: (I) minimizing
(P ((p. (P. [Ce(T] to learn initialization p. and (2) minimizing (h<(t) f fe(Pa)) /o) (e) to learn step size v. Combining the above two results leads to lask-averaged regret bounds in our Theorems 2 which are actually optimal w.r.l. m (i.e. of order O O(ym)). Therefore, what we can improve is the convergence rate w.r.t. T, and our explanations are three-fold: (1) For learning the initialization p. our Proposition 4 Acchieves a logarithmic regret O T). According to the related work of OCO in Appendix A the optimal regret for strongly-convex online optimization is Ollog T)). Therefore, we believe that our Proposition $ achieves the optimal regret for learning the initializa- tion. (2) For learning the step size v, our Propositions 3 and S actually achieve the (polynomial) logarithmic regret (log T). Therefore, we also obtain optimal or near optimal regret for learning the step size v. (3) Consider (I) and (2), if we still adopt the regret upper bound decomposition framework, we should refine the proof in Theorem]] 7 For example, there seems to be some improve- ment space in the 4-th inequality in the proof of our Theorem ! since other inequalities in this proof proof
hold due to the definition of regret bound; If not. we should use other avsk-aver regret analysis see whether we could achieve better convergence rate w.r.l. T smaller multiplier constant.
16

---

Published as a conference paper at ICLR 2024
C PROOFS OF THE NON-CONVEX OWO META LEARNING
REGRET BOUND FRAMEWORK FOR
Proof of Theorem
T m
Pri - lu)
mbde + ((Pr,,p)) + g(m)]
T Σ
d
T t=1
V()
Vmbbl=
Vmb Vmb++ g(m)
Vmnba
[o felpa))
Σ
/mb+ + g(m)
(v. vmbdd)
D + lelpa))
+ HT(1)
min Vmb 620
+ gm(
T
T
Ei= Se(pa))
Hr(()]
=min r20
Vmb
++
+ +g(m)
To
T
Vmblu++ Σt Selp) + PT(()
Hr(v)
min x20.)EP(())
+ g(mm
Tu
T
2iz1 Selp") + FT((') Hr(o)]
-T
min Vmlll r20
+ gm(m)
Tv
T
V2 Fr((")
+ Hr(u)]
=min mb v>0
+g(m)
Tv
T
HV((V)
Fr(p")
Fr(p"),
minf
22
} 1+2V) (en))mm+++ g(m),
T
VT
T
where the last inequality holds by taking v = V or
Lemma C.1 Shalev-Shwartt Kakade 2008 Corollary 1) Let E,...., by be sequence of func-
tions such that for all L [T), E, is o o--strongly convex. Assume that the FTL algorithm runs on this sequence and for each [T', let gr be in (l.) Then
||
Σ (e(O.)
min 8EB
Σ (()))
2 σ1xt
Furthermore, let L max; [|g:|| and assume that for all t E [T], o, a. Then the regret is bounded 12
by 20 (log T +1).
Proof of Proposition 1 Notice that for all E
[T],
dh.(o) de
felee) 62t
d(ha(r)
(fc(p))
du²
(f((P)) D8
Therefore (v) is 2f((en) -strongly convex function. Besides, since U,
(a(Pr)
D3
then (o)
Σ(- felen) and applying Lemma C. obtains the first result. For the second Σi fo(o))
17

---

Published as a conference paper at ICLR 2024
result, using f((11)
[B). we bound the above regret follow:
D
T
- Se(pr))/ - fa(Ps)) 2
4
ΣS 1 fs(Pa))
1=1
Σ felpe)) 2
D3
max {1,
- Sa (a(ar)
4B
(t- (t-11D2 max (1, (t- 1)B2
D3
4B²
D)
4B6 (lggT+1)
4B
D PROOFS OF THE REGRET BOUND FOR OWO META LEARNING WITH BOUNDED SECEWISS--LIPSHHINE FUNCTIONS
Lemma D.1 Let em. θ + M be any sequence of piecewise L-Lipschitz functions that are B-dispersed. Let 8" arg mingee Ex (0),, and Vpp.0") log _mso=_m-0 m- p(0)d0
So p(0)d where
is the initial distribution over ④ in EWA Algorithm. Then EWA has the following regret bound:
Σ ((0) S AM V(p.
Σ EB 1B-o: (.()
Ö((L 1)m²'
Proof. The demonstration strategy is upper bound pm+1 and lower bound Pm+11 respectively, For any E [m], define the utility function (f) = M (.)). It is not difficult to see that running EWA algorithm on utility functions [uij obtains the same sequence actions {0:) [ee)se as running EWA on {f]ee/m] For upper-bounding Pm+1. applying Jensen's inequality and basic inequality
1 I < e. we have:
P++1
Se e0) p:))dd
P.
P.
(n
(0)d0
AM 20 +0(1 -1(0) (0)
(0)
AMM +[1 (1())
S
M 1 (.)
M
(i(0)
(E
1)))p(()dd0
M
AM
u.(0)p:(O)dd
M
AM
/
S exp
u. (1(0)p;(0)d0..
M
Then Pmt1
Ea-p, (0) and can upper-bound Pm+1 For lower-bounding Pm41. let us first upper bound Σ u0())) u,(0), vo B(0", where m Notice that the utility functions (ueheetm) also dispersed L-Lipschitz. Suppose there exist most k discontinuities w.r.t. to {wr hiem)) in the ball B(0", c). then for any 0 B(6", c):
Pets 1-=1 P. exp
D Eanp,
(,+) - un (0) < l max (u;(0*) wx(() + (m L 0* s RM + mLc. (4)
18

---

Published as a conference paper at ICLR 2024
With Eq. 4
we can lower-bound Pm+1i
Pmt1
Ei 4:( (0)d0
8
2
c -inn u. Pi (0)
1((0'c) .c)
e> Dis -:00'-----
kdd kas- (1))d
2
((00)))
(O)d0.
B((+.c)
Combining the upper and lower bounds for Pm111 we have:
Σ k / (0) & Pmt1 S exp (0)
m
AM
m
Eg Eg-p. (0) p1(0)a0
exp
M
i=1
Rearranging the terms, we have
eAM
AM
m
V(p,,
Σ (,))
Σ Eoup, (4(0) S kM + mLe +
Eg u,(
AM
A
V(p2,0*)
I KM + mLe + AM2
X
where in the last inequality we use the fact that [0, e S 11+++ x² and (0) S M. Taking expectation both sides w.r.t. the randomness of {u, he(m) and noticing Ek S (em) according to Definition I gives the result.
Corollary D.1 If the non-cowex loss functions {liteelm) are uniformly L-Lipschitz over Q then the number of discontimuities in Eq. (4) becomes 0, and the expected regret Rm S Lant-B + AmM2 + V(p..0))
Proof of Proposition 2 Note that fe(p) -log (p) p) is (vo)( Lipschitz function w.r.t. ||
the constraint simplex domain {p [R/
prl: ||e|| 1, } since
Pi (pi,
max ||el] 1,2298
[V((())
max 1|el 11p22
11:00
Pī (pt,p)
1 (p; I (pt,
max A.p27D
S max
0270
(
7 AEEDD MAI
(v,)
Then applying the regret bound in (Shalev-Shwartz 2012 Thm 2.11) for FTRL algorithm with convex and Lipschitz functions, and noticing that (p'p") () is 1-strongly convex w.r.t its first argument, we can obtain
T Σ ((0n) < KL(P'ILD)
())
+
vvol(O,)²
+ nTT,2/72
Setting 7) G TVT gives the result.
Proposition D.1 (Proposition 3 in the main paper) Assume that the FTL algorithm runs on the sequence of functions (h,(v) Selpe) heer with fe(px) lolog (pi, p.))
19

---

Published as a conference paper at ICLR 2024
the domain [0, D). where D e log yvol(e,)
vol(e)
m f((pe).
Denote B²
log vol(@) (/oo))) Then we have
hh(())= < DJ (lgg
Σ be(ve) min vE(O,
4B
Furthermore, if we set d T with a 10.1/2), we have the regret bound Eis he(1s)
min Ets (())) S (a log log (v)l()) /Va) ((og)(( (+1)
413
Proof. According to the proof of Proposition the upper bound D of f((Pu) is: fi(pa) = log Pt I log vol(@) D Then we need to derive the lower bound B of fe(pr)) Let us first consider the maximum of (Pi:P), under the conditions of |||||
and p 2 yv. Using the Hölder inequality, can simply obtain that (p:: P) - |l b0leell = 1. But this z log 0, so the lower bound of log Tpt
zero, and thus we can- not use Lemma C.I Actually, considering the additional condition P 2 Sú, we can use La- grange multiplier method to calculate the maximum, or just simply achieve the maximum by observing the fact that: apart from the measure > AED MAi
means that log
7. the rest measure 1 -2 of p should be assigned uniformly to the indices A E DT where Pi
(i.e. A θ,) to maximize P) Assuming the cardinality of the set {A[A Dr, C ( is n, then )
maxp220<Pi.. p) = 1n2n + EAED, MMA) = -1-7+
() which is strictly less than
I 1. Thus we have log Pp 2 log 1-74 val
log (vol(e.)+ (1- Applying this lower
vl)
bound and the upper bound D2 of fe(pa)) into Lemma C.I
we obtain the first result. For the second
result, noticing D = log yvol[(.)
vol(e)
log
md" vo
log Va
completes the whole proof.
Va
am
Remark D.1 Assume that large enough. Then if a m8
C (0, 2)
lnf
la
have m
S 1 and B² loog yvol(
val(e)
[ 2 logg 1. The regret bound for learning
T
the step size of EWA algorithm in Proposition of order O(log 3)
Proof of Theorem 2 According to Lemma D.I. we know that the constant in Theorem D is equal to b 2 Then setting the distribution of in Theorem I as the Dirac measure on the optimal action 0r, and applying the regret bound in Theorem T we have
1
T
[((o,, 4x) (xx(0)) <
Hv(V) T
+ min
Fr(p*) VT 22
FI(e') T
} )+2V) VmM++gmm
+ g(m),
T
i=
where the expectation in the left-hand side is taken over the randomness of loss functions (le 1- It remains provide the regret bounds for learning the initialization and for learning the step size. For learning the initialization, note that y regret of FTRL in Proposition 2 for learning the initialization satisfies:
ad T L = 1 Σ vol(e)² vol())
then the
vol(e,
Fr(p") KL(P'1() nIL² 72
"
(L(D"(() "
+ 1+20
22
+ vo
+ vol (KL 110) 1)/Va.
where the last inequality holds by setting V₂r 1=20 - For learning the step size, it suffices to directly apply Proposition 3 Thus we can upper bound the task-averaged regret:
Rr.m Sg(m)+ + la + log (vol( (log 1)
4T
(KT()))(T
11)
((L +1), 22 VmM.
min
2
V2VT3-a
V
20

---

Published as a conference paper at ICLR 2024
E PROOFS OF THE REGRET BOUND FOR OWO META LEARNING WITH BOUNDED NON-LIPSCHITZ FUNCTIONS
Lemma E.1 (Minimizer of the Expected Bregman Divergence) Friiyiik et al. 2008 Thm III1) Let be a set of functions that lie on a fmite-dimensional manifold 9t and have associated differ- ential element dlt Suppose there is probability distribution PF defined over the set C. Suppose the function g* minimizes the expected Bregman divergence dø between the random function and any function g E A such that g" arg inf geA Er [do(F, (F,9). Then, if g exists, it is given by
9" = J = Ep,(F)
Proof of Proposition In the proof, write Pm in the main text as Pr for brevity, According to we have
Lemma
Pt arg min PEP(O)
(L(pille) arg min PEP(())
1 kL(p:llP)
Σ
- Σ p.
1
The existence of Pt. can be guaranteed by the convexity of KL-divergence w.r.t. its second argument. We also have p² arg peP(() Ei= (L + E pt. Then we have
T
(T.(oille))
(T(pille"
KL((ille)))
(T(eillett)
dpt flor
pi (d00) /
dpì dptt1 pt (d0)
log dp.
log
ΣJ [10g |log dpp,
dpi
dpi
(d(
dp
{ log
ddp+11
pi (d0) dp:
1 1(((t=
1)pt + pi)
log
(d(0)
7
dpt
Σ / flo8
log
[t --1 1
dpp
př (d())
dpp
dpt
log
+
08 (d())
dp.
dpř dp.
log
+ t
Pe (ao)
t
|+ _
[dot
1] p(())))
log
dp:
1 + -xi(oll0e))
log [I +
T
x2((1l)p) t
where the first inequality holds due to the the -eeeeee lemma (i.e. (Shalev-Shward 2012 Lemma 2.))). the second inequality holds due to Jensen's 's inequality, and the last step due to the fact
that log (1 x) & x.
21

---

Published as a conference paper at ICLR 2024
Proof of Proposition 5 Applying Lemma C.I finishes the whole proof. It remains verify that the lower bound of f((Pt) is strictly greater that O. Actually for each task t E [T], we use EWA algorithm to learn posterior pi, then we have dpī doa (6) f Texpi-A, D (((0))pn(()) # constant. If not, then exp(->, Ei 1 {n:(0)} = constant and hence 2; (0) constant for all 0 e O
expl 1xpp--Apo de Ei= (,(0))
which is trivial. Therefore pi # Pe1 and KL(pillpt)) > 0 for all & E [7]]
Proof of Theorem According to Lemma, set the positive constant b in Theorem as M2, the additional term (()) = 0. Then integrating the regret bounds from Proposition 4 and Proposition into the regret bound in Theorem we finish the proof.
F PROOFS OF THE TRANSFER RISK BOUND
Proposition F.1 Let a sequence of non-negative loss functions { 0 + RRoossmm) drawn i...d. from some distribution p be given to online algorithm that generates sequence of probability Assume the regret upper bound for the online algorithm is Um. Then let p 1 E i= Pt. for any p E P(O) that does not depend on the my
distributions {p; E ((O)) (i.e.
p=((e)))
choice of the sequence of loss functions { (Ei)e((m) we have the following bound:
Bo v Un + Ee E(0).
Proof.
E (1.
Eo-p(()
=E (1)). Eewp ((0)p(d0)
m
[1,) Ei
(d))
m
m
=Equ: m
E (O)p:(d))
Be Be e. + f (((0))((00)
m
(e.) m If -() + + Σ / ((())):(d))
m
1=1
m
E (E, 1 If (,, E m
1 m
Σ
(d())
m
=EE4 pm
(((0)p((d0)
Bamp, ((( - Ea-p- ((0) + E(a
Σ
Ean (0)
1=1
Um
m
+ E pm
Ea~p' (0)
m
m
Um
+ Ee- ((0),
m
where the third equality holds due the independence between E ~ a and pt, the Fubini-Tonelli Theorem for changing the order of integrals of non-negative function, as well as the fact that & is the i.idd copy of fú; in the six-th equality, {4, 1 ~ ب is the abbreviation for the notation μ is the product measure of i measures μ. Both
Eg n. Vj E j 1]; and -²'1 μ the six-th and the last equality hold due to the independence between p² and {L, ym (i.e. Fubini's Theorem for exchanging the order of integrals).
22

---

Published as a conference paper at ICLR 2024
Proposition F.2
T (L
1
Σ Pa) T
1
Σ (Tllol)
Σ
kL
1
T
06)
V2.
(5)
T
T
T
1=1
Furthermore, assume G2 2 m x2 (pillett) we have
1 KT T Σ pa) S 2V2+
Glllog ([logT+1])
(6)
T
T
Proof. For the first inequality. Using the joint convexity of KL-divergence w.r.t its pair argument and Jensen's 's inequality, we have
T
KL
1
Σ
Pr
Σ pn) S T
1
KL(pillen).
Plug the above result into the left-hand-sight of inequality in proposition, we have
T
KL
Σ
Pr))
Σ
(T:lll))
KT.
T 1=1
T
1=1
[L
Σ
Pri)
KT(
Pti
7
T
1=1
dpž
1 21=1 Pi:
Bampt
In
-Eg 2i.1
In
7 Σt
Ei=1
T
P11
7 Σt Prl
dpī
d ΣT Pt
In 7 2i=1 Pi:
Eanppt
- Egg 4 Σイ
7 Et=MP
P6
7 Ei=1 P+1
T Σ 2
|= Pr
dpī
7 TT
Li=1 pt
d Σイ= Pi
[Ba-p: In
+ Eomp In
B ΣT
In
d Et=1 Pi.
7 1
d Σイ Pr1
dpī
Bawn;
In
7
2t
Pi
KL
T
Σ PF).
(2) For the second inequality, notice the following decomposition
T
kL
1
Σ
Pn)
1
kL
Σ pi)
T
T
T
t=1
1=1
1=1
1=1
T 1 KL
-
Σ KL
Σ 7
Pn) - 7 Σ kL(pillen)
1 (
Σ KL(pillen) 1 E T m
Σ
+ Σ
pi))
Therefore, we can upper bound the first part of the right-hand-side of above equality by applying the first inequality in this proposition (i.e. Eq. (5)). and upper bound the second part of the right-hand- side of above equality by applying the regret bound in Proposition 4 Combining both upper bounds
yields the second inequality in this proposition (i.c. Eq. (6))
Proof of Theorem 4 Denote PT+1,1 1 ET Pel, AT11
ΣT. KL(o; lIpe)) for brevity, then TmM
applying Proposition F. we have
Epsr E B(, aa Ber < Eprr Camp-Ean--((0 17+1))
m
23

---

Published as a conference paper at ICLR 2024
Unlor Um(or-11ddr1)) Actually,
We next give upper bound B
m
Um (,.(PT+,,,,,441
E pmn
m
A + KLpp"llPr-111///
E /v0
E KL
MVTKT((''llers
-M1
+BRnr
Tm
Vmy Et KI(otllen)
TV2 + G2 T +1)
M IKL(O"llTTHI)
SM\
Exprr
Tm
VmB
V2
(log
MH
KL(P"IleTTL)
-M
R
m
Tm
/mB
H
V2
PlogT++1)
MH
KI,
(lertt)))
log 1/8
SM\
+
m
T'm
vmB T
H
2T
V2
Go +
MH
22
log 1/8
SM1
+
+
m
Tm
VmB
H
TH
27
V
G2 (loog +1)
2V²
G² T + +1 TvmB
H
log 1/6
<M
Vm
Tm
vmB
BV
2Tm
where the first inequality holds due to the regret bound Proposition 4 the second inequality due to Hoeffding's 's inequality holds with probability - 8, the third inequality holds due to Eq. (6) in Proposition
H2 Combining these results completes the whole proof.
G PROOFS OF THE PAC-BAYESIAN GENERALIZATION BOUNDS FOR STATISTICAL MULTI-TASE LEARNING
Lemma G.1 (Luosi & Neu 2023 Lemma 26) Let (Xi]i= be a sequence of non-negative random variables and for O, let Ft denote the o-algebra generated by XI,..., X,. Assume that X. has finite conditional mean ft Fx-1) and second moment of = [[ Then, for any X 0, the following bound holds with probability at least ō:
log
n
1 8"
Σ (m X1)
2
o log
2
Proof of Preposition For any t E [T'. define the regret of online algorithm II w.r.t. the probability distribution P as RI (pī) Em (pr: pi Ct3). According (Lgoosi & Neu 2023 Thm 1), for any task t [T]. we have gen AA,, Si) Au... (Ar(S.)) MIlem Then we have
m
T
T
Ru (A.(S.)) MuI... Rr. 1
gen Ac, St)
Mn
T
T t=1
T
Proof of Theorem
Notice that Ep Fr,i-1) S M then applying Lemma G. to bound
the sum of normalized martingale differences Tm Σt= Em (pes, Ges) in Proposition we have
RT. m
UT
m (pa,
UT... m
2M log
Mn....
m
Tm
Tm
where the last inequality holds with probability at least
Remark G.1 (Two Technical Novelties of deriving Generalization Bounds for Statistical Meta Learning). The technical novelties of our generalization bounds for statistical meta learn ing lie in the following two aspects: (1) For the transfer risk bound in Theorem 4 the novelties of
24

---

Published as a conference paper at ICLR 2024
our online-to-bor totbatch technique lie in 2 aspects: (i) The first novelty lies in bounding (ler++))))))
with Proposition 4 and Proposition F.2 both of which require the technical analysis of the proper- ties of the Radon-Nikodym derivative. To the best of our knowledge, such analysis does not exist in the previous online-to-batch literature. (ii) We further use concentration inequality to bound Bu KLig" (err+11), leading to the transfer risk bound in the non-convex setting. Such transfer risk bound, as shown in our Remark has almost the same convergence rate when compared with the latest transfer risk bound in the convex setting (i.e. (Balcan et al. 2021] Thm E.1), which is obtained by Jensen inequality of convex loss), demonstrating the novelty of the online-to-batch analysis de- veloped in our Theorem 4 (2) For the PAC-Bayes generalization bound in Theorem 5: first we need to admit that our Proposition is a direct corollary of recent online-to-PAC result in (Lugosi & Neu 2023 Thm 1) (i.e. we extent the result from single-task learning (Lugosi & Neu 2023) to our multi-task learning setting), but the novelty of our Theorem 5 lies in the combination of the online to- PAC analysis and the task-averaged regret analysis developed our Theorem Such combination pioneers new research direction to demonstrating PAC-Bayes generalization error bounds for statistical multi-task learning. If we do not combine the aforementioned two analysis tools, but just use the online-to-PAN analysis in (Lugosi & Neu 2023 Thm 1) and the traditional regret analysis for single-task learning in (Alquier 2021] Thm 2.1), we can only obtain the following trivial (to some extent) PAC-Baye generalization error bound for statistical multi-task learningg
H
Σ T Rg Ao.
1 T
BRamp ((0, 2)
1
Σ e(0, 240] VmM(1+++ + 7 ET= KL(p))lpa)) 1=1
+MV
2 log 3
m
m
Tm
which is less informative than our PAC-Bayes bound.oo statistical multi-task learning in Theorem 5
H EXPERIMENTS
We conduct k-center clustering experiment to verify the convergence performance of task-averaged regret Ry. /mm of our Algorithm| [ for non-convex OWO meta learning. We follow the existing work (Balcan et al., 202I) and meta learn the hyper-parameter a in the a-Lloyd's 's clustering algorithm.
Introduction of a- a-oydyd's Algorithm. a-Lloyd's algorithm consists of two phases: seeding phase and local search phase. The goal of the seeding phase is output ks initial centers with sampinng Concretely, each point v is sampled with probability proportional to min.ec d(e, c)", where d(,, )) the distance metric and C is the set of centers updated so far. The goal of local search phase is to run an iterative two-step procedure to output final centers. Specifically, the first step is to create a Voronoi tiling of all points induced by the initial set of centers from seeding phase; then, the new set of centers is updated by computing the centroid (c.g, median or mean) of each Voronoi tile. The a-Lloyd's 's algorithm family include popular clustering methods like randomly initialized k-means (a 0) and farthest-fire first traversal (a = oo). The indicator used to measure the performance of a-Lloyd's algorithm is the Hamming loss between the outputted clustering and the optimal target clustering (which is given in advance). The Hamming loss is piecewise constant function of a and hence is a piecewise Lipschitz function. More explanations for this algorithm family and proof for the piecewise constant property of Hamming loss can be found in (Balcan et al. 2021 Section 4.1).
Experimental Setting. We conduct k-center clustering experiment on both synthetic and real-world datasets, under the same settings as that in Balcan al. (202I). On the one hand, we create a Gaus- sian mixture binary classification dataset, where each class is a 2-dimensional diagonal Guassian distribution with variance and 20, as well as the expectation (0. and (be, We set b E [2, 3] to generate different tasks. On the other hand, we utilize the split of the real-world Omniglot dataset to create clustering tasks, by drawing random samples each composed of five characters among which four are constant throughout. We set the number T' E [1, 10) of training tasks and the number m E [5, 50) of samples per task for online optimization. Analogous to Balcan et al. (202T), we set the parameters 7 17 0.01 (not hyper-parameter searched), and set the step size À in EWA algorithm to minimize the regret in Eq. ( (not meta-learned). For any fixed T and m, we run our non-convex OWO meta learning algorithm to learn the hyper- saper-pprameter a in the a-Lloyd's is algorith- m, and calculate the normalized aask-averaged regret Ry.,. m over the T training tasks. In Figure 1 we show the convergence performance of Rm. m with respect to different number T E [1, 10] of training tasks, and validate the advantage of OWO meta learning over single-task learning. Each training task has m samples and is called m-ohot learning. In Figure? 2 we exhibit the asymptotic performance of averaged regret Rr.m m with respect to different number of samples on one task.
25

---

Published as a conference paper at ICLR 2024
00242
000
dngle baok Stittor mutti tock
25-t engletask
20sthor nulti tokk
10 10-hot
10o Lack
20-tor 20 mull
Tark-Nerage Regret Bom.
0.05
IV0232
0.022
Tash-Averaged Reghet
0/0193
0.029
04188
0.000
008383
0.003
0.001
0/07
10
10
Number of Training Tacks
Numbar Training Tasks
(a) Gaussian Mixture
(b) Omniglot
Figure Task-averaged regret
Ry with respect to the number of training tasks.
m
6.02
0.235
T Mak-Avernged Ragnet 3.
10
0.084
CJ911
0.022
0.000
Aol-Avegee
0.036
C/822
0.098
0.344
0003
4J22
0.000
30
Number of Samples Tack
Number Samples
Task
(a) Gaussian Mixture
(b) Omniglot
Figure 2: Task-averaged regret
Rrm with respect to the sample size m per training task.
Experimental Results in Figure We can observe that: (1) On both synthetic and real-world clus- tering dataset, running OWO meta learning algorithm can achieve sharper regret than that of online single-task algorithm, indicating the advantage of online meta learning framework. (2) When the training task number T 2 8, the task-averaged regret Rr,, of '10-shot multi-task algorithm in Figure (a)) smaller than the regret of '20-shot single-task' algorithm. This shows that, leveraging meta learning paradigm, even with less samples per task, can achieve the same or better performance compared with the single-task learning paradigm where the task has more training samples, hence al- leviating the cost of collecting labeled data. (3) On both synthetic and real- world clustering dataset, the normalized task avserged regret Rr.m/m m always decreases with the increase of the number T of training tasks, empirically validating the convergence performance of regret for OWO meta learning. However, we need to point out that, in some cases Figures aa)) Rr. m does decrease and even slightly increase when T' becomes larger. We attribute the counter-intuitive phenomenon to the encountering of a tough training task that is dissimilar to previous tasks and can lead to the increase of the value V defined in Section 4 Therefore, the task-averaged regret bound that involves the task similarity V in our Theorem 2 possibly becomes larger, and so does the regret. (4) On the real-world dataset Omniglot, the phenomenon that Rr.m/m slightly increases with the larger T appears more frequently than on the synthetic Gaussian mixture dataset. This implies the higher degree of similarity of Gaussian mixture clustering task than that of Omniglot splitting tasks, and attaches great importance of task similarity the success of online meta learning algorithms.
Experimental Results in Figure 2 We can observe that: (1) On both Gaussian mixture and Omniglot datasets, for any fixed 7, the normalized task-averaged regret Rr,m// m/m decreases with the increase of the number m of samples per task, verifying the vanishing regret property (i.e. Rr.m ol m)) of our results. (2) Leveraging OWO meta learning paradigm (i.e. when T =
or T = 10) achieves sharper regret than online single-task learning paradigm (i.e. T 1). (3)
When using more training tasks, the regret improvements Gaussian mixture dataset larger
26

---

Published as a conference paper at ICLR 2024
than that on Omniglot dataset. This is consistent with the observation in Figure I that Gaussian mix- ture clustering tasks share a higher degree of task similarity than that of Omniglot splitting tasks, revealing the great effect of task similarity to the performance of online meta learning algorithms.
Remark H.1 (More Discussions of our Algorithm 2 (1) The Limitation Aspect. We need to admit that at the current stage we are unable to run our Algorithm 2 in practice, because it is hard to compute the analytic form of RN derivative of pm w.E.t the Lebesgue measure (if we want to dou implement our algorithm in real-life applications, we need to compute de to let pt: be tractable in Euclidean space). The computation problem actually lies in line 6 (i.e. the meta update step of
Pt+1,1 = + E Pom) in Algorithm 2 even though pam is the Lebesgue measure (i.e. correspond- ing to uniform distribution) or Gaussian measure (i.e. corresponding to Gaussian distribution). Concretely, consider the simplest case where P11 is the Lebesgue measure v. and hence using EWA obtains the Gaussian measure Pim (with density ((11,, Assume that Prm is also a Gaus- sian measure (with density N (222, then p31 = Pammt.mmm and the density of pam w.t.t to v is +N o2)), indicating that p3m is not Gaussian measure and it is hard to compute the precise form of the density function 4pam du Nevertheless, it will also be difficult to compute the precise form of the density function 1p du
døam- dpam. p(prm=+-2mm)
X expl Eie(()
(xi)
de dpas
2dv
as well as the precise value of the normalized constant f sepp(>>44> E (0),, Therefore, it is also not easy to compute the precise form of dpr+i.m over the continuous domain.
dpt+1.1
(2) The Potential Application Aspect. However, we point out that our Algorithm is potentially ap- plicable to the discrete domuin where the updating rule P1+1,1 = Ex=1 pom/l /t of our Algorithm corresponds to the averaging of previous discrete probability density vectors, which is more feast ble. Thus our algorithm may be utilized to the Expert Advice problem for online model selection (see (Cesa-Biann Bianchi & Lugosi 2006 Sect 2)), and this serves as one of our ongoing research directions.
Remark H.2 (Detailed Comparisons between our Algorithm 7 and other Algorithms for Non- Couvex OWO Meta Learning) We discuss more differences between our Algorithm and the state- of-the-art art algorithm from (Balcan et al. 2021 Alg 3) as well as other baseline for OWO meta learning. The detailed explanations are three-fold: (1) The comparisons with the singletaskk al- gorithm. Actually, we choose single-task EWA algorithm as our baseline in all experiments. In both Figure 7 (m-shol multi-lask method v.s. single-task baseline) and Figure (T = 5 multi-lask method v.s. T 1 single-task buseline), we show advantages of the meta-learning based EWA algorithm over the single-task EWA algorithm baseline, and verify the convergence performance of task-averaged regret of our meta learning algorithm. (2) The comparisons with the state-of- the-art (Balcan et al. |027] Alg 3) for non-convex SrecewiseeLiischine OWO meta learning. Our Algorithm| L is actually based on the modification of (Balcan et al., [027] Alg 3), and the two main differences are as follows; (i) For learning the initialization p. we use FTRL algorithm to achieve the regret of O(T2/2+a), a E (0, 1)), and the mixture parameter 7 = 48 /Ta is ir- relevant to the optimal p" (hence "y can be set in advance). Existing work (Balcan al. (021] also uses FTRL algorithm, but (Balcan et al. (202]) leverages a more complicated analysis, at- taining a larger regret bound (2m4/2238/4 Nevertheless, their choice of KL.pp" (10)= (10)""" /mmm)// T1/Ay//2
in (Balcan et al. [021 Thm 3.2) depends on the knowledge of optimal distribution pa that con- tains information of T training tasks, which is unfeasible in the sequential online meia learn- ing setting. (ii) For learning the step size v, we choose FTL algorithm to learn the step size ve argmmnn DD] El= ha(w)) = (E-- Sa(pa)/ - -1)) 1/2 to derive a logarithmic regret bound of Olog T). In contrast, (Balcan et al. 2027)) chooses c-FTL algorithh optimize the func- tions (he(v) = v + (fe() + 2// on the domain [o. D2] (where D2 2 max, fe(Pt)) to +)) 1/2 and lead to the regret O(T22 + (log 2)), which O( log T) if we set <= 1/T1//4 and is slower than our regret bound. (3) Practical implementation of meta learning algorithm. However, (Balcan) et al. 2021) uses a heuristic method to learn (instead of meta learn) the step size X,, so their imple- mentation is not rigorously the same their pseudo code in (Balcan et al. 2021 Alg 3). We follow almost the same implementation details as (Balcan et al. 2021) (which is also explained in detail in the Experimental Setting part), with the main difference being that we verify the regret bound over training tasks but (Balcan et al. (222]) verify the regret bound over test tasks. Thus, we do not compare the convergence performance of regret of (Balean et al. 2027 Alg 3) in our experiments.
learn the step size U2 = arg min E ha(v) = (Et-)
27


Reviews:
[{"review_id": "PihjVYRXkf", "reviewer": "Reviewer_wQQZ", "summary": "The authors consider the problem of meta-learning, in particular the online-within-online setting with non-convex loss functions.  They consider the initialization and step size of the Exponentially Weighted Aggregation (EWA) algorithm.  For functions that are bounded, non-convex, and piecewise Lipschitz they propose modifications to the state of the art algorithm and obtain better task-averaged regret bounds.  For bounded, non-convex, non-Lipschitz functions they propose a new method and obtain the first task-averaged regret bounds for that problem.  They also apply those results to obtain novel PAC-Bayes generalization bounds for meta-learning.", "questions": "### Main comments/questions\n\n1. Can you include some discussion on how the problem set up, methods, and regret bounds for OWO relate to the problem of online learning with dynamic comparators, (eg “Online Optimization : Competing with Dynamic Comparators” https://proceedings.mlr.press/v38/jadbabaie15.pdf and more recent works).  It seems for OWO meta-learning the comparator sequence would be fixed for each task and the changes would be known a priori (every $m$ rounds).  Perhaps there would be a significant gap between regret bounds from online optimization with dynamic comparators specialized to OWO (eg accounting for task similarities etc) versus regret bounds for methods designed specially for OWO.\n\n### Minor comments/questions\n2. Can you add some discussion for problem parameter sizes --- eg for some potential applications would the number of iterations $m$ be large while the number of tasks $T$ be much smaller or vice versa?  \n3. (Related works) “These regret bounds are irrelevant to the sample size m per task…” does that mean ‘the regret bounds do not depend on the sample size m per task’ or something else?\n\n### Very minor notation/wording\n- Abstract and intro “mete learning”\n- Section 4.2 “at i-the round”\n- Experiments “Lloyd” not “Llyod”\n- Section 4 there is text in blue", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Results\n- For adversarial bounded, possibly non-convex, piecewise Lipschitz loss functions, the authors propose modifications to a state-of-the-art method in Balcan et al. (2021) and obtain significantly improved task-averaged regret bounds.  In contrast to prior bounds, the bound (Theorem 1) is sub-linear w.r.t. the number of per-task iterations $m$).  The dependence on the number of tasks $T$ is also improved.  \n- The authors consider a more general class of problems (removing assumption of piecewise Lipschitz) and propose a new algorithm and the first regret bounds for this setting.  Though there are some concerns about this set of results (discussed below)\n\n\n### Writing & Soundness\n- Overall I found the writing and organization to be good in terms of organization and clarity.  I did not carefully check the analysis, but as far I could tell the results appear sound.", "weaknesses": "### Significance of Algorithm 2 and its regret bound\nThe non-convex non-Lipschitz setting is challenging.  The authors derive the first task-averaged regret bounds  for non-convex non-Lipschitz loss functions.  However some issues (which are acknowledged and discussed in the appendix) lead to concerns about the significance of the results for this problem.  \n- It is noted in the appendix (Remark B.1, which is referenced at the end of Section 4) that due to the initialization update rule of the FTL algorithm, the regret bound in Theorem 3 may be vacuous under the regret definition in Eq (1) when the task optimal distribution $\\rho_t^*$ is a Dirac measure.    It is mentioned in Remark B.1 that alternative update rules of $\\rho_{t1}$ may address the issue but (i) are there candidates in mind and (ii) how badly might they impact the regret bound?  i.e. is it plausible that an analog to Proposition 4 could be found that would still yield the same or almost the same good task-averaged upper-regret bound as Theorem 3?\n- It is also noted in the appendix (Remark H.1, which I don’t think was referenced in Section 4) that the analytic form of the RN derivatives can’t be computed in practice even for uniform or Gaussian distributions. This also leads to concerns over the significance of Theorem 3\n\n### Experiments\n- It was good to include some experiments, but only Algorithm 1’s performance is shown, not (Balcan et al. (2021)) or any other baseline, even though the experiments used are set up the same as those in (Balcan et al. (2021)).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "viADsJnndE", "reviewer": "Reviewer_ESpG", "summary": "In this paper, the authors study an Online Within Online (OWO) meta learning problem in which both the tasks and data within each task become available in a sequential order. The correlation among tasks is assumed to be helpful for learning the latter tasks. This paper provides a sub-linear regret w.r.t. the number of iterations $m$, and the regret exhibit a better convergence rate w.r.t. the number of tasks $T$. The authors investigate both non-convex piecewise Lipschitz continuous functions and non-Lipschitz functions in section 4.1 and 4.2, which makes the contribution fruitful. The proposed algorithm uses FT(R)L to update distribution $\\rho_i$ in two different settings, which is motivated by previous work. The improvement comes from the learning initialization step and the choice of step size.\n\nThe authors are quite honest to discuss the limitation in Remark~B.1 of Appendix~B and Remark~H.1. Thus, there is no need to further discuss these issues in my comments. \n\nI strongly recommend the authors to complement more details and explanations in the proof to make it more readable. For instance, I was quite confused on the third equation in the proof of Proposition~F.1., where the explanation that $\\ell_i'$ ``is the i.i.d. copy...'' is not enough to show the equivalence, the boundedness of $\\ell_i$ is also required. I cannot fully understand $\\{\\ell\\}_{j=1}^{i-1}\\sim \\mu^{i-1}$, $j=0$ and $\\mu^{i-1}$ are not defined. The issues like that are common in proofs. I have to admit that I was convincing myself some (in)-equalities are correct since the authors are honest to admit their issues. Due to the time limit, I can only proof check some part of the proofs. I hope other reviewers and the authors could help checking the theoretical part in the future.", "questions": "Please refer to the summary.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Please refer to the summary.", "weaknesses": "Please refer to the summary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "Gocp2gXBuQ", "reviewer": "Reviewer_8VuH", "summary": "This paper first improves the regret bound of an existing non-convex online-within-online OWO) meta-learning algorithm for bounded and piecewise Lipschitz functions, and then design a new efficient OWO meta learning algorithm for bounded functions (maybe non-Lipschitz). This paper also derives a transfer risk bound and a PAC-Bayes bound for statistical meta learning via the regret analysis.", "questions": "1) The authors should explain why their analysis and algorithm led to the improvements in the regret bounds. \n2) The authors should explain whether there exist some advantages of the first improved regret bound when it is compared with the second one.\n3) The authors should conduct some experiments to compare their algorithms against existing algorithms.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1) The problem of non-convex online-within-online OWO) meta-learning problem studied in this paper is interesting, which does have many real applications.\n2) This paper has proposed two improved regret bounds for the non-convex OWO meta-learning problem.\n3) The authors also extend the improved regret bound to the transfer risk bound and PAC-Bayes generalization bound for multi-task learning.", "weaknesses": "1) Although improved regret bounds are presented, the authors do not explain why their analysis and algorithm led to these improvements. \n2) Moreover, it seems that the second improved regret bound is tighter than the first one, and holds in a more general case (non-Lipschitz). So, the value of the first one is not clear.\n3) The transfer risk and PAC-Bayes generalization bounds are derived by using the online-to-batch and online-to-PAC techniques, which are incremental to some extent.\n4) Although some experimental results are provided, no existing algorithms are compared and discussed in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "9EX1YzMejF", "reviewer": "Reviewer_NU9X", "summary": "In this work, the authors consider the problem of non-convex online within online (owo) meta learning, which is a framework where a learner has to adapt to several online learning problems sequentially, and aims to use knowledge of the learned learning rate and step size of previous tasks to speed up learning.\nThe author first consider the same restrictions for the loss function (namely bounded and piece-wise Lipschitz) as in a previous work of Balcan et al. (2021) and widely improve the results, deriving regret bounds with improved dependencies on the number of tasks $T$ and the number of episodes within each task $m$. This algorithm is easy to implement and experiments can be found in the appendix that highlight that transferring information helps. \n\nThey then propose a different more general approach, which only requires the assumption of bounded loss functions. They derive regret bounds that are tighter than for the first algorithm, and are even sharper than the bounds derived by Khodak et al. (2019). While the theoretical results hold, it is also indicated in the appendix that they cannot manage to implement the algorithm, which limits the practical interest of this algorithm to specific and easy to implement problem instances.\n\nFinally, they also provide generalization bounds for statisitical meta-learning and PAC-Bayesian bounds for statistical multi-task learning.", "questions": "Could you clarify the relation between the EWA and the FTRL formulations of Algorithm 2 l.4.  and how that prevents computations would be a good step towards understanding the limitations of this algorithm?\n\nCould you discuss existence of the lower bounds for this problem and of the optimality of the results?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper proposes significant improvements in the analysis of the non-convex OWO problem, which is a complex problem that has not been widely studied up to now.\nThe proposed algorithms rely on well studied frameworks of online learning, notably the EWA algorithms as well as the FTRL and FTL framework.\nUsing a similar framework as the only exisiting previous result for non convex OWO (to the best of my knowledge), they propose an algorithm with significantly tighter bounds in terms of $T$ and $m$, which can be implemented and appears to perform fine in experiments.\n\nThe second algorithm appears simple, but achieves a significant improvement.\n\nThe generalization bounds are novel and a good addition to the work.\n\nFrom what I got to see, the proofs seem correct and are well detailed.", "weaknesses": "It would be good to have a more detailed explanation of why the second algorithm does not work well in practice. \nIn particular, the EWA step is normally expressed in close form solution and thus computation should not be an issue. \nDetailing the relation between the EWA and the FTRL formulations of Algorithm 2 l.4.  and how that prevents computations would be a good step towards understanding the limitations of this algorithm. \nIn the current format of the paper, it is necessay to reach the last remark of the appendix to understand why the result of Theorem 2 is not \ndirectly eclipsed by the more general and tighter bound of Theorem 3, which affects the clarity of the paper.\n\nA discussion of the lower bounds and of the optimality of the results is lacking and would help getting a better understanding of how much the bounds can be further improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)