Learning-to-learn non-convex piecewise-Lipschitz functions
Authors: Nina Balcan
Mikhail Khodak
Dravyansh Sharma
Ameet Talwalkar
Venue: NeurIPS 2021 Poster (2021)
Keywords: meta-learning
data-driven algorithm design
robustness
online learning
nonconvex optimization

Abstract: We analyze the meta-learning of the initialization and step-size of learning algorithms for piecewise-Lipschitz functions, a non-convex setting with applications to both machine learning and algorithms. Starting from recent regret bounds for the exponential forecaster on losses with dispersed discontinuities, we generalize them to be initialization-dependent and then use this result to propose a practical meta-learning procedure that learns both the initialization and the step-size of the algorithm from multiple online learning tasks. Asymptotically, we guarantee that the average regret across tasks scales with a natural notion of task-similarity that measures the amount of overlap between near-optimal regions of different tasks. Finally, we instantiate the method and its guarantee in two important settings: robust meta-learning and multi-task data-driven algorithm design.

Learning-to-learn non-convex piecewise-Lipschitz functions
Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma
Carnegie Mellon University
(ninamf, ,mkhodak, dravyans) Ccs. Cew.emssssccc.m.... cmu.edu
Ameet Talwalkar
Carnegie Mellon University & Hewlett Packard Enterprise talwalkar@cmu. edu
Abstract
We analyze the meta-learning of the initialization and step-size of learning algo- rithms for Siecewise-Lipschie functions, non-convex setting with applications to both machine learning and algorithms. Starting from recent regret bounds for the exponential forecaster losses with dispersed discontinuities, them to be mntializaaionnddeeedeee meta-learning procedure that learns both the initialization and the step-size of the algorithm from multiple online learning tasks. Asymptotically, we guarantee that the average regret across tasks scales with natural notion of task-similarity that measures the amount of overlap between near-optimal regions of different tasks. Finally, we instantiate the method and its guarantee in two important settings: robust meta-learning and multi-task data-driven algorithm design.
generalize and then use this result to propose a practical
Introduction
While learning-tor le-rrr meta- -laanine has long been an object of study [45], in recent years it has gained significant attention as a multi-tast paradigm for developing algorithms for learning in dynamic environments, from multiple data sources, and in federated settings. Such methods focus using data from multiple tasks to improve performance when facing a new, potentially related task. A popular approach is initialization-base meta-learning, in which the meta-learner uses multi-task data to output an initialization for an iterative algorithm such as stochastic gradient descent (SGD) [25]. The flexibility of this approach has led to its widespread adoption, e.g. in robotics [23] and federated learning [18]. and to growing number of attempts to understand it, both empirically and theoretically [20, 29, 24, 40, 42]. However, outside some stylized setups our learning theorrtic understanding of how to meta-learn an initialization is largely restricted to the convex Lipschitz setting.
We relax both assumptions to study the meta meta-leaming of online algorithms over piecewise-Lipsenn functions, which can be nonconvex and highly discontinuous. As no-regret online learning over such functions is impossible in-general, we study the case of Seccewise-Lipschine functions with dispersed discontinuities that do not concentrate in any small compact subset of the domain [11]. Such functions arise frequently in data-driven algorüthu design, where the goal is to learn the optimal parameter settings of algorithms for difficult (often NP-Hard) problems over a distribution or sequence of instances [4]; for example, small change to the metric in cluster linkage can lead discontinuous change in the classification error [7]. In this paper, we also demonstrate that such losses are relevant in the setting of adversarial robustness, where we introduce novel online formulation. For both cases, the associated problems are often solved across many time periods or for many different problem domains, resulting in natural multi-task structure that might improve performance. To the best of our knowledge, ours is the first theoretical study of meta-learning in both of these application settings.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In the single-task setting the problem of learning dispersed functions can be solved using simple methods such as the soanentially-weigheee initialize online learners in this setting, we propose method that optimizes a sequence of data- dependent upper-bounds on the within-task regret [29]. The result is an averaged bound that improves upon the regret of the single-task exponential forecaster so long as there exists an initial distribution that can compactly contain many of the within-task optima of the different tasks. Designing the meta-procedure is especially challenging in our setting because it involves online learning over a set of distributions on the domain. To handle this we study a "prescient" form of the classic felgla-thereguulaiizeed leader (FTRL) scheme that is run over unknown discretization; we then show the existence of another algorithm that plays the same actions but uses only known information, thus attaining the same regret while being practical to implement.
forecaster. To design an algorithm for learning to
To demonstrate the usefulness of our method, we study this algorithm in two settings.
Multi-task data-driven algorithm design. We consider data-driven tuning of the parameters of combinatorial optimization algorithms for hard problems such as knapsack and clustering. The likely intractability of these problems on worst case instances have led to several approaches to study them in more realistic settings, such smoothed analysis [44] and data-driven algorithm configuration [4]. Our setting is more realistic than those considered in prior work. It is more challenging than learning from iid instances [27, 12]. but at the same time less pessimistic than online learning over adversarial problem instances [11] as it allows us to leverage similarity of problem instances coming from different but related distributions. We instantiate our bounds theoretically on several problems where the cost functions are piecewise-constant in the tuned parameters, allowing our meta-procs meta-procedure to learn the right initial distribution for exponential forecasters. This includes well-known combinatorial optimization problems like finding the maximum weighted independent set (MWIS) of vertices on a graph, solving quadratic programs with integer constraints using algorithms based on the celebrated Goemans- -iilaanm-o algorithm, and mechanism design for combinatorial auctions. Then we consider experimentally the problem of tuning the right a for the a-Lloyd's family of clustering algorithms [15]. In experimental evaluations on two datasets- a synthetic Gaussian mixture model and the well-known Omniglot dataset from meta-learning [33]-our meta- peea-procedure leads to improved clustering accuracy compared to single-task learning cluster. We also study results for a family of greedy algorithms for the knapsack problem introduced by [27] and obtain similar results for synthetic dataset. The results holds for both one-shot and five-shot tasks.
Online robust meta-learning. The second instantiation of our meta-learning procedure is to a new notion of adversarial robustness for the setting of online learning, where our results imply robust meta-learning in the presence of outliers. In this setting, the adversary can make (typically small) modifications to some example E X, which can result in potentially large changes to the corresponding loss value 4, (z)), where h E H is our hypothesis. For instance, consider the well-studied setting of adversarial examples for classification of images using deep neural networks [36, 17]. Given a neural network f. the adversary can perturb a datapoint x to a point x', say within small Lall around x, such that f(x) = f(z') but the true label of x' does not match x, and therefore 1 (x) * (t()). In general, under the adversarial influence, we observe a perturbed loss function 7, (z) = (z) + (z). Typically we are interested in optimizing both the perturbed loss (z).. i.c. measuring performance relative to optimum for adversarially perturbed losses, and the true loss la (I)) (performance on the unobserved, unperturbed loss). For example, in the online learning setting, [1] consider perturbed loss minimization for linear dynamical systems, while [41] look at true {0. 1} loss minimization in the presence of adversarial noise. Our approach ensures that regret for both the perturbed and true loss small, for Srareewss--Lisshhit but dispersed adversaries.
2 Preliminaries and initialization-deeeneen learning of dispersed functions
In this section we introduce our setup and notation for online learning of piecewise-Lipshhee functions in a multi-task environment. We then generalize existing results for the single-task setting in order to obtain within-task regret bounds that depend on both the initialization and the task data. This is critical for both defining notion of task similarity and devising meta-learming procedure.
Meta Meta-learning setup Following past setups [2, 21, 29], for some T, m > and all E [T] and i E [m]] we consider a meta-learner faced with sequence of T' loss functions l,, : C. - [0, over compact subset C' c: IRd that lies within a ball B(p, R) of radius R around some point p E R

---

Algorithm Exponential Forecaster
1: Input: step size parameter À E (0, 1]. initialization w C + 1220
2: Initialize w1 = w
3: for i = 1.2....,mm... do
4: W; : Jc wp)ppp
5: Sample Pr with probability proportional (x)())) i.e. with probability pi(p:) (0((1))
W.
6: Suffer (((pt) and observe fx(-)
7: For each p E C, set (p+1(p) (.,())
Here we used the notation [n] - {1....,,)) pick an element Pt, E C' before then suffering a loss or cost (p,(s) For fixed t, the subsequence f..1...., f.m defines task for which we expect a single element Pi E C' to do well, and thus we will use the within-task regret on task & to describe the quantity
n). Before each loss function l,, the meta-learner must
TR Σ Ee,le)
R -E (os(o))) - (x,( where Pi E arg min PEC
In the single-task setting the goal is usually to show that Rtm is sublinear in m., i.e. that the average loss decreases with more rounds. key point here is that the functions we consider can have numerous global optima. In this work we will assume, after going through the m rounds of task t, that we have oracle access to a single fixed optimum for t, which we will refer using Pi and use in both our algorithm and to define the task-similarity. Note that in the types of applications we are interested in nn--peeeewss--ipschheeee
functions the complexity of computing optima scales with the number of discontinuities. In the important special case of precewise-constane functions, this dependency becomes logarithmic [19]. Thus this assumption does not affect the usefulness the result.
Our goal will be to improve the guarantees for regret in the single-task case by using information obtained from solving multiple tasks. In particular, expect average performance across tasks to improve as we see more tasks; to phrase this mathematically we define the task-averaged regret
T RT... Σ R.m.
T
m
(es(pt)) - (pp(
and claim improvement over single-task learning if in the limit of - oo it is smaller than R,m-- Note that for simplicity in this work assume all tasks have the same number of rounds within-task, but as with past work our results are straightforward to extend to the more general setting.
functions We now turn to target functions and within-tan task algorithms for learning them: piecewise-Lipschitz losses, i.e. functions that are L--Lisshitz w.r.t. the Fuclidean norm everywhere except on measure zero subsets of the space; here they may have arbitrary jump discontinuities so long they still bounded between [0, 1]. Apart from being a natural setting of interest due its generality compared to past work on meta-learning, this class of functions has also been shown to have important applications in data-driven algorithm configuration [1]]; there these functions represent the cost, e.g. an objective value or time-complexity, of algorithms for difficult problems such as integer programming, auction design, and clustering.
Learning piecewise-Lipstee
This literature has also shown lower bounds demonstrating that nogretret learning Seeceeise--ipseeee function is impossible in general, necessitating assumptions about the sequence. One such condition dispersion, which requires that the discontinuities are not too concentrated.
Definition 2.1 ((UJ). The sequence of random loss functions E Eiy..., em is said to be 3-dispersed with Lipschitz constant L if. for all m and for all 2 m-9, we have that, expectation over the randomness of the finctions, at most Õ(e)) functions (the soft-O notation suppresses dependence on quantities beside e, m and 3, as well as logarithmic terms) are not L-Lipschitz for any pair of points distance in the domain C. That is, for all m and for all m
E max P.P' EC
li E [m] (((p) - E(('') Lllp - 111 < Ö(em)
(3)
Ilo-p' S'
3

---

Assuming a sequence of m B-dispersed loss functions and initial distribution wi set to the uniform distribution over C' and optimize the step size parameter, the exponential forecaster presented in Algorithm 1 achieves sublinear regret Ó dm log( Rm) + (I+ 1-)) While this result achieves no-regret procedure, its lack of dependence on both the task-data and on the chosen initialization makes it difficult to meta-learn. In the following theorem, we generalize the regret bound for the exponential forecaster to make it data-dependent and hyperparaameterddeeeddeee
Theorem 2.1. Let f1....,em em C + [0, 1] be any sequence of piecewise I.-Lipschitz, functions that are 3-dispersed. Suppose C' C R is contained in ball of radius R. The exponentially weighted forecaster (Algorithm 1) has expected regret Rm. S m. + log(1/Z) + +[([. + 1)m--9),, where
Z Sein".m 9) w(oydp for pr the optimal action in hindsight. Jc "((ddpp
The proof of this result adapts past analyses of Algorithm I; setting step-size À appropriately recovers the previously mentioned bound. The new bound is useful due to its explicit dependence on both the initialization w and the optimum in hindsight via the l1g(1 term. Assuming w is (normalized) distribution, this effectively measures the overlap between the chosen initialization and a small ball
Secp om -By w(p)d
around the optimum; we thus call- log Z log
the negative log-overlap of Je w(p)dp
initialization w(.) with the optimum p²
We also obtain asymptotic lower bound on the expected regret of any algorithm by extending the argument of [10] to the multi-task setting. We show that for finite D' we must suffer 22(m!=5 regret, which limits the improvement we can hope to achieve from task-similarity.
Theorem 2.2. There is a sequence of piecewise T--Lischitzz B-dispersed functions Eu, : 10, 1] + [0, 1). whose optimal actions in hindsight arg min, Eis (p) are contained in some fixed ball of diameter D*, for which any algorithm has expected regret Rm 2 5mm)--))
2.1 Task-similarity
Before proceeding to our discussion of meta-learning, we first discuss what we might hope to achieve with it; specifically, we consider what a reasonable notion of task-similarity is in this setting, Note that the Theorem 2.1 regret bound has three terms, of which two depend on the hyperparameters and the last is due to dispersion and cannot be improved via better settings. Our focus will thus be on improving the first two terms, which are the dominant ones due to the dependence on the dimensionality and the distance from the initialization encoded in the negative log overlap. In particular, when the initialization is the uniform distribution then this quantity depends inversely on the size of small ball around the optimum, which may be quite small. Via meta-learning we hope to assign more of the probability mass of the initializer to areas close to the optimum, which will decrease these terms. On average, rather than a dependence on the volume of a small ball we aim to achieve a dependence on the average negative log-overlap
min V2 = w:Cr+ wp)dpp=1 T
log
w(p)dp
(4)
which can be much smaller if the task optima Pf are close together; for example, if they are the same then V B(p", .m- around the shared optima. This is also true if vol(NrerBipp m-)) > 0, as one can potentially initialize with all the weight in the intersection of the balls. On the other hand vol(Nte B(p,, m. m-)) = 0, V > O. For example, if a p-fraction of tasks have optima Po and the remaining at P1 with llpo p1ll > 2m 8 the task similarity is given by the binary entropy function p logp (1 p) log(1-1)
V= == 0, corresponding to assigning all the initial weight within the common ball
V=H,(
The settings of Algorithm 1 that achieve the minimum in the definition of are directly related to V itself: the optimal initializer is the distribution achieving V and the optimal step-size is V/vm. Note that while the explicit definition requires computing a minimum over a set of functions, the fask-similarity can be computed using the discretization constructed in Section 3.1.

---

3 An algorithm for meta-learning the initialization and step-size
Having established a single-task algorithm and shown how its regret depends on the initialization and step-size, we move on to meta-learning these hyperparameters. Recall that our goal is to make the task-averaged regret (2) small, in partieular Algorithm 1 from the uniform distribution, up to or (1(1) terms that vanish as we see more tasks. This accomplishes the meta-learning goal of using multiple tasks to improve upon single-task learning.
improve upon the baseline of repeatedly running
In this paper, we use the strategy of running online learning algorithms on the data-dependent regret guarantees from above [29]. If we can do with sublinear regret in T, then we will improve upon the single-task guarantees up to or o1() terms, as desired. Specifically, we are faced with a sequence of regret-upper--ounds (w., v) (C + fe(w)/ /v) ym + g(m) on nonnegative functions over C and positive scalars v > 0. Note that g(m) cannot be improved via meta-learning, so we will focus on learning wr and To do so, we run two online algorithms, one over the functions ft and the other over h4 (v) = v + [((w;)) where we is set by the first procedure. As shown in the following result, if both procedures have sublinear regret then our task-averaged regret will have the desired properties:
Theorem 3.1. Assume each task t E [T] consists of a sequence of m 3-dispersed piecewise L- Lipschitz functions la C++ [0, 1.. Let Jr and g be functions such that the regret of Algorithm I run with step-size x = wo/ffor u > O and initialization w : C + Rzo is bounded by Ue(w, v) (v + fe(w)/ ////m//mmmmmmmmmmm + g(m). Suppose we have a procedure that achieves Fr(w) regret w.r.f. any w : C + Rzo by playing actions we C + R20 on fr and another procedure that achieves Hr(v) regret w.r.. any u > by playing actions Vt > on h((r) = y + fe(we)/u, where HT is non- non-increasing on the positive reals. Then by setting Pt. using Algorithm 1 with step-size v2/ /m and initialization we at each task for w* arg min wo: Ei= Selw) the optimal initialization and V the task- kusk-imilarrty (4) we get task-averaged regret bounded by
fraschitz,uuncionss
HT((V) T
{ FT(w") VT 22 (/Fr((w)/T] 2V
+ min
/m + g(m)
(5)
This result is an analog of [29, Theorem 3.1] and follows by manipulating the definition of regret. It reduces the problem of obtaining small task-averaged regret to solving two online learning problems, one to set the initialization and one to set the step-size. So long as both have sublinear regret then we will improve over single-task learning. In the next two sections we derive suitable procedures.
3.1 Meta-learning the initialization
The most technically challenging component of the procedure is learning the initialization. As dis- cussed, this can be done via no regret procedure for the sequence fi(w) = log Susez m By w[podd Je w(p)dp
This is nontrivial as the optimization domain a set of nonnegative functions or measures on the domain C. To handle this, we introduce some notations and abstractions. At each task t we face a function fe associated with an unknown closed subset C. C C in particular C. = B(pt m m=) with positive volume vol(C.) > 0 that is revealed after choosing W; C + R20 For each time
t define the discretization D, = (D= Nose c( c E [0, vol(D) > 0} of C, where
ci = Ct and c( = C.C,, We will use elements of these discretizations to index nonnegative vectors in Ialp.l specifically, for any measure w C + Rzo let w(t) R!Da denote the vector with entries w()) = JD w wp))dp for D E De. Note that we will exclusively use p. q, U, w for measures, with u specifically referring to the uniform measure, i.c. D()) = DD) For convenience, for all real vectors x we will use & to denote p/ /|pll. Finally, we abuse notation and remove the parentheses to refer those vectors associated with the final discretization, i.e. v v(T) and w w(T).
Now that we have this notation we can turn back to the functions we are interested in: fe(w))
Sc, w(())d
- -log Te "(()dpp where C. = B(pi, m m)). Observe that we can equivalently write this as fe(w) = -log wi, W), where Wiip: Inco, ; this translates our online learning problem from the domain of measures on to the simplex on |Dr| elements. However, we cannot play in this domain explicitly as we do not have access the final discretization Dr. nor do we get access to w after task t, except implicitly via Ct. In this section we design a method that implicitly run an online convex optimization procedure over RR (Drl while explicitly playing probability measures C' + R2--
80
5

---

Algorithm 2 Follow-the- herpoowttte-RegglaiieedLLL----- (prescient form)
1: Input: discretization Df of C, mixture parameter > E [0, I]. step-size v/ > 0
2: Initialize W1
3: for / = 1,2, 1,2,...; do
4: Play W; and suffer fe(w:) = - Log(w? wi).
5: Observe ft-
6: Update Ws41 = arg [|]l DRI(W]lV) + #nEss(
As the functions ft are exp-concave, might first consider applying method attaining logarithmic regret on such losses [28, 37]; however, such algorithms have regret that depends linearly on the dimension, which in our case is pTly(T). We thus turn to the the (FTRL) family of algorithms, which in the case of entropic regularization are well-known to have regret logarithmic in the dimension [43]. In Algorithm 2 we display the pseudo-code of a modification with regularizer D- where recall v is the vector of volumes of the discretization Dr of C, and we constrain the played distribution have measure at least 1V over every set D E Dr- While this requires knowing the discretization Dr of C' in advance, the following lemma shows that we can run the procedure knowing only the discretization D, after task by simply minimizing the same objective over distributions discretized on D,. This crucially depends on the re-scaling of the entropic regularizer by V (i.e. the uniform distribution over C') and the fact that w. E {0, 1) Pr.. Lemma 3.1. Let w C' + Rz0 be the probability measure corresponding to the minimizer ())(gl -1
W = arg min
> Logg(w'. q)
(6)
||/1==1,0220
SSS.
and let à C r R2o be the probability measure corresponding to the minimizer
(t)) arg min Dxz(al)((t)) [111-11)))0
log(w;()).cg
Then w W.
We can thus move on to proving regret guarantee for Algorithm 2. inequality together with standard results for FTRL once we show that the loss functions are vol(()))
This follows from Jensen's
Lipschitz over the constrained domain, yielding the following guarantee for Algorithm 2:
Theorem 3.2. Algorithm 2 has regret w.E.t. w E arg min wl Et= f((w) bounded by
T
1-7 DKL (w" (1 +
(vol(C.))² + log E
(8)
vol(C.)
11
E
B²g² Setting 72 = GB/VT and 122 TGT, where B = DKI(w*llo) and G2 = T ET (vol(
yields sublinear regret OC
Proof. Algorithm is standard FTRL with regularizer 1 (DKz(-lVV) which has the same Hessian
1) as the standard entropic regularizer over the simplex and is thus -sstrnngly-con Example 2.5]. Applying Jensen's 's inequality, the standard regret bound for FTRI. [43, Theorem 2.11] together with the Lipschitz guarantee of Claim B. and Jensen's 's inequality again yields the result:
w.r.t. || |l1 [43,
f((w)) - fe(w*)
fc(w.) - -1))((")) - 7F) + +(f((() - f((w"))
T
(w,, w*)
fe(w:) - f((// + (1 (1- >)w - y log
(wi, V)
1=1
1 DKL(TV + (1- +
+ log
1
722 t=1 (vol(C,))²
vol(Ca)
1=1
T Σ
<
? 1 1-7 DKL(W"llt)
72 (v)) + Σ log vol(C,)
"

---

Since the regret is sublinear in T, this result satisfies our requirement for attaining asymptotic improvement over single-task learning via Theorem 3.1. However, there are several aspects of this bound that warrant some discussion. The first is the rate of T which is less sublinear than the standard vTT and certainly the log I regret of exp-concave functions. However, the functions we face are (a) non-Lipschitz and (b) over domain that has dimensionality SQTT);; both violate conditions for good rates in online convex optimization [28, 43), making our problem much more difficult.
more salient aspect is the dependence on B² D (w" ). effectively the negative entropy of the optimal initialization. This quantity is in principle unbounded but is analogous to standard online convex optimization bounds that depend on the norm of the optimum, which in e.g. the Fuclidean case are also unbounded. In our case, if the optimal distribution is highly concentrated on very small subset of the space it will be difficult to compete with. Note that our setting of rj depends on knowing or guessing B; this is also standard but is certainly a target for future work to address. For example, past work on parameter-fiee free algorithms has solutions for optimization over the simplex [38]; however, it is unclear whether this is straightforward to do while preserving the property given by Lemma 3.1 allowing us to implicitly work with an unknown discretization. A more reasonable approach may be to compete only with smooth measures that only assign probability at most K vol D) to any subset D C C' for some constant A 2 1; in this case we will simply have B bounded by log K.
final issue the dependence on vG, which is bounded by the reciprocal of the smallest volume vol(C)), which in the dispersed case is roughly ((m this means that the task-averaged regret will have a term that, while decreasing as we see additional tasks, is increasing in the number of within-task iterations and the dispersion parameter, which is counter-intuitive It is also does so exponentially in the dimension. Note that in the common algorithm configuration setting of = 1/2 and d = 1 this will simply mean that for each task we suffer an extra or (1) loss at each within-task round, a quantity which vanishes asymptotically.
3.2 Meta-learning the step-size
In addition to learning the initialization, Theorem 3.1 requires learning the task-similarity to set the within- task step-size X > O. This involves optimizing functions of form (v) v fi fww))/e Since we know that the measures wy are lower-bounder in terms of y, we can apply a previous result [29]
that solves this by running the EWOO algorithm [28] on the modified sequence + f((w;)+e,
Corollary 3.1. For any E > 0, running the EWOO algorithm on the modified sequence v + [(w)+e? over the domain [E, / D2 log + = where D2
2 + E log vol(C,] attains regret
2 T
D 1 logg
D2 logy
} (1+ log(T + 1))
min
max
2
E2
on the original sequence he(v)= + f all v² > 0.
Setting IT gives a guarantee of form ((min(1/v" (T))))). Note this rate might be improvable by using the fact that u power-bounded due to the cyconstraint; however, we not focus on this since this component is not the dominant term in the regret. In fact, because of this we can adapt a related method that simply runs follow-the-leade (FTL) on the same modified sequence [29] without affecting the dominant terms in the regret:
Corollary 3.2. For any & > 0, running the FTL algorithm on the modified sequence v + fe(w)+e?
over the domain (s, / DD2 logg + 62,, where D2 2 1 Ei= log val(C.]. attains regret
DD2 1-2-lop 1og-oog) 1) 1 (1+ log(T (1+1og(T + +1)
min
+ 2 - log max
(10)
53
on the original sequence he(v) + fe(w)/u for all v* > O.
Setting 3 = 1/ gives a guarantee of form Ó((min(1/o", VT)) The alternatives are described in pseudocode at the bottom of Algorithm 3; while the guarantee of the FTL--based approach is worse, almost as simple to compute as the task similartyy and does not require integration, making it easier to implement.
7

---

Algorithm 3 Meta-learning the parameters of the exponential forecaster (Algorithm 1), Recall that pt)) refers the time-t discretization of the measure p + Rz0 (c.f. Section 3.1).
1: Input: domain C' C. IR dispersion B > 0, step-size 17 0, constraint parameter y [0, 1].
offset parameter > O, domain parameter D 0.
2: Initialize w1 to the uniform measure on C' and set X D+v
2/m
3: for task 1, ...,, T do
4: Run Algorithm with initialization wy and step-size A, and obtain task-t optimum P E C.
5: Set wi = 1B6n .m .m-a to be the function that is in the m -9 -ball round pł and 0 elsewhere.
6: Set Wi+1 to (t+1(t) = arg minl|//l (1,2x())))) DRL (xz(w(l(tt) - m..s log(w; (t), w).
7: if using EWOO then
exp a Lx tc2 Ense log(w (s). )) for 3 min
8:
Define (x(x)
Fzz
x
py +o 1 (pe(x)d
9: Set A441
vm f.v 1yD pi(2)do
10: else
Eest e² (s), tm
11: Set dc+1
3.3
Putting the two together
We now combine our methods for the initialization and step-size in Algorithm to meta-learn the parameters of the exponential forecaster. This yields a task-averaged regret bound via Theorem 3.1:
DwI(w" G² = + E (val(C.)] and D 2 Theorem 3.3. Define B² =
T 2t=1 log vol = O(3dlogm) Then Algorithm 3 with n, set as in Theorem 3.2 and E = I/VT (if using EWOO) or 1/ /T (otherwise) yields mask-averaged regret
VBG VVT
BG
δ
min
+ 2V +2V)
vm + g(m)
(11)
VT
As in past meta-leamiig work this achieves the goal of adapting to the task similaiill attaining asymptotic average regret of 2V /m + O(m=),, where we substitute for the dispersion term g and V is the task-similarity encoding the average probability mass assigned to different task balls by the optimal initialization. We include the minimum of two rates the bound: //V if the task sisiliiil a constant O (1) and 1/ V if it is extremely small. As discussed, this reflects the difficulty of our meta- veta-problem, in which
optimizing non-smooth functions over distributions; in contrast, past meta procedures take advantage of nice properties of Bregman divergences to obtain faster rates [29].
Meta-learning for data-driven algorithm design
We demonstrate the utility of our bounds in a series of applications across data-driven algorithm design and robust learning. This section focuses on the former and demonstrates how our results imply guarantees for meta-learning the tuning of solvers for difficult combinatorial problems. We also demonstrate the practical utility our approach for tuning clustering on real and synthetic datasets.
4.1 Instantiations for tuning combinatorial optimization algorithms
Algorithm configuration for combinatorial optimization algorithms involves learning algorithm pa- rameters from multiple instances combinatorial problems [27, 12, 4]. For well-known problems like MWIS (maximum weighted independent set), IQP (integer quadratic programming) and mecha- nism design for auctions, the algorithmic performance on fixed instance is typically a piecewise Lipschitz function of the algorithm parameters. Prior work has looked at learning these parameters the distributional setting (i.e. assuming iid draws of problem instances) [12] or the online setting where the problem instances may be adversarially drawn [11, 10). On the other hand, instantiating our results for these problems provide upper bounds for much more realistic settings where different tasks may be related and our bounds improve with this relatedness.
8

---

We demonstrate how to apply our results to combinatorial problems under mild smoothness assump- tions. The key idea is to show that if imputs come from a smooth distribution, the performance is dispersed (as sequence of functions in the algorithm parameters). We demonstrate this for the greedy algorithm for the knapsack problem and for initialization in k-center clustering. Similar results may be obtained for other problems, e.g. MWIS, IQP, and auction design (c.f. Appendix C).
Greedy Knapsack. Knapsack is well-known No-complete problem. We are given knapsack with capacity cap and items i E [m]] with sizes wi and values e, The goal is to select a subset S of items to add to the knapsack such that Lies W; S cap while maximizing the total value Eies 02 of selected items. The greedy heuristic add items in decreasing order of 0s/w; gives 2-approximation. We consider a generalization to use 0// uu. proposed by [27] for p E [0, 10]. For example, for the value -eight pairs {0..99, 1). (0.99, 1). (1.01, 1.01)} and capacity cap = 2 the classic heuristic p = gives value 1.01 but using p gives the optimal value 1.98. We can learn the optimal from similar tasks, and obtain the following formal guarantees (proof in Appendix C). Theorem 4.1. Consider instances of the knapsack problem given by bounded weights Wa.j E [1,C] and k- k-bounded independent values U1 E [0, 10 i E [m].] E [T]. Then the task-averaged regret for learning the parameter p p.ror the greedy heuristic family above is oT(1) + 2V V/mm + O( O(ym).
k--enter clustering. We consider the a-Llyod'ss algorithm family introduced in [15]. In the seeding phase, each point is sampled with probability x min.ec d(u, c)², where dl.,-) -) is the distance metric and C is the set of centers chosen so far. The family contains an algorithm for each a E [0, oo) U oc, and includes popular clustering heuristics like randomly initialized k-means (a = 0), k-means++ (a = 2) and farthest-firs traversal (ar = oo). Performance is measured using the Hamming distance to the best clustering and is piecewise constant function of a. Our result can be instantiated for this problem even without smoothness by leveraging the randomness of the clustering algorithm.
points, with Hamming loss 4,3 for é E j E [T] against some (unknown) ground truth. Then the task- averaged regret for learning the parameter a for the a-Lloyd's s algorithm family [15] is (1) + 2V /m + Olym).
Theorem 4.2. Consider instances of the k-center clustering problem
4.2 Experiments for greedy knapsack and k-center clustering
Next we demonstrate our meta-initialization algorithm empirically on knapsack and k-center cluster- ing, We design experiments on real and simulated data that show the usefulness of our techniques in learning sequence of piecewise-Lipschhe
functions. For knapsack, we generate a synthetic dataset of instances as follows. For each problem instance of each task, we have cap 100 and m 50. We have 10 'heavy' items with w; N227, 0.5) and 02 ~ A2277, 0.5), and 40 items with we ~ (11 + w., 0.5) and v2 ~ N18,, 0.5). where w, E [0, 2] is task daseddepen.
We also consider the a-Lloyddss algorithm family introduced in [15]. The performance of the algorithm is measured using the Hamming loss relative to the best clustering and is a piecewise constant function of We can compute the pieces for E [0, 10) by iteratively computing the subset of parameter values where a candidate point can be the next center. We use the small split of the Omniglot dataset [33], and create clustering tasks by drawing random samples consisting of five characters each, where four characters are constant throughout. We also create a Gaussian mixture binary classification dataset where each class is a 2D diagonal Gaussian distribution consisting of 100 points each with variance a and 20 and centers (0, 0) and (do, 0). We pick d E [2,3] to create different tasks.
We learn using 30 instances each of 10 training tasks and evaluate average loss over 5 test tasks. We use 100 trials to average over the randomization of the clustering algorithm and the exponential forecaster algorithm. We perform meta-initialization with parameters > = 1) = 0.01 (no hyperparameter search performed). The step-size is set to minimize the regret term in Theorem 2.1, and not meta-learned.
The relative improvement in task-averaged regret due to meta-learning in our formal guarantees depend on the task-similarity V and how it compares to the dispersion-relatted 0(m²-8) term, and can be significant when the latter is small. Our results in Table show that meta-learning an initialization, ie. a distribution over the algorithm parameter, for the exponential forecaster in this setting yields improved performance on each dataset. We observe this for both the one-shot and five-shot settings, Le. the number of within-taas iterations of the test task are one and five, respectively. The benefit of meta-learning is most pronounced for the Gaussian mixture (well-dispersed and similar tasks), and gains for Omniglot may increase with more tasks (dispersed but less similar tasks). For knapsack, the relative gains are smaller (similar tasks, but less dispersed). See Appendix D for further experiments.

---

Table I: Effect of meta-initialization few-shot learnnng of algorithmic parameters. Performance is as a fraction of the average value (Hamming accuracy, or knapsack value) of the offline optimum.
Dataset
Omniglor
Gaussian Mixture
Knapsack
One-shot
Five-shot
One-shot
Five-shot
One-shot
Five-shot
Single task
88.67 + 0.47%
95.02 + 0. 0.19%
90.10 1.10%
91.43 + 0.41%
81.74 + 0.29%
98 89.89 = 0.17% 99.12 + 0.15%
Meta-initialized
89.65 + 0.49%
96.05 0.15%
95.76 + 0.60%
96.39 + 0.27%
85.66 0.57%
5
Robust online meta-learning
In online learning, we aim to minimize a sequence of losses and want to perform well relative to the optimum in hindsight. It possible for the observed losses to be noisy on some inputs, either naturally or due an adversary. We explore the conditions under which robustness to adversarial influence (i.e. outlier injection) is possible, which is common in meta-learning with diverse sources.
Setup: At round i, we play 2₁, observe perturbed loss ū, X + [0, 1] which set by the adversary by modifying the true loss I + [0, 1] using an attack function a, : X + [0. 1] such that 1, + a, and may be non-Lipschitz, and suffer perturbed loss (2,) and true loss (x;). We seek to minimize regret relative to best fixed action in hindsight, i.e. Rm = -
1- (xx.) min >i=1 ((x)) for the perturbed loss and regret R. = Em= 4(x,) - minzex Ei=1 (xx for the true loss.
No regret can be achieved provided the adversary distribution is sufficiently smooth, i.e. satisfies 3-dispersion for some 3 >> 0, as this corresponds to online optimization of the perturbed loss function. We can show this for both perturbed and true loss. The perturbed loss guarantee is immediate from standard results on online learning of piecewise Lipschitz functions [11, 10]. For the true loss, we can achieve no regret if the adversary perturbation is limited to small balls and the centers of the balls are dispersed, which we capture using the following definition.
Definition 5.1 (é-bounded, 3.-dispersed attack). An attack function as is 8-bounded if there exists a ball () of radius ô such that ai(x) =0 called center Ca; for attack 0g. sequence of attack functions 01y...,0m is said be Ba- dispersed, if the positions of attack centers Fi are dispersed i.e. for all m and for all "2 m-.. E / (xEB((r)) {i [m] =ca, ca.ll I Ö(em).
-0 -fror each x E X x ABiza, o). va is
Theorem 5.1. Given sequence of 3-dispersed adversarially perturbed losses I, = 44 + ag where I, 1,, a, are piecewise L-Lipschitz functions X' + [0.1]for i = L...., m. and X C. Rd, the exponential forecaster algorithm has E[Rm] Ó(m + 1og(1/2) + (L + 1)m²~²) (with Z as in Theorem 2.1). If in addition we have that a, is a m m boundee,, Ba Ba-dispersed attack, then R[ =0mm) + [og(1/Z)
X + (L 1)m! 1)mm (min(())))
Together with Theorem 3.3, this implies regret meta- geta-learning in the presence of dispersed adver- saries, in particular the occurrence of unreliable data in small dispersed parts of the domain. We also show lower bound which establishes that our bounds are essentially optimal in the attack dispersion.
Theorem 5.2. There exist sequences of piecewise T.-Lipschitz functionn L, 4, 0g [0, 1] -> [0, for i 1, ..... m such that for any online algorithm
1. T is B-dispersed and E [mm] = 1(m1-9),
2. 4 is 8-dispersed, as is m -boundeed, Ba Ba-dispersed and E[Rm] = 4(m 1-1mmmmiffe (1..9.))))
6 Conclusion
In this paper we studied the initialization-bast meta-learning of piecewise-Lipseiee functions, demonstrating how online convex optimization over an adaptive discretization can find an initialization that improves the performance of the exponential forecaster across tasks, assuming the tasks have related optima. We then applied this result in two settings: online configuration of clustering algorithms and adversarial robustness in online learning. For the latter we introduced a dispersion- based understanding robustness that we believe to be of independent interest. In addition, there are further interesting applications of our work to other algorithm configuration problems.
10

---

Acknowledgments
This material is based on work supported by the National Science Foundation under grants CCF- 1535967, CCF-199033 IIS-1618714, IIS-1901403, SES-1919453, IIS-1705121, IIS-1838011 IIS-2046613 and IIS-211247I; the Defense Advanced Research Projects Agency under cooperative agreements HR001 12020003 and FA875017C0141; an AWS Machine Learning Research Award; an Amazon Research Award; a Bloomberg Research Grant; a Microsoft Research Faculty Fellowship; an Amazon Web Services Award: Facebook Faculty Research Award; funding from Booz Allen Hamilton Inc.; a Block Center Grant; and a Two Sigma Fellowship Award. Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies.
References
[1] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances, International Conference on Machine Learning, pages 111-119 PMLR, 2019.
[2] Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret bounds for lifelong learning. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
[3] Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pages 2938 2948. PMLR, 2020.
[4] Maria-Florina Balcan. Book chapter Data-Drives Algorithm Design, In Beyond Worst Case Analysis of Algorithms, Roughgarden (Ed). Cambridge University Press, 2020.
[5] Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang. On the power of abstention and data-driven decision making for adversarial robustness. arXiv preprint arXiv:2010.06154, 2020.
[6] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Proceedings of the 28th Annual Conference on Learning Theory, 2015.
[7] Maria-Floring Balcan, Travis Dick, and Manuel Lang. Learning to link. In International Conference on Leurning Representations, 2019.
[8] Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed setting. In Conference on Uncertainty in Artificial Intelligence, pages 909-918. PMLR, 2020.
[9] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pages 344-353. PMLR, 2018.
[10] Maria- Maria-Florina Balcan, Travis Dick, and Dravyansh Sharma. Learning piecewise Lipschitz functions in changing environments. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pages 3567-3577, 2020.
[11] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603-614, 2018.
[12] Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. -tteoretttt foundations of algorithm configuration for combinatorial partitioning problems. In Annual Conference on Learning Theory, pages 213-274, 2017.
[13] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 173-174, 2018.

---

[14] Maria-Florina Balcan and Dravyansh Sharma. Data driven algorithms for limited labeled data learning. arXiv preprint arXiv:2103.10547, 2021.
[15] Maria-Florina F Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized lloyd's families. Advances Neural Information Processing Systems, 31: 106411111 2018.
[16] Avrim Blum. Technical perspective: Algorithm selection learning problem. Communica- lions of the ACM, 63(6):86-66, 2020.
[17] Wieland Brendel, Jonas Rauber, Alexey Kurakin, Nicolas Papernot, Behar Veliqi, Sharada P Mohanty, Florian Laurent, Marcel Salathé, Matthias Bethge, Yaodong Yu, et al. Adversarial vision challenge. In The NeurlPS'18 18 Competition, pages 129-153. Springer, 2020.
[18] Fei Chen, Zhenhua Dong, Zhenguo Li, and Xiuqiang Hc. Federated meta-learning for recom- mendation. arXiv, 2018.
[19] Vincent Cohen-Addad and Varun Kanade. Online optimization of smoothed piecewise constant functions. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, 2017.
[20] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-leam stochastic gradient descent with biased regularization. In Proceedings of the 36th International Conference on Machine Learning, 2019.
[21] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Online-withnn-nline meta-learning. In Advances in Neural Information Processing Systems, 2019.
[22] Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably.
[23] Yan Duan, Marcin Andrychowicz, Bradly Stadie, Jonathan Ho, Jonas Schneider, llya Sutskever, Pieter Abbeel, and Wojeiech Zaremba. One-shot imitation learning. In Advances in Neural Information Processing Systems, 2017.
[24] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020.
[25] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, 2017.
[26] Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1 15-1145155 145, 1995.
[27] Rishi Gupta and Tim Roughgarden. PAC approach application-specifie algorithm selection. SIAM Journal on Computing, 46(3):992-1017, 2017.
[28] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69:169 19:169-192, 2007.
[29] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive paudient-based meta- learning methods. In Advances in Neural Information Processing Systems, 2019.
[30] Mikhail Khodak, Aarii-Florina Balcan, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning In Proceedings of the 36th International Conference on Machine Learning. 2019.
[31] Mikhail Khodak, Renbo Tu, Tian Li, Liam Li, Maria-Florina Balcan, Virginia Smith, and Ameet Talwalkar. Federated hyperparameter tuning: Challenges, baselines, and connections to weight-sharing, arXiv, 2021.
12

---

[32] Weihao Kong. Raghav Somani, Sham Kakade, and Sewoong Oh. Robust meta-learning for mixed linear regression with small batches, Advances in Neural Information Processing Systems,
33, 2020.
[33] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332-13333 2015.
[34] Jeffrey Li, Mikhail Khodak, Sebastian Caldas, and Ameet Talwalkar. Differentially private meta-learning. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[35] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(1):2853-288)) 2016.
[36] Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 427-436, 2015.
[37] Francesco Orabona, Nicolo Cesa-Bianchi, and Claudio Gentile. Beyond logarithmic bounds in online learning. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.
[38] Francesco Orabona and David Pal. Coin betting and parameter-free online learning. In Advances in Neural Information Processing Systems, 2016.
[39] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint arXiv:1912. 2019.
[40] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or fea- ture reuse? Towards understanding the effectiveness of MAML. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[41] Alon Resler and Yishay Mansour. Adversarial online learning with noise. In International Conference on Machine Learning, pages 5429-5437. PMLR, 2019.
[42] Nikunj Saunshi, Yi Zhang, Mikhail Khodak, and Sanjeev Arora. A sample complexity separation between non-convex and convex meta-lcarning. In Proceedings of the 37th International Conference Machine Learning. 2020.
[43] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2): 2011.
[44] Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385 2004.
[45] Sebastian Thrun and Lorien Pratt. Learning to Learn. Springer Science & Business Media, 1998.
[46] Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems. In European Symposium on Research in Computer Security, pages 480-501. Springer, 2020.
[47] Nilesh Tripuraneni, Chi Jin, and Michael I. Jordan. Provable meta-learning of linear representa- tions. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[48] Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using learning-to-lean approach. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[49] Yufan Zhou, Zhenyi Wang, Jiayi Xian, Changyou Chen, and Jinhui Xu. Meta-learning with neural tangent kernels. In Proceedings of the 9th International Conference on Learning Representations, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Alongside contributions in context, e.g. the end of Section 3.1.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our concern w.r.t. the negative societal impact of this theoretical work is limited to standard risks associated with MI., e.g. for privacy or fair treatment.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes] Supplemental
material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/]] Experiments run on personal computer (16GB, 2.3 GHz Dual-Core).
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "9IyEcKfXB3n", "reviewer": "Reviewer_dmBz", "summary": "The paper study the initialization-based meta-learning focus on the piecewise-Lipschitz functions whose discontinuities are dispersed. The authors designed an initialization method that implicitly run on online convex optimization procedure over an adaptive discretization to improve the performance of the exponential forecaster across multi-task. To demonstrate the usefulness of their proposed method, the authors instantiate the method in two settings: online configuration of clustering algorithms and adversarial robustness in online learning.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "A good initialization is critical to the success of a meta-learning method. The paper designed the meta-learning of the initialization and step-size of online learning algorithms for piecewise-Lipschitz functions in a multi-task environment. The method optimizes a sequence of data-dependent upper-bounds on the within-task regret. I consider this work interesting, However, I have some concerns too.\n1.\tTo demonstrate the effectiveness of the proposed new meta-initialization algorithm, the authors design experiments for clustering on the real Omniglot dataset and a simulated Gaussian mixture binary classification dataset. As the result showed in the Omniglot dataset, the meta-initialized method has little improvement over single task.. The authors should do more ablation experiments to demonstrate the effective of the proposed meta-initialization method.\n2.\tIn the original experiments, the authors chose the same hyperparameters of meta-initialization method at different experiment situations. The authors should try different hyperparameters to obtain best performance in various tasks.\n3.\tThe authors need to add more experiments to compare other initialization and step-size search methods. \n4.\tMore experiments and datasets are needed to further investigate the robustness and limitations of this approach.\n5.\tNote the addition of punctuation in some sentences！For example, In Line 44,48-49.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "72 hours"}, "extra_text": {}}, {"review_id": "57ISz9g7Xrr", "reviewer": "Reviewer_BRfJ", "summary": "The authors studied the initialization-based meta-learning of piecewise-Lipschitz functions, demonstrating how online convex optimization over an adaptive discretization can find an initialization that improves the performance of the exponential forecaster across tasks, assuming the tasks have related optima. They then applied this result in two settings: online configuration of clustering algorithms and adversarial robustness in online learning. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Many existing works of  meta-learning an initialization are largely restricted to the convex Lipschitz setting. This pape relaxes this assumption to study the meta-learning of online algorithms over piecewise-Lipschitz  functions, which can be nonconvex and highly discontinuous. This is the first theoretical study of meta-learning in these application settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think this paper is theoretically sound. One suggestion is to incorporate more experiments to demonstrate the efficiency of the proposed algorithms. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "2yp1O4ClGmF", "reviewer": "Reviewer_4fEk", "summary": "This paper proposed a meta-learning approach to learn piecewise-Lipschitz functions in the multi-task setting. Simply applying a traditional single-task exponential forecasting method multiple times cannot make the regret bound diminishes as the number of tasks $T$ increases. To tackle this issue, they first attempt to obtain a bound that involves the task similarity term, and then the authors propose two meta-learning algorithms, based on the observation that the regret bound depends on two things: learning rate and initialization probability choosing. Hence, they proposed two meta-learning algorithms, to efficiently learn to choose better initialization and learning rate. The theoretical results show that this algorithm can provably improve the baseline of applying a single-task algorithm $T$ times.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper proposes a novel meta-learning approach for online learning of piecewise-Lipschitz functions   in a multi-task environment. To my best knowledge, this paper is the first to generalize learning piecewise-Lipschitz functions problem to multi-task setting. It shows that the trivially applying single-task algorithm $T$ times will not make regret bound vanish, and then naturally introduce a quantity $V$ that captures the task similarity. Based on the bound, the proposal of two meta algorithms to learn to choose hyperparameters is also novel to me. The theoretical results look sound as far as I checked. The paper is well-organized and the motivations are very clear. I do not have much experience in this field but I learnt from this paper and enjoy reading it. Hyperparameter choosing is a longstanding difficulty in the machine learning community, and this paper sheds some light on this aspect, and the present paper has some merits. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I notice that in Line 214:  with positive volume $vol(C_t) > 0$ that is revealed after choosing $w_t$. I think $C_t$ is the ball center at optimum at $\\rho_t^*$, so does it mean we need some oracle knowledge to reveal $vol(C_t)$?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives an online algorithm for learning convex piecewise functions under certain assumptions regarding dispersion of the points of discontinuity. This follows recent work on algorithm meta-design and online learning.
Decision: Accept (Poster)