Generalization Properties of Retrieval-based Models
Authors: Soumya Basu
Ankit Singh Rawat
Manzil Zaheer
Venue: Submitted to ICLR 2023 (2023)
Keywords: Generalization bounds
retrieval-based models
local empirical risk minimization
semiparametric models
nonparametric models
kernel methods

Abstract: Many modern high-performing machine learning models such as GPT-3 primarily rely on scaling up models, e.g., transformer networks. Simultaneously, a parallel line of work aims to improve the model performance by augmenting an input instance with other (labeled) instances during inference. Examples of such augmentations include task-specific prompts and similar examples retrieved from the training data by a nonparametric component. Remarkably, retrieval-based methods have enjoyed success on a wide range of problems, ranging from standard natural language processing and vision tasks to protein folding, as demonstrated by many recent efforts, including WebGPT and AlphaFold. Despite growing literature showcasing the promise of these models, the theoretical underpinning for such models remains underexplored. In this paper, we present a formal treatment of retrieval-based models to characterize their generalization ability. In particular, we focus on two classes of retrieval-based classification approaches: First, we analyze a local learning framework that employs an explicit local empirical risk minimization based on retrieved examples for each input instance. Interestingly, we show that breaking down the underlying learning task into local sub-tasks enables the model to employ a low complexity parametric component to ensure good overall accuracy. The second class of retrieval-based approaches we explore learns a global model using kernel methods to directly map an input instance and retrieved examples to a prediction, without explicitly solving a local learning task.

Under review as a conference paper at ICLR 2023
GENERALIZATION PROPERTIES OF RETRIEVAL-BASED MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Many modern high-performing machine learning models such as GPT-3 primarily rely scaling up models, e.g., transformer networks. Simultaneously, parallel line work aims to improve the model performance by augmenting an input instance with other (labeled) instances during inference. Examples of such aug- mentations include task-specific prompts and similar examples retrieved from the training data by nonparametric component. Remarkably, retrieval- based methods have enjoyed success on a wide range of problems, ranging from standard natu- ral language processing and vision tasks to protein folding, as demonstrated by many recent efforts, including WebGPT and AlphaFold. Despite growing literature showcasing the promise of these models, the theoretical underpinning for such models remains underexplored. In this paper, present formal treatment of retrieval-base models to characterize their generalization ability. In particular, we focus two classes of retrieval-based classification approaches: First, we analyze a local learning framework that employs an explicit local empirical risk minimization based on retrieved examples for each input instance. Interestingly, we show that breaking down the underlying learning task into local sub-tasks enables the model to employ a low complexity parametric component to ensure good overall accuracy. The second class of retrieval-based approaches we explore learns a global model using kernel methods to directly map an input instance and retrieved examples to a prediction, without explicitly solving local learning task.
INTRODUCTION
As our world is complex, we need expressive machine learning models to make high accuracy predictions on real world problems. There are multiple ways to increase expressiveness a machine learning model. A popular way is to homogeneously scale the size of parametric model, such as neural networks, which has been behind many recent high-pperfomancce models such as GPT-3 (Brown et al., 2020) and ViT (Dosovitskiy et al., 2021). Their performance (accuracy) exhibits monotonic behavior with increasing model size, as demonstrated by "scaling laws" (Kaplan et al., 2020). Such large models, however, have their own limitations, including high computation cost, catastrophic forgeting (hard to adapt to changing data), lack of provenance, and explanability. Classical instance- based models Fix & Hodges (1989), the other hand, offer many desirable properties by design efficient data structures, incremental learning (casy addition and deletion of knowledge), and some provenance for its prediction based on the nearest neighbors w.r.t. the input. However, these models often suffer from weaker empirical performance as compared to deep parametric models.
Increasingly, middle ground combining the two paradigms and retaining the best of both worlds is becoming popular across various domains. ranging from natural language (Das et al., 2021; Wang et al., 2022; Liu al., 2022; Izacard al., 2022), vision (Liu al., 2015: 2019; Iscen et al., 2022; Long et al., 2022), to reinforcement learning (Blundell et al., 2016; Pritzel et al., 2017; Ritter et al., 2020). to even protein structure predictions (Cramer, 2021) In such approaches, given test input, one first retrieves relevant entries from data index and then processes the retrieved entries along with the test input to make the final predictions using a machine learning model. This process is visualized in Figure 1b. For example, in semantic parsing, models that augment parametric seq2seq model with similar examples have not only outperformed much larger models but also are more robust changes in data (Das et al., 2021).
While classical learning setups (cf. Figure la) have been studied extensively over decades, even basic properties and trade-off's pertaining retrieval-based models (ef. Figure 1b), despite their

---

Under review as a conference paper at ICLR 2023
fot-]
Ex
Parametric
Traininng
Teanting dita
Dx
data
Dx
Day
Isail - Day
Vicko
Nonparametric
(a) Classical learning setups
(b) Modern retrieval-basee setup
Figure 1: An illustration of retrieval-basee classification model. Given an input instance similar to an instance- custance-based model, it retrieves similar (labeled) examples R {(='s, 1/)} from training data. Subsequently, it processes (potentially via nonparametrie method) input instance along with the retrieved examples to make the final prediction ý = fxx ).).
aforementioned remarkable successes, remain highly under-explored. Most of the existing efforts on retrieval-based machine learning models solely focus on developing end-to-end domain- domain-speciffe models, without identifying the key dataset properties structures that are critical in realizing performance gains by such models. Furthermore, at first glance, due to the highly dependent nature of an input and the associated retrieved set, direct application of existing statistical learning techniques does not appear as straightforward. This prompts the natural question: What should be the right theoretical framework that can help rigorously showcase the value of the retrieved set in ensuring superior performance of modern retrieval- -bsedd models?
In this paper, we take the first step towards answering this question, while focusing the classification setting (Sec. 2.1). We begin with the hypothesis that the model might be using the retrieved set to do local learning implicitly and then adapt its predictions the neighborhood of the test point. This idea is inspired from Bottou& & Vapnik (1992). Such local learning is potentially beneficial in cases where the underlying task has local structure, where a much simpler function class suffices to explain the data in given local neighborhood but overall the data can be complex (formally defined in Sec. 2.2). For instance looking a few answers at Stackoverflow even if not for same problem may help us solve our issue much faster than understanding the whole system. We try to formally show this effect.
We begin by analyzing an explicit local learning algorithm: For each test input, (1) we retrieve a few training examples located in the vicinity of the test input, (2) train local model by performing empirical risk minimization (FRM) with only these retrieved examples - local ERM; and (3) apply the resulting local model to make prediction on the test input. For the aforementioned retrieval-based local ERM, we derive finite sample generalization bounds that highlight a trade-off between the complexity of the underlying function class and size of neighborhood where local structure of the data distribution holds in Sec. 3. Under this assumption of local regularity, we show that by using achieve similar loss/error that of complex global model (Thm. 3.4). Thus, we show that breaking down the underlying learning task into local sub-tasks enables the model to employ a low complexity parametric component to ensure good overall accuracy. Note that the local ERM setup is reminiscent of semiparametric polynomial regression (Fan & Gijbels, 2018) in statistics, which is special case of our setup. However, the semiparametric polynomial regression have been only analyzed asymptotically under mean squared error loss (Ruppert & Wand, 1994) and its treatment under more general loss unexplored.
much simpler function class for the local model,
We acknowledge that such local learning cannot be the complete picture behind the effectiveness of retreeval-based models. As noted in Zakai & Ritov (2008), there always exists model with global component that is more "preferable" to local-only model. In Sec. 3.2, we extend local ERM to a two-stage setup: First learn a global representation using entire dateset, and then utilize the representation at the test time while solving the local ERM previously defined. This enables the local learning to benefit from good quality global representations, especially in sparse data regions.
Finally, move beyond explicit local learning a setting that resembles more closely the empirically successful systems such as REINA, WebGPT, and AlphaFold: A model that directly learns to predict from the input instance and associated retrieved similar examples end-to-end. Towards this, take preliminary step in Sec. by studying a novel formulation of classification over an extended feature space (to account for the retrieved examples) by using kernel methods (Deshmukh al., 2019).
2

---

Under review as a conference paper at ICLR 2023
To summarize, main contributions include: 1) Setting up formal framework for classification under local regularity; 2) Finite sample analysis of explicit local learning framework; 3) Extending the analysis to incorporate globally learnt model; and 4) Providing the first rigorous treatment of an end-to-end retrieval-based models to understand its generalization by using kernel-based learning.
2 PROBLEM SETUP
We first provide brief background on (multiclass) classification along with necessary notations. Subsequently, we discuss the problem setup considered in this paper, which deals with designing retrieval-based classification models for the data distributions with local regularity.
2.1 MULTICLASS CLASSIFICATION
In this work, we restrict ourselves to (multi-class) classification setting, with access to n training examples 8 [x, y/1) be)n] C y, sampled i.i.d. from the data distribution D := Dx,y. Given 8, one is interested in learning classifier h X - y that minimizes miss-classification error. It is common to define a classifier via scorer f : + (fi(z).... fly (z)) E RM that assigns score each class in y for an instance z. For a scorer f. the corresponding classifier takes the form: (x))) arg max (I).. Furthermore, we define the margin of f at a given label E y as
75(2, v) [z) maxy #y for (x)).
Let (D(A) == ExxY)-D [4) for any random variable A. Given and set of scorers I S {ff X - ) learning a model implies finding a scorer in F that minimizes miss-classification error:
arg min (X) * Y).
One typically employs surrogate loss (Bartlett et al., 2006) E for the miss-classiffcation loss 1 (X) and aims minimize the associated risk:
R₂(f) [xxx))-
Since the underlying data distribution D is only accessible via examples in 8, one learns good scorer by minimizing the (global) empirical risk over a large function class gzlohal as follows:
f = arg segeloon Re(f)= = E {f(()))
(4)
2.2 DATA DISTRIBUTIONS WITH LOCAL REGULARITY
In this work, we assume that the underlying data distribution D follows local-regularity structure, where much simpler (parametric) function class suffices to explain the data in each local neighbor- hood. Formally, for X and > O, define B {z' X d(æ, 2²) I r), r-radius ball around x, w.r.t. a metric d X x X + IR. Let D be the data distribution restricted to Bay, i.c.
D (A) D(A)DD 4) AC y
Now, the local regularity condition of the data distribution ensures that, for each E X, there exists low-complexity function class Tet with | < [Fglobal], that approximates the Bayes optimal (w.r.t grglabal) for the local classification problem defined by D That is, for a given Ex > 0, we have"
minser= [()( Y)] S minferratotal ED (((((), Y)] + Ex, V X.
(6)
As example, if grglobal is linear in Rd (possibly dense) with bounded norm т, then 3r can be simpler function class such as linear in Rdd with sparsity lo & d and with bounded norm T₂ I T.
2.3 RETRIEVAL- CLASSIFICATION MODEL
This work focuses on retrieval-based methods that can leverage the aforementioned local regularity structure of the data distribution. In particular, we focus on two such approaches:
As stated, we require the local-regularity condition to hold for each z. This can be relaxed to hold with high probability with increased complexity of exposition.
3

---

Under review as a conference paper at ICLR 2023
Local empirical risk minimization. Given (test) instance 2, the local empirical risk minimization
(ERM) approach first retrieves a neighboring set R" = (22g. _ 8. Subsequently, it identifies a
(local) scorer frr from 'simple' function class gloc C [
:X
B as follows:
1
f arg min fegrise (f):: (E
[ (ar WERR ((f(z),
Here, Rx corresponds to the samples in S that belong to T hence, it follows the distribution D We assume there exists (r, 8) such that for any 0, and à > 0,
P(XY) [| < (r, S 6, and (XxXY)) [|=>||1111110
=.
(8)
Note that the local ERM approach requires solving local learning task for each test instance. Such a local learning algorithms was introduced in Bottou & Vapnik (1992). Another point worth mentioning here is that (7) employs the same function class gloe for each whereas the local regularity assumption (cf. (6)) allows for an instance dependent function class F We consider gloe that approximates F closely. In particular,
assume that, for some Eloe 0, we have
gegive E)=--((f((X), Y)]= S minseg* Epr.-le(f(X) Y)] + Eloc. V E X.
(9)
Continuing with the example following (6), where 9" linear with sparsity < and bounded norm Tz, one can take gloe to be linear with the same sparsity & and bounded norm 7' < supzex Tz-
Classification with extended feature space. Another approach to leverage the retrieved neighboring
labeled instances during classification is to directly learn scorer that maps x R E X x (X x y)* to per-class scores. One can learn such a scorer over extended feature space x (X x y)* as follows:
- ((( R*.), 91);
jex arg min min JEFeA R (f);
()) = 71
(10)
where geex C (s x (Xx x 4 - RRII} denotes function class over the extended space. Unlike local ERM approach, (10) learns a common function over extended space and does not require solving an optimization problem for each test instance. That said, since Fex operates the extended feature space, it can be significantly complex and computationally expensive to employ as compared to Floe.
Our goal is to develop theoretical understanding of the generalization behavior of these two retrieval- based methods for classification with locally regular data distributions. We present our theoretical treatment of local ERM and classification with extended feature space in Sec. 3 and 4, respectively.
3 LOCAL EMPIRICAL RISK MINIMIZATION
Before presenting an excess risk bound for the local ERM method, we introduce various necessary definitions and assumptions that play critical role in our analysis. We say that a scorer f is L-coordinate Lipschitz iff for all y E y and æ1, X2 E X, we have (z) - fy()) - -|Ix-z'l1
In this section, we restrict ourselves to the loss functions that act on the margin of a scorer (ef. (I)) ie., for any given example (z, y) and any scorer f. we have {(f(x). y)) = Elyy (z, y)). In addition, we assume that, naturally, e is a decreasing function of the margin. Furthermore, assume that l is Le-Lipschitz function, i.e., (((7) - {(>') & Lely - 7/1, Vy 2 2//
Note that the local ERM selects scorer from gloe, At E X, let fa.- denote the minimizer of the population version of the local loss, and f the population risk minimizer for the global loss, i.e.,
- arg min E(x, [e(s(X')) and f" arg min B(X.Y)= [(((x))))) (11)
fegloe
f
Given a distribution D, we define the weak margin condition (Döring et al., 2018) for scorer f as: Definition 3.1. A scorer f satisfies (a, w)- margin condition iff. for all t 2 0. ((xx))-D((sxXX Y)I 1) S etº.
One of the key assumptions that we rely on is the existence of an underlying scorer ftrue that explains the true labels, while ensuring the weak margin condition (cf. Definition 3. Here, we note that the true function frrue may neither lie in the function class gglobal nor in gloc
Assumption 3.2 (True scorer function). There exists scorer frrue such that for all, (z, v) E X frrue generates the true label, i.e., Tyuue (z. y) >> 0 and |R In (X, Furthermore, we assume pirue is chordicoor Lipschisz, and satisfies the (Derre, Ctrue) margin condition.
4

---

Under review as a conference paper at ICLR 2023
3.1 EXCESS RISK BOUND FOR LOCAL ERM
Now that we have introduced the required background and assumptions, we move to presenting our results on characterizing the generalization behavior of local ERM. In particular, we aim bound
(12)
Note that in the above equation fx (ef. (7)) is a function of Rxx and expectation over Rx is taken implicitly. Towards this, we first obtain the following upper bound on (12).
Lemma 3.3. The expected excess risk of the local ERM optimization fx is bounded
B Bix,yy-
$ BIXYY B YY)DD. (()xx((X))))))))))))()())))))))) -(7
Loval Glosbet Optivnal Risk
E (ecisxx-((((( ((T()))))))))))))) -((()),)) -
sup JEl
JC (Jrlobbbl
Global Locat! Sample
sup
E Dxx: ((F(('))
Σ {((()))))
SEsfle
(s' (e)
Cenemiiggaionn Lovel KRM
(x.. (X'),
E e(Fx>(ad))>)))
(o' (x'x0))2x
Morrett of
We delegate the proof of Lem. 3.3 to Appendix B. Now, as a strategy to obtain desired excess risk bounds, we separately bound the four terms appearing in Lem. 3.3. Note that the first term captures the expected difference between the loss incurred by global population optima f E Frslobll and the local population optima f E gloc a local region around test instance x. The second term aims to capture the loss for scorer evaluated at the expected value of the loss for the scorer at random instance sampled in the local region of x based on D The third term corresponds to the standard "generalization error' for the local ERM with respect the local data distribution D..,,, whereas the fourth term is the empirical variation of the true local function f. around its true mean under D.X.r,
Let the boodiintte-Lisschie constants for scorers in Floc and grglobal be Lioe and Lgiobal, respectively, We define function class 9(X, Y) {(x', ,/) - ((rr(:))) ((Tx(X, Y)) ʃ E Floo). Here, by subtracting { (x(X). Y) from the loss, we center the losses on R for any function f E gloo, and obtain tighter bound by utilizing the local nature of the distribution X.r, For any L > for notational convenience let us define
M, (L; E, ftrue, F) = 2 Lr + (max{Lr; Lr, a1 - Lr) Ear)crrel (2Irrue?) Orenc
(13)
Now, by controlling different terms appearing in the bound in Lem. 3.3, we obtain the following. Theorem 3.4. For any d > 0, the expected excess risk of the local ERM solution fx is bounded
E [(XYY~ [((x((), (x).
S (Ex + Eloc)
+ (Mtocot &, Strue, gloc) + My My (Iglobali &, frree Ficlobal)
Local va Global Optinal loss (1)
Global and Local: Sampie Retrieved Set Risk (II)
2 In (n(//)
+ 2 B Bex (S(X, YT)] (SCx.
5MMo e, ferue, gloo
48Le||
1b0 1b0 (21((42()))
N(r,0)
Generalization of Locat ERM
(1II)
where Rix (S(X,Y) is the empirical Rademacher complexity of 9(X,Y).
Before discussing the implications of the aforementioned excess risk bound, we instantiate Floe with a few common function classes from the literature (see Appendix B for the detailed proof of Thm. 3.4, and about the descriptions of these specifie instances).
5

---

Under review as a conference paper at ICLR 2023
Kernel-based classifiers. When fy belongs to bounded RKHS with &oo norm bound B (Zhang, 2004), for some universal constant C' > and any O,
E(x,y)~DRRxx (9(X, Y)) S ((VvV]LBBlnnn 1)8/2 ( +2B)).
Similarly, when (.(+) belongs to a bounded RKHS with la norm bound (Lei et al., 2019), for some universal constant C' 0 and any 8 0,
(Nr, E Dxx (9(X, S C² C"(L, // 28B).
Ferd-forward classifiers. Assume that f,(+) is L layer foed-forward network with 1-Lipschitz non-linearities (Bartlett et al., 2017). Let, for layers / = to L, the dimension of the weight matrix be (di x d=11) with dr. = 19,. Also, let by and si be the f2.1 norm and spectral norm upper bounds for layer weight matrix, respectively, with b1/st S K. We define dmax = maXte(t] di and let B- max || I 8t. Then, for some universal constant C" > and any >
Exxx (S(X, Y)) s C" (1n BL,, 3/2 N(r, + 25B).
Implications of the excess risk bound. Our main result for local-ERM highlights the trade-offs in approximation vs. generalization as the retrieval radius r varies. To further claborate, note that the approximation error comprises two components, defined by (1) and (II) in Thm. 3.4. Ex shows the gap in approximating the r-radius neighborhood around with a simple local function class g-X which vary with X E X. Eloc shows the gap in approximating the union of the local function class UxerFX with single function class gloe (possibly with smaller complexity) but while allowing for choosing different optimizer f Floc for each X X. As increases, both the terms ex and éloc typically increase. For example, in approximating polynomial function locally with linear function Ex increases as the radius increases. Thus, (I) increases with r. Note that the second component of the approximation error (II) corresponds to the difference of risk for the sample X and the retrieved set R for Fggloall and gloc, i.e., M, (Talobbal; e, Strue; gzlobal) and M, (Troc: e, Strue, Floo). As we increase Eq. (13) suggests that the terms increase as (ppoly(r)).
On the other hand, the generalization error (III) depends on the size of the retrieved set R and the Rademacher complexity of S(X, Y) which is induced by gloe, With increasing radius the term (r, 5) increases. The Rademacher complexity decays with increasing radius, r. typically at the rate of 0(1/ ((;/VN(r,))) 5)). Thus, under the local ERM setting the total approximation error increases with increasing radius r, given gloc is fixed. On the contrary, the generalization error decreases with increasing radius r for fixed gloe This suggests trade-off between the approximation and generalization error as we make a design choice about r. (We empirically validate this in Figure 2.)
Also, it's worth comparing local-ERM with conventional (non-local) ERM. Under the local-regularity condition assumption (Sec. 2.2), one would utilize a simple gloc for local-ERM, which would correspond the Rademacher complexity term in Theorem 3.4 being small. In contrast, the generalization bound for the traditional (non-local) ERM approach would depend on the Rademacher complexity of a function class gilobal that can achieve a low approximation error on the entire domain. Such function class (even under the regularity assumption) would be much more complex than gloc resulting in a large Rademacher complexity. For the right design choice of r, and gloo the approximation error increase of local-ERM can be offset by large generalization error of grlaball As a consequence, local ERM with simple function class gloe can outperform (non-local) ERM with a complex class Frllobal
3.2 ENDOWING LOCAL ERM WITH GLOBAL REPRESENTATION.
Note that the local ERM method takes a somewhat myopic view and does not aim to learn a global hypothesis that (partially entirely) explains the entire data distribution. Such approach may potentially result in poor performance in those regions of input domains that are not well represented the training set. Here, we explore two-stage learning approach as to leverage the global pattern present in the training data in order to address this apparent shortcoming of local ERM.
Given the training data S and simple function class gloc Rd - RM the first stage involves learning d-dimensional feature map &gg X R that simultaneously ensures good representation

---

Under review as a conference paper at ICLR 2023
for the entire data distribution (Radford al., 2021; Grill et al., 2020; Cer et al., 2018; Reimers & Gurevych, 2019). Subsequently, given a test instance I and its retrieved neighboring points R [(2', v } S S, one employs local ERM with the function class:
(14) At this point, it is tempting invoke the proof strategy outlined following Lem. 3.3, with groc replaced with Fas to characterize the performance of the aforementioned two-stage method. Note that one can indeed bound the first two terms appearing in Lem. 3.3 for the two-stage method as well. However, bounding the third term that corresponds to generalization gap for local ERM becomes challenging as F4, depends on S via the global representation &g learned in the first stage. Interestingly, Foster et al. (2019) explored a general framework to address such dependence for standard (non retrieval-based learning. In fact, as an instantiation of their general framework, Foster et al. (2019, Sec. 5.4) considers the ERM in feature space defined by representation. We employ their techniques to obtain the following result on the generalization gap for local ERM with Føs-
Fo. fI g (x(x) E gloo).
Proposition 3.5. Assume that the representation learned duing the first stage is A-sensitive, ie., for 8 and 8' that differ in a single example, we have [} 4 go (x) I A Vr E X. Furthermore, we assume that each g E gloc (cf. 14) is L-Lipschitz, the loss E (1) x 1y - IK is -Lppsscthtttzz w.r.t. || -looo-morm in the first argument, and E is bounded by Mr. Then, the following holds with probability at least 8.
log(1/0)
EXX,Y' ((((X') (0 -RE & (M, DV
sup SEFos
+
2|12*
ExenDerr
sup SEFus
v.) - R RT
(15)
Furthermore
Ex
sup JEJas
((((''), Y`) -EE S 299 (L Fos), (16)
where l o Fa. = ((x, y) + (((()))))= f Foxt and d denotes the Rademacher complexity of data dependent hypothesis sets Foster et al. (2019).
We defer the proof of Prop. 3.5 and necessary background on Foster et al. (2019) to Appendix C.
As potential advantage of utilizing global representation with local ERM, one can realize high- performance local learning with an even simpler function class. For example, it's common approach to only train linear classifier on learned representations. Furthermore, a high-quality global representation can ensure good performance for those local regions that are not well represented in the training set. We leave formal treatment of these topics for a longer version of this manuscript.
4 CLASSIFICATION IN EXTENDED FEATURE SPACE
Next, we focus on a family of retrieval-basee methods that directly learn a scorer to map an input instance and its neighboring labeled instance score vector (cf. (10)). In fact, as discussed in Sec. 1, many successful modern instances of retrieval-based models such as REINA (Wang et al., 2022) and KATE (Liu et al., 2022) belong to this family. In this section, we provide the first rigorous treatment (to the best of our knowledge) for such models.
Note that our objective is to learn a function f: X x (X x y)* - 91 (cf. Sec. 2.3). In this work, we restrict ourselves sub-family of such retrieval-based methods that first map R Da." to Dz.r an empirical estimate of the local distribution D which subsequently utilized to make a prediction for x. In particular, the scorers of interest are of the form:
Rx. - [sx D=-r) (Ji D*"))....
... S1y (xc, D(rr)) RIV
(17)
Note that the general framework for learning in the extended feature space X = X Axxy provides a very rich class of functions. Here, we focus on a specific form of learning methods in X by using the kernel methods, adapting the work on kernel methods for domain generalization (Deshmukh et al., 2019). In particular, ERM. Due to space constraint, we present an informal version of our result below. See Appendix D for the precise statement (cf. Thm. D.4), necessary background, and detailed proof.
study generalization of kernel-based classifier over X learnt via regularized
7

---

Under review as a conference paper at ICLR 2023
Theorem 4.1 (Informal). Ler 0 < 8 and (r, 6) be as defined in (8). Then, under appropriate assumptions, with probability at least - 6, we have
log(
+ Csy log(
sup (f) - R2 (f) 2 Cin (1+1og v2nly)) + C N(r; 2 SET (
where I is the extended feature kernel function class; and Te (f) and R are empirical and population risks, respectively.
Interestingly, the bound in Thm. 4.1 implies that the size of the retrieved set RH (as captured by (r, 2) has to scale at least logarithmically in the size of the training set n to ensure convergence.
5 EXPERIMENTS
There have been numerous successful practical applications of (e.g.. Wang et al., 2022; Das et al., 2021). Here, present brief empirical study for such models in order to corroborate the benefits predicted by our theoretical results.
models in the literature
Task and dataset. We perform experiments on both synthetic and real datasets, summarized below. Further details are relegated to Appendix E. (i) Synthetic. We consider a task of binary classification on a Gaussian mixture. Each mixture component is endowed with its local linear decision boundary. We randomly generate a train set of n = 10000 in 10-dimensional space. We use Euclidean distance for retrieval and perform a 10-fold cross-validation.
(ii) CIFAR-10. Next, we consider a task of binary classification on a real data for object detection. In particular, consider subset of CIFAR-10 dataset where only restrict images from "Cat" and "Dog" classes. We randomly partition the data into a train set of n = 10000 points and remaining 2000 points for test. We use Euclidean distance for retrieval and do 10-fold cross-validation.
(iii) ImageNet. Finally, we consider 1000-way classification task on ImageNet dataset. We use the standard train-test split with practice in literature, we use unsupervised but globally learned features from ALIGN (Jia et al., 2021) do image retrieval. This also showcases benefits of endowing local ERM with global representation (Sec. 3.2). Given large computational cost, we could only run each experiment once in this setting.
1281167 training and 50000 test examples. Following standard
Methods On all datasets, baseline, we consider simple linear classifier and multi-layer perceptron (MLP) of two layers. For retrieval- based models, we consider each of the above methods as the local model to fit on retrieved data points via local ERM framework (Sec. 3). For synthetic datasets, we also considered support vector machines with polynomial kernel (of degree 3) and with radial basis function (RBF) kernel, both for bascline and local ERM. For ImageNet, we additionally consider the late-of-the-art (SoTA) single model published for this task, which is from the most recent CVPR 2022 (Zhai et al., 2022) as baseline. In addition, for ImageNet, we also consider the pvetrain-fineture version of local ERM, where using the retrieved set we fine-tune a MobileNetV3 (Howard et al., 2019) model that has been pretrained on entire ImageNet.
Observations. In Fig. 2, observe the tradeoff of varying the size of the retrieved set (as dictated by the neighborhood radius) on the performance of retrieval-based methods across all settings. We that when the number of retrieved samples is small, local ERM has lower accuracy, this is due large generalization eитor. When the size of the retrieved sample space is high, local ERM fails to minimize the loss effectively due to the lack of model capacity. We see that this effect being more pronounced for simpler function classes such as linear classifier as compared to MLP. In Fig. 2c, we see that, via local ERM with a small MobileNet-W V3 model, we are able to achieve the top-1 accuracy of 82.78 whereas regularly trained MobileNet- V3 model achieves the top- accuracy of only 65,80. Also the result very competitive with SoTA of 90.45 with a much larger model. Thus, our empirical evaluation demonstrates the utility of retrieval- based models via simple local ERM framework. In particular, it allows small sized models to attain very high performance.
RELATED WORK AND DISCUSSION
Local polynomial regression. Perhaps the most similar problem to our setup is the rich set of work on local polynomial regression, which has been around for long time since the pioneering works
8

---

Under review as a conference paper at ICLR 2023
MM
MLNkyese2)
ARR
Lear ParayeS-22
Ret Satter--Mi
P
natt cro
WWV
90-
0.9
0.12
80-
0.7
0.00
75-
0.38
65-
0.
207
Number neighbor
Number nearee neighter
(a) Synthetic
(b) CIFAR-I0
(c) ImageNet
Figure 2: Performance of local ERM with size of retrieved set across models of different complexity.
of Stone (1977; 1980). This line of work aims to fit a low-degree polynomial at each point in the data set based on subset of data points. Such approaches gained lot of attention as parametric regression was not adequate in various practical applications of the time. The performance of this approach critically depends on subset selected to locally fit the data. Towards this, various selection approaches have been considered: fixed bandwidth (Katkovnik & Kheisin, 1979). nearest neighbors (Cleveland, 1979), kernel weighted (Ruppert & Wand, 1994), and adaptive methods (Ruppert et al., 1995). So far, the analysis of local polynomial regression has been mainly restricted to classical techniques like minimax estimation, on which the literature is a vast for various settings. First results on asymptotic minimax risks were established by Pinsker (1980) over Bobolov spaces. Minimax risks over more general classes were studied by Ibragimov & Has Minskii (2013), Donoho & Liu (1988), among others, for estimating entire function. But none of these works provide finite sample generalization bounds, which we obtain in this work.
Multi-task and meta learning At surface level, our setup might resemble multi-task and meta learning frameworks, In multi-task learning, we are given the examples from T' tasks/distrrbutions and the objective is to ensure good classification performance on all the tasks. In meta-learning, the setting is made harder by requiring good performance on a new target task. As a common approach in these settings, we learn shared representation across the tasks and then learn simple task-specific mapping on top of these learned shared features (Vilalta & Drissi, 2002, interalia). While there is vast literature on multi-task and meta-learning methods, the number of theoretical investigations is quite limited. There are few works studying upper-bounds on generalization error in multi-task environments (Amit Meir, 2017; Ben-David & Borbely, 2008; Ben-David et al., 2010; Pentina & Lampert, 2014), and even fewer in case of meta-learning (Balcan et al., 2019; Khodak et al., 2019; Tripuraneni et al., 2021; Du et al., 2020). However, most of these works assume linear or other classes of very simple models, whereas we consider general function class using kernel methods. Moreover, recall that our assumption on the underlying data distribution (Sec. 2.2) implies that can be approximated by mixture of tasks. However, by design most of these tasks have very little overlap in the instance space. Additionally, the number of tasks can be very large in our case. Finally, it's not a priori clear which task particular example belongs to. Thus, it is not straightforward to employ the aforementioned representation based approach for multi-task or meta-learning approaches for our setting. Interestingly, in this work, we show that retrieval-based approach alleviate the needs to identify the task-membership. By relying on retrieved neighboring instance, it is possible to obtain performance guarantees on their data domain which are attuned to local structure of the problem (cf. Sec. 3).
Conclusion and future direction. In this work, we initiate the development of a theoretical frame- work to study the generalization behavior of retrieval-basee modern machine learning models. Our treatment of an explicit local learning paradigm, namely local-ERM, establishes an approximation vs. generalization error trade-off. This highlights the advantage realized by access to a retrieved set during classification as it enables good performance with much simpler (local) function classes. As for the retrieval-basee models that leverage retrieved set without explicitly performing local learning, we present systematic study by considering a kernel- space. Studying end-to-end retrieval-basee models beyond kernel- classification is natural and fruitful direction for future work. It's also worth exploring if existing retrieval -based end-to-end models inherently perform implicit local learning via architectures such as Transformers.
classifier over extended feature

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-bayes theory. arXiv preprint arXiv: L..144, 2017.
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient-based meta-learning. In International Conference on Machine Learning, pp. 424-433. PMLR, 2019.
Peter L Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156, 2006.
Peter I. Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-norrmaiized margin bounds for
neural networks. Advances in neural information processing systems, 30, 2017.
Shai Ben-David and Reba Schuller Borbely. A notion of task relatedness yielding provable multiple- task learning guarantees. Machine learning, 73(3):273-28) 2008.
Shai Ben- Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1-2): 2010.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv preprint arXiv:1606.0m 140...466044400 04460, 2016.
Léon Bottou and Vladimir Vapnik. Local Learning Algorithms. Neural Computation, 4(6):888 11 1992. ISSN 0899-7667. doi: 10.1 10.1162/neco. 1992.4.6.888
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Vosse. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter. Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Suujardoo-Csseedee Steve Yuan, Chris Tar, et al. Universal sentence encoder. arXiv preprint arXiv: 1175, 2018
William S Cleveland. Robust locally weighted regression and smoothing scatterplots. Journal of the American statistical association, (A(366))829-836) 1979.
Patrick Cramer. Alphafold2 and the future of structural biology. Nature Structural Molecular Biology, 28(9):704-705, 2021.
Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-hased reasoning for natural language queries over knowledge bases. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 9594-9611, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/2022 http2/222..mmmmmmii.... 755.
Aniket Anand Deshmukh, Yunwen Lei, Srinagesh Sharma, Urun Dogan, James W. Cutler, and Clayton Scott. generalization error bound for multi-class domain generalization, 2019.
David L Donoho and Richard C Liu. The" automatic" robustness of minimum distance functionals. The Annals of Statistics, 16(2):552-586. 1988.
Maik Döring, László Györfi, and Harro Walk. Rate of convergence l n--nearest-niighbor classification rule. Journal of Machine Learning Research, 18(227): 1-1., 2018.
10

---

Under review as a conference paper at ICLR 2023
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint XXiv:2002.09434,, 2020.
Jianqing Fan and Irene Gijbels. Local polynomial modelling and its applications. Routledge, 2018.
Evelyn Fix and Joseph Lawson Hodges. Discriminatory analysis. nonparametric discrimination: Consistency properties. International Statistical Review/Revue Internationale de Statistique, 57(3): 238-247, 1989.
Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridha- ran. Hypothesis set stability and generalization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in Neural Information Processing Systems, 15:21271-212844 2020.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chies Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, Quoc V. Le, and Hartwig Adam. Searching for mobilenetv3. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
Ildar Abdulovich Ibragimov and Rafail Zalmanovich Has Minskii. Statistical estimation: asymptotic theory, volume 16. Springer Science & Business Media, 2013.
Ahmet Iscen, Alireza Fathi, Cordelia Schmid, Mathilde Caron, and Tom Bird. memory transformer network for incremental learning. arXiv preprint, 2022.
Gautier Izacard, Patrick Lewis. Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-YY Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave Few-shot learning with retrieval augmented language models. arXiv preprini arXiv:2208.0333 03299, 2022.
Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig. Scaling up visual and vision- language representation learning with noisy text supervision. In International Conference on Machine Learning, pp. 4904-4916. PMLR, 2021.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Vladimir Yakovlevich Katkovnik and VE Kheisin. Dynamic stochastic approximation of polynomials drifts. Avtomatika Telemekhanika, (5)88998, 1979.
Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar. Adaptive gradient-based meta- learning methods. Advances in Neural Information Processing Systems, 32, 2019.
Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 655555295,,, 2019.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures, pp. 100-114 14, Dublin, Ireland and Online, May 2022. Association for Computational Linguistics. doi: 10. 10.11863//1122222deeeii 1.10. URL https: : / //aclaante /aclanttoooogg org/2022 deelio-1.1 1.10.
11

---

Under review as a conference paper at ICLR 2023
Si Liu, Xiaodan Liang, Luoqi Liu, Xiaohui Shen, Jianchao Yang, Changsheng Xu, Liang Lin, Xiaochun Cao, and Shuicheng Yan. Matching- cnn meets knn: Quasi paaasi-arametric human parsing. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1419-1427, 2015.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large- scale long-tailed recognition in an open world. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 2537-2546, 2019.
Alexander Long, Wei Yin, Thalaiyasingam Ajanthan, Vu Nguyen, Pulak Purkait, Ravi Garg, Alan Blair, Chunhua Shen, and Anton van den Hengel. Retrieval augmented classification for long-tail visual recognition. In Proceedings of the IFEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 1959-6969, 2022.
Anastasia Pentina and Christoph Lampert. A PAC-bayesian bound for lifelong learning. In Interna- tional Conference on Machine Learning, pp. 991-999, 2014.
Mark Semenovich Pinsker. Optimal filtering of square-integrable signals in gaussian noise. Problemy Peredachi Informatsii, 16(2):52-68, 1980.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech Badia, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In International Conference Machine Leurning, pp. 2827-2836. PMLR, 2017.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. International Conference on Machine Learning, pp. 1748-8765 PMLR, 2021.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint arXiv: 10084, 2019.
Sam Ritter, Ryan Faulkner, Laurent Sartran, Adam Santoro, Matt Botvinick, and David Raposo. Rapid task tosk-no in novel environments. arXiv preprint arXiv:2006. 03662, 2020.
David Ruppert and Matthew P Wand. Multivariate locally weighted least squares regression. The annals of statistics, pp. 1346-1370, 1994.
David Ruppert, Simon J Sheather, and Matthew P Wand. An effective bandwidth selector for local least squares regression. Journal of the American Statistical Association, 125432): 1995.
Shai Shalev-Shwards and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In Marcus Hutter, Rocco A. Servedio, and Eiji Takimoto (eds.), Algorithmic Learning Theory, pp. 13-31, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg, ISBN 978-3-540-75225- 7.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387772413.
Charles Stone. Consistent nonparametric regression. The annals of statistics, pp. 595-620, 1977.
Charles Stone. Optimal rates of convergence for nonparametric estimators. The annals of Statistics, pp. 1348-1360, 1980.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In International Conference on Machine Learning, pp. 10443. PMLR, 2021.
Ricardo Vilalta and Youssef Drissi. A perspective view and survey of meta-learning Artificial intelligence review, 18(2):77-95, 2002.
12

---

Under review as a conference paper at ICLR 2023
Shuohang Wang, Yichong Xu, Yuwei Fang, Yang Liu, Siqi Sun, Ruochen Xu, Chenguang Zhu, and Michael Zeng. Training data is more valuable than you think: A simple and effective method by retrieving from training data, 2022.
Alon Zakai and Yaacov Ritov, How local should a learning method be?. In COLT, pp. 205-216. Citeseer, 2008.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp-
12104-12113, 2022.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550 2002.
Tong Zhang, Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, (200:t)):2221255:::: 2004.
13

---

Under review as a conference paper at ICLR 2023
A PRELIMINARIES
Definition A.1 (Rademacher complexity). Given a sample = {2+ (xi, vi Hil C 2 and a real-valued function class 3 Z R. the empirical Rademacher complexity of F with respect to 8 is defined as
1 Rg
EE n
sup fE3
of
(18)
where {ox)se(m) is collection of n. i.d.d. Bernoulli random variables. For E N, the Rademacher complexity (3) and worst case Rademacker complexity (F) are defined as follows.
(5) ES-D= [Rs(F)); and (F) sup (F) 8-22"
(19)
Definition A.2 (Covering Number). Let e 0 and ||- be norm defined over R" Given function class F 2 + R and collection of points = {2ibee(a] 2, we call set of points {us (em)) C T an (e, [l)-cover of with respect to 8, if we have
sup min (If(8) - 5 c, jE(m
(20)
where f(8) (f(z)), ((Zi) (zn)) E R". The ||. ||-covering number Ni,nne,,, denotes the
cardinally of the minimal (e, ||- (llv---overrre of with respect to 8. In particular, if ||]l|] is an normalized-f,
norm ([wll = [mm(p) Exn dim(r)) (o/(p)//p), then we simply use N, 8) to denote the corresponding
lp ep-covering number.
B PROOFS FOR SECTION 3.1
B. PROOF OF LEMMA 3.3
Note that
E(xYy>D (x)
// We add and subtract loss of the local optimizer / (x)(()) expected over X,r
-ExxYr eefx (X), (x)x)x)))xxxxxXX)))))x)))))))))) - (1)
+ [x (l)),.">xx.--- (<))x>xxxx(((xxxxx))))).))))))") Y')] e(f
// We add and subtract loss of the global optimizer (+) expected over X,r
Exxxri ec (X), B.
Y')l
E x (xxx,)))xxxx(((((()))) -
+ EX -xxx,r))-xx [e(fx: Y')] -xx [(( Y']]
// We group (1) local vs global optimizer, (2) global optimizer at X vs expected over D X,r // and (3) ERM loss at X vs local optimizer loss expected over X,r
Ex ( -()()))))(((())))))
E(XYY)~D ( [(xx)))
E(XY) [ - (((xx y']]
E
// We add and subtract loss of the empirical optimizer (.) expected over X.
E(XY)~ Exx [e(xx. Y") -(((()))())))
14

---

Under review as a conference paper at ICLR 2023
+ B
BXXYYD (( fx (X); Y) - -xx,
+ +B (e (X'), - ((foox/__((e_xx.).....____) r']
// We (1) bound difference of loss at X and loss expected over D by maximizing over function class,
// and (2) Subtract empirical loss of empirical optimizer and add (larger) empirical loss of local optimizer
2 ExxY B(X,YYNDXx,
(X'), X) -X(((x)))))
+ E(x,y~
sup fEgxiobal
E(x),Y))DXX (1)_))))xxx(((((())))))__))))))) - ((((X)
((f((x)) (([((')) XIll
|e(s(x;))) B -
sup
SEgiin
+ Ex BXX. (xx),,
((p* (.)))))
[
(z's)))xx
E
e(fxit B(x, [((sx*
(e)_:>xxx_[[[()xrrr_) (((xx(())))))
(21)
|RA]
// We (1) bound difference empirical vs expected loss of empirical optimizer by maximizing over function class,
< ExX,
B(x [C(S (x'), - -(((()),
+ E(x,r~~D
sup fEgTilobll
E B(x,y))DXx (( ((f(x),))]
- ((((x)), lill
sup fESFlo
+ E
sup
_ex.,)--xx-
E e(f(r))>/)
fectio
(2'M)))(
E ((Fx)((a))
(22)
B.2 PROOF OF THEOREM 3.4
As discussed in Sec. 3, the proof of Theorem 3.4 requires bounding three terms in Lemma 3.3. We now proceed to establishing the desired bounds.
Local vs global loss. The local vs global loss can bounded easily using the local regularity condition, and due the fact that Froe ss Ug Let
x.
arg min E Dxx (X(()))))
JEFx
ExXYY~D Bxx [[[ (X'), e(st
E(XYY-D ( (xx.Y)).xxx
+ E { E (x)_oxxxxxxxxxxxxxxxx))))))))))) - -((())))
Elec Err
Global and local: Sample retrieved set risk. The following lemma bounds the second term in Lemma 3.3. Recall the definition, for any I. > 0,
M, (L; é, Strue, F) = 2L Lr + (max Lr, 11 - Lr) Crrue (2 Ourrue
(23)
15

---

Under review as a conference paper at ICLR 2023
Lemma B.1. Under Assumption 3.2, for L-coordinate fiunctiot class F with ||3 supxex sup [ff co we have
[xXYD sup [([()),)) Y) (xxx,))-xxx(((((X),, SEJ
s 22ng Tr + (Tr, ol))) (1 Carue (2 ) )auue)
Proof. We are given the example (), Let fix an arbitrary E F, and any arbitrary example (x', v in the r neighborhood of X.
We first bound the perturbation in 7 (-) for given label Y.
hy((,,,)) - (, Y)1 - ffy (X1) - max fx( fg (X2) + max for (X2) ofY
8+4Y
s (X1) (X2)
max fa(X1) .#Y
-nax for (X2)
''GY
$ (X,) fx((2))
max (X1) fx(X2)
sFY
s 2 - X2112
We can now proceed with bounding the loss.
(e(f(x),)) - {(f((')))') =(1 = ((()s(X)))) (615(a',0) s'ii
S (X - 11 v/11
< 4Lellflboi of
2L y
Under Assumption 3.2, if we have y (X, LLeruer, then following the above argument we have Yyuuel (X', Y) >> 0, thus Y is the true label of X'. In other words, 7 (X, Y) > L imply for any X' in the r neighborhood of X its true label y =Y
(E({(X), Y) ((f(='),v')
$ 2. (X,Y) 2 + 2he max (r. 21] (7) (X,Y) S 2 $ 2L,Lr + ( max 2ll - Lr) ( (X,Y) S 2L
As w') was an arbitrary r-ieihhoor, we have
((((X), -xxxr)xxx
Y'II
- -xx < 2L,Lr + 2Lx max Lr, (r, Lr) (X,
-(f((')))
(X, Y) I 2Ltrue))
Furthermore, as was arbitrary, we have
sup (((((X), fET
S sup 2I Lr 2L max (Lr 2| [|]] Lr) 1 (T) (X,Y) S 2Inree))
feF
= 2L,Lr + 2 mr, 2| Lr) (7 (x, Y) < 2Ltrue)).
Note frrue is independent of f. which was used in the derivation of above inequalities. Taking expectation over (X,Y) and using the margin condition as given in assumption 3.2 we obtaín
E(X,Y>~
sup ((((()))) - feB
= 2o + 2T. (Tr - T. PX.YYDD (yprre (X, (XY) & TTrree
< 2L + 2L 2 - Lr) ctruc (2Irrue)) Croee = (L; E, (erree F)-
16

---

Under review as a conference paper at ICLR 2023
Plugging in the Lipschitz bounds for the function classes gloe and Fxlobal in the above lemma bounds the second term.
Generalization of Local ERM. Recall the function class 9(X, ((())(+))) ((,,, f e gloej, Here S(X,Y) X + IR. Note that the function class is parameterized by (X, Y) Let us define some quantities of the function class on a set S - X x y as
Mmax (X,
sup sup lg(2", (E (ES
By centering each function f E gloc at the point (X, Y) we can transform the generalization over the function class gloc, to the generalization over the function class 9(X, Y). In particular, we have
E Exxxrr)-xx ((((x))))(((()))))))
Σ e(f(r))
sup fEgloe
|
-
sup fEffiee
E (0rr)))>xx1((((((",..) E((()))))
1
Σ (((+')))) ((
|Rx
= EXYY~
sup (E
E BW Y'I
Σ
R
(a' (xx)
We next state a standard result of learning theory that bounds the final term using the Rademacher complexity of the function class 9(X, Y) ShaalevSShwart & Ben-David, 2014).
Lemma B.2 (Adapted from Theorem 26.5 Shalev-Shware & Ben-David (2014).). For any (X,Y) X x y and a neighborhood set RX and any function g 9(X, Y), for each ó > 0 with probability at least (1 - 8) the following holds
[=x,,))-xxx (X)]
Σ
a(2',5)
|
(w' WRR
2 2lm(4/))
S 2 (9(X,Y)) + 49 ( ((X, ()+
Rx
Taking expectation with respect to (X, Y). we obtain
EXXYD~
sup (ES(X,M)
[(X,Y)=DX (X',, Y'1 |
Σ 9(2',2/)
(Exx))
2 Rax (9(X, X))]
2ln(4/0)
4BxxYy/D 9max 1R=
+ L- 1100
[
< ( Rox (9(X,
21m(4/5) [XX]
4E 4E(x,r)D ( 9max (XX, 1R
+ 48L g| 100
121(4/0)
< 2E 2X
(Roee Rix (S(X, + 4M, (Lwoc e, firee gloc)
N(r,
+ 110 2lm(4/0) [
| S N(r, + +
2ln(4/8)
<2E Fixx (9(X, + 4D,, e, firee gloo)
N(r,)) + 16Le|] + /21m(4/8).
17

---

Under review as a conference paper at ICLR 2023
In the first inequality, we condition on retrieved sets of size at least (r, 8) which happens with probability at least 6, by assumption. In the second inequality, with probability (1- 6) apply the bound from Lemma B.2, whereas we use the bound 4Lg | with remaining probability 5. For the second inequality, with probability ó we 4Lg |3 I1 Further, we use that the | (rr 6) with probability at least (1 1--). 6). Also from the proof of Lemma B.1 we have that
Imax m Y); S 2 Lr (max Lr, 2||3 - Lr) (Tyuuc (X,Y) ([rrue)))
Taking expectation with respect to completes the bound.
Central Abslute Moment of fxi As the function fxx* fixed using centering, and then Hoeffding bound, we can directly bound the remaining term. We have with probability at least (1 6)
E(X 1e(x 1e(f" (X'),
Σ
((Fx:((z'),8')
|RA
- - [((s*=((') r) ((Sxx'(XX (x),)(
E
((fxi -((p:/))))((((......))))
|R
(x"x,"))
/n((2/5)
S Smax ((, ():Y):
|
Taking expectation similar the previous case obtain,
Ex E ExxxYY>Dx. [e(s (x',
Σ e(px=(2))))))
R
(arl (x))
In(2/8) S Exx,y 9max (mmax((X ((,,))
|Ra||
In(2/5)
S M, (Looc l, ftrue; Floo)
+ 46 1o
(r;
This concludes the proof of Theorem 3.4.
B.3 BOUNDING THE RADEMACHER COMPLEXITY Rg (S(X,Y))
We now derive bounds on the Rademacher complexity of the class 9(X, Y). We use the covering number based bounds for that purpose. We then start by relating it to the covering number of the gloc function class. Finally, we provide bound on the class of functions residing bounded norm Reproducing Kernel Hilbert Space.
We will use 9max (X, Y) instead 9max ((X, R-X) when context is clear. Similar to 9(X, Y). we define the function class 9 = (E(7)(, )) f E gloe] which does not depend on the locality cen- tered around (X, Y). On a set C X x y we can define Imax(() = supges sup (')s" 19(2', v/)]
Lemma B.3. Under Assumption 3.2 we have for any retrieved set within radius of X, xx for any p> P21
Rgx ()(X,
S mar (X,Y)/2
inf <e(0.9p.mmxxx,11
4e
log 22mmax log (Np(v/2.9,3xx))
VIRA
Furthermore, we have
Rex ()(X,Y)
9mar (X,r
inf < ce(0.Bmm.(x,
4c 12 / VPxi
log (No, (XX, Y21) av)
18

---

Under review as a conference paper at ICLR 2023
Proof. Given the set R* and some function g Y) let define for p 2 1
119lpp,ex (1222)
Σ
1g(ø', v()p)) 1/m
(ar' "))x
Then, we have Sp.max ((X, )); = maxges |1gl|1 for all g E Y(X,Y). For the sake of brevity we will use mp.max X, Y) in place of Sp.mux ((X, R))) Note that we have from previous definition mmax(X; (X,Y) Y) = moo (x, Y) 2 Sp.max (X, Y) for any 2 1.
Thus using the Chaining method (Shalev-Shwand & Ben-David, 2014, Chapter 27) we can bound the Radamacher complexity as
Sp.max (X,Y1/2
Agg (S(X)Y))
inf cE(0.. ce(0.5p..axxxx)//
4E
V ((1
VIR8
To finish the proof we need to show, for p 2 1
(( x*) S N,p(u/2, M,10//2,,,. (())))
First we fix any p 2 1. Let il (a set of real numbers) be a 1 cover (in ép norm) of 9 with respect ((XY)) We have (v, 9(X, Y), S 29max for any p 2 1 and any 0. Further, let U be v/2 cover of with respect to Rx Note for any à Ut we have à RI
Now, we fix any g' 9. We have least one E U, and u such that
-(("''")-@(c''"))) u(z'.))))) 1/P 1//2, and (X, ûl s 1/2.
3X
(E)))))
Therefore,
Σ
(0'(2')))-900 - (()d)) 1/8
|
(x'x))))XX
=(1EET
Σ
- - + (ū ( -xx 1/P
x
(e' (')xx
1s'(z',0/) ((d':/)-=(c''')))))) 1/8
Σ
+ +1a - =la-g((X,X) XX(
(u' x
S v/2 V
The first inequality follows by applying Minkowski's inequality. Whereas, for the second incquality we apply Jensen's inequality for (-) being concave function for p 2 1, and applying the appropriate scaling. Therefore, given the covers Ū and Ü, we construct the set U' with entries w' | as: U' : {u' = (ā(a, y) - ú) à E U, â E Ú.. In particular, [u'] [ As the choice of g' E 9 and (x',v') E X were arbitrary, we have 'I' to be the cover of 9(X,Y).
For p oo we can specialize the bound. In particular, consider to a v/2 cover (in fox norm) of 9 with respect to xx U {XX Y).. Then W' := {u' (É(I, y) a(X, Y)) â E U} creates (normalized) Lx cover for 9 with respect to Xx This is true because 1/v
x (le (x',8")~
01 = v/2. This concludes the M('', (('','')1)) s <lg'- - - = v/2 and l g'(X,)) s lg proof.
The first term in the above Lemma is similar to the Chaining based Rademacher bounds (Shalev- Shwartz & Ben-David, 2014. Chapter 28) for S. but the (in inf and in the integral) varies in [0, (X, Y instead of [0, 9ma]] For small r we have 9max Y) << Smax, which can be leveraged to give tight bounds in certain situations.
19

---

Under review as a conference paper at ICLR 2023
Example: gloc loc -oundee RKHS (Zhang, 2004); Let consider the setting of Zhang (2004). this setting, given some Reproducing Kernel Hilbert Space (RKHS) H, and a function f E H, we can define the function f(.) = f o hg where for some h E H. We further define the set of functions with bounded norm
HA = (i()) H1 II sup IIe S AJ.
=EX
Finally, our local function class can be defined
gloc = H (1() : 5O) E HA. Vy E y).
We have || A. Recall that loss function for any y E is given as ((yy (z, y)), for any
E Floc, We also have for all y y. (0( v)) (or (2r, v))l 2 sup, (1) (x)) (Zhang, 2004, Assumption 15) with YA = 2Lx).
Given the above setting, following Lemma 17 Zhang (2004)* 2, we have for universal constant
log (2L S U ((X, - dd In(2 + | /v) + (n(RR +1)
v2
This gives the following bound for the Rademacher complexity of gloe
Rgx s 0 Le Flnc
(24)
V|Ra
Proof of Equation (24). Without optimizing over above, we plug in e Sm
We obtain
V
Rgx ()(X,Y)
Smax Smax(XX)Y) (X,Y)/2
$ 19mmx(X.))
12 x
V log (Nso 1/2,9, (1/2,9,8"0 (((x) du
V
(
VI
(X,1
48 o/ / Liellllloo 1o:
Smax (X,Y)/2
In(2 + 4Lg
glnc
loe/v)
IR +
dv
V|Rx|
v x2
Smax (X.V)
y2
V13x
Imax (X,n)
(X,)
48 48 Le 1l.
In Ix((9moxXX.))+1/)) 1/2)) 1-11 dv
v [x1
(X.
VIRA
(XY)
48 / M Lelllloo 1oo
In([14-4L [gloe
Smma (X.Y)) x (+1) de
V |
VIRAI
32 M (X,Y) VIRA
3/2
Inn ((1 4L || 1 Mmax (X, (X, (), RX1) + 1 + 1))
[X
We use Ja / /I(aa/x) b/adx -2/3(ln(a/z) + 6)3/2 for the final inequality, and ignore the negative part.
Example: gloc = l2 bounded RKHS (Lei et al., 2019): We consider fixed kernel K K(x, x²) (Ø(x), ((x))) for x, x' E X, and let H k be the RKHS induced by K. Let us define the Ep.y norm for the vectors W = (W1, W2, ... w(y) E H YI
K [1( "/y))ll II(])= llp .p..... | lpg
For some norm bound A > 0, the local hypothesis space is defined as gloc
(f(.) f-) (w,, (c))) wy HH. Vy y, ")]K(,, S A}.
Recall that we have the loss function class 9 (((x)((-)) f Floe), where the loss function E(-) is assumed to be L-Lipschitz continuous w.r.t. Eo norm.
We correct for typographical emror in Zhang (2004), where the n = | comes in the denominator of the bound presented in Lemma 17. But Theorem 4 of Zhang (2002) shows this is typographical error. Indeed, the covering numberia is suppossed decrease with increasing number of points.
20

---

Under review as a conference paper at ICLR 2023
Given the retrieved set R* for some positive integer n 2 1, Fx after Equation (8) in Lei al. (2019)
induced by Rx Let the worst case Rademacher complexity of function class over n points be defined as RR (F). Also, for a set 5 let (SS) = (s supw: ( Wl (wy ((x)). We have
from Theorem 23 in Lei et al. (2019) that the covering number is bounded as follows: for any set = {(x,, 3k) 1, :,...::7 n of size n 2 1, for any I (Fxx
16m|8112(9t
[xx )2 log (2nlH1
log Noo (E,
Furthermore, from equation (18) in Lei et al. (2019) we have for any set A piccs [|o())l22
< Rnyyl (#*) S
A (max( [d(a])2
vn/y
Therefore, have for all 2 4L A (ax wes
wes ld(())22
/2n
log (..
mess [o(x)) log 2en HIB(S)L)
Plugging this covering number in in our Rademacher bound with 2 4L A mm [|(())l2 and taking S = Rxx U ((X,Y) we get
V2(12x [+)]
Smax (X,Y)/2
Rgx (S(X,Y)) s
inf mm
(cc+ V
/o ((X,
16 max (ww)) (((X,)) (((()) 12LL 12 (6. 10(x))IAL x
22( 1)
9mar 1/2
((X,)))) )dv |
log
ALA max wwweRRutox.. |le())lla
( 1)|3|
16 max((..)))))) (ACRRR(((X)))) (()(() 2AL
8 x 16 (a..." [[o())]AAL x
V2(R 1)
V
AvZeL UXXX, (+1)III (1E +DIID)
3/2
log
4LA (... ((( [o(=)]
16 (1.ex (1(()) 12LL
8 x 16 maX(E.))ERNN(((X.) [|(())]ALL x
+
22([ 1)
((og log (V2e( 1)191) 8/3) 3/2
In the final inequality we use the fact that
B(R* U U(XXY))) <
|x(x))12
sup willW la.a5A
2
(a.) ((())RR(((XX)))
[b(())]12
max (..))EXX(((X.1)
Therefore, the final bound on the Rademacher complexity can given as
Rgx S (Lel| 1lc Iu(ly px 11/2)
(25)
/
Example: gloe = I.-layer Fully Connected Deep Neural Network (DNN)(Bartlett et al., 2017): Following Bartlett al. (2017), we consider L-layer deep neural network (DNN)
fA = (A 11-2-. A'x) for z e X where A Ag.,, is the sequence
We need gx only to state some theorems in Lei et al. (2019). We refer interested readers to Lei et al. (2019) for the details.
21

---

Under review as a conference paper at ICLR 2023
of weight matrices. The matrix A' Rd for | = 1 to L, with d2 = 1 and du d given X C IR. Furthermore, 0i(.) 14 - R4 denotes the non- non-linearity (including pooling and activa- tion), ds are taken to be 1-Lipschitz, and 0,(0) 0. We assume that the A' matrix is initialized at M', for each I = 1 to L. We consider the local function class
gloc = (fa ||A'
12.11 S by || S st WSISL-1)
Furthermore, we have for any f gloe and any a X the function (f(z), - ((rr(;,-)) is 2 -Lipschitz. Therefore, for a fixed set S. we have from Theorem 3.3 in Bartlett et al. (2017) that the covering number of the 9 (((7)(;))) fA gloo) given as
log (Na(e, S
(n max
(II
L
L
(b//st) 8/2////222 2/3))/8)
R
e2
1=1
1=1
where dmax maxt= di, V [ Exes ||0||
S B, and
R = A (2d
(
(b1/s1)2/3)00
8t)
Using the covering number based bound on Rademacher complexity we obtain Mgx (S(X,))
92 max (X,Y)/2
log 4L, BL, " log (NG(v/2.9.2x)) dv)
inf 4c +
12
<E|0,9 2 (/
ViRii
Smax (X,Y)/2
inf
+
Vlog( 4h I1 "1 va dv
(x,))
v V
inf
+
SyR Vixx
log
3/2 4he AbeBBT(
SVR V
log 3/2 8L IT Th=1+ S2 (X (X,)
ma (/2
(X,,)
RvR
log
3/2
ALe
B
IT
81 //v/ |
3/2
SL. IT 32.maxeeX,
ViseX
V
xx1
92,
VIR+1
C PROOFS FOR SECTION 3.2
This section focuses providing proof of Proposition 3.5. It follows the proof technique of (Foster et al., 2019, Eq. (9)). Before presenting the proof of Proposition 3.5, we need to introduce a slight variation of the Rademacher complexity for data-dependent hypothesis set.
Let = X x y. Let R = [= {=]} E 2 be two m-sized samples and o E (+1,-11) -1) be vector of independent Rademacher variables. Now define RT, = (2) Rr
E 2 such that
if if 1, if af =-1
Ri.-
(26)
i.e., Ry.,. is obtained by replacing i-th element of R by i-th element of T iff = -1 1. U 2m be an m n-sized sample; for R 2.mh 8R 11 U.UR E z Note that, following this notation, we have SRy.. = U Ry or For 8 E 2", let IC(S) be data dependent function class (hypothesis set), which does not depend on the ordering of the elements in S.
Definition C.1 (Rademacher complexity for data-dependent function class). Let H. = (H(S)) be family of data dependent function classes. Given R { [e J.J = {zjE[m]} } ~ D and
I = (=M+ss)eenmm) the empirical Rademacher complexity De R (H) and Rademacher complexity Hi (H) are defined as follows.
1 Ri Ri. (H) = - Es
sup hE
m
i=1
m a (2
Hi (H)
ER.TT
sup
(27)
m
1=1
22

---

Under review as a conference paper at ICLR 2023
C.I PROOF OF PROPOSITION 3.5
We are now ready to establish the proof of Proposition 3.5, As discussed above, we extend the proof technique of (Foster et al., 2019, Eq. (9)) to obtain this result. Our setting differs from that of Foster et al. (2019) as the local ERM objective only depends on the retrieve samples R while the function class of interest Fg Fes in (14) depends on the entire training set 8 via representation &g. We suitably modify the proof techniques of Foster et al. (2019) to handle this difference.
Let [R]] ;= m and U R For R, J 2mm we define
T( = sup fEFeuux
BXx,Y''>- ((U((')) (xxx)))>-==+UXXXX))))
Σ ("E
(((2'),)))
=Re(f:Do)))
=R((::))
Re(S:D=.)) Pe(
sup
JEFoauR
Note that we are interested in bounding
E(R (")
sup fEJog
Σ {(f(x',,))
Re(f:Deir)
(=)
where we have used the fact that UUR = S. Towards this, we first establish that E(R, R) satisfies the Me + 22LL,,) difference property, i... for R,K N 2m that only differ in one m element, we have
Mr m
E(R, - ERRR, R')
+ 24LL2,1
(28)
Note that
3 (R, R)
FERRRRR < (R, R) - (RR R')
ERR R') - E(R'R')
(29)
Now, we will separately bound the two terms in the RHS. Let 2 (ø, 1) E R' and = RRR Thus, we have the following bound on the first term
I T= R) RR)
|Re(f: - Ro()) - sup
[R(fF:"..)) -Re(F:
sup SEToxux
JET
[Ro(J:D=.)) - Rc([:RR - |Re[[;
( De.)
Ro(S:
sup JETeaux
sup [Re(f:Dar) - -Re(f:R) - Re(f:D" + Re(f::R))
JEF+aux
[Re(J:R)) Rc((:R)
sup
/Efegux
1 (e(f(*)))) - ((f() M
sup JEF
(30)
where the last inequality follows from our boundedness assumption for the loss function é.
Now we move to term II. Towards this, note that, it follows from the definition of supremum that, for any > 0, there exists f E F Farax such that
sup JEF
Re(f:D= - -cs
- (e:3R))
(31)
Let f f= PUUR E FF and f' = ğ FUUR E Feewer Note that, for any (I. 2,,
(((())))) v) le( Puam ( v) E(ğ PuL (x), v)
23

---

Under review as a conference paper at ICLR 2023
Le,1 ll (u)x(()) 9 $ Puu (r)
L g o (uux( - g o tuu (x)1l2
(40
2 Lr, L P1L. - Puuux(()))l
(80)
I.D.
(32)
where we use Lipsccipcssseeeess of l w.r.t I loe norm, L-Lipschitzness of g, and A-sensitivity of the representation & in (i), (fi), and (tii), respectively.
Now, we have
II E(R, RR)
Dei") Re(f:RR)
Re(f:DD.") - Re(f:
sup
sup fEF
EEF aauR
DR. Re(F:
Re(ff:D.rr Re(f:301
sup
f
Re(fiDD.r) Re(F;RR) - | - :
[Re(f: :=*r) [Re(fi - -Relf'; xK) +
(e((FDD RelF': D [F((F: :e((P: +e
K T.A +
(33)
where (1) and (it) follow from (31) and (32), respectively. Now, since (31) can be chosen arbitrarily small, it follows from (29), (30), and (33) that
(RR R) E(R'RR) S Me 24LLE1
i.e., ERR, R) indeed satisfies the Mr + 24LL
--buudddd -bounded difference property. Now, it follows
from the McDiarmid's 's inequality that, for 8 >> O, we have with probability at least - 8:
log(1/0)
E(R",R*) S E ERR [RR] + (M, + 20L.e.mm)
2m
or
sup SEJog
Re(f:D*t)-Rii - S Eg=
sup fEJo2
[Re((
RTz (F)
log(1/0)
(M, + 2-LL2 1m)
(34)
2m
Now, first statement of Proposition 3.5 follows from (34) and the fact that = 1.
follows from the proof steps in (Foster et al., 2019, Section E. that
Exg
sup Se SEURUT
RR(F:D"
TE s 2
(35)
where F {Fouue FREZm and R is defined in (27). This completes the proof of Proposition 3.5.
D CLASSIFICATION IN EXTENDED FEATURE SPACE: A KERNEL-BASED APPROACH
As introduced in Sec. 2.3, objective is to learn function f 3 x (xxx - 91 For given instance x, such a function can leverage its neighboring set R E (XC x y)* to improve the prediction on In this work, restrict ourselves sub-family of such retrieval-based methods that first map
24

---

Under review as a conference paper at ICLR 2023
RR ~ D to D empirical estimate of the local distribution D which is subsequently utilized to make a prediction for æ. In particular, the scorers of interest are of the form:
(x, - f(z, D*-r)= - (fi (z, D*.")..... fly (x, D*))) E R
(36)
where fa( D=.r)) denotes the score assigned to the y-th class. Thus, assuming that Axxy denotes
the set of distribution over y. we restrict to a suitable function class in (f : : Axxy + R/ }.
Note that, given surrogate loss & IR M x y + R and scorer f. the empirical risk 12, and population risk (f)(())
(f) take the following form:
= - - (E(M) ((I; D".") and (R) = B(xYY [e(J(X,D*.)) Y)]
-
(37)
Note that that the general framework for learning in the extended feature space X : X x A provides a very rich class of functions. this paper, we focus on a specific form of learning methods in the extended feature space by using the kernel methods. The method as well as its analysis is obtained by adapting the work on utilizing kernel methods for domain generalization (Blanchard et al., 2011; Deshmukh al., 2019).
D.1 KERNEL-BASED CLASSIFICATION
Before introducing a kernel method for the classification, we need to define a suitable kernel k: X X + R on the extended feature space X := I x Axxy. Towards this, let kz be kernel over 2 == x y. Assuming that Hxz is the reproducing kernel Hilbert space (RKHS) associated with lz. we can define kernel mean embedding (Smola et al., 2007) V A - Hkz as follows:
(PP) =
kz
(38)
For an empirical distribution D defined by RR, kernel embedding in (38) takes the following form.
(D
|R Σ (x) kz kz((a', (/)
(39)
Now, using& kernel lx over X and a kernel-like function over vi (Az), we define a desired kernel x x x R as follows:
k ((x,xx)) (x((1,, (N."), (X,, (X2, Dxxx") kxx (X1, X2) x (V.(D..)), (DN)))))
(40)
Let Hy be the RKHS corresponding to the kernel in (40), and || || be the norm associated with Hy. Equipped with the kernel in (40) and associated Hμ. for À > 0, we propose to learn a scorer
(Si,.... -(y1) H|! = Hk x Hg via the following regularized ERM problem.
fex arg min
Σ (((())))))) +X-2(()
(41)
seH,"
where 7; = (x,, D and R( = 11 M = Epey l It follows from the representer
theorem that the solution of (41) takes the form fox(.) = ExE((n) (,,,(1, D=)r),.). One can apply multiclass extensions of SVMs to learn the weights {a;} (Deshmukh et al., 2019). Next, we focus on studying the generalization behavior of the scorer fex recovered in (41).
D.2 GENERALIZZTION BOUNDS FOR KERNEL- CLASSIFICATION
Before presenting generalization bound for kernel-based classification over the extended feature space X. we state the three key assumptions that utilized in our analysis.
Assumption D.I. The loss function é: RRI y is Le,1 -Lipsciit w.r.f. the first argument, i.e.,
[e((1. y) f(32. v) S La,1 || - $2 loo Furthermore, assume that (..)) (xx, v) = Mr S co.
V$1, $2 E R(9) and E y.
(42)
25

---

Under review as a conference paper at ICLR 2023
Assumption D.2. Kernels Ro, and are bounded by Max Mx,. and Mc. respectively.
Assumption D.3. Let Huz and Hn be the RKHS associated with kzz and K, respectively, Then, the canonical feature mup 9p. H&g > Hx is o-Hölder continuous with a E (0, 1], i.e,
[(px(h1) (m S I' || hallin vh,, h2 {h E Hkz
||A|| S MMz3 (43)
The following result states our generalization bound for the kernel-based classification method described in Sec. D.1.
Theorem D.4. Let 0 S å S 1 and Assumptions D.I-D.3 hold. Furthermore, let (r, be as defined in (8). Then, for any B > the following holds with probability least 33
RE R2 (F) s 32, log 2T. BM, Mex n= (1 log2 v2nl1)
sup feFB
2log(#) N(r, +
4M log(#) 3N 4)
log( ())
+ Le, May
Maz
Maz
MV
N(r, 4)
2n
fly)) where B3 (f..... E
H! (f()) & B²) and M Me + L M..
Before presenting the proof of Theorem D.4, we state two key results from the literature that are used our analysis.
Proposition D.5 (Steinwart Christmann (2008)). Let (22, A. P) be a probability space. be separable Hilbert space, and M > O. Let m...... 7m O - H be m independent H- H-valued random variables satisfying ||, S for all j E [m]. The, for the following holds with probability
at least 5.
T70
2 llg((/))
1 MV
4M log(1/5)
Ep [n]]
S M
+
(44)
m7
H
m
m
3m
Proposition D.6. (Deshmukh et al., 2019; Lei et al., 2019) Let ž x y be (extended) input and output space pair and $ {ă1. ?,, Let H2 be RKHS defined on X, with k being the associated kernel. Let
3
fy H2 Vy y and Σ 115
s SB}
DEM
and é: RRM y + be functtonn in its first argument, i.e.,
|f(5). u) f(52, 3) S Le, 11. - 82llo0 Vs1, 82 E M and y E y.
Then the Rademacher complexity of the induced function class l J = (Eo f: Fh satisfies
Rg o (o)))))))))) = E.g sup fETt
Σ c=((f(t)).v.))
iE|n]
< 16L / log 2B sup / /k(ā, 11y
(1+ 2
v2n1yl). (45)
aEt
Note that a (o1,..., on) denotes i...d. Rademacher random variable.
Proof of Theorem D.4. Note that
[ (f) R (
(f((z, (...)) ( Y,]]
sup Segt
sup 1E91
< sup feg
1 Σ
E(S(xs, Dewr),,
- ).s)
iml
im1
26

---

Under review as a conference paper at ICLR 2023
sup F
RX ((i(x))))))))))))
(46)
11
Bounding the term-l in (46). Note that
1 Σ
(((r,,Duir)) 1
Σ
(f(x;, (mi",,)
I = sup fe9t
==1
i=1
LE,1
Σ
(lf Devr)) - f(x, )0)0)))o0
"
iE|n]
Le,1
Σ
max 1fg (zi, Dz.rr) fy( Deirr)
wEy
ic|m
S Tg,1 max max [s (1,, Da..r) s D=:r)]
(47)
yEy
iE(n]
follows from the reproducing property of the kernel that, for any y E y,
[f,(,, Br..)) fu D**'"] 1ff. (((,,, ((t,, - k((2,, D= )>>
$ llfyllee [ [IA(((;, D..)),)) k((z,, (.."),,)lla
(48)
Now,
[[b((2,,
((zz, Dew,") -)) Dair), Duur),))
(N((E;, Dett), (Ii, D.rr)) + k((z,, D D=.")))) (2;, (z;, 2k((,;, Betr), (2;; D1) 1/2
Vkx(s, 24) (n) (( (D
"D=..))))))))))))) (D=..))
1/2
2x(V ((*.)))) V(D
)).))
Mr. (D=..)) N( (V((D=))) Hx
(49)
Max p V/ (Da.)) - px (V. Hr
$ L'M (D (D(...)))) )1,
(50)
By combining (48) and (49), obtain that
(z,, D (I, D**"") s L'Mxx Ilfull ||v((">.)) "D" 1l
(51)
Now, Hoeffding's s inequality in Hilbert spaces (cf. Proposition D.5) implies that, for E [n]]. the following holds with probability at least 6.
[v(()r (D**"") lie =
ka(le', - Ep [kz ))
RR..
Hag
2log(1/8) [R
1
4M,r log(1/8)
<
MEz
+ Maz
(52)
|RR=
3|R².
follows from (51) and (52) that, for each i [n]. (xs De..") (2 D*!r))
< L' Mex 11 (Mes V
log( Ru..
4MKx log( 1
+ Mez
Vyey
(53)
3 3|R0.
holds with probability at least - 5. Next, taking union bound over i [m]] implies that the following holds for all E [n] and y with probability at least 6.
(2,, B=..r) (*r,)) D*.rr)
27

---

Under review as a conference paper at ICLR 2023
2 2lo((n/6) [Rai]
4. log(n/6)
S Mk 1lll
M
+ Maz
+
(54)
Re.
3 3|3=.
Recall that, for each E [n]] we have |RaH| 2 Nr, 5) with probability at least 1 - (cf. (8)). Using union bound, we have [R [r, 6/n), A i E [n], with probability at least 1 8. Thus, the following holds for all E [n] and y E y with probability at least 26
(1s D(s.)= (2 D*
2lo((n/5)
4MR. log(n/0)
S &kx ll
Mks
Mxz
(55)
6(r,6/n)
N(r, 5/n)
(r,
By using 1lllle S B and combining (47) with (55), we obtain that
log(n/0)
1 N(r, 5/n) Ma2y N(r,8/n)
4M log(n/6)
I L B Mk V
+
(56)
(N(r,
holds with probability at least 1 - 25.
Bounding the term-ll in (46). Note that
II sup fEgt
(U.x), Ex
(57)
Using the Assumptions D.I and D.2 and the fact that f E Fz. we can argue that
((f(I,D*)), v) = E(0.g) y) + 1e(f(x, ".""),))) - E(0,g)]
< Mc + (x, 17
$ Mc + Le,1 max y'Ey
(fy' k ((x, DRir), ))
M₁ L1,1 max y'EN
|| || 11, Mr
S M, + Lz,1 RM, S M, + LF,1 RM M, := M
Now, it follows from the Aruaa-MeDiarmid's inequality that the following holds with probability at least 1 8.
(f(x,, D*."",,))) E(x,YyD [((((, X ),
sup fE
1=1
De""), - (e
< E
sup fET
i=1
log (1/))
+ .M
(58)
2n
Using the standard symmetrization procedure, we get that
( (f(x;, D=..)) Exx.ri [(
E
sup fETT
Σ 0 (, ((( (E(m)
< E(x.YY)DDE
29g (e F/:)
where a = (oi...., a.) denotes n i.i.d. Rademacher random variables and Rig (logt) denote the Rademarcher complexity of the function class
oo It
{ (I. v, DTT) e )()))) : :
28

---

Under review as a conference paper at ICLR 2023
Now, using Proposition D.6 with p 2 and Assumption D.2, we have
Rg (l Fh) v 16bz, v log 2B sup v k(T, F)n - (1+ log /2n(2l)
16 V log M (1+ (og log v2n(y)
(59)
Now, by combining (57), (58), and (59), we obtain that with probability at least 1 - 8
log log(1/6)
II 3221ogg 2L,,1 BM, Mxx" (1+ log V2uly1) + My Finally, combining (46), (56) and (60) completes the proof.
(60)
2n
E ADDITIONAL DETAILS FOR EXPERIMENTS
E.1 SYNTHETIC
Task and data. We consider the task of binary classification on mixtures using synthetic data: In
particular, we assume k 100 clusters D 10-dimensional space. Each cluster specified by
10) and a classification weight vector wi E 12 ~ No, I) for 1, k. We randomly generate train set of 10000 points as follows: To generate a labeled example (ær, J E [n]: 1) select cluster i uniformly at random, and 2) sample zy (W, II) and its label y sign(u)) w/ (x, pa)). Additionally, we also generate another set of points as test set using the same procedure.
mean parameter E _DD Uniform(-
Methods As baseline, we consider models of various com- plexity, starting from simple linear classifier, to support vector machines with polynomial kernel (of degree 3) and with ra- dial basis function (RBF) kernel, to a multi-layer perceptron (MLP) of two layers. For retrieval-based models, we consider each of the above method as the local model to fit on retrieved data points via local ERM framework (Sec. 3). Additionally, we also report simple KNN baseline. We compare all these methods using classification accuracy the held out test We repeat all the experiments 10 times.
Linarr PelylAogss1
537
MUMliycrse)
Nor revv MiMeeeeee
4NN
0.5
0.8
0.7
0.6
Observations In Figure 3, observe the tradeoff of varying the size of the retrieved set (as dictated by the neighborhood radius) the performance of the proposed algorithms. We see that when the number of retrieved samples is small the local methods have lower accuracy, this is due large generaliza- tion error. When the size of the retrieved sample space is high, the local methods fail to minimize the loss effectively due to the lack of model capacity. We see that this effect being more pronounced for simpler function classes such as linear classifier as compared to RBF or polynomial classifiers.
0.5
nearest
Figure 3: Performance of ERM and local ERM for various models on synthetic data.
E.2 CIFAR-10
Task and data. We consider the task of binary classification on a real image data for object detection. In particular, consider subset of CIFAR-10 dataset where only restrict images from "Cat" and "Dog" classes. We randomly partition the data into a train set of n = 10000 points and remaining 2000 points for test. We do a 10-fold cross-validation.
We consider a subset of method from Appendix. E. In particular, we only consider simple linear classifier and a multi-layer perceptron (MLP) of two layers. For retrieval-based models. we consider each of the above methods as the local model to fit on retrieved data points via local ERM framework (Sec. 3). The retrieval is done using L.2 distance in the input space directly (no features is extracted). Additionally, we also report simple kNN baseline. We compare all these methods using classification accuracy on the held out test set. We repeat all the experiments times.
Methods
29

---

Under review as a conference paper at ICLR 2023
Uhear
Retr ove-
Filkees-2)
exeeett Flbgers-2)
Observations Similar to Figure 3, Figure 4 exhibits tradeoff, where varying the size of the retrieved set (as dictated by the neighborhood radius) impacts the performance of the proposed algorithms. We see when the number of retrieved samples is small the local methods have lower accuracy, this is due to large generalization errоr, and when the number of retrieved samples is large, simple local function class incurs large approximation error.
CNV
0.62
0.61
0.57
E.3 IMAGENET
10a
30'
10"
10
Number nearest neighbor
Task and data. We consider the task of 1000-way image clas- sification ImageNet ILSVRC-12 dataset. We the stan- dard train-test set split, where we have of n = 128116 points for training and 50000 points for test. Given large computa- tional cost, we could only run each experiment once.
Figure 4: Performance of ERM and local ERM for various models on (binary) CIFAR-10.
Methods We compare proposed Local ERM (Sec. 3) to state- of-the-art (SoTA) single model published for this task, which from the most recent CVPR 2022 (Zhai et al., 2022). For the local parametric model we use a small MobileNetV3 ar- chitecture (Howard et al., 2019) with 4.01M parameters and 156 MFLOPs compute cost. Contrast this to SoTA model ViT-G/14 with 1.84B parameters and 938 GFLOPs compute cost. Following standard practice in literature, we use unsu- pervised learned features from ALIGN (Jia al., 2021) to do image retrieval using L2 distance. For solving the local ERM, we fine-tune a MobileNetV3 model, which has been pretrained on ImageNet, timizer with a linear decay schedule. Additionally, we also report simple kNN baseline. We compare all these methods using classification accuracy on the held out test set.
Liear
<B Satroveedirear
66
the retrieved set using Adam op-
10r
10.
10a
100
102
107
Namber nearest neighber
Figure 5: Performance of ERM and local ERM for various models on on ImageNet.
Observations In Figure 5, we that local ERM with small MobileNet-V3 model is able to achieve the top-1 accuracy of 82.78 whereas regularly trained MobileNet-V3 model achieves the top-1 accuracy of only 65.80. Also the result is very competitive with SoTA of 90.45 with much larger model. Thus, the result suggest that the simple local ERM framework (analyzed in our work) is able demonstrate the utility of retrieval-ber based models. In particular, it allows a realistic small sized model to attain very competitive numbers on the popular ImageNet benchmark. Furthermore, as pointed at end of Sec. 3.2, using global representation from ALIGN embeddings help simplest linear model to outperform MobileNet-V V3 working directly on image input, thereby showcasing the benefits endowing local ERM with global representation.
30


Reviews:
[{"review_id": "OPabcywGd_", "reviewer": "Reviewer_94k1", "summary": "", "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": "", "summary_of_the_paper": "The authors proposed a theoretical framework to analyze the retrieval-based machine learning models for multi-class classification problems. The authors specifically focused on Local Empirical Risk Minimization~(Local ERM), in which the neighboring labeled data of a test sample is retrieved to train a model in a simple function class by minimizing the empirical risk given the retrieved data. The authors analyzed the expected excess risk of Local ERM compared to the global ERM, in which the empirical risk of all the training data was minimized to train a model in a more complex function class. The main results showed that under some assumptions, the expected excess risk of Local ERM is bounded by the sum of an approximation error term, which typically increases as the number of retrieved data increases, and a generalization error term, which typically decreases as the number of retrieved data increases. \n\nThe authors extended the analysis of Local ERM to a two-stage learning framework in which the first stage will learn a feature map whose mapping function can depend on all the training data. The authors also included the analysis of another retrieval-based framework, where the scorer jointly takes the test data and neighboring labeled data for prediction. Lastly, the authors experimentally showed that (I) There exists a trade-off between approximation error term and generalization error term in the Local ERM framework; (II) The Local ERM can achieve the result similar to the SOTA with a much simpler model. ", "summary_of_the_review": "The authors proposed a theoretical framework to analyze the retrieval-based machine learning models based on previous generalizability and learnability results. The presented theoretical and empirical results are interesting. The authors may need to check thoroughly their proofs to make sure that the presentation is correct and self-explaining as much as possible. It will be interesting if the authors can test some new learning strategies in retrieval-based models based on the analysis. ", "strength_and_weaknesses": "Theoretical analysis of retrieval-based models on their generalizability is indeed interesting and timely. The presented empirical experiments have also shown the agreement with the analyses. \n\nIt may be interesting to consider how the analysis results may help guide the design and hyperparameter tuning of retrieval-based models. \n\nMore critically, as the paper is mostly on theoretical analysis, the authors may want to improve the presentation and make sure that all the proofs are correct and self-explaining. For example: \n\n1) Proof of Lemma B.2, on which the Theorem 3.4 is based, may not be correct. In the first inequality, the third term should be $8\\delta L_l||\\mathcal{F}^{loc}||_{\\infty}$ instead of $4\\delta L_l||\\mathcal{F}^{loc}||_{\\infty}$. In the second inequality, the authors should explain clearly why the expectation in the second term can be decomposed. \n2) In Appendix C, ${R}_{{U}}^{\\diamond}$ may need to be replaced with ${R}_{{U}, m}^{\\diamond}$  for consistency.\n3) The definition of $\\hat{R}^{\\text{ex}}_l(f)$ in Equation 37 seems to be wrong (should it be $\\hat{R}^{\\text{ex}}_l(f) = \\frac{1}{n}\\sum_{i\\in [n]} l(f(x_i, \\hat{D}^{x_i, r}), y_i)$?). There seems to be an unnecessary \"that\" in the following sentence. Such typos appeared at several places and the authors may want to carefully proofread the paper to improve the presentation. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Mw-aiagkkY_", "reviewer": "Reviewer_5HmN", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper students the theoretical properties of two variants of retrieval-based models, a popular topic in improving large models. The two variants are formulated as a local empirical risk minimization problem and a classification problem in an extended feature space. Theoretical analysis are given in terms of the expected excess risk, with more detailed results for the local empirical risk minimization. Experiments are conducted to verify the theory for local empirical risk minimization.", "summary_of_the_review": "This paper studies theoretical properties of retrieval based models from two perspectives. It develops expected excess risk for both cases, trying to show the factors impacting the risk, including the size of the retrieval set (which I believe is the most important one). The results are nice, but there are some discrepancies between the theoretical results and the empirical results, as well as some empirical practices.", "strength_and_weaknesses": "Strength:\n1. Divide the retrieval-based models into two categories: a local empirical risk minimization problem, and a classification problem in an extended feature space, which provides more clear directions for empirical designs.\n2. Detailed theoretical analysis on the local empirical risk minimization, which enable one to get better ideas on the underlying principles of the related retrieval-based models.\n3. Empirical results also verify part of the theoretical results.\n\nWeaknesses:\n1. The focus of the paper is somewhat disconnected with practical settings. This paper gives more theoretical analysis on the local empirical risk minimization setting, which is rarely applicable in practice, as it needs to learn a separate classifier for each testing samples, which is very expensive. In practice, the extended feature space setting is usually adopted. Unfortunately, there is only limited theoretical results for this case. Moreover, there is no experiments corresponding to the provided results for this setting, i.e., the experiments only focus on the local empirical risk minimization setting. I actually think experiments for the extended feature space is necessary, as from the theoretical results, it indicates that the retrieval set size needs to scale at least logarithmically in the size of the training set, which is somewhat contradicted with practical setting, where typically a few (e.g,, 10) retrieval data points are used while still being able to get good results. I would expect some empirical evidence to verify this claim.\n2. In the local empirical risk minimization setting, it is not clear how the retrieval set size impacts the generalization error. For the bound in Theorem 3.4, it seems to indicate that with larger retrieval set sizes, we can get smaller error. However, the empirical results indicates that larger retrieval set sizes can harm the performance if the classifier is too simple. I think this phenomenon is not reflected in the theoretical result. Is there a way to quantify this?\n\nAlso, do we know the increase rate of r in the (I) term in Theorem 3.4?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EZuriK8pGA", "reviewer": "Reviewer_bKCw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "", "summary_of_the_paper": "This paper aims to provide theoretical characterizations of the generalization abilities of retrieval-based models. Specifically, this paper focuses on classification problems and examines two classes of retrieval-based approaches: \n\n1. A local learning framework where a model is trained on retrieved examples and then used to make predictions for the test example.\n2. A global model that treats retrieved examples as augmented features and directly make make predictions for the test example.\n\nFor the local learning framework, an empirical study is conducted to verify the theoretical results for two cases: one that uses the Euclidean distance for retrieval and the other employs a global learned neural representation. The performance of locally trained models improves as more examples are retrieved until a point where the local empirical risk minimization fails due to the lack of model capacity. This empirical study demonstrates the effectiveness of the local learning framework that allows small models to attain competitive performance.\n\nDespite the complexity of theoretical analysis, the paper is presented in a way that the main points are clear and well-motivated. Since I am not an expert of the field, I was unable to verify the correctness of proofs; yet, the implication of the empirical study is straightforward and provides indirect support to authors’ argument. ", "summary_of_the_review": "See summary", "strength_and_weaknesses": "See summary", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "91oebXKOkR", "reviewer": "Reviewer_uQx9", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper is motivated by the empirical success of retrieval-based classification models and therefore studies the generalization properties of these models. The models that this paper touches on broadly involve models which retrieves similar labeled examples from training data for an instance. The question that this paper seeks to answer is to provide a theoretical framework that can help analyze the retrieval set in ensuring the empirical performance of retrieval-based models.\n\nThe mathematical setup that this paper proposes is as follows:\n- It considers a multi-class classification setting. There is a training set including i.i.d. samples.\n- It assumes that the underlying data distribution follows a local-regularity structures; this ensures there exists a low-complexity function class that approximates the Bayes optimal for the local classification problem defined by these locally retrieved samples.\n\nFrom a algorithm/model aspect, this paper focuses on two approaches:\n- Local empirical risk minimization first retrieves a neighboring set; then, it identifies a local scorer/function by minimizing the empirical risk of the local set.\n\n- Classification with extended feature space learns a common function over both the original instances and the retrieved neighboring labeled instances.\n\nThe main results of this paper provide generalization upper bounds for both of the above two approaches:\n- The generalization bounds generally depend on some function that depends on the size of the neighborhood retrieval set (in the generalization errors of local ERM), the local and global optimal losses.\n- A similar (albeit simpler) statement is stated for the second approach above.", "summary_of_the_review": "Overall this paper provides a study of the generalization properties of retrieval-based models (in the sense of learning with several retrieved similar examples with a test instance). The main results involve generalization error bounds for two approaches (local ERM and extended feature space learning) under a local regularity condition. As stated above, the technical contribution is limited and the bounds could benefit from better interpretation and connection with empirical examples. Therefore, I'm recommending a \"reject\" for this submission.", "strength_and_weaknesses": "Strength:\n- This paper formulates a theoretical study of the generalization properties of retrieval based models.\n- It also provides experiments to validate the generalization error bound.\n- The experiments show that the performance of local ERM varies with the size of the neighborhood. In particular, it observes a trend in which the accuracy generally increases with the size of the retrieval set but then decreases afterwards.\n\nWeakness:\n- The significance of the contributed generalization bound is unclear; although understanding the generalization properties of retrieval-based models is a valuable quest, the current bounds rely on specific data regularity conditions and are generally difficult to interpret. Here're some specific feedback:\n    - In eq (6), what does it mean that the complexity of $F^x$ is much less than the complexity of $F^global$?\n    - In theorem 3.4, are all of the terms stated in the generalization bound properly defined? it would help provide a pointer to the def. of each term.\n    - In theorem 4.1, you use $N(r, \\delta)$ in the text but $N(r, \\delta /n)$ in the equation. Is this due to a union bound over the training set?\n- From a quick gloss of the appendix, the techniques also seem standard in the literature, so the technical contribution is limited at best.\n    - It would also help if the main text could include some discussion about the technical contribution.\n- It is also unclear whether and how tight are the proposed generalization bounds.\n- The experiments are largely disconnected with the theoretical statements. There is a lack of elaboration about the benefits predicted by the theoretical results.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject