Reciprocal Learning
Authors: Julian Rodemann
Christoph Jansen
Georg Schollmeyer
Venue: NeurIPS 2024 poster (2024)
Keywords: Convergence
Decision Theory
Bandits
Active Learning
Self-Training
Semi-Supervised Learning
Online Learning
Primary area: learning_theory
TL;DR: We generalize active learning, self-training, multi-armed bandits, superset learning, and Bayesian optimization to reciprocal learning and give sufficient conditions for convergence.

Abstract: We demonstrate that numerous machine learning algorithms are specific instances of one single paradigm: reciprocal learning. These instances range from active learning over multi-armed bandits to self-training. We show that all these algorithms not only learn parameters from data but also vice versa: They iteratively alter training data in a way that depends on the current model fit. We introduce reciprocal learning as a generalization of these algorithms using the language of decision theory. This allows us to study under what conditions they converge. The key is to guarantee that reciprocal learning contracts such that the Banach fixed-point theorem applies. In this way, we find that reciprocal learning converges at linear rates to an approximately optimal model under some assumptions on the loss function, if their predictions are probabilistic and the sample adaption is both non-greedy and either randomized or regularized. We interpret these findings and provide corollaries that relate them to active learning, self-training, and bandits.

Reciprocal Learning
Julian Rodemann
Christoph Jansen Computing & Communications Lancaster University Leipzig c. jansen@lancaster. uk
Georg Schollmeyer Department of Statistics LMU Munich g. schollmeyerr@mmu
Department Statistics LMU Munich j .rodemann@mmu.cc de
Abstract
We demonstrate that numerous machine learning algorithms specific instances of one single paradigm: reciprocal learning. These instances range from active learning multi-armed bandits to self-training We show that all these algo- rithms not only learn parameters from data but also vice versa: They iteratively alter training data in way that depends the current model fit. We introduce reciprocal learning as a generalization of these algorithms using the language of decision theory. This allows us study under what conditions they converge. The key is to guarantee that reciprocal learning contracts such that the Banach fixed-point theorem applies. In this way, we find that reciprocal learning converges at linear rates to an approximately optimal model under some assumptions on the loss function, if their predictions are probabilistic and the sample adaption is both non-greedy and either randomized or regularized. We interpret these findings and provide corollaries that relate them to active learning, self ooffttrainnng, and bandits.
Introduction
The era of data abundance is drawing to close. While GPT-3 still had to make do with 300 billion tokens, Llaama 3 [022] was trained on 15 trillion. With the stock of high-quality data growing at
much smaller rate 667 adequate training data might run within this decade (58) 107]. Generally
and beyond language models, machine learning is threatened by degrading data quality and quantity [60]. Apparently, learning ever more parameters from ever more data is the exclusive route to success. Models also have to learn from which data to learn. This has sparked lot of interest in sample efficiency 770
92
27
105), J, subsampling [7 101 71]. coresets 62 76 86 data
subset selection [55
13 82
and data pruning [32 118
57
in recent years.
Instead of proposing yet another method along these lines, demonstrate that broad spectrum of well-established machine learning algorithms already exhibits a reciprocal relationship between data and parameters. That is, parameters not only learned from data, but data is also iteratively chosen based on currently optimal parameters with the aim of increasing sample efficiency. For instance, consider self-training algorithms in semi-supervised learning [106] 12 103 87 section 2.1 They iteratively add pseudo-labeled variants of unlabeled data to the labeled training data. The pseudo-labei. are predicted by the current model, and thus depend on the parameters learned by the model from the labeled data in the first place. Other examples comprise active learning [93].
Bayesian optimization (63 64| 198). superset learning [3| 34 85 36), and multi-armed bandits
81 see Appendix A for details.
In this paper, develop unifying framework, called reciprocal learning, that allows for principled analysis of all these methods. After an initial model to the training data, reciprocal learning algorithms alter the latter in way that depends on the fit. This dependence can have various facets, ranging from predicting labels (self-training) over taking actions (bandits) to querying an oracle (active learning), all based on the current model fit. It can entail both adding and removing data. Figure 7 illustrates this oscillating procedure and compares it to well-known illustration of classical
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

re
realization
deseet
dlosast
ruth
closest 1
mACA Daak
The population
(a) Classical machine lcarning
(b) Reciprocal learning
Figure 1: (A) Classical machine learning fits a model from the model space (restricted by red curve) to realized sample from the sample space (blue-grey); figure replicated from "The Elements of Statistical Learning" (3T] Figure 7.2]. (B) In reciprocal learning, the realized sample is no longer static, but changes in response to the model fit. Grey ellipse indicates restriction of sample space in f = 2 through realization in / 1. Sample in f thus depends on model in and sample in r 1.
machine learning. A pressing question naturally arises: Given the additional degrees of freedom these algorithms enjoy through data selection, can they at all reach a stable point; that is, can they converge? Convergence well-understood for classical empirical risk minimization (ERM), where refers to the sequence of model parameters. In reciprocal learning, however, we need to extend the notion of convergence the sequence of both parameters and data. It is self-evident that convergence is a desirable property of any learning algorithm. Only if an algorithm converges to a unique solution, we can identify unique model and use it for deployment or assessment on test data. Practically speaking, convergence of training procedure means that subsequent iterations will no longer change the model, giving rise to stopping criteria. Generally speaking, convergence a prerequisite for any further theoretical or empirical assessment of such methods. In the literature
reciprocal learning
algorithms like active learning, self-training, or multi-armed bandits, there is no consensus on when to
stop them. And while myriad of stopping criteria exist [109 121 48 TO 28 22
79 96 only
some come with generalization error bounds [41] 40 88 but none to the best of our knowledge
comes with rigorous guarantees of convergence. We address this research gap by proving convergence of all these methods under a set of sufficient conditions.
Our strategy will be to take theision- perspective on both the parameter and the data selection problem. While the former is well studied, in particular its ubiquitous solution strategy FRM, little attention is commonly paid to formal treatment of the other side of the coin: data selection. We particularly study the hidden interaction between parameter and data selection. We identify sample adaption function ff which maps from the sample and the empirical risk minimizer iteration to the sample in / + 1. Bounding the change of the sample + I by the change in the sample and the change in the model in r (i.e., f being Lipschitz-conttnnuut with sufficiently small constant) will turn out to guarantee convergence of reciprocal learning algorithms. In response to study which algorithms fulfill this restriction
this key finding, adaption is sufficiently Lipschitz for reciprocal learning to converge, if (1) it is non-greedy, i.e., probabilistic and (3) the selection of data is either randomized or regularized. Conclusively, we transfer these results to common practices active learning, self-training, and bandits, showing which algorithms converge and which do not.
We prove that the sample
it adds and removes data, (2) predictions
2 Reciprocal learning
Machine learning deals with two pivotal objects: data and parameters. Typically, parameters are learned from data through ERM. various branches machine learning, however, the relationship between data and parameters is in fact reciprocal, as argued above. In what follows, we show that this reciprocity corresponds to two interdependent decision problems and explicitly study how learned parameters affect the subsequent training data. We emphasize that our analysis focuses reciprocity

---

between parameters and training data only. The population and test data thereof are assumed to be fixed, i.e., our inference goal static. Specifically, we call machine learning algorithm reciprocal it performs iterative ERM on training data that depends on the previous ERM, see definition [ This dependence can be induced by any kind of data collection, removal, or generation that affected by the model fit. In particular, it can be stochastic (think of Thompson-sampling in multi-armed bandits) as well as deterministic in nature (think of maximizing a confidence score in self-training).
Definition 1 (Reciprocal Learning, informal). An algorithm that iteratively outputs O, arg min, (y-, E(Y, X. 0) shall be called reciprocal learning algorithm if
P = P(
where P, E SP are empirical distributions - frrm space of probability distributions -- Yf X of size ny in iteration i E {l....,T? T. Let E(Y, X. 0) E(Y, p(X,0) denote a loss function with p(X, 0) a prediction function that maps to the image of Further denote by Y, X random variables describing the training data, and 0, E O a parameter vector of the model in t.
In principle, the above definition needs no restriction on the nestedness between data in I and r - 1. In practice, however, most algorithms iteratively either only add training data or both add and remove instances, see extensive list of examples in appendix [ That is, data in is either superset of data i- 1 or a distinct set. We will address these two cases in the remainder of the paper, referring to the former as greedy (only adding data) and to the latter non non-greedy (adding and removing data). For classification problems, i.c., discrete image of Y. we typically have p(X. 0) = (g 0)) with : R [0. 1] sigmoid function and g X x θ - R. For regression problems, we simply have : X. x - R. The notation P, = f(0-1, F,-1, -1,1) shall be understood as a mere indication of the distribution's 's dependence ERM in the previous iteration. We will be more specific soon.
2.1 An illustrating running example: self-training
In appendix A we demonstrate at length that several well-established machine learning procedures turn out to be special cases of reciprocal learning as specified in defimition and more formally in definitions 6 and below. Here, we seek to illustrate the principles of reciprocal learning by the simple rumming example of self-training in semi-supervised learning (SSL) setup. The aim of SSL to learn a predictive classification function f(x, parameterized by utilizing both labeled and unlabeled data. Self-training is a popular algorithm class within SSL. Algorithms of that class start by fitting model on labeled data by ERM and then exploit this model to predict labels for the unlabeled data. In a second step, some instances of the unlabeled data are selected (according to "confidence
score", a measure of predictive uncertainty, see 22 49 80 83 53 84 [8] for examples) to be added to the training data together with the predicted labels. In other words, self-training algorithms label unlabeled data themselves and ultimately learn from these "pseudo-labels" by iteratively adding pseudo-labeled variants of unlabeled data to the labeled training data. The pseudo-labels are predicted by the current model, and thus depend on the parameters learned by the model from the labeled data in the first place. This latter dependence constitutes the sample adaption function in definition I The sample of labeled and pseudo-labeled data in / depends on the sample and the model (through its predicted pseudo-labels) in z 1. For more comprehensive and formal introduction of self-training, we refer the curious reader to appendix A.I
2.2 A theoreiii perspective
On a high level, reciprocal learning can be viewed as sequential decision decision-making. First, a parameter O, fitted through ERM, which corresponds to solving a decision problem characterized by the triple (0, A.,A. .L' with θ the unknown set of states of nature, the action space A = O of potential parameter fits (estimates), and loss function L À x - IR, analogous to classical statistical decision theory (6). Secondly, features e XX. are chosen and data points (x,, yr) are added to or removed from the training data inducing a new empirical distribution P,+1, where y, is predicted (self-training), queried (active learning) or observed (bandits). These features X, are found by solving another decision problem (O, A. L',), where - crucially - the loss function Lo, depends on the previous decision problem's 's solution 0, This time, the action space corresponds to the feature space A = X. Illustration 1. Think of reciprocal learning as a sequential decision-making problem:
== 1: 0 solves decision problem (6, O.))
2: 02 solves decision problem (0, e (o)
aj solves decision problem (0, A, Lo)
a2 solves decision problem (0. A. Lo.)
3

---

Loosely speaking, the data is judged in light of the parameters here. Excitingly, such an approach is symmetrical to any type of classical machine learning, where parameters are judged in light of the data. This twist in perspective will later pave the way for another type of regularization that of data, not of parameters. As the decision problem (0, ()) well-known through its solution strategy ERM, see definition 1 we want to be more specific about (0, A. ee,) with A XX. In particular, we need solution strategy for all of the loss functions in the family Le It x θ - I;; (x, 0) + L'e, (9,x) in iteration r. Definition 2 does the job. The family L'a describes all potential Ioss functions in the data selection problem arising from respective solutions of the parameter selection problem Redefining this family of functions as a single one L I x
- R makes clear that we can retrieve the decision criterion c .C. x Q - R from it, which is generalization of classical decision criteria e: : R retrieved from classical losses L x
R. see (6] for instance.
Definition 2 (Data Selection). Lete: : x+ - R be a criterion for the decision problem ( A., Lo,) with bounded A I of featuee to be added to the sample in iteration Define ē Xxx explc(x.0.) 00))
[0, 1]; (x, 0,) H I, expic(x', (dp(x) us standardized version thereof with μ the Lebesgue measure on X.. For a model 0, in iteration 1, it assigns to each feature fachfeature vector x a value between O and
that can be used as drawing probubilities. Drawing E X. according to ē(x, 02) shall be called stochastic data selection xx(0,) The function x : O - 0; + arg max C(x, 0r) shall be called deterministic data selection function.
The data selection function can be un- derstood as the workhorse of reciprocal learning: It describes the non-trivial part of the sample adaption function f. see definition [ For any model 0, in r, data selection function chooses a feature vector be added to the training data in I + 1, based on a criterion c. This hap- pens either stochastically through x, by drawing from X'' according to é or deter- ministically through xd. Examples for comprise confidence measures in self- training, acquisition functions in active ban-
Med caieei
doeni Mi
reguiraadd
Peatisten
restricted space
rugienadd M
restricted model space
Figure 2: Data regularization is symmetrical to classical regularization, see illustration in "The Elements of Statis- tical Learning" [1 Figure 7.2].
learning, or policies in multi- dits. For an example of stochastic data selection, consider to be the classical Bayes criterion 6 in (O, A. L.,). In this case, drawing from .C. as prescribed by x, corresponds to well-known Thompson sampling [12 90). As already hinted at, we will need some regularization (definition 33 of the data selection. Intuitively, the regularization term smoothes out the criterion c(., 0). In other words, the higher the constant +.2 the less the selection of data is affected by small changes of 9 for given R-). This is completely symmetrical to classical statistical regularization in ERM, where the regularization terms smoothes out the effect of the data on parameter selection, see also figure 2
Definition 3 (Data Regularization), Consider c: x R. a criterion for the decision problem (O, A. Lo,) with ē as in definition Define the following regularized (deterministic) data selection function:
c(xx 0)+ - R(x)
Xd. 2 X;
0
argmax XE.
where R() is a k-strongly convex regularizen. complete analogy to definition we can define stochastic regularized data selection functtionn as xx,x (0) by drawing x E X according to normalized version of c(x, () + (x).
I Like most other sequential decision-making problems, solving these decision problems by extensive search computationally explodes, both in the normal and extensive form (37 (88 Reciprocal learning thus corresponds a one-step look-ahead approximation. As such, it is method that aims at subtree solutions in the extensive form. Reciprocal learning can he understood infeasible extensive search.
compromise hetween the sub-optimal greedy strategy and
2 An alternative to stochastic data selection via direct randomization of actions discussed in appendix D

---

We will denote generic data selection function as t' E Xdd.R Xs,R in what follows. For the non-greedy variant of reciprocal learning, where data is both added and removed. we need define data removal as well. A straightforward strategy is to randomly remove data points with uniform removal probabilities. The following function w describes the effect of this procedure in expectation. Definition 4 (Data Removal Function). Given empirical distribution P(Y, X) of sample, the function w7 9 - X;; X) + XdP((X) shall be called data removal function.
2.3 Formal definition and desirable properties
In order to study reciprocal learning in a meaningful way, we need to be a bit more specific about how P, depends on empirical risk minimization / 1, and specifically on 0,-1. The following definition 3 of the sample adaption function allows for this. It will be the pivotal object in this work. The function describes in a general way and for any how empirical distributions of training data in are affected by the model, the empirical distribution of training data, and its size in / 1, respectively.
Definition 5 (Sample Adaption). Denote by @ a parameter space, by P a space of probability distributions of X and Y, and N the natural numbers. The function f @ x P x N - P shall be called the greedy and the function fn θ P - P the non non-greedy sample adaption function.
A greedy sample adaption function outputs distribution P'(Y, X) E P in the iteration after A E Q solved ERM on a sample of size n E N described by P(Y.X) E P, which led to an enhancement of the training data that changed PYY, X) to P X). It will come in different flavors for different types of algorithms, see examples in section A. Generally, we have f(0, P(Y, X), n) = PY,, X), with P' P'(Y, x) being induced by
P' = -1x=1,xxx) / f(x===
1(x =(x==(0)) z(0)) x(0(0), 0) P = -1 P3 dy Pe dx,
(1)
in case of y (0, 1). where X' O {0. 1} any function that assigns label y. potentially based on the model 0, to selected x, and w any function that selects features given a model 6, for example, xd. xy. .ud.Rt or Xs.R as defined above. They give rise to P3 and Ps. respectively. We can be so specific about the sample adaption function due to P(Y = 1, X = x) P(X = x) - P(Y 0, X x) in binary classification problems. We can analogously define the non- con-greedy variant fn (0 P.Y. X)). where one instance is removed by w and one instance is added by w per iteration. To this end, define P'(Y 1, x) by replacing the integrand in equation (1) by
1(x (0)) 3 ( (0), 0) P(Y 1, X= 1(x w (P(Y, w (P(Y, ()),))),)
no
where no is the size of the initial training data set. Notably, we observe that both sample adaption functions entail a reflexive effect of the model on subsequent data akin to performative prediction
(99 section 5 for a discussion.
We can now define reciprocal learning (definition I more formally given the sample adaption function as follows, both in greedy and non-greedy flavors.
Definition (Greedy Reciprocal Learning). With O, SP, X. Y, and N as above, we define
R: 10XPXN
-0XPXN
((.P(Y, - ((.
as reciprocal learning, where O' arg m B(r (r, ((Y))((YXX,,) X, and PY S0, , X), n) as well n' n with f a sample adaption function, function see definition 5 Note the equivalence to the informal recursive definition with (0,-1,P(Y) X),-1,
P(Y, X),
Definition 7 (Non-Greede Reciprocal Learning). With θ P, X, and Y as above, we define
10x0 Ø R,
-0x x P: (0, - (O.,P((Y
as reciprocal learning, where (Y, = fa X)) and 6' arg ming ((xx))-F(XX)) ((YXX,0)
with fo non- non-greedy sample adaption function, see definition
5

---

We introduce two desirable properties of reciprocal learning. First, we define convergence as a state in which the model stops changing in response to newly added data. This kind of stability allows to stop the process in good faith: Hypothetical subsequent iterations would not have changed the model. g offers a straightforward way of formalizing this, implying standard Cauchy convergence. Definition
Definition& 8 (Convergence of Reciprocal Learning). Let N - R be strictly monotone decreasing function and (R)) any (non-greed (non-greedy) reciprocal learning algorithm (definitions (andd)) outputting R2 (Rna) in iteration I. Then
(R, Ra is said to converge if ejll s g(t) for all k. 2 1, and oo 8 = 0, where || || is norm on the codomains of R and Rn, respectively. In this case, define Qc E (Rc, Rn.c) as the limit of this convergent sequence e.
Contrary to classical ERM, convergence of reciprocal learning implies stability of both data and parameters. Technically, it refers to all components of the functions R and R,, respectively, see definition 8 It guarantees that f,-1 solves ERM on the sample induced by it in However, this does not say much about its optimality in general. What if the algorithm had outputted a different 0111 in the first place? The empirical risk could have been lower on the sample in induced by it. The following definition describes such look-ahead optimality. It can be interpreted as the optimal aata-parameter combination.
Definition 9 (Optimal Data- ParamParrreter Combination). Consider (non-greedy) reciprocal learning R (Rn), see definitions 6 and 7 Define R' and R as optimal data-parameter combination in reciprocal learning if R = (6,, "n) nn) = arg ming.r B( (X-f1.P)) E(Y, 0) and R* = =6", nn" arg ming,2,n (( {(Y, X, 6), respectively.
An optimal 6* (or 6% analogously) not only solves ERM on the sample it induces, but is also the best ERM-solution among all possible 0 (0,,) that could have led to optimality on the respectively induced sample. In other words, 0 (0%) is found by minimizing the empirical risk with respect to whole R (R,). That is, it is found by minimizing the empirical risk with respect to @ given sample (characterized by PP and n) and steering this very sample through 9 simultaneously given only the initial sample. Technically, optimality (definition ? is a bivariate arg min-condition on E (1y,))_(((.. {(Y, X, 0) and By (0..())).)) ((Y, X, 0), respectively. In contrast, convergence (definition translates to a fixed-point poiitpoint condition the arg min viewed as function θ x S x N x f x N case of R and as 2 x s - θ sP in case of R,, see section
2.4 Self-training is an instance of reciprocal learning
Let us get back to our running example of self-training. It is easy to see that self-training is a special case of reciprocal learning with the sample adaption function fSsL O x P; (0, - PY,,, X) defined through P)) being induced by
/ 1(x 1(x=x(0) ((x) 0) + nP(Y 1, x Prix Px dx (3)
P'YY ,(
n n+1
where (0) (definition 2 selects data with highest "confidence score" 2
80
83
53
84
18), see section 2.1, according to the model 9 and gives rise to Px. The prediction function y: x O - [O.T] returns the predicted "pseudo-label" of the selected x, (0) based on the learned still assume binary target variables, i.e., the image Y is (0, 1). real-valued features X, and only consider cases where the sample changes through the addition of one instance per iteration The averaging with respect to Px and Prix accounts for the fact that we allow stochastic inclusion of X in the sample through randomized actions and for probabilistic predictions of Y X, respectively. For now, however, it suffices think of the special case of degenerate distributions Px and Prix putting point mass on data with hard labels in the sample and 0 elsewhere 4 Through averaging with respect to Prix we can describe the joint distribution of hard labels (y1,x))..... ())....()....... and predicted soft labels y p(Y 1 xx 8) [0. 1] (wez). Summinn up, both deterministic data selection and non prbobbbbaii
model 0 and gives rise to Prix. Moreover,
of (p+1)...)....................... (i.e.. hard labels) predictions are well-defined special cases of the above with Pr|x and Px collapsing to trivial Dirac measures, respectively.
3 case more than one instance is added per iteration, the sample adaption function can be defined as a composite function of the used sample adaption functions.
In this case, P(Y 1.X x) 1(x=x(#)) ((x,))))))xx)))))))))))))))))))) P0

---

3 Convergence of reciprocal learning: Lipschitz is all you need
After having generalized several widely adopted machine learning algorithms to reciprocal learning, we will study their convergence (definition ( and optimality (definition 9 Our general aim is to identify sufficient conditions for any reciprocal learning algorithm to converge and then show that such a convergent solution is sufficiently close to the optimal one. This will not only allow to assess convergence and optimality of examples | through 3 (self-training, active learning, multi-armed bandits, see appendix A but of any other reciprocal learning algorithm. Besides further existing examples not detailed in this paper like superset learning [35] or Bayesian optimization [63), we are especially aiming at potential future yet to be proposed algorithms. On this background, our conditions for convergence and optimality can be understood as design principles. Before turning to these concrete conditions on reciprocal learning algorithms,, we need some general assumptions on the loss function for the remainder of the paper. [ and can be considered quite mild and are fulfilled by a broad class of loss functions, see [95] Chapter 12] or (14). For instance, the L2-regularized (ridge) logistic loss has Lipschitz-contimuuus gradients both with respect to features and parameters. For a discussion of assumption 3 we refer to appendix E.2
Features). A loss function E(Y, X) is said to be continuously differentiable with respect to features if the gradient Vxt(Y, X, 0) exists and is a-Lipschitz continuous in 8, x, and y with respect to the L2-norm on domain and codomain.
Assumption 1 (Continuous Differentiability
Assumption 2 (Continuous Differentiability in Parameters). A loss function E(Y, X, 0) is continuously differentiable with respect to parameters if the gradient Vol(Y, X, 0) exists and is B-Lipschitz continuous in 0, x, and with respect to the L2-norm Assumption 3 (Strong Convexity)- Loss E(Y, X, 8) is said to be y-strongly convex if Ely, x, f) 2 f (y,x, 0'+ + Vol (y.x,0') (0- - 0') + 2 ||0 - 0'112 for all 0, 0', y.x. Observe convexity for y = O.
domain and codomain.
Let us now turn to specific and more constructive conditions on reciprocal learning's workhorse, the data selection problem (o)) At the heart of these conditions lies common goal: We want to establish some continuity in how the data changes from / - 1 to in response to 0 and P,-1. It is self-evident that without any such continuity, convergence seems out of reach. As will turn out, bounding the change of the data in by the change of what happens in / - 1 will be sufficient for convergence, see figure We thus need the sample adaption function (definition [5) to be Lipschitz-continuouss continuous. Theorem will deliver this for subsets of conditions [ through in case of binary classification problems. The reason for the latter restriction that we need an explicit definition of f to constructively prove its hipschitz-comtinnii
Condition 1 (Data Regularization), Data selection is regularized as per definition 3
Condition 2 (Soft Labels Prediction). The prediction function ÿ -X' x θ - {0, 1) on bounded X gives rise to a non-degenerate distribution Y X for any such that we can consider soft label
predictions p : X' x θ - [0, 1] with p(x, f) = o (g(X, X, O)) with o : R - [0. 1] a sigmoid function. Further, assume that the loss is jointly smooth in these predictions. That is, Vpl(y. 0)) exists and is conttitzz-o in x and 0.
Condition 3 (Stochastic Data Selection). Data is selected stochastically according to x, by drawing exple(x,0;))
from a normalized criterion T. csp(e(xx...)))dxts see definition
Condition 4 (Continuous Selection Criterion). holds for the decision criterion c: -X' x θ R in the decision problem (O, A., L of selecting features to be added to the sample that V cxc(x, 0) and Vec(x, 0) are bounded from above.
Condition 5 (Linear Selection Criterion). The decision criterion X x θ - R. in (0, A. Le, is linear in x and Lipschitz-contiiuunn in 0 with a Lipschitz constant Le that is independent from x.
We can interpret as PY x) in condition 2 see also definition I In other words, soft labels in the form of probability distributions are available. Adding observations with soft labels the data can be implemented either through randomization, i.e., by adding x with label I with probability and vice versa, or through weighted retraining. Note that condition X implies condition (5) through characterization of Lipschitz-comtinnt conditions to establish Lipschizz-continuig of the sample adaption in reciprocal learning. First, can be shown that regularized data selection (condition I is Lipschitz-continuous in the model, see lemmal] | Second, the soft label prediction function (condition 2 Lipschitz in both data and model, if the data selection, in turn, is Lipschitz-comtinuuus in the model, see lemma 2
by bounded gradients. We need two implications of these
7

---

Lemma (Regularized Data Selection is Lipschitz). Regularized Data Selection
xd I;; 0 H argmax x=x
c(x, 0) Rxx)
L2
with k-strongly convex regularizer, see definition 3 and condition is Ludt Lipschitz continuous,
if e is linear in x (condition 5 and Sopschizz-onttinen in 0 with a Lipschitz constant Le that is
independent of
Lemma (Soft Label Prediction is Lipschitz). The soft label prediction function (condition
_] (w(()) () dy Podw
p D x x (000)000000))00000,,000
Lipschitz-continuuus in both x X and E 2 and (x, 0) x x if Pad is Lipschitz-
continuous.
Proofs of all results in this paper can be found in appendix F] With the help of lemma | and we are now able to state two key results. They tell us under which conditions the sample adaption functions both greedy and non-greedy reciprocal learning are Lipschitz-continuuus which will turn out to be sufficient for convergence.
Theorem (Regularization Makes Sample Adaption Lipschit--Continuuss If predictionn are soft (condition 2) and the data selection is regularized (conditions [add S both greedy and non-greedy sample adaption functions f and fn (see definition 5) in reciprocal learning with y (0, 1} are on P. Theorem (Randomization Makes Sample Adaption Lipschitz-Continuuui Continuous). If predictions are soft (condition 2 and the data selection is randomized (conditions and + greedy and non-greedy sample adaption functions are Lipschit--cominnuuss in the sense of theorem 7
continuus with respect to the L2-Rorm O and N, and the Wussersteinn-I-ditaam
The general idea for both proofs to show Lipschitz-continuity component-wise and then infer that and fn are Lipschitz with the supremum of all component-wise Lipschitz-constants We can now leverage these theorems to state our main result. It tells us (via theorems [ and and conditions
I
which types of reciprocal learning algorithms converge. Recall that convergence (definition g
reciprocal learning implies convergent model and a convergent data set.
Theorem 3 (Convergence of Non-Greedy Reciprocal Learning). the non-greedy sample adaption fn Lipschitz-continunni with (1 7 f)-1, the iterates Rn, (0,,P,) of non-greedy reciprocal learning R, (definition 7 converge to R,,c (f,.Pc) at a linear rate.
The proof idea is as follows. We relate the Lipschitz-continitty of fn the Lipschitz- continuity of R, via the dual characterization of the Wasserstein metric [43]. If fn Lip- schitz with < (I (1+))=1. we further show that R, is a bivariate contraction. The Banach fixed-point theorem [
72 [7] then directly delivers uniqueness and existence of (0c. F.) convergent fixed point, which means that it holds 0, = arg ming E(r,x)-(10,5 complete proof can be found in appendix [.5 Building on earlier work on performatively op- timal predictions [73], we can further relate this convergent training solution to the global so- lution of reciprocal learning, i.c., the optimal Mata-parameter fit, see definition [ The follow- ing [accormm[ssaaee that our convergent solution is close to the optimal one. It tells us that we did not enforce trivial or even degenerate form of convergence (e.g., constant 0,) by regularization and randomization. Theorem only refers to the convergent parameter solution, not to the data. Note that the parameter solution is the crucial part of reciprocal learning for later deployment and assessment test data.
d(F" (P LLS
truth
Lipschitz condition on
sample adaption x
((Y, X, 0).
rathor than
omprirical risk minimization P
Figure 3: Reciprocal learning converges if the change in sample (purple) is bounded by the change in model (yellow) and previous sample.

---

Theorem 4 (Optimality of Convergent Solution). If non iton-greedy reciprocal learning converges in the sense of theorem 3 it holds ||0 0 I 2LL for 0g and O³ from the convergent data-paramerd tuple R,, (0cs F and the optimal one R (0", ) if the loss is Lt- L--ipsccittz in X and Y.
y
While theorem I and 2 guarantee that both greedy f and non-greedy fn are Lipschitz, theorem 3 and thus also theorem 4 only hold for non-greedy reciprocal learning. The question immediately comes to mind whether we can say anything about the asymptotic behavior of the greedy variant, too. The following theorem 5
gives affirmative answer. Intuitively, there no fixed point in O S N if data is constantly being added and not removed such that n - 00.
Theorem 5. Greedy Reciprocal Learning does not converge in the sense of definition
g
We conclude this section with another negative result. It states that theorem 3is tight in theorem | and Summing things up, Lipschitz-continutty is all you need for non con-greedy reciprocal learning to converge.
Theorem 6. If the sample udaption fu is not Lipschitz, non-greedy reciprocal learning can diverge.
4 Which reciprocal learning algorithms converge?
We briefly relate the above results to specific algorithms in active learning, bandits, and our running example of self-training. Assume binary target variable and I. s (1 +) with y and / in the sense of assumption I throughout. First observe that any greedy (definition 6 algorithm that only adds data without removal does not converge in the sense of defintion [ with respect to 6, P, and n, see theorem [ This provides a strong case for non- gen-greeyy self seff-training algorithms, often referred to as amending strategies [103) or self- self-training with editing (52) and noise filters [104). that add and remove data, as opposed to greedy ones like incremental or batch-wise self-training (103), see example 1 that only add pseudo-labeled data without removing any data. For detailed explanation and comparison of the two, please refer to Appendix [.p..
Corollary 1 (Self- Training). Amending self feff-traaning algorithmss converge in the sense of definition g
if predicted pseudo-labet labels are soft (condition) 2 and data selection is regularized (condition or randomized (condition 3
Furthermore, we shed some light on the debate 99 120 in the literature on aulti-armed bandits
about whether to use deterministic strategies like upper confidence bound [10
100
42
or stochastic
ones like epsilon-greede [45 54] search or Thompson sampling (89 90 see example 3 Note,
however, that this insight relates to in-sample convergence only, definition
g
Corollary 2 (Bandits). grn-gy multi-armed bandits with Thompson sampling and epsilon- strategies converge in the sense of definition 8 under additional condition 2
while bandits with upper
confidence bound (UCB) are not guaranteed to converge.
What is more, condition 2 allows us to distinguish between active learning from weak and strong oracles, see (59] 93 78] for literature surveys. The former posits the availability of probabilistic or
noisy oracle feedback through soft labels [59
T14 117|: the latter assumes the oracle have access
to an undeniable ground truth via hard labels 26
19 10].
Corollary 3 (Active Learning). Active Learning from a strong oracle (i.e., providing hard labels) is not guaranteed to converge, while active learning from weak oracle (soft labels) converges in the sense of definition under additional condition or
Related work
Convergence of active learning, self-training, and other special cases of reciprocal learning has been
touched upon in the context of stopping criteria [109 121
48
110
28
22
83
79 96). We refer
to section [ for discussion and relate reciprocal learning to other fields in what follows.
While reciprocity through, e.g., gradient-based data selection is a known phenomenon in continual learning [1] 112 15 the inference goal is not static as in reciprocal learning. Continual learning rather aims at excelling at new tasks (that is, new populations), while reciprocal learning can simply be seen as greedy approximation of extended ERM, see section 2
Continual Learning:

---

Online Learning: In online learning and online convex optimization, the task is to predict by y from iteratively receiving x. After each prediction, the true y and corresponding loss E(y. 3) is observed, see (94) for an introduction and appendix B.2 for an illustration. Reciprocal learning can thus be considered special online learning framework. Typically, online learning assumes incoming data to be randomly drawn or even selected by an adversarial player, while being selected by the algorithm itself in reciprocal learning. The majority of the online learning literature is concerned with how to update model in light of new data, while we focus on how data is selected based on the current model fit. Loosely speaking, online learning deals with only one side of the coin explicitly, while we take reciprocal point of view: We study both how to learn parameters from data and how to select data in light of fitted parameters.
Coresets:
The aim of coreset construction is to find subsamples that lead to parameter fits close to the originally learned parameters [62]
68 33.. can be seen as post hoc approach, while reciprocal learning algorithms directly learn "parameter-fffcient" sample on the go.
76 69
Performative Prediction: The sample adaption functions in reciprocal learning are reminiscent of performative prediction, where today's 's predictions change tomorrow's 's population [74] 29 61].
and, more generally, of the "reflexivity problem" in social sciences (99 66). We identify analogous reflexive effects on the sample level in reciprocal learning via the sample adaption function f (or fn), see section _ Contrary to performative prediction, however, I (fr) describes an in- in-salle (performative prediction: population) reflexive effect of both data and parameters (performative prediction: only parameters). Moreover, reciprocal learning describes specific and implementable algorithms, which allows for an explicit study of these reflexive effects. While we rely on similar and Wasserstein- distancee, our work is thus conceptually different. For an illustration of these differences, see appendix [.11
techniques as in (74 [T]. namely Lipschitz-contin
Safe active learning explores the feature space by optimizing an acquisition criterion under a safety constraint [122] 51, 91]. While this can be viewed as regularization akin to the one we propose in definition 3 both aim and structure are different: We want to enforce explicitly via a penalty term in data selection; safe active learning optimizes a selection criterion without penalty terms under constraints that are motivated by domain knowledge.
Safe Active Learning:
Discussion
We have embedded a wide range of established machine learning algorithms into unifying framework, called reciprocal learning. This gave rise to a rigorous analysis of (1) under which conditions and (2) how fast these algorithms converge to approximately optimal model. We further applicd these results to common practices in self-training, active learning, and bandits.
Summary:
While our results guarantee the convergence of reciprocal learning algorithms, the opposite does generally not hold. That is, if our conditions are violated, we cannot rule out the possibility of (potentially weaker notions) of convergence, Furthermore, our analysis requires assumptions on the loss functions, as detailed section Saationnaaad and appendix [E] In particular, it needs to be y-strongly convex and have B-Lipschitz gradients, such that L S (1+ -1 with the Lipschitz- constant of the sample adaption. This limits our results' applicability. From another perspective, however, this is feature rather than bug, since the described restrictions can serve design principles for self-training, active learning, or bandit algorithms that shall converge, see below.
Limitations:
This article identifies sufficient conditions for convergence of reciprocal learning. These restrictions pave the way for a theory-informed design of novel algorithms. In particular, our results emphasize the importance of regularization of both parameters and data for convergence. While the former is needed to control y and B. see appendix E.2 for the example of Tikhonov- regularization, the latter guarantees Lipschitz-continuity of the sample adaption through theorem [] Parameter regularization is well-studied and has been heavily applied. We conjecture that the concept of data regularization might bear similar practical potential. Another line of future research would be to address the question whether reciprocal learning algorithms are stable with respect to slight changes in the initial training data. In this sense, 30 might serve as a bridge to future research.
Future Work:
10

---

Acknowledgements
We sincerely thank Thomas Augustin, James Bailie, and Lea Höhler for helpful comments earlier versions of this manuscript. We also thank all four anonymous reviewers for their assessment of our paper. Moreover, we are indebted several participants of the 2024 Workshop on Machine Learning under Weakly Structured Information in Munich for critically assessing preliminary ideas and conjectures regarding reciprocal learning presented at the workshop.
Julian Rodemann acknowledges support by the Federal Statistical Office Germany within the co-operation project "Machine Learning in Official Statistics", the Bavarian Academy of Sciences (BAS) through the Bavarian Institute for Digital Transformation (bidt), and the LMU mentoring program of the Faculty of Mathematics, Informatics, and Statistics.
References
[1] Rahaf Aljundi et al. "Gradient based sample selection for online continual learning". In: Advances Neural Information Processing Systems. Ed. by H. Wallach al. Vol. 32. Curran Associates, Inc., 2019.
[2] Eric Arazo et al. "Pseudo-labeling and confirmation bias in deep semi- semi-supperiied learning". In: 2020 International Joint Conference on Neural Networks. IEEE. 2020, pp. 1-8.
[3] Peter Auer, Nicolo Desa-BBanchii, and Paul Fischer. "Finite-time analysis of the multiarmed bandit problem". In: Machine learning 47 (2002). pp. 235-256.
[4] Stefan Banach. "Sur les opérations dans les ensembles abstraits leur application aux équations intégrales". In: Fundamenta mathematicae 3.1 (1922), pp. 133-181.
[5] Emanuel Ben- Baruchrrcchh et al. "Distilling the Knowledge in Data Pruning". In: arXiv preprint arXiv:2403. 07854 (2024).
[6] James O. Berger. Staristical decision theory and Bayesian analysis. 2nd. Springer, 1985.
[7] Surojit Biswas et al. "Low-N protein engineering with data-efficient deep learning". In: Nature methods 18.4 1). pp. 389-396.
[8] Olivier Bousquet and André Elisseeff. "Stability and generalization". In: The Journal of Machine Learning Research (2002). pp. 499-526.
[9] Tom Brown et al. "Language models are few-shot learners". In: Advances in neural informa- tion processing systems 33 (2020), pp. 1877-1901.
[10] Alexandra Carpentier et al. "[pper-confiddeneebooo
algorithms for active learning in multi- armed bandits". In: International Conference on Algorithmic Learning Theory. Springer. 2011, pp. 189-203.
[1I] Deepayan Chakrabarti et al. "Mortal multi-armed bandits". In: Advances in neural information processing systems 21 (2008).
[12] Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-supervised learning. Adap- tive computation and machine learning series. MIT Press, 2006.
[13] Anshuman Chhabra et al. "What data benefits my classifier? Enhancing model performance and interpretability through influence-based data selection". , In: International Conference on Learning Representations. 2024.
[14] Geoffrey Chinot, Guillaume Lecué, and Matthieu Lerasle. "Robust statistical learning with Lipschitz and convex loss functions". In: Probability Theory and related fields 176.3 (2020), pp. 897-940.
[15] Aristotelis Chrysakis and Maaic-Francine Moens. "Online Continual Learning from Imbal- anced Data". In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, 13-18 Jul 2020, pp. 1952-1961.
[16] David A Cohn, Les Atlas, and Richard Ladner. "Improving generalization with active learn- ing". In: Machine Learning 15.2 (1994), pp. 201-221.
[17] Patrick Combettes and Jean-Christophe Pesquet. "Fixed point strategies in data science".
In: IEEE Transactions on Signal Processing 69 (2021), pp. 3878-3905.
[18] Stefan Dietrich, Julian Rodemann, and Christoph Jansen. "Semi-Supervised Learning guided by the Generalized Bayes Rule under Soft Revision". arXiv preprint arXiv:2405.I /5294 (2024).
11

---

[19] Shi Dong. "Multi class SVM algorithm with active learning for network traffic classification". In: Expert Systems with Applications 176 (2021), p. 114885.
[20] Liat Ein Dor et al. "Active learning for BERT: an empirical study". In: Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP). 2020, pp. 7949-7962
[21]
Dheeru Dua and Casey Graff. UCI Machine Learning Repository. httt:://archveer ics
uci uciiedu/ml 2017.
[22]
Hyal Even-Dar al. "Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems." In: Journal of machine learning research 7.6 (2006). Gabriele Farina et al. "Stable- caable-predictive optimistic counterfactual regret minimization". In: International conference on machine learning. PMLR. 2019, pp. 1853-1862.
[23]
[24] Susanne Frick, Amer Krivosija, and Alexander Munteanu. "Scalable Learning of Item Re- sponse Theory Models". In: Proceedings of The 27th International Conference on Artifi- cial Intelligence and Statistics. Ed. by Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li. Vol. 238. Proceedings of Machine Learning Research. PMLR, Feb. 2024, pp. 1234-1242.
[25] Yarin Gal, Riashat Islam, and Zoubin Ghahramani. "Deep bayesian active learning with image data". In: International conference on machine learning. PMLR. 2017, pp. 1183-1192.
[26] Mingfei Gao et al. CConsistency-basee semi-supervised active learning: Towards minimizing labeling cost". In: Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part X 16. Springer. 2020, pp. 510-526.
[27] Laura Graves, Vineel Nagisetty, and Vijay Ganesh. "Amnesiae machine learning". In: Pro- ceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. 13. 2021, pp. 11516- 11524.
[28]
Edita Grolman et al. "How and when to stop the co-training process". In: Expert Systems with Applications 187 (2022), p. 115841.
[29]
Moritz Hardt and Celestine Sendler-Dünnner, "Performative Prediction: Past and Future". In: Xrviv preprint arXiv:2310. 16608 (2023).
[30] Moritz Hardt, Ben Recht, and Yoram Singer. "Train faster, generalize better: Stability of stochastic gradient descent". In: Proceedings of The 33rd International Conference on Ma- chine Learning. Ed. by Maria Florina Balcan and Kilian Q. Weinberger, Vol. 48. Proceedings of Machine Learning Research. New York, New York, USA: PMLR, 20-22 Jun 2016, pp. 1225-1234.
[31] Trevor Hastie et al. The elements of statistical learning; data mining, inference, and prediction.
Vol. 2. Springer, 2009.
[32] Shuo He et al. "Candidate Label Set Pruning: A Data-centric Perspective for Deep Partial- label Learning". In: The Twelfth International Conference on Learning Representations. 2023.
[33] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. "Coresets for scalable Bayesian logistic regression". In: Advances in neural information processing systems 29 (2016).
[34] Eyke Hüllermeier. "Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization". In: International Journal of Approximate Reasoning 55 (2014), pp. 1519-1534.
[35] Eyke Hüllermeier and Weiwei Cheng. "Superset learning based on generalized loss mini- mization". In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer. 2015, pp. 260-275.
[36] Eyke Hüllermeier, Sébastien Destercke, and Ines Couso. "Learning from imprecise data: adjustments of optimistic and pessimistic variants". In: International Conference on Scalable Uncertainty Management. Springer, 2019, pp. 266-279.
[37] Nathan Huntley and Matthias Troffaes. "Subtree perfectness, backward induction, and normal- extensive form equivalence for single agent sequential decision making under arbitrary choice functions". : In: arXiv preprint arXiv: wtepii19.336000 (2011).
[38] Nathan Huntley and Matthias CM Troffaes. "Normal form backward induction for decision trees with coherent lower previsions". In: Annals of Operations Research 195.1 (2012), pp. 111-134.
[39] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge university press, 2015.
12

---

[40] Hideaki Ishibashi and Hideitsu Hino. "Stopping criterion for active learning based on deter- ministic generalization bounds". In: International Conference on Artificial Intelligence and Stafistics. PMLR. 2020, pp. 386-397.
[41] Hideaki Ishibashi and Hideitsu Hino. "Stopping criterion for active learning based error stability". In: arXiv preprint arXiv:2104.01830 (2021).
[42] Anand Kalvit and Assaf Zeevi. "A closer look at the worst-case behavior of multi-armed bandit algorithms". In: Advances in Neural Information Processing Systems 34 (2021), pp. 8807-8819,
[43]
Leonid Vasilevich Kantorovich and SG Rubinshtein. "On space of totally additive functions".
In: Vestmik of the St. Petersburg University: Mathematics 13.7 (1958), pp. 52-59. William Karush. "Minima of functions of several variables with inequalities as side con- straints". In: M. Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago (1939). Volodymyr Kuleshov and Doina Precup. "Algorithms for multi-armed bandit problems". In:
[44]
[45]
arXiv preprint arXiv: /402.6028 (2014).
[46] Yongchan Kwon et al. "Datainf: Efficiently estimating data influence in lora-tuned Ilms and diffusion models". In: arXiv preprint arXiv:2310.000 110.00902 (2023).
[47] Hunter Lang, Aravindan Vijayaraghavan, and David Sontag. "Training subset selection for weak supervision". In: Advances in Neural Information Processing Systems 35 (2022), pp. 16023-16036.
[48] Florian Laws and Hinrich Schüize. "Stopping criteria for active learning of named entity recognition".. In: Proceedings of the 22nd International Conference on Computational Lin- guistics (Coling 2008). 2008. pp. 465-472.
[49] Dong-Hyun Lee al. "Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks". In: Workshop on challenges in representation learning, International Conference on Machine Learning. Vol. 2013, p. 896.
[50] David Lewis and William Gale. "A sequential algorithm for training text classifiers". In: SIGIR '94: Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval. Springer. 1994, pp. 3-12.
[51] Cen- You Li, Barbara Rakitsch, and Christoph Zimmer. "Safe active learning for multi-output gaussian processes". In: International Conference on Artificial Intelligence and Statistics.
PMLR. 2022, pp. 4512-4551.
[52] Ming Li and Zhi-Hua Hua Zhou. "SETRED: Self-training with editing". In: Pacific-Asia Confer- ence on Knowledge Discovery and Data Mining. Springer. 2005, pp. 61 6-1-621.
[53] Shuangshuang Li et al. "Pseudo-label selection for deep semi-supervised learning". In: 2020 IEEE International Conference on Progress in Informatics and Computing (PIC). IEEE. 2020, pp. 1-5.
[54] Tian Lin, Jian Li, and Wei Chen. "Stochastic online greedy learning with semi-bandit feed- backs". In: Advances in Neural Information Processing Systems 28 (2015).
[55] Wei Liu et al. "What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning". In: arXiv preprint arXiv:2212.15568 (2023).
[56] Debmalya Mandal, Stelios Triantafyllou, and Goran Radanovic. "Performative reinforcement learning". In: International Conference on Machine Learning. PMLR. 2023, pp. 23642- 23680.
[57] Max Marion al. "When less is more: Investigating data pruning for pretraining Ilms at scale". In: arXiv preprint arXiv:2309.0m 234404430 (2023).
[58] Nestor Maslej et al. "Artificial intelligence index report 2023". In: arXiv preprint arXiv:2310.03715 (2023).
[59] Björn Mattsson. "Active learning of neural network from weak and strong oracles". In: (2017).
[60]
Lara Mauri and Ernesto Damiani. "Estimating degradation of machine learning data assets". In: ACM Journal of Data and Information Quality (JDIQ) 14.2 (2021), pp. 1-15.
[61] John P Miller, Juan C Perdomo, and Tijana Zmnie "Outside the echo chamber: Optimizing the performative risk". In: International Conference on Machine Learning. PMLR. 2021, pp. 7710-7720.
13

---

[62] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. "Coresets for data-efficient training of machine learning models". In: International Conference on Machine Learning. PMLR. 2020, pp. 1950-6960.
[63] Jonas Močkus. "On Bayesian methods for seeking the extremum". In: Optimization Tech- niques IFIP Technical Conference: Novosibirsk, July 1-7, 1974. Springer. 1975, pp. 400- 404.
[64]
Jonas Močkus, Vytautas Tiesis, and Antanas Zilinskas. "The application Bayesian methods for seeking the extremum". In: Towards global optimization 2.117-129 (1978), p. 2.
[65] Robert Munro Monarch. Human-in-the-LLog Machine Learning: Active learning and annola- tion for human-centered Al. Simon and Schuster, 2021.
[66] O Morgenstern. "Wirschhffsprognosee Eine Untersuchung ihrer Voraussetzungen und Möglichkeiten, Wien 1928, cited after: G. Betz (2004), Empirische und aprioristische Gren- zen von Wirtschaftspronnosenn Oskar Morgenstern nach 70 Jahren". In: Wissenschafistherrie in Ökonomie und Wirtschaf/sinformatii,, Deutscher Universitäts-Verree Wiesbaden (1928), pp. 171-190.
[67]
Niklas Muennighoff et al. "Scaling data-constrained language models". In: Advances in Neural Information Processing Systems 36 (2024).
[68] Alexander Munteanu and Chris Schwiegelshohn. "Cothsets-Methods and History: A Theo- reticians Design Pattern for Approximation and Streaming Algorithms". In: KI Künstliche Intelligenz 32.1 (Feb. 2018), 37-53. ISSN: 1610-1987.
[69] Alexander Munteanu et al. "On Coresets for Logistic Regression". In: Advances in Neural Information Processing Systems. Ed. by Bengio al. Vol. 31. Curran Associates, Inc.,
2018 8.
[70] Ofir Nachum et al. "Data-efficient hierarchical reinforcement learning". In: Advances in neural information processing systems 31 (2018).
[71] Malte Nalenz, Julian Rodemann, and Thomas Augustin. "Learning de-biased regression trees and forests from complex samples". In: Machine Learning (2024), pp. 1-20. Vittorino Pata et al. Fixed point theorems and applications. Vol. 116. Springer, 2019. Juan Perdomo. "Performative Prediction: Theory and Practice". PhD thesis. UC Berkeley, 2023.
[72]
[73]
[74] Juan Perdomo al. "Performative prediction". In: International Conference on Machine Learning. PMLR. 2020, pp. 7599-7609.
[75]
Nitin Namdeo Pise and Parag Kulkarni. "A survey of semi-supervised learning methods". In: 2008 International conference on computational intelligence and security. Vol. 2. IEEE. 2008, pp. 30-34.
[76] Omead Pooladzandi, David Davini, and Baharan Mirzasoleiman. "Adaptiie second order coresets for data-cfficient machine learning". In: International Conference on Machine Learning. PMLR. 2022, pp. 17848-17869.
[77] Daniel Reker. "Practical considerations for active machine learning drug discovery". In: Drug Discovery Today: Technologies 32 (2019), pp. 73-79.
[78] Pengzhen Ren et al. "A survey of deep active learning". In: ACM computing surveys (CSUR)
54.9 (2021), pp. 1-40.
[79] Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. "Satisficing in multi-armed bandit problems". In: JEEE Transactions on Automatic Control 62.8 (2016), pp. 3788-3803
[80] Mamshad Nayeem Rizve et al. "In Defense of Pseudo-Labeling: An Uncertainty-Awer Aware Pseudo-label Selection Framework for Semi-Supervised Learning". In: International Confer- ence on Learning Representations, 2020. 2020.
[81] Herbert Robbins. "Some aspects of the sequential design of experiments". In: Bulletin of the American Mathematical Society 58.5 (1952), pp. 527-535.
[82]
Julian Rodemann. "Bayesian Data Selection". In: arXiv preprint arXiv:2406, 12560 (2024). 5th Workshop on Data-Centric Machine Learning Research (DMLR) at ICML 2024.
[83] Julian Rodemann et al. "Approximately Bayes-optimal pseudo-label selection". In: Proceed- ings of the Niith Conference on Uncertainty in Artificial Intelligence (UAI). Vol. 216. Proceedings of Machine Learning Research. PMLR, 2023, pp. 1762-1773.
14

---

[84] Julian Rodemann et al. "In all likelihoods: Robust selection of pseudo-labeles data". In: International Symposium on Imprecise Probability: Theories and Applications. PMLR. 2023,
pp. 412-425.
[85]
Julian Rodemann et al. "Levelwise Data Disambiguation by Cautious Superset Classification",
In: International Conference on Scalable Uncertainty Management. Springer. 2022, pp. 263- 276.
[86]
Julian Rodemann al. "Not All Data Are Created Equal: Lessons From Sampling Theory For Adaptive Machine Learning". In: International Conference on Statistics and Data Science (ICSDS) by the Institute of Mathematical Statistics (IMS). 2022.
[87] Chuck Rosenberg, Martial Hebert, and Henry Schneiderman. "Semi- Sunei--see Self- Training of Object Detection Models". In: 2005 Seventh IEEE Workshops on Applications of Computer Vision (WACVMOTION (55--5llum 1. Vol. 1. IEEF. 2005, pp. 29-36.
[88] Jean-Fran Francis Roy, Mario Marchand, and François Laviolette. "A column generation bound minimization approach with PAC-Bayesian generalization guarantees". In: Artificial Intelli- gence and Statistics. PMLR. 2016, pp. 1241-1249.
[89] Daniel J Russo and Benjamin Van Roy. "An information analysis of thompson sampling". In: Journal of Machine Learning Research 17.68 (2016), pp- 1-30.
[90] Daniel Russo al. "A tutorial on thompson sampling". In: Foundations and Trends@ in Machine Learning 1 11.1 (2018), 8), pp. 1-96.
[91] Jens Schreiter et al. "Safe exploration for active learning with Gaussian processes". In: Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part III 15. Springer. 2015, pp. 133-149.
[92] Max Schwarzer et al. "Pretraining representations for data-efficient reinforcement learning". In: Advances in Neural Information Processing Systems 34 (2021), pp. 22699. [93] Burr Settles. Active Learning Literature Survey, Tech. rep. Computer Sciences Technical
Report 1648. University of Wisconsin-Madiion. 2010.
[94] Shai Shalev-Shwartz. et al. "Online learning and online convex optimization". In: Foundations and Trends Machine Learning 4.2 (2012), pp. 107-194.
[95] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithmss Cambridge university press, 2014.
[96]
Jaehyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. "On Conditional Versus Marginal Bias in Multi-Armed Bandits". In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, 13-18 Jul 2020, pp. 8852-8861.
[97] Aleksandrs Slivkins et al. "Introduction to multi-armed bandits". In: Foundations and Trends in Machine Learning 12.1-2 (2019), pp. 1-286.
[98] Jasper Snoek, Hugo Larochelle, and Ryan Adams. "Practical bayesian optimization of machine learning algorithms". In: Advunces in neural information processing systems 25 (2012).
[99]
George Soros. The alchemy finance. John Wiley & Sons, 2015.
[100]
Niranjan Srinivas et al. inforrmtion-tthorele regret bounds for gaussian process optimization in the bandit setting". In: IEEE transactions on information theory 58.5 (2012), pp. 3250- 3265.
[101] Bernadette Stolz. "Outlier-obbust subsampling techniques for persistent homology". In: Journal of Machine Learning Research 24.90 (2023), pp. 1-35.
[102] Hugo Touvron et al. "Llama: Open and efficient foundation language models". In: arXiv preprint arXiv:2302.13977 (2023).
[103] Isaac Triguero, Salvador Gareía, and Francisco Herrera. "Self-labeled techniques for semi- supervised learning: taxonomy, software and empirical study". In: Knowledge and Informa- tion systems 42.2 (2015), pp. 245-284.
[104] Isaac Triguero et al. "On the characterization of noise filters for self-training semi-supervised in nearest neighbor classification". In: Neurocomputing 132 (2014), pp. 30-41.
[105] Vishaal Udandarao et al. "No" zero-shot" without exponential data: Pretraining concept frequency determines multimodal model performance". In: arXiv preprint arXiv:2404.0413 04125 (2024).
15

---

[106] Jesper E Van Engelen and Holger H Hoos. "A survey on superviieeeiee learning". In:
Machine Learning 109.2 (2020), pp- 373 -40-
[107]
Pablo Villalobos et al. "Will we run out of data? an analysis of the limits of scaling datasets in machine learning". In: arXiv preprint arXiv:2211.0432. (2022).
[108]
Cédric Villani al. Optimal transport: old and new. Vol. 338. Springer, 2009.
[109]
Andreas Vlachos. "A stopping criterion for active learning". In: Computer Speech Lan- guage 22.3 (2008), pp. 295-312.
[110] Wenquan Wang. Wenbin Cai, and Ya Zhang. "Stability- stopping criterion for active learning". In: 2014 IEEE International Conference on Data Mining. IEEE. 2014, pp. 1019- 1024.
[111] Ximei Wang al. "Self-tuming for data-efficient deep learning". In: International Conference on Machine Learning. PMLR. 2021, pp. 10738-10748.
[112] Felix Wiewel and Bin Yang. "Entropy-based Sample Selection for Online Continual Learn- ing". In: 2020 28th European Signal Processing Conference (EUSIPCO). 2021, pp. 1477-
1481.
[113] Zimo Yin et al. "Embrace sustainable AI: Dynamic data subset selection for image classifica- tion". In: Pattern Recognition (2024), p. 110992.
[114] Taraneh Younesian et al. "Qactor: Active learning noisy labels", In: Asian Conference Machine Learning. PMLR. 2021, pp. 548-563.
[115] Kelly Zhang, Lucas Janson, and Susan Murphy. "Statistical inference with m-estimators on adaptively collected data". In: Advances in neural information processing systems 34 (2021), pp. 7460-7471
[116] Lijun Zhang, Tie- Yan Liu, and Zui-Hua Zhou. "Adaptive regret of convex and smooth functions". In: International Conference on Machine Learning. PMLR. 2019, pp. 7414-7423,
[117] Wentao Zhang et al. "Information gain propagation: a new way to graph active learning with soft labels". In: arXiv preprint arXiv:2203.0100 (2022).
[118] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. "Dataset Condensation with Gradient Matching". In: International Conference on Learning Representations. 2020.
[119] Peng Zhao et al. "Dynamic regret of convex and smooth functions". In: Advances in Neural Information Processing Systems 33 (2020), pp. 12510-12520.
[120] Li Zhou. "A survey on contextual multi-armed bandits". In: arXiv preprint arXiv:1508.03322 (2015).
[121]
Jingbo Zhu et al. "Confidence- based stopping criteria for active learning for data annotation". In: ACM Transactions on Speech and Language Processing (TSLP) 6.3 (2010), pp. 1-24.
[122] Christoph Zimmer, Mona Meister, and Duy Nguyen-Tuong. "Safe active learning for time- series modeling with Gaussian processes". In: Advances in Neural Information Processing Systems 31 (2018).
16

---

A Familiar examples of reciprocal learning
We will demonstrate that well-established machine learning procedures are special cases of reciprocal learning. We start by illustrating reciprocal learning by self-training in semi-supervised learning (SSL), see section 2.1 and then turn to active learning and multi-armed bandits.
A.1 Self-Training
For ease of exposition, we will start by focusing on binary target variables, i.e., the image of is {0, lt. with real real-valued features X. Moreover, we will only consider cases where the sample changes through the addition of one instance per iteration Leaning on [006. 12 103], we describe SSL as follows. Consider labeled data
D ((x,)))) (X))))"
4
and unlabeled data x E X. The aim of SSL is learn a predictive classification function fxx, 8) parameterized by 0 utilizing both labeled and unlabeled data. According to (75) and (106), SSL can be broadly categorized into self-training and co-training. We will focus the former. Self-training involves fitting model on D by ERM and then exploiting this model to predict labels for X.. In second step, some instances [=++ E I are selected to added the training data together with the predicted label, typically the ones with the highest confidence according to some criterion, see (2)
49 80
53
84
18
for examples.
Example 1 -raainnr.i Self-training is an instance of reciprocal learning with the sample adaption function (see definition (5) fSsL : x - P;; (0,P(Y,)) = PY,, with
P'YY, X) induced by
P(Y= 1(Y=1,x=x)= - ((xa(0).0) 0) + nP((Y = x1 Prix dy Px dx
1(x ((x=x(0))
n+
where (0) (definition)) 2 selects data with highest confidence score, see 12 80 53 the model O, and gives label of the selected (0) based on the learned model and gives rise to Py(x-
according to Px. The prediction function ÿ X. Q - {0, returns the predicted
The averaging with respect to Px and Pyix accounts for the fact that we allow stochastic inclusion of X in the sample through randomized actions and for probabilistic predictions of Y X, respectively. For now, however, it suffices to think of the special case of degenerate distributions Px and Py x putting point mass on data with hard labels in the sample and 0 elsewhere Through averaging with respect to Pyix we can describe the joint distribution of hard labels (y1..1),.... .,,,)) and predicted soft labels y P(Y 1 x, 0) E [O. 1] of (n++) ... (f+)) Summing up, both deterministic data selection and non non-probabiliittc (i.e., hard labels) predictions are well-defined special cases of the above with Prix and Px collapsing to trivial Dirac measures, respectively.
A.1.1 Implications of convergence results
Our corollaries in section 4 shed some light on the convergence of self-training methods in semi- supervised learning regime. Recall from above that the aim of these methods is to learn a predictive classification function fxx, 6) parameterized by 0 utilizing both labeled data Ø {(x,, )
(XC x z)" and unlabeled data 2/ = {(x, )m (JC 2"')"=" from the same data generation process. Self-training involves fitting a model identified with parameters 0 on D by ERM and then exploiting this model to predict labels for U. incremental self-training, some instances from U/ are selected to be added to the training data (together with the predicted label) according to some regularized data selection criterion e, (x, 0) c(x, 0) + (xx, see example and pscudo code below. Amending self- training does the same, but additionally removes instances from U. see below.
'In case more than one instance is added per iteration, the sample adaption function can be defined as a composite function of the used sample adaption functions.
In this case, P(Y 1.X x) 1(x=x(#)) ((x,))))))(())))))))))((((())))) P(
17

---

The key insight from our analysis is that the sequence of 0 converges at a linear rate in case of amending self eeff-tranning and regularized data selection.
Algorithm 1: Incremental Self- Self-Training in -emi-Super learning
Data: Labeled data D unlabeled data 2/
Result: Updated ( fitted model
while stopping criterion not mer do
fit model 0 on labeled data D for E (l...., } do
compute c, (x:.0)
end
obtain i" arg max, Cr (xi.0)
predict 1/ 8r- = (xp,, 8)
update O - 1 U ((p,,
update U - u {(xp, 3
end
Algorithm 2: Amending Self-Training in Semi-Supervised learning
Data: Labeled data D unlabeled data 2/
Result: Updated D, fitted model while stopping criterion not met do
fit model 0 on labeled data for E (I...., [2]] do | compute c, (x:.0)
end
obtain i" = arg max; Cr (x)
predict 1/ 3 8r- = (xx, 0) for j (1..... [ do
compute ,()
end
obtain jt= arg min, , er (xj:0)
update D - D u (Xr, }o)] \ ((91,z9)
update U 11 {(xe, l)pp
end
A.2
Active learning
Active learning is machine learning paradigm where the learning algorithm iteratively asks oracle to provide true labels for training data [50] 16 93]. The goal is to improve the sample efficiency of the learning process by asking queries that are expected provide the most information. Let X be the input space and / the set of possible labels. Consider training data
(5) above. The active learning cycle is follows. First, train model on the currently labeled dataset D. Next, select the most informative sample x" E X based on an acquisition function (criterion) such as uncertainty, representativennss,, or expected model change and obtain the label y" for the selected instance x² from an oracle (e.g., human expert). Finally, update the training data D - D U ((x", .ir",y") y")} and refit the model. This cycle repeated until stopping criterion is met (e.g.. performance threshold).
n {xx,, ri) E (.C. x 2/)"
Example 2 (Active Learning.. Active Learning is instance of reciprocal learning with the following sample adaption function (see definition 5 SAL. x P x N - P: PO, X), - P'(Y, X) with P' P' X) induced by
/
1(x= 1(x=x(0)) qy(xx + n nP 1, Py dy Px dx
1((==1,==))
n+
where x, (0) is a data selection function, see definition 2 Its induced distribution on X. is Px. The query function qy : X - [0, 1] returns the true class (probability) for the selected x, (0) and gives
18

---

rise to Pylx. In contrast to self-training (example p. the queried labels (y (0)) do not directly depend on the model 0, only indirectly through x, (0).
Again, both deterministic data selection through (s) and non-probabilistic (i.e., hard labels) queries through qy .C x {0, 1) well defined special cases of the above with Prjx and Px collapsing to trivial Dirac measures, respectively. As far as we can oversee the active learning literature, hard are more common than probabilistic or soft queries (114).
label queries 77 25 65
A.3 Multi-armed bandits
The multi-armed bandit problem is one of the most general setups for evaluating decision-making strategies when facing uncertain outcomes. It is named after the analogy of a gambler at row of slot machines, where each machine provides a different, unknown reward distribution. The gambler must develop strategy to maximize their rewards over series of spins, balancing the exploration of machines to learn more about their rewards versus exploiting known information to maximize returns. Typically, a contextual bandit algorithm is comprised of contexts (X1),=1- actions (Ar) and primary outcomes (Y.) again with binary image of Y, for simplicity, denoted by / (0, 1}. We assume that rewards are deterministic funetion of the primary outcomes, i.e., R, ff (Y, for some
known function f. Following [115), we use potential outcome notation (39) and let (Y(a) : a E A) denote the potential outcomes of the primary outcome and let Y, := Y (A,) be the observed outcome.
Define these quantities analogously for X(a) and call
Hi = (Xp, Ar
(6)
the history for 1 2 1 and Hy := 0 as in 115 The fixed and (time-independentt) potential joint distributions of X, and Y, shall be denoted by
Y, a a) P(X,Y) P for {I.....T).
(7)
Further assume that we learn model of P(X.Y,A) or P(Y A), which can be parameterized by 6, E @. Note that for specific reward function and A = XX active learning could be formulated as multi-armed bandit problem. The following embedding into reciprocal learning, however, is much more general. It only requires that the probability of playing an action P (A, H1 is informed by our model 0, i.e.,
P (A, H6-1) P (A, ((
8
which is very mild assumption given that the latter is the whole point of 0 in multi- armed contextual bandit problems.
Example 3 (Multi-Armed Bandits). Multi-Armed Bandits are instances of reciprocal learning with the following sample adaption function (see definition 5y fMAR Ox XxN - P; (0, X). P'YYXX X) with F' PY.X) X) induced by
P(Y 1Xx==, (1x== y(a()) + 1 1, P P O(H)-1)) da n+l
where a(i) : A is an action selection function also referred as policy function in the bandit literature that induces the well-known action selection probabilities P (A ((H,-1)), often called policies and denoted by : (n1))2t Further note that the indicator function takes argument that depends on only through a, contrary to active and semi-supervised learning.
Several strategies exist to solve multi-armed bandit problems, including upper confidence bound (deterministic), epsilon-greed,, (stochastic) and already mentioned Thompson sampling (stochastic). Deterministic strategies like upper confidence bound can be embedded into the above general stochastic formulation through degenerate policies P (A 0 0(H(-1)) putting point mass 1 on the deterministically optimal action.
It is usually directly defined in terms of action selection probabilities P (A, 12-1)), see 115 for instance.
19

---

B Additional Illustrations
B.1 Difference between reciprocal learning and performative prediction
realication E
closest
rCa lzadon (
1ea toattoooonnno
closest 11 -
Closest 2
truth
(a) Reciprocal Learning
(b) Performative Prediction
Figure (A) Reciprocal learning fits a model from model space (restricted by red curve) to realized sample from the sample space (blue-grey) that depends on the previous model fit, see Figure [bb] (B) In performative prediction, the population, not the sample, changes in response to the model fit. In other words, reciprocal learning algorithms have static inference goal, while performative prediction is concerned with moving targets.
B.2 Reciprocal learning compared to general online learning
Iealaaioon
Cloweet
aksest Eil 2
Tu
Clowed In
(a) One-Shot Learning
(b) Reciprocal Learning
(c) Online Learning
Figure 5: (A) Classical one-shot machine learning fits model from the model space (restricted by red curve) realized sample from the sample space (blue-grey), see [3T] Figure 7.21. (B) Reciprocal learning fits model from the model space (restricted by red curve) to a realized sample from the sample space (blue-grey) that depends on the previous model fit, see Figure [b (C) In the general online learning setup, there is no interaction between sample in and model in
C Illustrative experiments on data regularization
We run two simple experiments to illustrate the effect of data regularization (definition) 3 on stability of parameters 0, in reciprocal learning by the example of self-training in semi-supervised learning, sections 2.1 A.I and example Code to reproduce findings can be found in
20

---

Specifically, we deploy incremental self-training with soft labels real world datasets (banknote
data) with 90%, 80%, and 70% unlabeled data, see figures 7a 7
and
7c The task is to predict the
authenticity of banknote based on labeled and unlabeled data. We
generalized additive model
and multiple selection criteria from the literature (83 35 80 I03)). one of which is regularized according section 3 We want compare the stability of the parameter vector 0, of self-training with regularized data selection to self-training with unregularized data selection criteria. Specifically, we are interested in comparing the regularized Bayesian selection criterion (gold) its unregularized counterpart (red). The goal is not to study convergence under all conditions
| to 5 but merely to
illustrate the stabilizing effect the novel concept of data regularization (condition [ on the sequence of learned parameters. To do so, we compute the L2-norm of the parameter vector 0, at each iteration I, see figures 7a and 7c. becomes evident that self-training with regularized data selection is more stable than with unregularized data selection. Note that this setup analyzes variation (or rather, the absence thereof) within an experiment. We also assess the variations 0, between experiments. In order to do so, restart the experiment 40 times and average the L2-norm of 0, over these 40 restarts of the experiment and compute 95%--cnffidene intervals to assess the variation between experiments. We observe that the regularized selection criterion has much higher variation than its unregularized counterpart. Interestingly, the lower in-experiment variation due to data regularization variation.
seems to come the cost of higher
D Alternative stochastic data selection
Definition 10 (Data Selection alternative). Let I xx B. be a criterion for the decision problem (Q, A., Lo,) of selecting features be added to the sample in iteration Let (XC) denote suitable set of probability measures on the measurable space (X,, or (2C).. Define
E: [D(X)x
RR
(1,0)
- Bx(((,,0,)
Each à D(X) is interpreted a randomized feature selection strategy. The function ē evalu- ales randomized feature selection strategies based on the expectation of the criterion e under the randomizution weights.
E
Discussion of assumptions on loss
E.1
General discussion of asssumptio and
Assumptions 2 and address the loss funetion E in standard ERM, i.e., the first decision problem, as detailed in section 2 These are general assumptions often needed in a wide array of repeated (empirical) risk minimization setups, (56. 116 119] and particularly (74) well as [95] for an overview. Assumption T will needed in both decision problems of data selection and parameter selection, but is still fairly general and mild.
E.2 Discussion of assumption 3 Strong convexity of loss function
Assumption is typically required for fast convergence of repeated ERM solution strategies. Here, needed for reciprocal learning to converge at all. Thus, it can be considered stronger assumption than assumptions and It is easy to see that common loss functions like the linear loss ((y, 0) Oxy convex. but not strongly convex. The same holds for the logistic loss E(y,x, 0) log( 1 exp(6xy)). To see this, consider its second partial derivative V2 (y.x, 0). It is
x²2 exp(() 0yx)
V&ee (y.x, (1 ++xx((x0xx)
Hence, there is no K that can bound V2 (y,x, 0) from below. However, Tikbloov-regullarized version thereof (,(y,x,0) 0) log(1 + exp(Oxy) + 2110112 y-strongly convex, which follows from analogous reasoning. This sheds some light on the nature of our sufficient conditions for convergence, also section 6 In
becomes evident that lom -oo v2 (y.x.
21

---

20000
15000
Selection. Criterion
Bayes-Orit
L2 Norm
Bayes-oni--oo
10000
Likelhood
Predictive Var
Probability Score
5000
25
50
75
Iteration
(a) Self-training banknote data with 90% unlabeled data.
15000
Selection. Selection.Criterion Criterion
10000
Bayes-Crit
L2 Norm
Bayes-crit-Reg
Likelihood
nn Burtfui
Predictive Var
5000
Probability
80
Iteration
(b) Self-training hanknote data with 80% unlaheled data.
20000
Dolecciion.Crteriiin
15000
Bayes-Crit
L2 Norm
Bayes-crit-Reg
Likelihood
Predictive
Probability Score
5000
0
60
Iteration
(c) Self-training on banknote data with 70% unlabeled data.
Figure 6: Self-training with soft labels and varying selection criteria c(x, 8), of which (Bayes-crit-reg) regularized, on banknote data 21] with 70% (a) 80% (b) unlabeled data; y-axis shows L2-Norm of d at itcration r. Iterations vary between (a), (b), and (c) due to varying size of unlabeled data. Model: Generalized additive regression. Data source: Public UCI Machine Learning Repository (1]). References for other selection
criteria: Bayes-crit: Rodemann, J.. et al. "Approximately payes-optimal pseudo-labe selection. [83 Likeli-
hood: Hüllermeier, E., Cheng.
"Superset leamingg based generalized loss minimization:
[35 Predictive
Var: Rizve, M, N., et al. "In Defense of Leeuo-LLabeling An Uncertainty-Awan Pseudo-label Selection Framework for Semi-SSpprrvied lcarming."
(80) Probability Score: Triguero, I., García, S., Herrera, F. (2015).
"Sell-labeled techniques for semi-supervise. learning: taxonomy, software and empirical study." [103]. For
details, see httts:://// /gthttttbb......
22

---

Ealection.Crrterioo
20000
Bayes-Crit
L2 Norm
Bayes-ori-Reg
Likelhood
Predictive Var
10000
Probability
Iteration
(a) Self-training on banknote data with 90% unlabeled data.; distribution L2-norms over 40 restarts.
20000
Crittion
Bayes-Crit
L2 Norm
15000
Bayes-crit-Reg
Likellhood
10000
Probability Score
5000
60
80
Iteration
(b) Self-training on banknote data with 80% unlabeled data; distribution of L2-norms over 40 restarts.
Selectionn Criterion
20000
Bayes-Crit
L2 Norm
Bayes-crit-Reg
Likellhood
Predictive Var
Probability Score
20
40
60
Iteration
(c) Self-training on banknote data with 70% unlabeled data; distribution of L2-norms over 40 restarts.
Figure 7: Self telfntraining with soft labels varying selection criteria c(x, 0), one which (Bayes-crit-rees regularized, on banknote data (21] with 70% (a) and 80% (b) unlabeled data; y-axis shows L2-Norm of 0, averaged over 40 restarts. Shaded area indicates 95f--confiencce region.
23

---

fact, we require regularization of parameters to obtain strong convexity of the loss function and of data to obtain spschitz-continuii of the sample adaptions, see theorem This paves the way for theory-informed design of regularized reciprocal learning algorithms that are guaranteed to converge.
F
Proofs
F.1
Proof Lemmall
Proof. Recall definition Of c: I' x θ - R as criterion for the decision problem (6, (0, Lo)) We will prove the
of regularized data selection:
1 -
xd.0
X;; + argmax c((x, 0)
(9)
Lsg
xex
where R(-) is a k-strongly convex regularizer. The variational inequality for the optimality of argmax ((xx, 0) L. Rxx)) =: s(0) implies
xe.r
V)c(s(0).0) I (V.(()())) (s(0)- - s(()) 2 O.
(10)
Ls
Symmetrically for (0")
Vxc(s(("),0) - - ((0))s(00)) 2 o.
(11)
L,
Summing the above two inequalities yields
Vvc(s((0) +) L L, (V)((((0)) (s(0)) ((0))s(0))+(A)) (()))))( ! (. (s(0) (s(0)-s(0)) s(0)) 2 0.
L,
(12)
Rearranging terms, L
(s()) s (000)))))))))o(((()))))))))) (s(0))
(13)
It is known fact that for any x-strongly convex function holds that (V))))
x||x 112, Vx, y. This allows bwwr-bounding the left-hand side by f.r [|s(0) (
If c is linear in have c(x, g(0) for some appropriate function g. Thus, V.c(x, 0) g(0) and (Vvc((((0)) 8²) (.c(s(0),))) s 1-ell0' eI] and we can also upper bound the right-hand side using the generalized Mauchy-Schware inequality, see also [33] Appendix A.1].
||((e) s (00))1 z L. (|s(()) - s (0')l l|e 1'
(14)
Lng
Equivalently,
- s (0') L, Le
110 0'
(15)
which was to be shown.
F.2 Proof of Lemma 2
Proof. By Fubini, / ((((()))))p)) dyd = ʃ (() dp, dy. For brevity, set 6()) J (o0)).dw. To prove that ((((0) 0) is Lipschitz-contnuuss, we will proceed follows. First, we will show that (((()..) is Lipschitz-comtinuone Second, we will show that p(, 0) is Lipschitz- continuous. Third, we will show that the Lipschitz-continuity of p (5(0), 8) follows from the first and second result.

---

1. To show that p()(0).-) ) is Lipschitz-continun with Lipschitz-constanee LgLp, first observe that this holds (0) and p( are both Lipschitz-contmmuus with Lipschitz-constant. Lg and lp, respectively, since
- (p] ((())) = L.pell0 0'12.
(16)
The first premise the above statement holds per assumption. Let us now show that the second premise for the above statement holds.
To show that p ((ū.) Lipschitz-contimuuus first recall condition 2 by which we have that p(5.-) = p(x, 0) (g(xx, 0)) with or R - [0. 1] sigmoid function. Further recall that the prediction function of a classifier p(x, 0) is implicitly given by loss function {(y,p(x, p(x, 0)) per definition] [ By assumption [ we inter alia have that Vx((y, p(x, 6)) is
Lipschitz-cootinuuus in x for all and By chain rule,
v,l(y,pxx,
vp (l).)pp(x.))v.pxx...)))
(17)
Now note that we also have by condition 2 that V p. 0)) Lipschitz-continuout in The Lipschitz-comtinutty of T.l(y.p(x, 0)) in per assumption thus implies the Lipschitz-continuity of Vxp(x, 0) in x, because the first is product of the second and another function that is Lipschiz--oominnous in Recall that X is bounded (Definition and Condition 2). is a known fact that any Lipschitz-comtinouus function is bounded on bounded domain. We thus concluded that (.x, #) is bounded on the whole domain X. Any differentiable function is Lipschitz-conting continuous if and only if its gradient is bounded. See (95), for instance. We can thus conclude that (xx, 0) is Lipschitz-continnn 'y and 0 E O.
x for all
2. Let
show that 0)) is Lipschizz-contimuous, too. By assumption we have that V Vol (Y, pxx, 0)) is Lipschitz-conttimuur in B. With reasoning analogous to (b), it follows that p(x, 0) is Lipschit--continuous in for all y and all e
p 3. It remains to be proven that the Lipschitz of ((())) 0) xxx - [0. 1] follows
from those of p(x,)) :) X > [0, 1] and p(-.0) e - [0, 1]. To do so, denote by Lx the Lipschitz-constann of pxx.-) and by Lg the Lipschitz-constant of p(.0)).
First note vO, Ø O; Vx, X::
(lp(0.x) p(,, & p((.) p(0.x)ll2
(18)
By triangle inequality, we get
-(..) s 11p(0.x) p(0. (1p(0.8) p(0
(19)
Exploiting the Lipschitz-continuity of p(x.)) and p(- 8) allows us to upper bound this expression by
Lallx Rll2 Lx110 - 0112-
(20)
which eventually delivers
1lp(0.x) p(0,2)l2 s sup(Lo, 4,][ x||2 110-0110 0112).
(21)
We conclude that pxx, 0) is Lipschitz-continunnn with Lipschitz-constant sup( Ix) p(x, -) and p(,, 0) are Lipschitz-comtinuous with Lipschitz constants l.g and l.c, respectively.
The assertion follows from 1., 2., and 3.
25

---

F.3 Proof of Theorem
Proof. We will first prove the sipschitz-contimiity of the greedy sample adaption f 0xPxN P.
The strategy of the proof is as follows. We first show that 1. f(....). 2. f(,, and
3. f(....)) are Lipschitz-coninuos with Lipschitz constants Le. L2. and Ln respectively. We then show in 4. that the I Lipschitz-continiity of 7(0,(YY (0),(( follows with Lipschitz constant
max (L., Lp, I.n).
1. We prove the Lipschitz-continutty of f(0.,,) given conditions
and 5
To show that (Y, X), is Lipschitz-continuous in 6, it is sufficient show that
f(0(0),)) / ((==
Po dx
(22)
we can directly infer that v(0) is Lipschitz-continuout through lemma the remainder of the proof, the strategy is follows. We first show that f(w,-) -) is Lipschitz-continuss and then demonstrate the Lipschitz-continiity of (()()), 8) e. With reasoning analogous to argument (3.) in the proof of lemma?) 2 it then follows that f(0(O), 0) is Lipschitz-conimmouus on O O
is Lipschitz-continuuus in O. First note that by Conditions 1 and 4
(a) We start by showing that the function
f(w, f 1(x w) 3(5 p dy Po dx
(23)
Lipschitz-continuuus W. Apply Fubini get
f(0.-)= = f 1(x 1(x= = 0) s( 0) Po dx $ dy
(24)
Condition 3 limplis that features are drawn according to
[X [xx0 [0. 1]
exp(c(x.8)) 8: (x, = (.pppc(t.,))dppa))
see definition That is. f(( =) 30. Po dx 2(w. 6) S(E(W, f), 0). Per condition 5 c(x, 0) is linear x and thus Lipschitz-continuunn
x. Further note that the mapping C - E is softmax function, which is continuosly differentiable and thus Lipschitz-continuous. We thus conclude with the argument (1.) in the proof of lemma? 2 equation [6] that č(x, 0) is Lipschitz-continuous in since it is composition of two Lipschitz-comtinuous functions.
Now recall that by Conditions] and we can infer that (0)) is Lipschitz-comtinnone through lemma This and Condition 2 imply that we can apply lemma which delivers that
f(D) = f E(W. ((((0)))))) c( 9) / = 8)
E
(25) and that p( 0) Lipschitz-continouus in both arguments. Now note that both ē X. x 0 + [0, 1] and p ... x θ - [0. 1] are both bounded from above by 1. We thus conclude by triangle inquality that fW) Lipschitz-continuuus in w. Explicitly,
[1(()) - f(0'll2 (0',,))(w''"" .0)12
= [|E(0,
<llčw, ()..))))(ww)) ((0,0) 0) [|ā( ()p(w')(w))))))))))))))))))))))) -aw'' ())(("(
1000p((()pp(00000000) () |||
(0 0) p(w' 00]112
$ 0) -(("0))(
-ppl -0 -=++ -
$ (Lpp La) v'1l2.
(26)
where Lp and La denote the Lipschitz constants of ē and p, respectively.
26

---

(b) To show the papschizz-continun of f(w(0). 0) in O, first note the Lipschitz susschizz-ootinnity f(#(0) -) in 0 directly follows from the facts that 1) #()) is Lipschit--oontinonn 2) f(w, -) is Lipschitz-continuuus in w. and 3) any composition of Lipschitz-continuuus functions Lipschizz-continuuus We have proven and 2) right above. For a proof of 3), see equation Tōlin the proof of lemma
What remains to be shown is the Lipschitz-contiiitty of f(-, 0), which translates to the Lipschilz-continiity of
[1<==V) - { pdy dx.
(27)
in 8, which in turn translates to the Lipschiz-continuity of the inner integral. Condi- tion and lemma deliver
f s(c,0) pdy= ((0(0)) ) p(,
(28)
with p( f) being Lipschizz-continuuss in (c) remains be shown that ((((), 8) is Lipsshitz- on O. This follows from reasoning analogous to the proof of lemma 2 resulting in
(I)())), 8) f()(0), 112 sup(La, ( 011 (|m(0) =()))22) (29)
with Le and Lo(a) being the Lipschitz-constame of 0 and w(0), respectively.
This concludes the proof that f0, X), is Lipschitt-ccomiinous in 0)
2. To see that f(-, P(Y, .) is Lipschitz-continuous with respect to Beasserstein---ditaaaee on both domain @ and codomain P,, recall the definition of Wasserstein- -ewersttiii---distaceess (108).
Let (X", d) be metric space, and let p E oo). For any two probability measures 14, on X,, the Wasserstein distance of order p between and is defined by
inf (elll(a,)) S d(xx y)x dxxx)))))))))
1/p
Wp Wp v)
(30)
[1u v) denotes the set of all joint measures on .'' X' with marginals a and v. For p and empirical distributions P(Z) and (Z') this translates to
F(()()).'(Z')) min Σ ズi. d(zn,tf) : Ri.j 2 0, πi. -T,1=
= Bj. Σ n.. = =
(31)
with Æi,i joint measure on Z and Z' and and corresponding to marginal measures of Z and Z', respectively.
It becomes evident that any marginal change in f(0,P(Y, X), caused by change P(Y, X) is essentially R4T.
That is,
6f NY,, X)))
n
(32)
5P(Y,
n
which analytically follows from
P(Y. (1)) s000)) - d Po dx
(33)
- 1000))) n+1
P dy P dx + =I(
n+1
The partial derivative in equation 32 that differentiable functions are L.pschiz-contimmuus if and only the gradient is upper bounded, see [95 page 161], for instance.
trivially upper-bounded by 1. It is known fact
27

---

3. Choose n, n E - such that n * n' arbitrarily. It is self-evident that for fixed
((x = ((0) 3(0(0), =1 1(x (x==(0)) -00(0) 0) + + P 11, 1 1.
(34)
And thus also for any x
- F10.P. s 1.
(35)
Since supp(Z) supp Z') with Z ((B.F(Y.)). and Z' f(), we have (T ((). S
(36)
as well as In-n'l | 2 1, from which the assertion that f(6, ((Y, X), is Lipschitz-cooninuous in directly follows.
4. With reasoning analogous to (3.) in the proof of lemma have that the Lipschitz- continuity of f00,P(Y P(Y, X), follows from the Lipschizz-comtiniity of 1. f(e,..), 2.
X), and f(..,n). That is,
(i(S(O,P,n) f( ,n))) max(Lo, Lp, Ln) [ (37)
from which the assertion follows with 1 for the p-norm.
What remains be proven is the Lipschitz-continitty of the non-greedy sample adaption function fn x S with fn (0,P(Y. X)) = PY,, induced by
P'Y = 11X
= / 1(x -(0)) (((()) Mn P(Y 1, X x) 1(x (P(Y,X)) 3( (P(Y, P3 dy Po dx.
The reasoning is completely analogous to the greedy sample adaption function f. see 4. above. In particular, we can directly transfer the proof of 1. (0...)) being Lipschitz-ccontnnouus What remains to be shown is that the Lipschitz-cominnitty in P E P also holds for fa. This translates to showing that w is Lipschitz-contimuuuss in since we have the Lipschitz-continuity of no P(X, Y) with analogous reasoning as in 2. above. However, note that the Lipschitz-constant is not necessarily the same, since the partial derivative fn also includes the indirect effect through w and S.
To see that w is Lipschitz-comtinuuuu note that for two arbitrary P, P' E P we have that
x'p=_xx'PPI=== / (x-x))dp(xx')) & f 1x-xx/dpxxxx), (38)
| (P) (P))= xdp x'dP'112=
where x'x,x') any joint probability measure on XC. Now recall that the Wasserstein- Leaserstein---distnnee defined as the infimum of f xx'I'dpp(xxx* x') with respect to p(x,x'), We conclude that
| (P) (P')ll2 Lo WI(P,P')
(39)
with L--- constant.
The Lipschiz-continuity of fu then follows from the Lipschitz-continiity of fn in and the Lipschitz- continuity in with the argument in 4.
E.4 Proof of Theorem 2
Proof. The structure of the proof is analogous to the proof theorem T
We show that 1. f(A,
2. (Y),() and 3. f(...n) are Lipschitz-continuos with Lipschitz constants Lg. Lz, and
28

---

Ln, respectively. We then show in 4. that the Lipschitz constant max Ls. Ln). Since none of conditions c [ were required to show
of P(Y, P(), X), follows with
1,, 2., and 4., in the proof of theorem we only need to show that 1. also holds under conditions 2 and
To show that ((0,P(Y,X), is Lipschiiz-coniinouss in 0, it is sufficient to show that
f(w(0),)) / / 1(x 1(x= 300 0) dy Po dx
(40)
is Lipschizz-contimuuss in O.
In the remainder of the proof, the strategy is follows. We first show that fw. ) is Lipschitz- continuos and then demonstrate the Lipschitz-contnnity of ((z(O), 8) With reasoning analogous to argument (3.) in the proof of lemma 2 @.
then follows that f(W(O), 0) is Lipschitz-cooitmuuus
We start by showing that the function
s(w = /
(00 Po dx
(41)
Lipschitz-contimuuus in w. Apply Fubini get
f(w.,) / ʃ 1(x = )() dx p
(42)
Condition 3 iimplis that features are drawn according to
X x - [0,
ē: (xx
(x,(c(xx0))
(43)
Is (eppl((x,,))ddp
see definition That is, f 1(x w) YWW, 0) Py dx=== E(0, 366 0), 0). Per condition 4 c(x, 0) has bounded gradients with respect to x, which implies that c(x, 0) is Lipschitz-contintne Further note that the mapping c - is softmax function, which continuosly differentiable and thus Lipschitz conschizz-ommiiuuuus We thus conclude with the argument (1.) in the proof of lemma 2 see equation 16, that ē(x, 0) is Lipschitz-continuuus in x, since it is a composition of two Lipschitz- continuous functions.
in
We now need to verify that f w(() Pydw is Lipschitz such that we can apply lemma 2 By condition we have that f (e(U) = ε(x, 0), which is Lipschitz-comtinuous in 0 per condition
Condition 2 and lemma then directly deliver that
E(0 f f 2( 0) ((((0.0).0)p. =6(w, / ((1
(44)
with pww 8) Lipschitz continuous in both arguments. Now note that both ē X' θ - [0. 1] and X x θ - [0, I] are both bounded from above by 1. We thus conclude by triangle inquality that f(w) Lipschitz-continuuu in W. analogous to the proof of theorem Explicitly.
- -
= ||č(0, (w. 8(w',0))(() (01))
s [|ē(w. ()) - ((0, ((',)) [|ā -
- ppp (20))(0))l
=
(ppp0)))pp'0))) |1l+ [1p(w' (o(w"0))(((0
(45)
< [lpp (111,00)l++1(((0. p(w',0))2
$ =''ll= Lello-w1l]
La) v'll2.
where Lp and La denote the Lipschitz constants of and p, respectively.
To show the Lipschitz-cominiityy of (w((), 0) 6, first note the Lipschitz-contimitty (()(A). directly follows from the facts that 1) (00) is Lipschitz-continuour 2) f(w.) is Lipschitz-contintous
29

---

in v, and 3) any composition of proven 1) and 2) right above. For a proof of 3), see equation i the proof of lemma 2
functions is Lipschitz-comee continuuu.s We have
What remains to be shown is the Lipschitz-continutty of f(:00, which translates to the Lipschitz- continuity of
f [(x==) f =(0.0) 0) p dy Po dx.
(46)
in 8, which in turn translates to the Lipschitz-continuity of the inner integral. Condition lemma 2 (which we can apply, since f ((0) is Lipschitz, see above) deliver
and
ʃ 3 ddy= = f ((w(0),0))dy= p(v
(47)
with p(0, 0) being Lipschitz-contimuuss in 0
It remains to be shown that f(0(0). 0) is Lipschitz-continuuus on x O. This follows from reasoning analogous the proof of lemma resulting in
(( -(( 011 s sup(I-o. l-x(o))
||=(0) (0)122),
(48)
with Lo and Lo(o) being the Lipschitz-consttats of 0 and w(0), respectively.
This concludes the proof that F(Y,P(Y, x). is Lipschitz-contimuuus in A. The Lipschitz-continee of (0, P(Y, X)) directly follows, since the Lipschitz-continitty of w (P) has been shown in the proof of theorem]
F55 Proof of Theorem
Proof. Choose (O'P). E Q x J arbitrarily. Set F(1) == ((rx))-((0.P) E(Y, X, 77) and F' (n) == (x C(Y, ((Y,x,m) X). As integrals over y-strongly convex functions, both and lo are y-strongly convex themselves.
Let Ri := (i, P) and R₁= Ri (0', P') be first components of (0, P) and R, F),, respectively, Since, by construction, we know that Rí is the unique minimizer of F and that R is the unique minimizer of F", we can conclude that:
F(R1) - F(R)) 2 (Ri (RR--R) VF(R)) + 2/4 ||RR Rill
(49)
F(R') F(RI) ž || - -
(50)
Adding the above inequalities yields
-y||R| - R1l2 2 (R) 21-RR (R)RR)/FF(R))
(51)
Now, consider the function y(x,y) = (R) RR) v((y,x, R1). Due to Cauchy-Schward incquality, we have that
- T(x' [R] [(), RD12
(52)
As is B-jointly smooth, we have that
Ve(y,x, R2) - -(y''x'' Rille s Bl((x,)) - (x',3')12
(53)
Thus, together, the latter two inequalities imply
[T(x,)) y) - T(x', s || R Bllx,,1(x,,)) x212
(54)
showing that 7 is |R - Rill, B-Lisschitz This implies that
f :: (| R)1188)11
(55)
30

---

is 1-Lipschitz. As, due to theorem 1 the non non-greedy sample adaption function f. is Lipschitz with respect W1 and || pp for some constant L, we can use the dual characterization of the Wasserstein
metric, i.e. the Kantorovich-Rubinsseenn lemma 43 to obtain
s - W(
(56)
We compute:
(T,x)-) (x (T(Y,)))
(T(X))) RR Rill,
(R) -R VF(R;)
(57)
|| Rill2 B
Here, we used that -Ri-R is constant with respect to the measure fn P) and that the order of integration and differentiation can be exchanged according Lebesgue's 's dominated convergence theorem. Analogously, we obtain
(70 = (1.))=/((00.,))(((..
(RI RT)T (F)(
B(xx))-A.0 (T),
(58)
R Rilla
|R
(RI-Rill2?
Rilla, B
Together, this yields
(R) (RI-R)(VF(R) - (RI ( RF -1.B| -R Killa (110 6'112 (P,)))))
(59)
As R is the unique minimizer of F", conclude that the second product the left-hand side of this incquality larger or equal to Thus, the inequality reduces to
(Ri - RV)(F((R) 2 -L - RRll2 (lle - 0'1l2 + (((P))))
(60)
which, together with Equation (51) yields
-y R|||R 1/ll2 -LB Rill2 (110- 0 +
(61)
which proves after some rearranging that R₁ θ x P θ is Lipschitz-continuous with Lipschitz-constant L Precisely, get
|| Rille = (110 0' WP,PP)).
(62)
y
We further have per theorems and that fn x - S is Lipschiz--onntinouus with constant L, used above. can easily be verified (see definitions 7 and 5 that the second component R2 = (2(0, P) of R)e,P) equates fn. Thus,
| R2 s 1.(10 - 8'112 + Wi(P.P)
(63)
with R' = R2(,',
(((''P)) P') and arbitrary 0 o and arbitrary P.P' P. We can conclude that R, Lipschitz-contimuous with Lipschitz-constant L(1 + ()) and the sum-metric on + x P by adding the two Lipschitz-neequaliies, yielding
||| Rill2 + +||22 Rills L P 1.= 0'112 Wi(,F)) L(II0 0'112 WPPPPP).
(64)
That is,
B
Rn, Rill s L(1+ _ (l1e - ((
(65)
31

---

Remains to be shown that, assuming L < (1+ ()++))-11 the sequence (O,((,, converges to fix point at a linear rate. The existence and uniqueness of a fix point follows from Banach's 's fix point
theorem [4], since equation 65 guarantees that the map R is contraction for L (1 + 6)-1 complete metric space. So, let Pe) denote such fix point. Observe that it holds per equation 65 for all e N
e |I(0,. (0c, Po)ll L(1 (ll(,,, (0c, Pa)ll
(66)
Repeatedly applying this yields
|I(0, P,) - (0c, (0c, 1'(1+ ")l(((,, Po) Fell
(67)
Setting the expression on the right-hand side to at most A gives
(K0,P)) - Pc)l s L'(1+ [ (1(0,, Po) (0c, Pe). s A
(68)
Rearranging and setting the expression on the right-hand side to be at most A gives
A logll(0,,P,)) - (0c. Pa)ll s r rog [1(1 + 6} = log |I(0,,P,) (0c, Pc)Hl
(69)
Rearranging for and exploiting that L(1+ ))
yields
1 12 log (o)
(70)
log 1.(1 + (
since [1(0,. Po) Pe)ll and L(1 + ()) are fixed quantities, we have that
|1 - (fc.P.)l1 A
(71)
if 2 log [()..o))((0..
(log L(I + - which proves the linear rate of convergence.
Note that the proof was mainly application of Banach fixed-poine theorem 4 and such similar to the proof [74] theorem 3.5]. The key differences to (74, theorem 3.5) are: (1) We need to prove the Lipschitz-continuity of the sample adaption function f first, see theorem [ which is non-trivial for several instances of reciprocal learning.
(2) (74) theorem 3.5] considers simple repeated risk
minimization, i.e., mapping + O while reciprocal learning R x
O S N or
R, ④ x Ø - θ x l (definitions 0 and
F.6 Proof of Theorem 4
Proof. Recall that R; (0", P') arg min X) ((Y, X, 9) per definition and arg ming B(y () C(Y, X, 0) per definition First assume that 6 # 0", since otherwise the the statement would be trivial due to Le o.y per assumptions.
We will prove the statement ||0, 001l 24r by contradiction. Thus, assume that ||0 0 21,4.
First observe that E (xx.x))_.( E(Y, X, 0) is loss is Le-Lipschitz and fn is L-Lipschitz in 0, since Lo-Licchhitz in (see 1. in proof of theorem and L max(Le. Le, Ln). That is,
in 0 for fixed P. and Oc, since the
Byy.x)-5A10RR2 C(Y X.) E(y.))-f. e(Y.X,0) LeLl 0cll.
(72)
32

---

Further note that
(o..)) ((YXX,0)) -(xxx)-S((0..P)) (Y,X,00) 2 21100 Oclp. (73)
2
which holds because we can state due to assumption 3 (strong convexity) that
B (0)00))- [e(x.x.0') <(r ((x)) (0 [Vo((Y,X.00) (0' 0c)]
110 -f
(74)
by taking expectations on the inequality stated in assumption g (strong convexity). By classical first-order optimality conditions [44] we know that the first term the right-hand side is larger equal to 0, from which equation 73 directly follows, see also [4 Theorem 4.3].
now |10,
A* > 2 or equivalently K110e - 1- Le - 0* as we assumed, we have
per equations 72 and 73 that
((xxx)-((00PPP) ((Y,X.0.) - -(r,x))-(( (YY,X00)
<B(x,))-(x(00R)) ((Y,X,0") Bxxx))-(0022 (Y, (75)
which would imply
(Xx (Y.X,0) B(yx))-f. X, 0c),
(76)
which contradicts definition 9 and the non-negativity of the loss function.
F.7 Proof of Theorem
Proof. By Cauchy criterion for series R,, / E N with respect to sum or product norm on θ x f x N. According to the Cauchy criterion the series R, diverges, if there is such that 3/ N Vm, I dp Rm R₂) = dp ((0m- P Pm. Rm)) - (0,, P, n2))) > with dp the sum norm and m $ n. m, n E N. This holds for e (0, 1), since ||mm nn 1.
F88 Proof of Theorem 6
Proof. By counterexample. Assume fn :0x J - S is not Lipschiizzcontiiuuus, i.c., no < co exists such that
W ((. F)) & L. |1(11 12, (I,,
Let again R,,1 == RM.1 ( P) and R == Rn, (0', PP) be first components of R(0,P) and R(0', R(O'P)), respectively. Further assume that R,.1 = C L. C e R. becomes evident that for any fixed point 0g it must hold: 0, 7-Z
C If + co, this fixed point does not exist: lim = 100.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract and section (introduction) of the paper accurately reflect the paper's contribution and scope, covering all results presented in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the work are explicitely discussed in sections and (Subsection "Limitations) of the main paper as well as mentioned when stating the main results in sections 3 and
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
34

---

Answer: [Yes]
Justification: The theoretical results of the paper are stated in Theorems I, 2. 3,4, 4, 5, and 6 as well in Lemmata and 2. For each of these theorems and Lemmata, full sets of assumptions and conditions are provided. Moreover, complete proofs for all these statements are provided in the paper's appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The paper does include two experiments section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
35

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
See section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeee/eeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
36

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еттоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper is, in every aspect, conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
We do not foresee direct negative societal impact from the current work. Positive societal impact form of making decisions based on reciprocal learning algorithms such as active learning self-training more reliable and trustworthy are discussed in section 1, 2, and the paper.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
37

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
38

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "DeIxYAJKAI", "reviewer": "Reviewer_MkM4", "summary": "This paper presents reciprocal learning, a framework that enables proving convergence for various classes of Machine Learning algorithms including classes of self-training methods, bandit algorithms and active learning methods.", "questions": "- Can the authors comment on how their framework connects to algorithmic stability [1,2] which studies generalization as a function of perturbing the dataset by a single sample and how that alters model parameters?\n- How does the proposed algorithm ensure that the data selection procedure will not lead to degenerate distributions which causes the subsequent ERM procedure to work with very small effective sample sizes leading to models that have high estimation error (thus leading to poor generalization).\n- It seems like the proposed algorithm is trying to get to some kind of a saddle point (min_{model-params} max_{data-distribution}) which appears to bear interesting connections with 2 player games and potentially even to boosting style methods. Any thoughts on whether this can lead to statements about generalization?\n- Can the authors maybe comment on how this framework connects to other learning paradigms such as distributionally robust optimization?\n\n[1] Olivier Bousquet, André Elisseeff, \"Stability and generalization\"\n[2] M Hardt, B Recht, Y Singer, \"Train faster, generalize better: Stability of stochastic gradient descent\"", "limitations": "N/A.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- General framework that presents convergence guarantees that shows the stability of both data and model parameters. Interestingly, the strategies described in this result involve data selection through pruning and augmentation, which is certainly a perspective that is new to my knowledge.", "weaknesses": "- The connections to practically relevant algorithm design is lacking\n- It is unclear how this paper's result ties to generalization guarantees of various classes of these algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer MkM4 for the thorough and helpful review! We address all your remarks point by point:\n\n**“algorithmic stability”**\n\nOur results address the question of whether (and at what rate) a wide range of machine learning algorithms stabilize (converge). The referenced papers deal with the question of how stable a learning algorithm is under slight changes in the training data set, see [1, page 499].\n\nIn this sense, [1,2] constitute a really interesting bridge to future research on what can still be said about the stabilization of a reciprocal learning algorithm if the quality of the initial training dataset is distrusted. We think that the results of the referenced papers (in particular Theorems 11 and 12 in [1]) could help to find good answers here and plan to refer to them in the revised version of our manuscript. \n\n**“small effective sample”**\n\nGenerally, regularization (cond. 1) and/or randomization (cond. 3) of data selection in reciprocal learning helps preventing this kind of “overfitting” of data to the current model. They ensure data is not greedily selected based on the current model fit. The latter would reinforce this fit by preferring data that is similar to the current data, eventually leading exactly to the degenerate distribution with small effective sample sizes that you have described.    \n \nHowever, we have not yet obtained explicit results on this. But, inspired by your remark, we are currently conducting a rigorous analysis. Start with Theorem 4, which guarantees that the convergent solution $\\theta_c$ (Def. 8) of reciprocal learning is sufficiently close to the optimal one $\\theta^*$ (Def. 9). While this does not directly relate to the distance of convergent data distribution $\\mathbb P_c$ to the optimal $\\mathbb P^*$ , we might indirectly relate the two by techniques from data attribution (like influence functions) or inverse problems. We conjecture a single $\\mathbb P^*$ might not be identifiable from $\\theta^*$, but possibly a credal (i.e., convex) set of probability distributions. Utilizing recent results [3], we might be able to characterize the so-obtained set of empirical distributions. Concretely, we plan to build on Theorem 5 in [3], which shows that Lipschitz-continuity of data generation (Def. 1 in [3], here: sample adaption) induces an interval of measures, which gives rise to a credal set of probability measures.\n\n[3] Bailie, J., & Gong, R. (2023). Differential privacy: general inferential limits via intervals of measures. ISIPTA.\n\n\n**“practically relevant algorithm design”**\n\nThanks for identifying this room for improvement in our initial submission! We hope our extensive experiments on bandits and self-training, as suggested by Br7x, help to bridge the gap from our theorems/corollaries to practically relevant algorithm design (see reply to Br7x). \n\n**“ties to generalization guarantees”** \n \nWe think such considerations are an interesting and natural next step for future research, but this certainly requires a lot of work and very careful consideration, see also reply on DRO, and would thus go beyond the scope of this paper. \n\n\n**“2 player games”**\n\nWe have decided to look at the problem in terms of decision theory (see illustration 1) rather than game theory. To the best of our knowledge, minmax equilibrium results of the form intended by the reviewer relate more to the realm of non-cooperative game theory, i.e., to games with opponents pursuing opposite goals. In our situation, however, common goals are pursued: Both decisions, the choice of the parameter as well as the data to be added aims at maximizing a common underlying utility. For this reason, an embedding in (sequential) decision theory seemed to be the more natural choice for us.\n\n**“boosting”**\n\nThis is an intriguing idea that we have not thought about before! Thanks!\n\nIndeed, boosting style algorithms like gradient boosting could be subsumed in reciprocal learning under certain conditions. Consider regression with squared loss $\\ell(y, \\hat y) = - \\frac{1}{2} (y - \\hat y)^2$ for instance. In this case, gradient boosting’s pseudo-residuals correspond to the residuals $\\nabla_{\\hat y} \\ell(y, \\hat y) = y - \\hat y$. This means that gradient boosting iteratively fits a model to the residuals of the initial training data (for varying $\\hat y_t$ in iter $t$). That is, $\\mathbb P_t$ can be written as a function of $\\mathbb P_{t-1}$ and $\\hat y_t$ (i.e. $\\theta_t$ for fixed $x$), which fulfills def. 1 and 7 of (non-greedy) reciprocal learning. \n\nTo establish Lipschitz-continuity of this kind of sample adaptation $f_n: \\Theta \\times \\mathcal P \\rightarrow \\mathcal{P}$, however, we would need more assumptions, e.g., $y \\mid x$ being normally distributed. Then $f_n$ is Lipschitz-continuous w.r.t. $\\theta \\in \\Theta$, since the change in $\\mathbb P$ (a mean shift by $\\hat y$) w.r.t. Wasserstein-2-distance can be bounded by the change in $\\theta$, because $\\hat y$ can be expressed in terms of $\\theta$. (Recall the W-2-distance between two normal distr. with same cov-matrix is the eucl. distance between their mean vectors.)\n\nWe plan to study this further and beyond such simple examples. \n\n\n**“distributionally robust optimization” (DRO)**\n\nThis point is related to the robustness aspect in our answer on “algorithmic stability“. Main difference (afawk): DRO is not interested in robustness under perturbed input but in performance under distributional shifts (see, e.g., disambiguation in [4].). DRO attempts to optimize a functional that depends on the probability law (in the simplest case, an expectation). The challenge here is that the probability law is unknown and instead only a set of possible candidate laws (a so-called \"ambiguity set of probability measures\") is given. A starting point for the derivation of generalization bounds may thus be [5]. \n\n[4] Jose Blanchet et al.: Distributionally Robust Optimization and Robust Statistics.\n\n[5] Michele Caprio et al.: Credal Learning Theory.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b5c30ncIp1", "reviewer": "Reviewer_T1mz", "summary": "The paper presents a new, unifying framework called reciprocal learning for studying learning scenarios in the batch setting --- which, in contrast to one-shot ERM, may go through an entire sequence of ERMs where each previously fitted parameter gives rise to new data that the next ERM procedure will be trained on. The authors show that this framework in particular has, as its instances, active learning, bandits, and self-training. They proceed to show generic results on convergence --- and on non-convergence --- of such procedures to fixed-points or to optimality, under reasonable assumptions on the loss function that the ERMs use. And, the authors point out that the resulting convergence and non-convergence statements, when projected onto specific instance settings such as active learning, give rise to previously not studied guarantees on the learning procedures.", "questions": "As stated above, I would like to see expanded and improved presentation/writing (in various places, especially when it comes to references to methods in the literature that are subsumed by, or related to, the current framework such as active learning, bandits, performative prediction).", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper points out, and develops notation/generic guarantees for, a general setup that encompasses diverse, distantly related but quite distinct, learning settings. The main strength of the paper, of course, lies in the generality of its proposed framework — it definitely has the potential to create, and foster, new interaction between researchers active in the various areas/literatures that it touches on (active learning, bandits, but also other work such as self-training), and as such can be a valuable contribution. \n\nAs far as I checked, the instantiations of the generic convergence result in some specific cases, which the authors claimed as one of their contributions, indeed appears unexplored in the respective literatures (and noticing that this flavor of convergence result is possible to prove in these settings is definitely much easier when armed with the “reciprocal learning” perspective). Moreover, even though the requirements (Lipschitzness, convexity etc.) for the fixed-point convergence result to hold are both to-be-expected and quite stringent, the authors provide a formal construction hinting at (at least a subset of) these requirements (notably Lipschitzness) appearing to be necessary for convergence.\n\nFurther on the technical side, I think the concept of data (as opposed to parameter) regularization appears to be a new and interesting idea.", "weaknesses": "1. The paper’s main merit — its generality and potential usefulness as a bridge between several literatures — also gives rise to its main weakness in my opinion, which is presentation and writing. The main aspect that I am concerned about is that in various key places invoking related work, the manuscript reads like an informal/incomplete note or memo rather than like a conference paper aimed at researchers coming from several different areas. For instance, consider the sentence in lines 348-352, whose function is ostensibly to distill the above non-convergence theorems into a concrete new insight into why amending strategies, and several other self-training methods, may be preferable to incremental batch self-training — but it never defines any of these terms or provides any further self-contained details to the readers. Or, consider the sentence in lines 391-392, whose function is to compare the “reciprocal” setup to the performative learning setup along several dimensions; once again this reads like an informal note that readers must decipher on their own time. Another example is Section 3 (Familiar examples of reciprocal learning), whose function is to define (some setups in) self-training, active learning and multi armed bandits as special cases of reciprocal learning. Once again, only a very brief sketch is given for each of these (and only self-training makes it into the main part). While one could argue that all these instances are a function of conference-imposed space constraints, but the Appendix similarly doesn’t aim to complement any omissions in the main part, and the overall writing seems extremely rushed and currently unsuitable as a means of bringing diverse groups of researchers together.\n\n2. It is not a significant weakness per se, but on the theory side, the main generic convergence guarantees — and the Lipschitzness/convexity assumptions that go along with them — are derived in a quite standard way relative to the convex optimization literature and in that way offer “unsurprising” results; therefore I would not consider the technical contribution of this paper to be its strongest suit, in contrast to its merits in terms of formulating the setting itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer T1mz for the thorough and helpful review. We are glad about the generally positive feedback and address the reviewer’s two concerns with the initial state of the paper below.\n\n$~$\n\n**\"presentation and writing\"**\n\nWe really owe a great deal of thanks to the reviewer for these concrete suggestions on how to further improve the presentation of our analysis. We fully agree that, in order to serve as a bridge between distinct areas, it is of utmost importance for the paper to communicate all insights into these areas in a detailed manner that is accessible to audiences inside and outside these specific fields. This particularly holds for corollaries in sec. 5, which relate the general results to the specific instances of reciprocal learning like amending self-training. We initially focused on communicating those to readers from the field affected by the corollary. Our thinking was to address these readers in a language they are familiar with and refer readers from related fields to literature that is accessible to them. \n\nReading review T1mz, however, made us aware we had paid scant attention to all other readers familiar with neither the field itself nor with related fields. We thus have (and still do) put much effort into carefully revising the affected parts of our paper, especially sec. 5. While we cannot share all changes due to character limitations of this rebuttal, we apply a \"pars pro toto\" approach, ensuring that the revision of lines 348-352 (as suggested) we discuss here represents broader changes throughout the paper. We have changed lines 348-352 (starting with ”This provides a…”) as follows: \n\n---\n\nThis sheds some light on the convergence of self-training methods in a semi-supervised learning regime. Here, the aim is to learn a predictive classification function $\\hat y(x,\\theta)$ parameterized by $\\theta$ utilizing both labeled data\n\n$ \\mathcal{D}$ $= \\{\\left(x_{i}, y_{i}\\right)\\}_{i=1}^{n}$ $\\in$ $\\left(\\mathcal{X} \\times \\mathcal{Y}\\right)^{n}$\n\nand unlabeled data\n\n$\\mathcal{U}$ $=\\{\\left(x_{i}, \\mathcal{Y}\\right)\\}_{i=n+1}^{m}$ $\\in$ $\\left(\\mathcal{X} \\times 2^\\mathcal{Y}\\right)^{m-n}$\n\nfrom the same data generation process, whereby $\\mathcal{X}$ is the feature space like above and unlabeled data are notationally equated with observing the full categorical target space ${\\cal Y}$.\n\nSelf-training involves fitting a model identified with parameters $\\theta$ on $\\mathcal{D}$ by ERM and then exploiting this model to predict labels for $\\mathcal{U}$. In incremental self-training, some instances from $\\mathcal{U}$ are selected to be added to the training data (together with the predicted label) according to some regularized data selection criterion $c_r(x,\\theta) = c(x,\\theta) + \\frac{1}{L_s} \\mathcal R(x)$, see definition 2. Amending self-training does the same, but additionally removes instances, see pseudo code below. \n\nThe key insight from our analysis is that the sequence of $\\theta$ converges at a linear rate in case of amending self-training, while it does not for incremental self-training.\n\n$~$\n\n**Algorithm 1**: _Incremental_ Self-Training in Semi-Supervised Learning\n\n**Input**: Labeled data $\\mathcal{D}$, Unlabeled data $\\mathcal{U}$\n\n**Output**: Updated labeled data $\\mathcal{D}$, fitted model $\\theta$\n\n**While** stopping criterion not met:\n\n1. **Fit** model $\\theta$ on $\\mathcal{D}$\n\n2. **For** each $i \\in \\{1, \\dots, \\lvert \\mathcal{U} \\rvert \\}$:\n\n   - **Compute** $c(x_i, \\theta)$\n\n3. **Obtain** $i^* = \\arg\\max_i c_r(x_i, \\theta)$\n\n4. **Predict** $\\mathcal{Y} \\ni \\hat y_{i^*} = \\hat y(x_{i^*}, \\theta)$\n\n5. **Update** $\\mathcal{D} \\leftarrow \\mathcal{D} \\cup (x_{i^*}, y_{i^*})$, where $y_{i^*} = \\hat y_{i^*} $ from 4.\n\n6. **Update** $\\mathcal{U} \\leftarrow \\mathcal{U} \\setminus \\left(x_{i^*}, \\mathcal{Y}\\right)_{i^*}$\n\n**End While**\n\n$~$\n\n**Algorithm 2**: _Amending_ Self-Training in Semi-Supervised Learning\n\n**Input**: Labeled data $\\mathcal{D}$, Unlabeled data $\\mathcal{U}$\n\n**Output**: Updated labeled data $\\mathcal{D}$, fitted model $\\theta$\n\n**While** stopping criterion not met:\n\n1. **Fit** model $\\theta$ on $\\mathcal{D}$\n\n2. **For** each $i \\in \\{1, \\dots, \\lvert \\mathcal{U} \\rvert \\}$:\n\n   - **Compute** $c(x_i, \\theta)$\n\n3. **Obtain** $i^* = \\arg\\max_i c_r(x_i, \\theta) $\n\n4. **Predict** $\\mathcal{Y} \\ni \\hat y_{i^*} = \\hat y(x_{i^*}, \\theta)$\n\n5. **For** each $j \\in \\{1, \\dots, \\lvert \\mathcal{D} \\rvert \\}$:\n\n   - **Compute** $c(x_j, \\theta)$\n\n6. **Obtain** $j^{\\text{✝}} = \\arg\\min_j c_r(x_j, \\theta)$\n\n7. **Update** $\\mathcal{D} \\leftarrow \\mathcal{D} \\cup (x_{i^*}, y_{i^*}) \\setminus (x_{j^{\\text{✝}}}, y_{j^{\\text{✝}}})$, where $y_{i^*} = \\hat y_{i^*} $ from 4.\n\n8. **Update** $\\mathcal{U} \\leftarrow \\mathcal{U} \\setminus \\left(x_{i^*}, \\mathcal{Y}\\right)_{i^*}$\n\n**End While** \n\n---\n\nWe also agree that the overall writing and presentation (beyond section 5) needed further polishing. Besides revising the other two passages mentioned by the reviewer, we have 1) added Thompson sampling bandits as an illustrative running example including simulations, see reply to Br7x, 2) provided more context for conceptual explanations, 3) corrected typos, and 4) added results from experiments with amending self-training (Algo. 2) on real world data to further illustrate the concrete implications of our results, see reply to Br7x. \n\n$~$\n\n**level of surprise**\n\nWe are in accord with the reviewer w.r.t the main strengths of our paper, which lie in the conceptualization. However, we also consider the stability guarantees and (approximate) optimality guarantees provided by our paper in this broad setup a valuable contribution. We fully agree with the reviewer that the proof techniques used are rather standard and therefore not really surprising (from a technical perspective). However, the fact that such standard techniques are suitable to derive general guarantees in such a general and interesting framework is - at least from our point of view - quite surprising.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZPkkflgps3", "reviewer": "Reviewer_y1vN", "summary": "This paper models the general process of learning where the data and the parameters are learned iteratively under a new framework of reciprocal learning. Moreover, it provides convergence results given regularity.", "questions": "It is usually challenging to validate a new general framework if no new insights can be drawn from it. Therefore, my question is: why frame such a general framework when the most general phenomenon that can be stated is Lipschitzness? Are there any specific facts, whether in terms of algorithms or analysis, or any conclusions of intellectual interest that are not already known that can be derived from this framework?", "limitations": "adequately addressed", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a general view of the learning tasks and is novel to my knowledge. It is interesting to see that a general convergence result holds.", "weaknesses": "The convergence result does not seem to capture phenomena beyond Lipschitz continuity and strong convexity, which makes the result appear somewhat limited. In the case of bandits, it is quite well-known that UCB converges; however, this framework does not seem to be able to recover it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank Reviewer y1vN for the thorough and helpful review of our work. \nWe are glad the reviewer acknowledges both the soundness and the contribution of our paper as “good”. We completely agree that the presentation (“fair”) could be improved, as we did in response to the reviews, see below and also see reply to T1mz. Furthermore, we are pleased the reviewer emphasizes the novelty and generality of our results. We are grateful the reviewer also asked two critical questions, giving us the chance to clarify:\n\n**“does not seem to capture phenomena beyond Lipschitz continuity and strong convexity, which makes the result appear somewhat limited” / “why frame such a general framework when the most general phenomenon that can be stated is Lipschitzness?“** \n\nWe completely agree with the reviewer that Lipschitzness can be seen as a strong condition, and the sample adaption induced by UCB is indeed an example that does not fulfill it. On the other hand, being so specific about the loss function (strongly convex, cont. differentiable in parameters and features, see assumption 1-3) and the Lipschitzness of sample adaption (see cond. for theorem 1 and 2) allows us to get meaningful results on convergence and optimality for a pretty wide array of algorithms. These conditions appear to be the price we need to pay for the paper’s unifying view on these diverse algorithms. We regard this as the main strength of our work: It connects the dots between many (at first sight) different ML algorithms. This connection apparently only holds under specific conditions on loss and sample adaption.\n\nEven if these specific conditions *were* severely limiting the practical applicability of our results (which we think they are not, at least not in a severe way, see below), the connecting view would still be of much interest to the ML community. This is because it allows to transfer methods/results from one field to another, regardless of convergence and optimality. Plus it might serve as a starting point of research towards such general results on convergence and optimality under weaker assumptions.     \n  \nNevertheless, it is worth emphasizing that we firmly believe our conditions are *not* an extremely severe limitation. We demonstrate in section 5 that they are fulfilled by e.g., amending self-training algorithms, active learning from weak oracles and Thompson sampling bandits, see below and also see the simulation results explained in the reply to reviewer Br7x. We admit that the presentation of these corollaries can be improved and we have put much effort in communicating and illustrating them more clearly. Due to character limitations for this rebuttal, we refer to our reply to reviewer T1mz for details on how we specifically changed the presentation.  \n\n  \n\n\n**\"Are there any specific facts, whether in terms of algorithms or analysis, or any conclusions of intellectual interest that are not already known that can be derived from this framework?”**\n\nOne intriguing insight from our analysis relates to data regularization. To the best of our knowledge, it was not already known that regularization (as opposed to randomization, which is pretty common in bandits or active learning) leads to convergence. This novelty is also acknowledged by reviewers T1mz and MkM4, cf. reviewer T1mz: “The concept of data (as opposed to parameter) regularization appears to be a new and interesting idea.” We agree and emphasize that parameter regularization has proven to be of great practical advantage both in statistics and machine learning. The concept of data regularization might bear similar practical potential.\n\nAnother conclusion of intellectual interest (besides the fact that such “a general convergence result holds”, as you have put it yourself) relates to self-trainingin semi-supervised learning, see reply to reviewer T1mz. Here, one practically relevant and novel insight is that amending strategies (that add and remove self-labeled data) converge under cond. 2 (probabilistic pred.) and cond. 1 or 3 (regularization or randomization) , while incremental and batch-wise strategies (that only add self-labeled data) do not. This directly follows from the positive result in theorem 3 and the negative result in theorem 5. \n\nMoreover, we have learned from our analysis that active learning with soft oracle (providing soft labels, i.e., probabilities) converges, while active learning with hard labels can diverge, see corollary 3.   \n\nIn line with our reply to reviewer T1mz, we admit that the presentation/explanation in section 5 of all these conclusions about specific instances of reciprocal learning needed further polishing. In the revised version, we used the additional page provided to explain the different setups in more detail, see reply to T1mz. We further illustrate these corollaries with experiments on simulated and real world data, as suggested by reviewer Br7x.\n\nGenerally, we think that there are many “specific facts in terms of algorithms or analysis” that can be derived from our paper. And we conjecture there might be even more not yet known. This is because our analysis identified sufficient conditions for convergence and optimality of reciprocal learning, which paves the way for a theory-informed design of novel algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CdmhDlvAfB", "reviewer": "Reviewer_Br7x", "summary": "This paper introduced a unifying framework that generalizes a range of ML algorithms that consist of data selection in a *reciprocal learning* fashion. The paper then presents requirements that guarantee convergence of these algorithms. It shows when and how fast these algorithms converge to an approximately optimal model.", "questions": "1. I would suggest the authors start with an example and build the theory around that, rather than starting so general so that you have to spend 5 pages on introduction and definitions; for instance, Theorem 1 holds only for binary classification, so we could start with that instead.\n\n2. How would you generalize Theorem 1 to multi-class classification? It would be a good practice to add to the Appendix.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper clearly defines the conditions and states the results rigorously using proper notation. This helps with readability and reproducibility of the results.\n\n2. The reciprocal learning framework is general enough to include several different ML algorithms; therefore, the results in this paper make a significant contribution to the ML theory literature.", "weaknesses": "1. The paper lacks empirical studies; the validity of the theoretical results (e.g., the corollaries in Sec 5) could be tested using examples given in Sec. 3. For instance, the condition on $L$ given in Theorem 3 could be validated through a simple Thompson sampling bandits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank Reviewer Br7x for the thorough and helpful review of our work. We are glad the reviewer acknowledges the “significant contribution to the ML theory literature” of our paper. \n\nBelow, we answer both the reviewer’s questions. We start, however, by addressing the only weakness mentioned by the reviewer.\n\n**“The paper lacks empirical studies”**\n\nAs suggested by the reviewer, we illustrate the condition on $L$ for Theorem 3 for Thompson sampling bandits. We conduct a simulation study with 6-armed simple Bernoulli bandits. Through randomized data selection and probabilistic predictions (see Condition 1 and 2, which is given in standard TS), we retrieve $L=\\frac{1}{2}$ and $\\beta = 2$. Note that regularization of data selection (Condition 1) is not necessary, since Theorem 3 requires either randomization **or** regularization of data selection. However, we need to regularize parameter estimation, i.e., classical ERM, through classical Tikhonov-regularization with regularization parameter $\\frac{\\gamma}{2}$, such that the logistic loss function is $\\gamma$-strongly convex as per Assumption 3, see also appendix E.2. \n\nTheorem 3 states that reciprocal learning converges at linear rates, if it is sufficiently Lipschitz in the sense that the following holds for its Lipschitz-constant $L$:\n\n$$ L \\leq  \\frac{1}{(1 + \\frac{\\beta}{\\gamma} )} $$ \n\nIt becomes evident that this holds for $\\gamma \\geq 2$ in our study, since $L=\\frac{1}{2}$ and $\\beta = 2$ . By varying the regularization parameter $\\frac{\\gamma}{2}$, we can illustrate this requirement for convergence. We run $1000$ trials for each regularization parameter\n$\\frac{\\gamma}{2}= 0.000001$, $\\frac{\\gamma}{2}=0.001$, $\\frac{\\gamma}{2}=1$.\nResults are included in the pdf which is attached to our general reply to all reviewers. We observe the L2-Norm of the parameter vectors (solid black line) to stabilize in case of $\\gamma = 2$ (reg. parameter $\\frac{\\gamma}{2}=1$), while no stabilization is observed for $\\gamma < 2$ (reg. parameter $< 1$). \n\nExcitingly, this simulation further provides us with some concrete intuition on why $\\gamma \\geq 2$ is needed here. The regularizer smooths out the effect of current $\\theta$ on arm selection. It thus enforces that currently suboptimal arms are played more often, which leads to a more stable estimate of their respective parameters. You can see this by observing the single parameter values (grey lines) in the plots in the attached pdf (see above).  \n\nIn the absence of randomization of data selection, regularized data selection is required for convergence in reciprocal learning, which was an intriguing result of our analysis and to the best of our (and reviewer T1mz’s and reviewer MkM4’s) knowledge, a novel insight. We demonstrate that regularization in the absence of randomized data selection together with probabilistic predictions (as before) also guarantees Lipschitz-continuity of the non-greedy sample adaption function and thus convergence at linear rates as per Theorem 3. We therefore conduct additional experiments with regularized instead of randomized data selection.\n\nAs suggested by the reviewer, we run these experiments for the example given in Sec. 3, namely amending self-training with soft labels in semi-supervised learning. We use a generalized additive model and various selection criteria from the literature (sources: see pdf), one of which is regularized s.t. $ L \\leq  (1 + \\frac{\\beta}{\\gamma} )^{-1} $. We deploy amending self-training with soft labels on two real world datasets, one from the life sciences (breast cancer data) and one from the social/economic sciences (banknote data) with 80% unlabeled data each. Results again confirm convergence in case of $ L \\leq  (1 + \\frac{\\beta}{\\gamma} )^{-1} $, see pdf. Interestingly, the unregularized criterion of predictive variance also imposes convergence, at least for the case of banknote data. Note that this is in line with our analysis: We only rule out convergence in case of incremental self-training, see also reply to T1mz.\n\nWe will make all code to reproduce these experiments public after acceptance. (We are not allowed to share code through links to anonymous repositories during the rebuttal.) \n\nSince we addressed the only weakness you mentioned so thoroughly, we would appreciate it a lot if you took these additional simulations and experiments into account in your final assessment. Thank you very much.\n\n\n**“start with an example and build the theory around that””**\n\nWe agree with the reviewer that illustrating the theoretical reasoning with a running example would improve the accessibility of the paper and increase the potential audience, see also the remarks on presentation by reviewer T1mz. For this reason, we use a substantial share of the extra page in the revision of the manuscript for this very purpose. We have decided to use the suggested study on Thompson sampling bandits (see above) as a running example, which will be built up successively with the introduction of the new concepts. Many thanks for the valuable advice! \n \n**“How would you generalize Theorem 1 to multi-class classification? It would be a good practice to add to the Appendix.”**\n\nIf we do not oversee some subtleties, then Theorem 1 would translate straight-forwardly to multi-class classification: For condition 2, soft label prediction p should be changed to $p: \\mathcal{X} \\times \\Theta \\longrightarrow [0,1]^K$ and it should be assumed that it is e.g., of multilogistic form with bounded derivative (which can be ensured by bounded $\\mathcal{X}$) , which would make it Lipschitz (say with constant $L$) in every component and therefore also  Lipschitz in $[0,1]^K$ with Lipschitz constant $L K$. This Lipschitz-continuity would then naturally translate to (the natural multivariate generalization of) $f$ and $f_n$, respectively (due to construction). We will add a more detailed reasoning to the appendix, as suggested by the reviewer.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
$~$

**Authors’ summary of reviews:** *The paper is found to have sound and rigorously stated results for the unifying, interesting framework of "reciprocal learning" with relevant and novel implications for self-training, bandits, and active learning. Presentation of those implications could be improved by more detailed writing and illustrative simulations.*

$~$

We sincerely thank all four reviewers for assessing our manuscript so thoroughly! We are encouraged by the favorable, affirmative reviews and feel grateful for the precise and constructive suggestions on how to further improve our paper, especially in terms of presentation and writing.

We are glad all the reviewers consider our “new, unifying” (T1mz) perspective on a wide range of ML algorithms through the lens of data-parameter reciprocity to be “novel” (y1vN, MkM4), carrying “interesting” (MkM4, T1mz) insights and ideas such as data regularization. Our results on convergence and optimality are found to be of “excellent” soundness (MkM4), previously “unexplored in the respective literatures” (T1mz) and – once again – “interesting” (y1vn). Reviewer Br7x underlines that “the results in this paper make a significant contribution to the ML theory literature.”

Besides the theoretical analysis, the reviewers unanimously acknowledge the *conceptual* generality of reciprocal learning, serving as “a bridge between several literatures”, as reviewer T1mz puts it. This is the very reason why we consider NeurIPS an excellent venue for this paper. The conference is known for bringing together various subfields of artificial intelligence and machine learning. 

Generally, neither the relevance/novelty nor the soundness/correctness of the paper’s results were questioned. The reviews rather focused on the presentation of these results' implications for concrete instances (mainly Reviewer T1mz and y1vN) as well as on practical algorithms/simulations (mainly reviewer MkM4 and Br7x). We took the reviewers’ suggestions on how to address these aspects very seriously and have put quite some effort in further improving our manuscript:

* **presentation:** In terms of assessing writing and presentation, the reviews exhibit some variation. Reviewer Br7x notes that our paper “clearly defines the conditions and states the results rigorously using proper notation. This helps with readability.” Reviewer T1mz, however, considers writing and presentation the paper’s “main weakness.” This is how we read these mixed opinions: While the presentation of theoretical results – including sufficient conditions and detailed proofs, which are mostly constructive and with a lot of contexts – is considered very readable, the transfer to specific instances requires further clarification. In line with this, reviewers T1mz and y1vN ask for more details on (and further interpretation of) our results’ implications for existing methods in the literature that are subsumed by, or related to, reciprocal learning. We completely agree that an expanded and improved presentation will help “bringing diverse groups of researchers together” (T1mz). To do so, we have

  * included Thompson sampling (TS) bandits as a running example along with simulation studies that a) illustrate TS bandits as a concrete instance of reciprocal learning and b) confirm conditions of our theorems and corollaries, see reply to Br7x.

  * polished the overall writing by correcting typos and adding more context to conceptual explanations. 

  * provided *way* more details on all concrete algorithms mentioned, see our “pars pro toto” example in the reply to T1mz.



* **simulations:** Reviewer MkM4 legitimately criticizes missing links to “practically relevant algorithm design” and reviewer Br7x asks for "empirical studies". We hear you and adopt your suggestions to

   * include simulations confirming our convergence results empirically for Thompson sampling bandits, see attached pdf. For an explanation of the concrete setup, we refer to our reply to reviewer Br7x.

   * conduct detailed experiments for the example in section 3 (self-training in semi-supervised learning) using real world data. Results again confirm our theorems, see attached pdf and reply to Br7x.

   * notably, the illustrative simulations and experiments also foster a better understanding of the concrete implications of our results and thus add to a clearer and more accessible presentation, too, see above.

   * visualizations of simulations'/experiments' results can be found in the **attached pdf**. Please refer ro reply to reviewer Br7x for explanations and interpretations of these results.


The reviewers also pointed out very interesting references that sparked deep discussions within the author team. Thanks for that! We have tried to summarize those in the individual replies as well as in the related work section of the revised paper.

Besides these main points, we also responded to every minor/notational remark. We are confident we have addressed and resolved all issues thoroughly. We would very much appreciate it if the reviewers took our answers, revisions, and the additional simulations/experiments into account in their final assessment.

**Conclusively, we would like to thank the reviewers again for helping us improve our paper. We believe it really did.**

$~$

Meta-review: This paper considers a general frame work for sequential decision problems that alternates between rounds of ERM and data collection and asks an interesting question -  what conditions on the data collection process guarantee convergence of the ERM. They demonstrate a Lipschitz condition, which can be guaranteed by regularizing the underlying data collection function.

The reviewers (and I) agree that this is an interesting avenue of exploration, and that the paper provides some useful insights. One of the key concerns was readability. I appreciate the additional experiments that were added, and in general would encourage the authors to work on the clarity of the paper and follow some of the reviewer suggestions - 1) use a running example throughout, b) add connections with the current literature. For the latter, the authors may want to take a look at https://arxiv.org/abs/2106.02126 - I think the current paper shines light on the very different behaviors of UCB vs Thompson Sampling.
Decision: Accept (poster)