Learning-to-learn non-convex piecewise-Lipschitz functions
Year: 2021

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.

heading: 1 Introduction
text: While learning-to-learn or meta-learning has long been an object of study [45], in recent years it has gained significant attention as a multi-task paradigm for developing algorithms for learning in dynamic environments, from multiple data sources, and in federated settings. Such methods focus on using data from multiple tasks to improve performance when facing a new, potentially related task. A popular approach is initialization-based 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 a growing number of attempts to understand it, both empirically and theoretically [20, 29, 24, 40, 42]. However, outside some stylized setups our learning-theoretic understanding of how to meta-learn an initialization is largely restricted to the convex Lipschitz setting.
We relax both assumptions to study the meta-learning of online algorithms over piecewise-Lipschitz 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 piecewise-Lipschitz functions with dispersed discontinuities that do not concentrate in any small compact subset of the domain [11]. Such functions arise frequently in data-driven algorithm 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, a small change to the metric in cluster linkage can lead to a 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 a 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 (NeurIPS 2021).
In the single-task setting the problem of learning dispersed functions can be solved using simple methods such as the exponentially-weighted forecaster. To design an algorithm for learning to initialize online learners in this setting, we propose a method that optimizes a sequence of datadependent 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 follow-the-regularized leader (FTRL) scheme that is run over an 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.
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 as 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-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-Williamson algorithm, and mechanism design for combinatorial auctions. Then we consider experimentally the problem of tuning the right α for the α-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-procedure leads to improved clustering accuracy compared to single-task learning to cluster. We also study our results for a family of greedy algorithms for the knapsack problem introduced by [27] and obtain similar results for a 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 x ∈ X , which can result in potentially large changes to the corresponding loss value lh(x), where h ∈ 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 a small Lp-ball around x, such that f(x) = f(x′) but the true label of x′ does not match x, and therefore lf (x) 6= lf (x′). In general, under the adversarial influence, we observe a perturbed loss function l̃h(x) = lh(x) + ah(x). Typically we are interested in optimizing both the perturbed loss l̃h(x), i.e. measuring performance relative to optimum for adversarially perturbed losses, and the true loss lh(x) (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 are small, for piecewise-Lipschitz but dispersed adversaries.

heading: 2 Preliminaries and initialization-dependent learning of dispersed functions
text: In this section we introduce our setup and notation for online learning of piecewise-Lipschitz 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 a notion of task similarity and devising a meta-learning procedure.
Meta-learning setup Following past setups [2, 21, 29], for some T,m > 0 and all t ∈ [T ] and i ∈ [m] we consider a meta-learner faced with a sequence of Tm loss functions `t,i : C 7→ [0, 1] over a compact subset C ⊂ Rd that lies within a ball B(ρ,R) of radius R around some point ρ ∈ Rd.
Algorithm 1 Exponential Forecaster 1: Input: step size parameter λ ∈ (0, 1], initialization w : C → R≥0. 2: Initialize w1 = w 3: for i = 1, 2, . . . ,m do 4: Wi := ∫ C wi(ρ)dρ
5: Sample ρi with probability proportional to wi(ρi), i.e. with probability pi(ρi) = wi(ρi) Wi 6: Suffer `i(ρi) and observe `i(·) 7: For each ρ ∈ C, set wi+1(ρ) = e−λ`i(ρ)wi(ρ)
Here we used the notation [n] = {1, . . . , n}. Before each loss function `t,i the meta-learner must pick an element ρt,i ∈ C before then suffering a loss or cost `t,i(ρt,i). For a fixed t, the subsequence `t,1, . . . , `t,m defines a task for which we expect a single element ρ∗t ∈ C to do well, and thus we will use the within-task regret on task t to describe the quantity
Rt,m = m∑ i=1 `t,i(ρt,i)− `t,i(ρ∗t ) where ρ∗t ∈ arg min ρ∈C m∑ i=1 `t,i(ρ) (1)
In the single-task setting the goal is usually to show that Rt,m is sublinear in m, i.e. that the average loss decreases with more rounds. A 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 to using ρ∗t and use in both our algorithm and to define the task-similarity. Note that in the types of applications we are interested in—piecewise-Lipschitz functions—the complexity of computing optima scales with the number of discontinuities. In the important special case of piecewise-constant functions, this dependency becomes logarithmic [19]. Thus this assumption does not affect the usefulness of 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, we expect average performance across tasks to improve as we see more tasks; to phrase this mathematically we define the task-averaged regret
R̄T,m = 1
T T∑ t=1 Rt,m = 1 T T∑ t=1 m∑ i=1 `t,i(ρt,i)− `t,i(ρ∗t ) (2)
and claim improvement over single-task learning if in the limit of T →∞ it is smaller than Rt,m. Note that for simplicity in this work we 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.
Learning piecewise-Lipschitz functions We now turn to our target functions and within-task algorithms for learning them: piecewise-Lipschitz losses, i.e. functions that are L-Lipschitz w.r.t. the Euclidean 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 to 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 [11]; 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.
This literature has also shown lower bounds demonstrating that no-regret learning piecewise-Lipschitz function is impossible in general, necessitating assumptions about the sequence. One such condition is dispersion, which requires that the discontinuities are not too concentrated. Definition 2.1 ([11]). The sequence of random loss functions `1, . . . , `m is said to be β-dispersed with Lipschitz constant L if, for all m and for all ≥ m−β , we have that, in expectation over the randomness of the functions, at most Õ( m) functions (the soft-O notation suppresses dependence on quantities beside ,m and β, as well as logarithmic terms) are not L-Lipschitz for any pair of points at distance in the domain C. That is, for all m and for all ε ≥ m−β ,
E  max ρ,ρ′∈C ‖ρ−ρ′‖2≤ ‖ ∣∣{i ∈ [m] | `i(ρ)− `i(ρ′) > L‖ρ− ρ′‖2}∣∣  ≤ Õ( m) (3)
Assuming a sequence of m β-dispersed loss functions and initial distribution w1 set to the uniform distribution over C and optimize the step size parameter, the exponential forecaster presented in Algorithm 1 achieves sublinear regret Õ( √ dm log(Rm)+(L+1)m1−β). While this result achieves a 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 hyperparameter-dependent:
Theorem 2.1. Let `1, . . . , `m : C 7→ [0, 1] be any sequence of piecewise L-Lipschitz functions that are β-dispersed. Suppose C ⊂ Rd is contained in a ball of radius R. The exponentially weighted forecaster (Algorithm 1) has expected regret Rm ≤ mλ + log(1/Z)λ + Õ((L + 1)m 1−β), where
Z =
∫ B(ρ∗,m−β) w(ρ)dρ∫
C w(ρ)dρ
for ρ∗ the optimal action in hindsight.
The proof of this result adapts past analyses of Algorithm 1; 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 log(1/Z) term. Assuming w is a (normalized) distribution, this effectively measures the overlap between the chosen initialization and a small ball
around the optimum; we thus call − logZ = − log ∫ B(ρ∗,m−β) w(ρ)dρ∫
C w(ρ)dρ the negative log-overlap of initialization w(.) with the optimum ρ∗.
We also obtain an 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 Ω̃(m1−β) regret, which limits the improvement we can hope to achieve from task-similarity.
Theorem 2.2. There is a sequence of piecewise L-Lipschitz β-dispersed functions `i,j : [0, 1] 7→ [0, 1], whose optimal actions in hindsight arg minρ ∑m i=1 lt,i(ρ) are contained in some fixed ball of diameter D∗, for which any algorithm has expected regret Rm ≥ Ω̃(m1−β).

heading: 2.1 Task-similarity
text: 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 a 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
V 2 = − min w:C 7→R≥0, ∫ C w(ρ)dρ=1 1 T T∑ t=1 log ∫ B(ρ∗t ,m−β) w(ρ)dρ (4)
which can be much smaller if the task optima ρ∗t are close together; for example, if they are the same then V = 0, corresponding to assigning all the initial weight within the common ball B(ρ∗,m−β) around the shared optima. This is also true if vol(∩t∈TB(ρ∗t ,m−β)) > 0, as one can potentially initialize with all the weight in the intersection of the balls. On the other hand if vol(∩t∈TB(ρ∗t ,m−β)) = 0, V > 0. For example, if a p-fraction of tasks have optima ρ0 and the remaining at ρ1 with ||ρ0 − ρ1|| > 2m−β the task similarity is given by the binary entropy function V = Hb(p) = −p log p− (1− p) log(1− p). The settings of Algorithm 1 that achieve the minimum in the definition of V are directly related to V itself: the optimal initializer is the distribution achieving V and the optimal step-size is V/ √ m. Note that while the explicit definition requires computing a minimum over a set of functions, the task-similarity can be computed using the discretization constructed in Section 3.1.

heading: 3 An algorithm for meta-learning the initialization and step-size
text: 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 particular to improve upon the baseline of repeatedly running Algorithm 1 from the uniform distribution, up to oT (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.
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 so with sublinear regret in T , then we will improve upon the single-task guarantees up to oT (1) terms, as desired. Specifically, we are faced with a sequence of regret-upper-bounds Ut(w, v) = (v + ft(w)/v) √ m+ g(m) on nonnegative functions w over C and positive scalars v > 0. Note that g(m) cannot be improved via meta-learning, so we will focus on learning w and v. To do so, we run two online algorithms, one over the functions ft and the other over ht(v) = v + ft(wt)/v, where wt 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 ∈ [T ] consists of a sequence of m β-dispersed piecewise LLipschitz functions `t,i : C 7→ [0, 1]. Let ft and g be functions such that the regret of Algorithm 1 run with step-size λ = v √ m for v > 0 and initialization w : C 7→ R≥0 is bounded by Ut(w, v) =
(v + ft(w)/v) √ m + g(m). Suppose we have a procedure that achieves FT (w) regret w.r.t. any w : C 7→ R≥0 by playing actions wt : C 7→ R≥0 on ft and another procedure that achieves HT (v) regret w.r.t. any v > 0 by playing actions vt > 0 on ht(v) = v + ft(wt)/v, where HT is non-increasing on the positive reals. Then by setting ρt,i using Algorithm 1 with step-size vt/ √ m
and initialization wt at each task t, for w∗ = arg minw:C 7→R≥0 ∑T t=1 ft(w) the optimal initialization and V the task-similarity (4) we get task-averaged regret bounded by( HT (V )
T + min
{ FT (w ∗) V T , 2 √ FT (w∗)/T } + 2V )√ 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 a 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.

heading: 3.1 Meta-learning the initialization
text: The most technically challenging component of the procedure is learning the initialization. As discussed, this can be done via a no regret procedure for the sequence ft(w) = − log ∫ B(ρ∗t ,m
−β) w(ρ)dρ∫ C w(ρ)dρ
. This is nontrivial as the optimization domain is 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 ft associated with an unknown closed subset Ct ⊂ C—in particular Ct = B(ρ∗t ,m−β)— with positive volume vol(Ct) > 0 that is revealed after choosing wt : C 7→ R≥0 For each time t define the discretization Dt = {D = ⋂ s≤t C (c[s]) s : c ∈ {0, 1}t, vol(D) > 0} of C, where C (0) t = Ct and C (1) t = C\Ct. We will use elements of these discretizations to index nonnegative vectors in R|Dt|≥0 ; specifically, for any measure w : C 7→ R≥0 let w(t) ∈ R |Dt| ≥0 denote the vector with
entries w(t)[D] = ∫ D w(ρ)dρ for D ∈ Dt. Note that we will exclusively use p, q, v, w for measures, with v specifically referring to the uniform measure, i.e. v(t)[D] = vol(D). For convenience, for all real vectors x we will use x̂ to denote p/‖p‖1. 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: ft(w) = − log ∫ Ct w(ρ)dρ∫
C w(ρ)dρ , where Ct = B(ρ∗t ,m−β). Observe that we can equivalently write this as ft(w) = − log〈w∗t , ŵ〉, where w∗t[D] = 1D⊂Ct ; this translates our online learning problem from the domain of measures on C to the simplex on |DT | elements. However, we cannot play in this domain explicitly as we do not have access to the final discretization DT , nor do we get access to w∗t after task t, except implicitly via Ct. In this section we design a method that implicitly run an online convex optimization procedure over R|DT |≥0 while explicitly playing probability measures w : C 7→ R≥0.
Algorithm 2 Follow-the-Regularized-Leader (prescient form) 1: Input: discretization DT of C, mixture parameter γ ∈ [0, 1], step-size η > 0 2: Initialize w1 = v̂ 3: for t = 1, 2, . . . , T do 4: Play wt and suffer ft(wt) = − log〈w∗t ,wt〉. 5: Observe ft. 6: Update wt+1 = arg min‖w‖1=1,w≥γv̂DKL(w||v̂) + η ∑ s≤t fs(w)
As the functions ft are exp-concave, one might first consider applying a 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 poly(T ). We thus turn to the the follow-the-regularized-leader (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 DKL(·||v̂), where recall v is the vector of volumes of the discretization DT of C, and we constrain the played distribution to have measure at least γv̂[D] over every set D ∈ DT . While this requires knowing the discretization DT of C in advance, the following lemma shows that we can run the procedure knowing only the discretization Dt after task t by simply minimizing the same objective over distributions discretized on Dt. 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∗t ∈ {0, 1}|DT |. Lemma 3.1. Let w : C 7→ R≥0 be the probability measure corresponding to the minimizer
w = arg min ‖q‖1=1,q≥γv̂ DKL(q||v̂)− η ∑ s≤t log〈w∗s ,q〉 (6)
and let w̃ : C 7→ R≥0 be the probability measure corresponding to the minimizer w̃(t) = arg min
‖q‖1=1,q≥γv̂(t) DKL(q||v̂(t))− η ∑ s≤t log〈w∗s(t),q〉 (7)
Then w = w̃.
We can thus move on to proving a regret guarantee for Algorithm 2. This follows from Jensen’s inequality together with standard results for FTRL once we show that the loss functions are 1γ vol(Ct) - Lipschitz over the constrained domain, yielding the following guarantee for Algorithm 2:
Theorem 3.2. Algorithm 2 has regret w.r.t. w∗ ∈ arg min‖w‖1=1,w≥0 ∑T t=1 ft(w) bounded by
1− γ η DKL(w ∗||v̂) + η γ2 T∑ t=1
1
(vol(Ct))2 + γ T∑ t=1 log 1 vol(Ct) (8)
Setting γ2 = GB/ √ T and η2 = B 2γ2
TG2 , where B 2 = DKL(w ∗||v̂) and G2 = 1T ∑T t=1 1 (vol(Ct))2 ,
yields sublinear regret Õ( √ BGT 3 4 ).
Proof. Algorithm 2 is standard FTRL with regularizer 1ηDKL(·||v̂), which has the same Hessian as the standard entropic regularizer over the simplex and is thus 1η -strongly-convex w.r.t. ‖ · ‖1 [43, Example 2.5]. Applying Jensen’s inequality, the standard regret bound for FTRL [43, Theorem 2.11] together with the Lipschitz guarantee of Claim B.1, and Jensen’s inequality again yields the result: T∑ t=1 ft(wt)− ft(w∗) = T∑ t=1 ft(wt)− (1− γ)ft(w∗)− γft(v̂) + γ(ft(v̂)− ft(w∗))
≤ T∑ t=1 ft(wt)− ft(γv̂ + (1− γ)w∗) + γ log 〈w∗t ,w∗〉 〈w∗t , v̂〉
≤ 1 η DKL(γv̂ + (1− γ)w∗||v̂) + η γ2 T∑ t=1
1
(vol(Ct))2 + γ T∑ t=1 log 1 vol(Ct)
≤ 1− γ η DKL(w ∗||v̂) + η γ2 T∑ t=1
1
(vol(Ct))2 + γ T∑ t=1 log 1 vol(Ct)
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 3 4 , which is less sublinear than the
standard √ T and certainly the log T regret of exp-concave functions. However, the functions we face are (a) non-Lipschitz and (b) over a domain that has dimensionality Ω(T ); both violate conditions for good rates in online convex optimization [28, 43], making our problem much more difficult.
A more salient aspect is the dependence on B2 = DKL(w∗||v̂), 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 Euclidean case are also unbounded. In our case, if the optimal distribution is highly concentrated on a very small subset of the space it will be difficult to compete with. Note that our setting of η 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-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 κ vol(D) to any subset D ⊂ C for some constant κ ≥ 1; in this case we will simply have B bounded by log κ. A final issue is the dependence on √ G, which is bounded by the reciprocal of the smallest volume vol(Ct), which in the dispersed case is roughly O(mβd); 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 oT (1) loss at each within-task round, a quantity which vanishes asymptotically.

heading: 3.2 Meta-learning the step-size
text: In addition to learning the initialization, Theorem 3.1 requires learning the task-similarity to set the within-task step-size λ > 0. This involves optimizing functions of form ht(v) = v+ft(wt)/v. Since we know that the measures wt are lower-bounded in terms of γ, we can apply a previous result [29] that solves this by running the EWOO algorithm [28] on the modified sequence v + ft(wt)+ε 2
v :
Corollary 3.1. For any ε > 0, running the EWOO algorithm on the modified sequence v+ ft(w)+ε 2
v over the domain [ε, √ D2 − log γ + ε2], where D2 ≥ 1T ∑T t=1 log 1 vol(Ct) , attains regret
min
{ ε2
v∗ , ε
} T + √ D2 − log γ
2 max
{ D2 − log γ
ε2 , 1
} (1 + log(T + 1)) (9)
on the original sequence ht(v) = v + ft(w)/v for all v∗ > 0. Setting ε = 1/ 4 √ T gives a guarantee of form Õ((min{1/v∗, 4 √ T}) √ T ). Note this rate might be improvable by using the fact that v is lower-bounded due to the γ-constraint; however, we do 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-leader (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 + ft(w)+ε 2
v over the domain [ε, √ D2 − log γ + ε2], where D2 ≥ 1T ∑T t=1 log 1 vol(Ct) , attains regret
min
{ ε2
v∗ , ε
} T + 2 √ D2 − log γmax { (D2 − log γ) 32
ε3 , 1
} (1 + log(T + 1)) (10)
on the original sequence ht(v) = v + ft(w)/v for all v∗ > 0. Setting ε = 1/ 5 √ T gives a guarantee of form Õ((min{1/v∗, 5 √ T})T 35 ). The alternatives are described in pseudocode at the bottom of Algorithm 3; while the guarantee of the FTL-based approach is worse, it is almost as simple to compute as the task-similarity and does not require integration, making it easier to implement.
Algorithm 3 Meta-learning the parameters of the exponential forecaster (Algorithm 1). Recall that p(t) refers to the time-t discretization of the measure p : C 7→ R≥0 (c.f. Section 3.1).
1: Input: domain C ⊂ Rd, dispersion β > 0, step-size η > 0, constraint parameter γ ∈ [0, 1], offset parameter ε > 0, domain parameter D > 0. 2: Initialize w1 to the uniform measure on C and set λ1 = ε+ √ D2+ε2−log γ 2 √ m
. 3: for task t = 1, 2, . . . , T do 4: Run Algorithm 1 with initialization wt and step-size λt and obtain task-t optimum ρ∗t ∈ C. 5: Set w∗t = 1B(ρ∗t ,m−β) to be the function that is 1 in the m
−β-ball round ρ∗t and 0 elsewhere. 6: Set wt+1 to wt+1(t) = arg min‖w‖1=1,w≥γv̂(t)DKL(w||v̂(t))− η ∑ s≤t log〈w∗s(t),w〉. 7: if using EWOO then
8: Define µt(x) = exp ( −α ( tx+ tε2− ∑ s≤t log〈w ∗ s (s),ws(s)〉
x
)) for α = 2D min { ε2 D2 , 1 } .
9: Set λt+1 = ∫√D2+ε2−log γ ε
xµt(x)dx √ m ∫√D2+ε2−log γ ε µt(x)dx .
10: else 11: Set λt+1 =
√∑ s≤t ε
2−log〈w∗s (s),ws(s)〉 tm .

heading: 3.3 Putting the two together
text: We now combine our methods for the initialization and step-size in Algorithm 3 to meta-learn the parameters of the exponential forecaster. This yields a task-averaged regret bound via Theorem 3.1:
Theorem 3.3. Define B2 = DKL(w∗||v̂), G2 = 1T ∑T t=1 1 (vol(Ct))2
, and D2 ≥ 1 T ∑T t=1 log 1 vol(Ct) = O(βd logm). Then Algorithm 3 with η, γ set as in Theorem 3.2 and
ε = 1/ 4 √ T (if using EWOO) or 1/ 5 √ T (otherwise) yields task-averaged regret
Õ ( min {√ BG
V 4 √ T , 4 √ BG 8 √ T
} + 2V ) √ m+ g(m) (11)
As in past meta-learning work this achieves the goal of adapting to the task-similarity, attaining asymptotic average regret of 2V √ m+O(m−β), where we substitute for the dispersion term g and V 2 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 in the bound: 1/ 4 √ T if the task-similarity is a constant ΘT (1) and 1/ 8 √ T if it is extremely small. As discussed, this reflects the difficulty of our meta-problem, in which we are optimizing non-smooth functions over distributions; in contrast, past meta procedures take advantage of nice properties of Bregman divergences to obtain faster rates [29].

heading: 4 Meta-learning for data-driven algorithm design
text: 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 of our approach for tuning clustering on real and synthetic datasets.

heading: 4.1 Instantiations for tuning combinatorial optimization algorithms
text: Algorithm configuration for combinatorial optimization algorithms involves learning algorithm parameters from multiple instances of combinatorial problems [27, 12, 4]. For well-known problems like MWIS (maximum weighted independent set), IQP (integer quadratic programming) and mechanism design for auctions, the algorithmic performance on a fixed instance is typically a piecewise Lipschitz function of the algorithm parameters. Prior work has looked at learning these parameters in 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.
We demonstrate how to apply our results to combinatorial problems under mild smoothness assumptions. The key idea is to show that if inputs come from a smooth distribution, the performance is dispersed (as a 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 a well-known NP-complete problem. We are given a knapsack with capacity cap and items i ∈ [m] with sizes wi and values vi. The goal is to select a subset S of items to add to the knapsack such that ∑ i∈S wi ≤ cap while maximizing the total value∑
i∈S vi of selected items. The greedy heuristic to add items in decreasing order of vi/wi gives a 2-approximation. We consider a generalization to use vi/w ρ i proposed by [27] for ρ ∈ [0, 10]. For example, for the value-weight pairs {(0.99, 1), (0.99, 1), (1.01, 1.01)} and capacity cap = 2 the classic heuristic ρ = 1 gives value 1.01 but using ρ = 3 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 wi,j ∈ [1, C] and κ-bounded independent values vi,j ∈ [0, 1] for i ∈ [m], j ∈ [T ]. Then the task-averaged regret for learning the parameter ρ for the greedy heuristic family above is oT (1) + 2V √ m+O( √ m).
k-center clustering. We consider the α-Llyod’s algorithm family introduced in [15]. In the seeding phase, each point x is sampled with probability∝ minc∈C d(v, c)α, where d(·, ·) is the distance metric and C is the set of centers chosen so far. The family contains an algorithm for each α ∈ [0,∞) ∪∞, and includes popular clustering heuristics like randomly initialized k-means (α = 0), k-means++ (α = 2) and farthest-first traversal (α =∞). Performance is measured using the Hamming distance to the best clustering and is a piecewise constant function of α. Our result can be instantiated for this problem even without smoothness by leveraging the randomness of the clustering algorithm. Theorem 4.2. Consider instances of the k-center clustering problem on n points, with Hamming loss li,j for i ∈ [m], j ∈ [T ] against some (unknown) ground truth. Then the task-averaged regret for learning the parameter α for the α-Lloyd’s algorithm family [15] is oT (1) + 2V √ m+O( √ m).
4.2 Experiments for greedy knapsack and k-center clustering
Next we demonstrate our meta-initialization algorithm empirically on knapsack and k-center clustering. We design experiments on real and simulated data that show the usefulness of our techniques in learning a sequence of piecewise-Lipschitz 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 wi ∼ N (27, 0.5) and vi ∼ N (27, 0.5), and 40 items with wi ∼ N (19 + wt, 0.5) and vi ∼ N (18, 0.5), where wt ∈ [0, 2] is task-dependent. We also consider the α-Lloyd’s 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 α ∈ [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 σ and 2σ and centers (0, 0) and (dσ, 0). We pick d ∈ [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 γ = η = 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-relatedO(m1−β) term, and can be significant when the latter is small. Our results in Table 1 show that meta-learning an initialization, i.e. 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, i.e. the number of within-task 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.

heading: 5 Robust online meta-learning
text: In online learning, we aim to minimize a sequence of losses and want to perform well relative to the optimum in hindsight. It is possible for the observed losses to be noisy on some inputs, either naturally or due to 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 xi, observe perturbed loss l̃i : X → [0, 1] which is set by the adversary by modifying the true loss li : X → [0, 1] using an attack function ai : X → [0, 1] such that l̃i = li + ai and may be non-Lipschitz, and suffer perturbed loss l̃i(xi) and true loss li(xi). We seek to minimize regret relative to best fixed action in hindsight, i.e. R̃m = ∑m i=1 l̃i(xi)−minx∈X ∑m i=1 l̃i(x) for the
perturbed loss and regret Rm = ∑m i=1 li(xi)−minx∈X ∑m i=1 li(x) for the true loss.
No regret can be achieved provided the adversary distribution is sufficiently smooth, i.e. satisfies β-dispersion for some β > 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 ai is limited to small balls and the centers of the balls are dispersed, which we capture using the following definition. Definition 5.1 (δ-bounded, βa-dispersed attack). An attack function ai is δ-bounded if there exists a ball B(xa, δ) of radius δ such that ai(x) = 0 for each x ∈ X \ B(xa, δ). xa is called a center cai for attack ai. A sequence of attack functions a1, . . . , am is said to be βadispersed, if the positions of attack centers xa are dispersed i.e. for all m and for all ≥ m−βa , E [ maxx,x′∈X ,x∈B(x′, )
∣∣{i ∈ [m] | x = cai}∣∣] ≤ Õ( m). Theorem 5.1. Given a sequence of β-dispersed adversarially perturbed losses l̃i = li + ai, where l̃i, li, ai are piecewise L-Lipschitz functions X → [0, 1] for i = 1, . . . ,m and X ⊂ Rd, the exponential forecaster algorithm has E[R̃m] = Õ(mλ + log(1/Z)λ + (L + 1)m
1−β) (with Z as in Theorem 2.1). If in addition we have that ai is a m−βa-bounded, βa-dispersed attack, then E[Rm] = Õ(mλ+ log(1/Z)λ + (L+ 1)m 1−min{β,βa}).
Together with Theorem 3.3, this implies no regret meta-learning in the presence of dispersed adversaries, in particular the occurrence of unreliable data in small dispersed parts of the domain. We also show a lower bound which establishes that our bounds are essentially optimal in the attack dispersion.
Theorem 5.2. There exist sequences of piecewise L-Lipschitz functions l̃i, li, ai [0, 1]→ [0, 1] for i = 1, . . . ,m such that for any online algorithm
1. l̃i is β-dispersed and E[R̃m] = Ω(m1−β),
2. l̃i is β-dispersed, ai is m−β-bounded, βa-dispersed and E[Rm] = Ω(m1−min{β,βa}).

heading: 6 Conclusion
text: In this paper we 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. 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 dispersionbased understanding of robustness that we believe to be of independent interest. In addition, there are further interesting applications of our work to other algorithm configuration problems.

heading: Acknowledgments
text: This material is based on work supported by the National Science Foundation under grants CCF1535967, CCF-1910321, IIS-1618714, IIS-1901403, SES-1919453, IIS-1705121, IIS-1838017, IIS-2046613 and IIS-2112471; the Defense Advanced Research Projects Agency under cooperative agreements HR00112020003 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; a 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 or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies.

Review summaries:
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. 

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.