Reciprocal Learning

Authors: julian  rodemann
christoph  jansen
georg  schollmeyer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:20:24

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.

Main paper: 
 introduction: 
 The era of data abundance is drawing to a close. While GPT-3 [9] still had to make do with 300 billion tokens, Llama 3 [102] was trained on 15 trillion. With the stock of high-quality data growing at a much smaller rate [67] , adequate training data might run out 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 not the exclusive route to success. Models also have to learn from which data to learn. This has sparked a lot of interest in sample efficiency [70, 92, 111, 7, 46, 27, 105] , subsampling [47, 101, 71] , coresets [62, 76, 86] , data subset selection [55, 113, 13, 82] , and data pruning [32, 118, 57, 5] in recent years.Instead of proposing yet another method along these lines, we demonstrate that a broad spectrum of well-established machine learning algorithms already exhibits a reciprocal relationship between data and parameters. That is, parameters are 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] , see section 2.1. They iteratively add 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. Other examples comprise active learning [93] , Bayesian optimization [63, 64, 98] , superset learning [35, 34, 85, 36] , and multi-armed bandits [3, 81] , see Appendix A for details.In this paper, we develop a unifying framework, called reciprocal learning, that allows for a principled analysis of all these methods. After an initial model fit to the training data, reciprocal learning algorithms alter the latter in a 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. 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 is well-understood for classical empirical risk minimization (ERM), where it refers to the sequence of model parameters. In reciprocal learning, however, we need to extend the notion of convergence to 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 a unique model and use it for deployment or assessment on test data. Practically speaking, convergence of a training procedure means that subsequent iterations will no longer change the model, giving rise to stopping criteria. Generally speaking, convergence is a prerequisite for any further theoretical or empirical assessment of such methods. In the literature on reciprocal learning algorithms like active learning, self-training, or multi-armed bandits, there is no consensus on when to stop them. And while a myriad of stopping criteria exist [109, 121, 48, 110, 28, 22, 11, 79, 96] , only some come with generalization error bounds [41, 40, 88] , but none -to the best of our knowledgecomes 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 a decision-theoretic perspective on both the parameter and the data selection problem. While the former is well studied, in particular its ubiquitous solution strategy ERM, little attention is commonly paid to a formal treatment of the other side of the coin: data selection. We particularly study the hidden interaction between parameter and data selection. We identify a sample adaption function 𝑓 which maps from the sample and the empirical risk minimizer in iteration 𝑡 to the sample in 𝑡 + 1. Bounding the change of the sample in 𝑡 + 1 by the change in the sample and the change in the model in 𝑡 (i.e., 𝑓 being Lipschitz-continuous with a sufficiently small constant) will turn out to guarantee convergence of reciprocal learning algorithms. In response to this key finding, we study which algorithms fulfill this restriction on 𝑓 . We prove that the sample adaption is sufficiently Lipschitz for reciprocal learning to converge, if (1) it is non-greedy, i.e., it adds and removes data, (2) predictions are probabilistic and (3) the selection of data is either randomized or regularized. Conclusively, we transfer these results to common practices in active learning, self-training, and bandits, showing which algorithms converge and which do not. 
reciprocal learning: 
 Machine learning deals with two pivotal objects: data and parameters. Typically, parameters are learned from data through ERM. In various branches of 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 on reciprocity between parameters and training data only. The population and test data thereof are assumed to be fixed, i.e., our inference goal is static. Specifically, we call a machine learning algorithm reciprocal if it performs iterative ERM on training data that depends on the previous ERM, see definition 1. This dependence can be induced by any kind of data collection, removal, or generation that is 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 𝜃 𝑡 = arg min 𝜃 E (𝑌 ,𝑋)∼P 𝑡 ℓ(𝑌 , 𝑋, 𝜃) shall be called reciprocal learning algorithm if P 𝑡 = 𝑓 (𝜃 𝑡 -1 , P 𝑡 -1 , 𝑛 𝑡 -1 ), where P 𝑡 ∈ P are empirical distributions -from a space of probability distributions P -of 𝑌 , 𝑋 of size 𝑛 𝑡 in iteration 𝑡 ∈ {1, . . . , 𝑇 }. Let ℓ(𝑌 , 𝑋, 𝜃) = ℓ(𝑌 , 𝑝(𝑋, 𝜃)) denote a loss function with 𝑝(𝑋, 𝜃) a prediction function that maps to the image of 𝑌 . Further denote by 𝑌 , 𝑋 random variables describing the training data, and 𝜃 𝑡 ∈ Θ a parameter vector of the model in 𝑡.In principle, the above definition needs no restriction on the nestedness between data in 𝑡 and 𝑡 -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 A. That is, data in 𝑡 is either a superset of data in 𝑡 -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 as non-greedy (adding and removing data). For classification problems, i.e., discrete image of 𝑌 , we typically have 𝑝(𝑋, 𝜃) = 𝜎(𝑔(𝑋, 𝜃)) with 𝜎 : R → [0, 1] a sigmoid function and 𝑔 : X × Θ → R. For regression problems, we simply have 𝑝 : X × Θ → R. The notation P 𝑡 = 𝑓 (𝜃 𝑡 -1 , P 𝑡 -1 , 𝑛 𝑡 -1 ) shall be understood as a mere indication of the distribution's dependence on ERM in the previous iteration. We will be more specific soon.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 definition 1 and more formally in definitions 6 and 7 below. Here, we seek to illustrate the principles of reciprocal learning by the simple running example of self-training in a semi-supervised learning (SSL) setup. The aim of SSL is to learn a predictive classification function ŷ(𝑥, 𝜃) parameterized by 𝜃 utilizing both labeled and unlabeled data. Self-training is a popular algorithm class within SSL. Algorithms of that class start by fitting a 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 a "confidence score", a measure of predictive uncertainty, see [2, 49, 80, 83, 53, 84, 18] 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 1. The sample of labeled and pseudo-labeled data in 𝑡 depends on the sample and the model (through its predicted pseudo-labels) in 𝑡 -1. For a more comprehensive and formal introduction of self-training, we refer the curious reader to appendix A.1.On a high level, reciprocal learning can be viewed as sequential decision-making. First, a parameter 𝜃 𝑡 is fitted through ERM, which corresponds to solving a decision problem characterized by the triple (Θ, A, L) with Θ the unknown set of states of nature, the action space A = Θ of potential parameter fits (estimates), and a loss function L : A × Θ → R, analogous to classical statistical decision theory [6] . Secondly, features 𝑥 𝑡 ∈ X are chosen and data points (𝑥 𝑡 , 𝑦 𝑡 ) are added to or removed from the training data inducing a new empirical distribution P 𝑡+1 , where 𝑦 𝑡 is predicted (self-training), queried (active learning) or observed (bandits). These features 𝑥 𝑡 are found by solving another decision problem (Θ, A, L 𝜃 𝑡 ), where -crucially -the loss function L 𝜃 𝑡 depends on the previous decision problem's solution 𝜃 𝑡 . 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: 𝜃 1 solves decision problem (Θ, Θ, L) 𝑎 1 solves decision problem (Θ, A, L 𝜃 1 ) 𝑡 = 2: 𝜃 2 solves decision problem (Θ, Θ, L 𝑎 1 ( 𝜃 1 ) ) 𝑎 2 solves decision problem (Θ, A, L 𝜃 2 )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 (Θ, Θ, L) is well-known through its solution strategy ERM, see definition 1, we want to be more specific about (Θ, A, L 𝜃 𝑡 ) with A = X. In particular, we need a solution strategy for all of the loss functions in the family L 𝜃 : X × Θ → R; (𝑥, 𝜃) ↦ → L 𝜃 𝑡 (𝜃, 𝑥) in iteration 𝑡. Definition 2 does the job. The family L 𝜃 describes all potential loss functions in the data selection problem arising from respective solutions of the parameter selection problem. 1 Redefining this family of functions as a single one L : X × Θ × Θ → R makes it clear that we can retrieve the decision criterion 𝑐 : X × Θ → R from it, which is a generalization of classical decision criteria 𝑐 : X → R retrieved from classical losses L : X × Θ → R, see [6] for instance. Definition 2 (Data Selection). Let 𝑐 : X ×Θ → R be a criterion for the decision problem (Θ, A, L 𝜃 𝑡 ) with bounded A = X of selecting features to be added to the sample in iteration 𝑡. Define c : ) as standardized version thereof with 𝜇 the Lebesgue measure on X. For a model 𝜃 𝑡 in iteration 𝑡, it assigns to each feature vector 𝑥 a value between 0 and 1 that can be used as drawing probabilities. Drawing 𝑥 ∈ X according to c(𝑥, 𝜃 𝑡 ) shall be called stochastic data selection 𝑥 𝑠 (𝜃 𝑡 ). 2 The function 𝑥 𝑑 : Θ → X; 𝜃 𝑡 ↦ → arg max 𝑥 ∈X c(𝑥, 𝜃 𝑡 ) shall be called deterministic data selection function. The data selection function can be understood as the workhorse of reciprocal learning: It describes the non-trivial part of the sample adaption function 𝑓 , see definition 1. For any model 𝜃 𝑡 in 𝑡, a data selection function chooses a feature vector to be added to the training data in 𝑡 + 1, based on a criterion 𝑐. This happens either stochastically through 𝑥 𝑠 by drawing from X according to c or deterministically through 𝑥 𝑑 . Examples for 𝑐 comprise confidence measures in selftraining, acquisition functions in active learning, or policies in multi-armed bandits. For an example of stochastic data selection, consider 𝑐 to be the classical Bayes criterion [6] in (Θ, A, L 𝜃 𝑡 ). In this case, drawing from X as prescribed by 𝑥 𝑠 corresponds to well-known Thompson sampling [12, 90] . As already hinted at, we will need some regularization (definition 3) of the data selection. Intuitively, the regularization term smoothes out the criterion 𝑐(•, 𝜃). In other words, the higher the constant 1 𝐿 𝑠 , the less the selection of data is affected by small changes of 𝜃 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 .X×Θ → [0, 1]; (𝑥, 𝜃 𝑡 ) ↦ → exp(𝑐 ( 𝑥, 𝜃 𝑡 ) ) ∫ 𝑥 ′ exp(𝑐 ( 𝑥 ′ , 𝜃 𝑡 ) ) 𝑑 𝜇 ( 𝑥Definition 3 (Data Regularization). Consider 𝑐 : X × Θ → R a criterion for the decision problem (Θ, A, L 𝜃 𝑡 ) with c as in definition 2. Define the following regularized (deterministic) data selection function:𝑥 𝑑,R : Θ → X; 𝜃 ↦ → argmax 𝒙∈X 𝑐(𝒙, 𝜃) + 1 𝐿 𝑠 R (𝒙) ,where R (•) is a 𝜅-strongly convex regularizer. In complete analogy to definition 2, we can define a stochastic regularized data selection function as 𝑥 𝑠,R (𝜃) by drawing 𝑥 ∈ X according to a normalized version of 𝑐(𝒙, 𝜃) + 1 𝐿 𝑠 R (𝒙).1 Like most other sequential decision-making problems, solving these decision problems by extensive search computationally explodes, both in the normal and extensive form [37, 38] . Reciprocal learning thus corresponds to a one-step look-ahead approximation. As such, it is a method that aims at subtree solutions in the extensive form. Reciprocal learning can be understood as a compromise between the sub-optimal greedy strategy and infeasible extensive search. 2 An alternative to stochastic data selection via direct randomization of actions is discussed in appendix D.We will denote a generic data selection function as ‫ש‬ ∈ {𝑥 𝑑 , 𝑥 𝑠 , 𝑥 𝑑,R , 𝑥 𝑠,R } in what follows. For the non-greedy variant of reciprocal learning, where data is both added and removed, we need to define data removal as well. A straightforward strategy is to randomly remove data points with uniform removal probabilities. The following function ‫ש‬ -describes the effect of this procedure in expectation. Definition 4 (Data Removal Function). Given an empirical distribution P(𝑌 , 𝑋) of a sample, the function ‫ש‬ -: P → X; P(𝑌 , 𝑋) ↦ → ∫ 𝑋 𝑑P(𝑋) shall be called data removal function.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 in 𝑡 - EQUATIONin case of Y = {0, 1}, where ‫צ‬ : X × Θ → {0, 1} is any function that assigns a label 𝑦, potentially based on the model 𝜃, to selected 𝑥, and ‫ש‬ any function that selects features 𝑥 given a model 𝜃, for example, 𝑥 𝑑 , 𝑥 𝑠 , 𝑥 𝑑,R , or 𝑥 𝑠,R as defined above. They give rise to P‫צ‬ and P‫ש‬ , respectively. We can be so specific about the sample adaption function due to 𝑃(𝑌 = 1, 𝑋 = 𝑥) = 𝑃(𝑋 = 𝑥) -𝑃(𝑌 = 0, 𝑋 = 𝑥) in binary classification problems. We can analogously define the non-greedy variant 𝑓 𝑛 (𝜃, P(𝑌 , 𝑋)), where one instance is removed by ‫ש‬ -and one instance is added by ‫ש‬ per iteration. To this end, define P ′ (𝑌 = 1, 𝑋 = 𝑥) by replacing the integrand in equation (1) byEQUATIONwhere 𝑛 0 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 [29] , see section 5 for a discussion.We can now define reciprocal learning (definition 1) more formally given the sample adaption function as follows, both in greedy and non-greedy flavors. An optimal 𝜃 * (or 𝜃 * 𝑛 , analogously) not only solves ERM on the sample it induces, but is also the best ERM-solution among all possible 𝜃 (𝜃 𝑛 ) that could have led to optimality on the respectively induced sample. In other words, 𝜃 * (𝜃 * 𝑛 ) is found by minimizing the empirical risk with respect to whole 𝑅 (𝑅 𝑛 ). That is, it is found by minimizing the empirical risk with respect to 𝜃 given a sample (characterized by P and 𝑛) and steering this very sample through 𝜃 simultaneously given only the initial sample. Technically, optimality (definition 9) is a bivariate arg min-condition on E (𝑌 ,𝑋)∼ 𝑓 𝑛 ( 𝜃 ,P) ℓ(𝑌 , 𝑋, 𝜃) and E (𝑌 ,𝑋)∼ 𝑓 ( 𝜃 ,P,𝑛) ℓ(𝑌 , 𝑋, 𝜃), respectively. In contrast, convergence (definition 8) translates to a fixed-point condition on the arg min views as a function Θ × P × N → Θ × P × N in case of 𝑅 and as Θ × P → Θ × P in case of 𝑅 𝑛 , see section 3.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 𝑓 𝑆𝑆𝐿 : Θ × P × N → P; (𝜃, P(𝑌 , 𝑋), 𝑛) ↦ → P ′ (𝑌 , 𝑋) defined through P ′ (𝑌 , 𝑋) being induced byEQUATIONwhere 𝑥 𝑑 (𝜃) (definition 2) selects data with highest "confidence score" [2, 49, 80, 83, 53, 84, 18] , see section 2.1, according to the model 𝜃, and gives rise to P𝑋 . The prediction function ŷ : X × Θ → {0, 1} returns the predicted "pseudo-label" of the selected 𝑥 𝑑 (𝜃) based on the learned model 𝜃 and gives rise to P𝑌 | 𝑋 . Moreover, we still assume binary target variables, i.e., the image of 𝑌 is {0, 1}, real-valued features 𝑋, and only consider cases where the sample changes through the addition of one instance per iteration. 3 The averaging with respect to P𝑋 and P𝑌 | 𝑋 accounts for the fact that we allow stochastic inclusion of 𝑋 in the sample through randomized actions and for probabilistic predictions of 𝑌 | 𝑋, respectively. For now, however, it suffices to think of the special case of degenerate distributions P𝑋 and P𝑌 | 𝑋 putting point mass 1 on data with hard labels in the sample and 0 elsewhere. 4 Through averaging with respect to P𝑌 | 𝑋 we can describe the joint distribution of hard labels (𝑦 1 , 𝑥 1 ), . . . , (𝑦 𝑛 , 𝑥 𝑛 ) and predicted soft labelsỹ = p(𝑌 = 1 | 𝑥, 𝜃) ∈ [0, 1]of ( ỹ𝑛+1 , 𝑥 𝑛+1 ), . . . , ( ỹ𝑛+𝑡 , 𝑥 𝑛+𝑡 ). Summing up, both deterministic data selection and non-probabilistic (i.e., hard labels) predictions are well-defined special cases of the above with P𝑌 | 𝑋 and P𝑋 collapsing to trivial Dirac measures, respectively.Active learning is a machine learning paradigm where the learning algorithm iteratively asks an 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 to provide the most information. Let X be the input space and Y the set of possible labels. Consider training data Again, both deterministic data selection through 𝑥 𝑑 (𝑠) and non-probabilistic (i.e., hard labels) queries through 𝑞 𝑦 : X ×Θ → {0, 1} are well defined special cases of the above with P𝑌 | 𝑋 and P𝑋 collapsing to trivial Dirac measures, respectively. As far as we can oversee the active learning literature, hard label queries [77, 25, 65] are more common than probabilistic or soft queries [114] .EQUATIONThe 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 a row of slot machines, where each machine provides a different, unknown reward distribution. The gambler must develop a strategy to maximize their rewards over a 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 {𝑋 𝑡 } 𝑇 𝑡=1 , actions {𝐴 𝑡 } 𝑇 𝑡=1 , and primary outcomes {𝑌 𝑡 } 𝑇 𝑡=1 , again with binary image of 𝑌 𝑡 for simplicity, denoted by Y = {0, 1}. We assume that rewards are a deterministic function of the primary outcomes, i.e., 𝑅 𝑡 = 𝑓 (𝑌 𝑡 ) for some known function 𝑓 . Following [115] , we use potential outcome notation [39] and let {𝑌 (𝑎) : 𝑎 ∈ A} denote the potential outcomes of the primary outcome and let 𝑌 𝑡 := 𝑌 ( 𝐴 𝑡 ) be the observed outcome. Define these quantities analogously for 𝑋 (𝑎) and callH 𝑡 := {𝑋 𝑡 ′ , 𝐴 𝑡 ′ , 𝑌 𝑡 ′ } 𝑡 𝑡 ′ =1 (6)the history for 𝑡 ≥ 1 and H 0 := ∅ as in [115] . The fixed and (time-independent) potential joint distributions of 𝑋 𝑡 and 𝑌 𝑡 shall be denoted by {𝑋 𝑡 , 𝑌 𝑡 (𝑎) : 𝑎 ∈ A} ∼ P(𝑋, 𝑌 ) ∈ P for 𝑡 ∈ {1, . . . , 𝑇 }.Further assume that we learn a model of P(𝑋, 𝑌 , 𝐴) or P(𝑌 | 𝑋, 𝐴), which can be parameterized by 𝜃 𝑡 ∈ Θ. Note that for a specific reward function and A = X, active learning could be formulated as a 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 ( 𝐴 𝑡 | H 𝑡 -1 ) is informed by our model 𝜃, i.e.,EQUATIONwhich is a very mild assumption given that the latter is the whole point of 𝜃 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 5) 𝑓 𝑀 𝐴𝐵 : Θ × P × N → P; (𝜃, P(𝑌 , 𝑋), 𝑛) ↦ → P ′ (𝑌 , 𝑋) with P ′ (𝑌 , 𝑋) induced byP ′ (𝑌 = 1, 𝑋 = 𝑥) = ∫ 1(𝑥 = 𝑥(𝑎(𝜃))) • 𝑌 (𝑎(𝜃)) + 𝑛 P(𝑌 = 1, 𝑋 = 𝑥) 𝑛 + 1 P ( 𝐴 𝑡 | 𝜃 (H 𝑡 -1 )) 𝑑𝑎where 𝑎(𝜃) : Θ → A is an action selection function 7 , also referred to as policy function in the bandit literature that induces the well-known action selection probabilities P ( 𝐴 | 𝜃 (H 𝑡 -1 )), often called policies and denoted by 𝜋 := {𝜋 𝑡 } 𝑡 ≥1 . Further note that the indicator function takes an argument that depends on 𝜃 only through 𝑎, contrary to active and semi-supervised learning.Several strategies exist to solve multi-armed bandit problems, including upper confidence bound (deterministic), epsilon-greedy (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 ( 𝐴 | 𝜃 (H 𝑡 -1 )) putting point mass 1 on the deterministically optimal action. We run two simple experiments to illustrate the effect of data regularization (definition 3) on stability of parameters 𝜃 𝑡 in reciprocal learning by the example of self-training in semi-supervised learning, see sections 2.1, A.1 and example 1. Code to reproduce findings can be found in https://github.com/rodemann/simulations-self-training-reciprocal-learning.Specifically, we deploy incremental self-training with soft labels on a real world datasets (banknote data) with 90%, 80%, and 70% unlabeled data, see figures 7a, 7b and 7c. The task is to predict the authenticity of a banknote based on labeled and unlabeled data. We use a generalized additive model and multiple selection criteria from the literature ( [83, 35, 80, 103] ), one of which is regularized according to section 3. We want to compare the stability of the parameter vector 𝜃 𝑡 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) to its unregularized counterpart (red). The goal is not to study convergence under all conditions 1 to 5, but merely to illustrate the stabilizing effect ot the novel concept of data regularization (condition 1) on the sequence of learned parameters. To do so, we compute the L2-norm of the parameter vector 𝜃 𝑡 at each iteration 𝑡, see figures 7a, 7b and 7c. It 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 of 𝜃 𝑡 between experiments.In order to do so, we restart the experiment 40 times and average the L2-norm of 𝜃 𝑡 over these 40 restarts of the experiment and compute 95%-confidence 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 seems to come at the cost of higher between-experiment variation.Definition 10 (Data Selection alternative). Let 𝑐 : X × Θ → R be a criterion for the decision problem (Θ, A, L 𝜃 𝑡 ) of selecting features to be added to the sample in iteration 𝑡. Let D (X) denote a suitable set of probability measures on the measurable space (X, 𝜎(X)). Definec : D (X) × Θ → R (𝜆, 𝜃 𝑡 ) ↦ → E 𝜆 (𝑐(•, 𝜃 𝑡 ))Each 𝜆 ∈ D (X) is interpreted as a randomized feature selection strategy. The function c evaluates randomized feature selection strategies based on the expectation of the criterion 𝑐 under the randomization weights.E.1 General discussion of assumption 1, 2, and 3Assumptions 2 and 3 address the loss function ℓ 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, see [56, 116, 119] and particularly [74] as well as [95] for an overview. Assumption 1 will be needed in both decision problems of data selection and parameter selection, but is still fairly general and mild.Assumption 3 is typically required for fast convergence of repeated ERM solution strategies. Here, it is needed for reciprocal learning to converge at all. Thus, it can be considered a stronger assumption than assumptions 1 and 2. It is easy to see that common loss functions like the linear loss ℓ(𝑦, 𝑥, 𝜃) = 𝜃𝑥𝑦 are convex, but not strongly convex. The same even holds for the logistic loss ℓ(𝑦, 𝑥, 𝜃) = log(1 + exp(𝜃𝑥𝑦)). To see this, consider its second partial derivative ∇ 2 𝜃 ℓ (𝑦, 𝑥, 𝜃). It is∇ 2 𝜃 ℓ (𝑦, 𝑥, 𝜃) = 𝑦 2 𝑥 2 exp(𝜃𝑦𝑥) (1 + exp(𝜃𝑦𝑥)) 2 .It becomes evident that lim 𝑥→∞ lim 𝑦→∞ ∇ 2 𝜃 ℓ (𝑦, 𝑥, 𝜃 ′ ) = 0 Hence, there is no 𝐾 > 0 that can bound ∇ 2 𝜃 ℓ (𝑦, 𝑥, 𝜃) from below. However, a Tikhonov-regularized version thereof ℓ 𝑟 (𝑦, 𝑥, 𝜃) = log(1 + exp(𝜃𝑥𝑦)) + 𝛾 2 ||𝜃|| 2 is 𝛾-strongly convex, which follows from analogous reasoning. This sheds some light on the nature of our sufficient conditions for convergence, see also section 6. In fact, we require regularization of parameters to obtain strong convexity of the loss function and of data to obtain Lipschitz-continuity of the sample adaptions, see theorem 1. This paves the way for theory-informed design of regularized reciprocal learning algorithms that are guaranteed to converge.Proof. Recall definition 2 of 𝑐 : X × Θ → R as a criterion for the decision problem (Θ, A, L 𝜃 𝑡 ). We will prove the Lipschitz-continuity of regularized data selection:EQUATIONwhere R (•) is a 𝜅-strongly convex regularizer. The variational inequality for the optimality of argmax 𝒙∈X 𝑐(𝒙, 𝜃)EQUATION)Symmetrically for 𝑠 (𝜃 ′ )EQUATION)Summing the above two inequalities yieldsEQUATION)Rearranging terms,EQUATIONIt is a known fact that for any 𝜅-strongly convex function R it holds that (∇R (𝑥) -∇R (𝑦)) 𝑇 (𝑥 -𝑦) ≥ 𝜅∥𝑥 -𝑦∥ 2 , ∀𝑥, 𝑦. This allows lower-bounding the left-hand side by 𝜅 𝐿 𝑠 ∥𝑠(𝜃) -𝑠 (𝜃 ′ ) ∥ 2 . If 𝑐 is linear in 𝑥 we have 𝑐(𝑥, 𝜃) = 𝑥 • 𝑔(𝜃) for some appropriate function 𝑔. Thus, ∇ 𝑥 𝑐(𝑥, 𝜃) = 𝑔(𝜃) and ||∇ 𝑥 𝑐(𝑠(𝜃 ′ ), 𝜃 ′ ) -∇ 𝑥 𝑐(𝑠(𝜃), 𝜃)|| ≤ 𝐿 𝑐 ||𝜃 ′ -𝜃|| and we can also upper bound the right-hand side using the generalized Cauchy-Schwarz inequality, see also [23, Appendix A.1] .EQUATION)Equivalently,EQUATIONwhich was to be shown. □Proof. By Fubini, ∫ ∫ ŷ(‫,)𝜃(ש‬ 𝜃) p 𝑑𝑦𝑑 P‫ש‬ = ∫ ∫ ŷ(‫,)𝜃(ש‬ 𝜃) p 𝑑 P‫ש‬ 𝑑𝑦. For brevity, set ‫)𝜃(ש‬ = ∫ ‫)𝜃(ש‬ P‫ש‬ ‫.ש𝑑‬ To prove that 𝑝( ‫,)𝜃(ש‬ 𝜃) is Lipschitz-continuos, we will proceed as follows. First, we will show that 𝑝( ‫,)𝜃(ש‬ •) is Lipschitz-continuous. Second, we will show that 𝑝(•, 𝜃) is Lipschitzcontinuous. Third, we will show that the Lipschitz-continuity of 𝑝( ‫,)𝜃(ש‬ 𝜃) follows from the first and second result. 1. To show that 𝑝( ‫,)𝜃(ש‬ •) is Lipschitz-continuous with Lipschitz-constant 𝐿 ‫ש‬ 𝐿 𝑝 , first observe that this holds if ‫)𝜃(ש‬ and 𝑝( ‫,ש‬ •) are both Lipschitz-continuous with Lipschitz-constants 𝐿 ‫ש‬ and 𝐿 𝑝 , respectively, sinceEQUATIONThe first premise of the above statement holds per assumption. Let us now show that the second premise for the above statement holds.To show that 𝑝( ‫,ש‬ •) is Lipschitz-continuous, first recall condition 2, by which we have that 𝑝( ‫,ש‬ •) = 𝑝(𝑥, 𝜃) = 𝜎(𝑔(𝑥, 𝜃)) with 𝜎 : R → [0, 1] a sigmoid function. Further recall that the prediction function of a classifier 𝑝(𝑥, 𝜃) is implicitly given by a loss function ℓ(𝑦, 𝑝(𝑥, 𝜃)) as per definition 1. By assumption 1 we inter alia have that ∇ 𝑥 ℓ(𝑦, 𝑝(𝑥, 𝜃)) is Lipschitz-continuous in 𝑥 for all 𝑦 and 𝜃. By chain rule,EQUATIONNow note that we also have by condition 2 that ∇ 𝑝 ℓ(𝑦, 𝑝(𝑥, 𝜃)) is Lipschitz-continuous in 𝑥. The Lipschitz-continuity of ∇ 𝑥 ℓ(𝑦, 𝑝(𝑥, 𝜃)) in 𝑥 per assumption 1 thus implies the Lipschitz-continuity of ∇ 𝑥 𝑝(𝑥, 𝜃) in 𝑥, because the first is a product of the second and another function that is Lipschitz-continuous in x. Recall that X is bounded (Definition 2 and Condition 2). It is a known fact that any Lipschitz-continuous function is bounded on a bounded domain. We thus concluded that ∇ 𝑥 𝑝(𝑥, 𝜃) is bounded on the whole domain X. Any differentiable function is Lipschitz-continuous if and only if its gradient is bounded. See [95] , for instance. We can thus conclude that 𝑝(𝑥, 𝜃) is Lipschitz-continuous in 𝑥 for all 𝑦 ∈ Y and 𝜃 ∈ Θ.) is Lipschitz-continuous, too. By assumption 2, we have that ∇ 𝜃 ℓ(𝑌 , 𝑝(𝑥, 𝜃)) is Lipschitz-continuous in 𝜃. With reasoning analogous to 1 (b), it follows that 𝑝(𝑥, 𝜃) is Lipschitz-continuous in 𝜃 for all 𝑦 ∈ Y and all 𝑥 ∈ X. First note ∀𝜃, θ ∈ Θ; ∀𝑥, x ∈ X:EQUATIONBy triangle inequality, we getEQUATIONExploiting the Lipschitz-continuity of 𝑝(𝑥, •) and 𝑝(•, 𝜃) allows us to upper bound this expression byEQUATIONwhich eventually deliversEQUATIONWe conclude that 𝑝(𝑥, 𝜃) is Lipschitz-continuous with Lipschitz-constant sup{𝐿 𝜃 , 𝐿 𝑥 } if 𝑝(𝑥, •) and 𝑝(•, 𝜃) are Lipschitz-continuous with Lipschitz constants 𝐿 𝜃 and 𝐿 𝑥 , respectively.The assertion follows from 1., 2., and 3. □Proof. We will first prove the Lipschitz-continuity of the greedy sample adaption 𝑓 : Θ × P × N → P.The strategy of the proof is as follows. We first show that 1. 𝑓 (𝜃, •, •), 2. 𝑓 (•, P(𝑌 , 𝑋), •), and 3. 𝑓 (•, •, 𝑛) are Lipschitz-continuos with Lipschitz constants 𝐿 𝜃 , 𝐿 P , and 𝐿 𝑛 , respectively. We then show in 4. that the Lipschitz-continuity of 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) follows with Lipschitz constant 𝐿 = max{𝐿 𝜃 , 𝐿 P , 𝐿 𝑛 }.1. We prove the Lipschitz-continuity of 𝑓 (𝜃, •, •) given conditions 1, 2, and 5.To show that 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) is Lipschitz-continuous in 𝜃, it is sufficient to show thatEQUATIONis Lipschitz-continuous in 𝜃. First note that by Conditions 1 and 4 we can directly infer that ‫)𝜃(ש‬ is Lipschitz-continuous through lemma 1. In the remainder of the proof, the is as follows. We first show that 𝑓 ‫,ש(‬ •) is Lipschitz-continuos and then demonstrate the Lipschitz-continuity of 𝑓 ‫,)𝜃(ש(‬ 𝜃) in 𝜃. With reasoning analogous to argument (3.) in the proof of lemma 2, it then follows that 𝑓 ‫,)𝜃(ש(‬ 𝜃) is Lipschitz-conitnuous on Θ × Θ.(a) We start by showing that the functionEQUATIONis Lipschitz-continuous in ‫.ש‬ Apply Fubini to getEQUATIONCondition 3 implies that features are drawn according to c :X × Θ → [0, 1] (𝑥, 𝜃) ↦ → exp(𝑐 ( 𝑥, 𝜃 ) ) ∫ 𝑥 ′ exp(𝑐 ( 𝑥 ′ , 𝜃 ) ) 𝑑 𝜇 ( 𝑥 ) , see definition 2. That is, ∫ 1(𝑥 = ‫)ש‬ • ‫,ש(צ‬ 𝜃) P‫ש‬ 𝑑𝑥 = c(‫,ש‬ 𝜃) • ‫(צ‬ c(‫,ש‬ 𝜃), 𝜃). Per condition 5, 𝑐(𝑥, 𝜃) is linear in 𝑥 and thus Lipschitz-continuous in 𝑥. Further note that the mapping 𝑐 → c is a softmax function, which is continuosly differentiable and thus Lipschitz-continuous. We thus conclude with the argument (1.) in the proof of lemma 2, see equation 16, that c(𝑥, 𝜃) is Lipschitz-continuous in 𝑥, since it is a composition of two Lipschitz-continuous functions. Now recall that by Conditions 1 and 5 we can infer that ‫)𝜃(ש‬ is Lipschitz-continuous through lemma 1. This and Condition 2 imply that we can apply lemma 2, which delivers thatEQUATIONand that ‫,ש(𝑝‬ 𝜃) is Lipschitz-continuous in both arguments. Now note that both c : X × Θ → [0, 1] and 𝑝 : X × Θ → [0, 1] are both bounded from above by 1. We thus conclude by triangle inquality that 𝑓 ‫)ש(‬ is Lipschitz-continuous in ‫.ש‬ Explicitly,EQUATIONwhere 𝐿 𝑝 and 𝐿 c denote the Lipschitz constants of c and 𝑝, respectively. (b) To show the Lipschitz-continuity of 𝑓 ‫,)𝜃(ש(‬ 𝜃) in 𝜃, first note the Lipschitz-continuity 𝑓 ‫,)𝜃(ש(‬ •) in 𝜃 directly follows from the facts that 1) ‫)𝜃(ש‬ is Lipschitz-continuous, 2) 𝑓 ‫,ש(‬ •) is Lipschitz-continuous in ‫,ש‬ and 3) any composition of Lipschitz-continuous functions is Lipschitz-continuous. We have proven 1) and 2) right above. For a proof of 3), see equation 16 in the proof of lemma 2. What remains to be shown is the Lipschitz-continuity of 𝑓 (•, 𝜃), which translates to the Lipschitz-continuity ofEQUATION)in 𝜃, which in turn translates to the Lipschitz-continuity of the inner integral. Condition 2 and lemma 2 deliverEQUATIONwith ‫,ש(𝑝‬ 𝜃) being Lipschitz-continuous in 𝜃. (c) It remains to be shown that 𝑓 ‫,)𝜃(ש(‬ 𝜃) is Lipschitz-continuous on Θ × Θ. This follows from reasoning analogous to the proof of lemma 2, resulting inEQUATIONwith 𝐿 𝜃 and 𝐿 ‫(ש‬ 𝜃 ) being the Lipschitz-constants of 𝜃 and ‫,)𝜃(ש‬ respectively. This concludes the proof that 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) is Lipschitz-continuous in 𝜃.2. To see that 𝑓 (•, P(𝑌 , 𝑋), •) is Lipschitz-continuous with respect to Wasserstein-1-distance on both domain P and codomain P, recall the definition of Wasserstein-p-distancees [108] . Let (X, 𝑑) be a metric space, and let 𝑝 ∈ [1, ∞). For any two probability measures 𝜇, 𝜈 on X, the Wasserstein distance of order 𝑝 between 𝜇 and 𝜈 is defined byEQUATIONΠ(𝜇, 𝜈) denotes the set of all joint measures on X × X with marginals 𝜇 and 𝜈. For 𝑝 = 1 and empirical distributions P(𝑍) and P ′ (𝑍 ′ ) this translates to 𝑊EQUATIONwhich analytically follows fromEQUATIONThe partial derivative in equation 32 is trivially upper-bounded by (34) And thus also for any 𝑥 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) -𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛 ′ ) ≤ 1.(EQUATIONSince supp(𝑍) = supp(𝑍 ′ ) with 𝑍 ∼ 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) and 𝑍 ′ ∼ 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛 ′ ), we have (37) from which the assertion follows with 𝑝 = 1 for the 𝑝-norm.𝑊What remains to be proven is the Lipschitz-continuity of the non-greedy sample adaption function 𝑓 𝑛 : Θ × P → P with 𝑓 𝑛 (𝜃, P(𝑌 , 𝑋)) = P ′ (𝑌 , 𝑋) induced by The reasoning is completely analogous to the greedy sample adaption function 𝑓 , see 4. above. In particular, we can directly transfer the proof of 1. 𝑓 (𝜃, •, •) being Lipschitz-continuous. What remains to be shown is that the Lipschitz-continuity in P ∈ P also holds for 𝑓 𝑛 . This translates to showing that ‫ש‬ -is Lipschitz-continuous in P, since we have the Lipschitz-continuity of 𝑛 0 • P(𝑋, 𝑌 ) with analogous reasoning as in 2. above. However, note that the Lipschitz-constant is not necessarily the same, since the partial derivative of 𝑓 𝑛 also includes the indirect effect through ‫ש‬ -and ‫.צ‬P ′ (𝑌 = 1, 𝑋 = 𝑥) = ∫ ∫ 1(𝑥 = ‫)To see that ‫ש‬ -is Lipschitz-continuous, note that for two arbitrary P, P ′ ∈ P we have thatEQUATIONwhere 𝜌(𝑥, 𝑥 ′ ) is any joint probability measure on X × X. Now recall that the Wasserstein-1-distance is defined as the infimum of ∫ |𝑥 -𝑥 ′ |𝑑𝜌(𝑥, 𝑥 ′ ) with respect to 𝜌(𝑥, 𝑥 ′ ). We conclude that‫ש||‬ -(P) -‫ש‬ -(P ′ )|| 2 ≤ 𝐿 ‫ש‬ -• 𝑊 1 (P, P ′ ) (39) with 𝐿 ‫ש‬ -a constant.The Lipschitz-continuity of 𝑓 𝑛 then follows from the Lipschitz-continuity of 𝑓 𝑛 in 𝜃 and the Lipschitzcontinuity in P with the argument in 4.Proof. The structure of the proof is analogous to the proof of theorem 1. We show that 1. 𝑓 (𝜃, •, •), 2. 𝑓 (•, P(𝑌 , 𝑋), •), and 3. 𝑓 (•, •, 𝑛) are Lipschitz-continuos with Lipschitz constants 𝐿 𝜃 , 𝐿 P , and 𝐿 𝑛 , respectively. We then show in 4. that the Lipschitz-continuity of 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) follows with Lipschitz constant 𝐿 = max{𝐿 𝜃 , 𝐿 P , 𝐿 𝑛 }. Since none of conditions 1 through 5 were required to show 1., 2., and 4., in the proof of theorem 1, we only need to show that 1. also holds under conditions 2, 3, and 4.To show that 𝑓 (𝜃, P(𝑌 , 𝑋), 𝑛) is Lipschitz-continuous in 𝜃, it is sufficient to show thatEQUATIONis Lipschitz-continuous in 𝜃.In the remainder of the proof, the strategy is as follows. We first show that 𝑓 ‫,ש(‬ •) is Lipschitzcontinuos and then demonstrate the Lipschitz-continuity of 𝑓 ‫,)𝜃(ש(‬ 𝜃) in 𝜃. With reasoning analogous to argument (3.) in the proof of lemma 2, it then follows that 𝑓 ‫,)𝜃(ש(‬ 𝜃) is Lipschitz-conitnuous on Θ × Θ.We start by showing that the functionEQUATIONis Lipschitz-continuous in ‫.ש‬ Apply Fubini to getEQUATIONCondition 3 implies that features are drawn according to c : Further note that the mapping 𝑐 → c is a softmax function, which is continuosly differentiable and thus Lipschitz-continuous. We thus conclude with the argument (1.) in the proof of lemma 2, see equation 16, that c(𝑥, 𝜃) is Lipschitz-continuous in 𝑥, since it is a composition of two Lipschitzcontinuous functions.EQUATIONWe now need to verify that ∫ ‫)𝜃(ש‬ P‫ש‬ ‫ש𝑑‬ is Lipschitz such that we can apply lemma 2. By condition 3 we have that ∫ ‫)𝜃(ש‬ P‫ש‬ ‫ש𝑑‬ = c(𝑥, 𝜃), which is Lipschitz-continuous in 𝜃 per condition 4.Condition 2 and lemma 2 then directly deliver thatEQUATIONwith ‫,ש(𝑝‬ 𝜃) Lipschitz continuous in both arguments. Now note that both c : X × Θ → [0, 1] and 𝑝 : X × Θ → [0, 1] are both bounded from above by 1. We thus conclude by triangle inquality that 𝑓 ‫)ש(‬ is Lipschitz-continuous in ‫,ש‬ analogous to the proof of theorem 1. Explicitly,EQUATIONwhere 𝐿 𝑝 and 𝐿 c denote the Lipschitz constants of c and 𝑝, respectively. Rearranging for 𝑡 and exploiting that 𝐿 (1 EQUATIONby taking expectations on the inequality stated in assumption 3 (strong convexity). By classical first-order optimality conditions [44] we know that the first term on the right-hand side is larger or equal to 0, from which equation 73 Guidelines:• The answer NA means that the paper has no 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 a 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 8) 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 1 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. Assumptions 1 and 2 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-continuous gradients both with respect to features and parameters. For a discussion of assumption 3, we refer to appendix E. ≥ ℓ (𝑦, 𝑥, 𝜃 ′ ) + ∇ 𝜃 ℓ (𝑦, 𝑥, 𝜃 ′ ) ⊤ (𝜃 -𝜃 ′ ) + 𝛾 2 ∥𝜃 -𝜃 ′ ∥ 2 2, for all 𝜃, 𝜃 ′ , 𝑦, 𝑥. Observe convexity for 𝛾 = 0. Let us now turn to specific and more constructive conditions on reciprocal learning's workhorse, the data selection problem (Θ, X, L 𝜃 ). At the heart of these conditions lies a common goal: We want to establish some continuity in how the data changes from 𝑡 -1 to 𝑡 in response to 𝜃 𝑡 -1 and P 𝑡 -1 . It is self-evident that without any such continuity, convergence seems out of reach. As it 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 3 . We thus need the sample adaption function (definition 5) to be Lipschitz-continuous. Theorem 1 will deliver this for subsets of conditions 1 through 5 in case of binary classification problems. The reason for the latter restriction is that we need an explicit definition of 𝑓 to constructively prove its Lipschitz-continuity. Condition 1 (Data Regularization). Data selection is regularized as per definition 3. Condition 2 (Soft Labels Prediction). The prediction function ŷ : X × Θ → {0, 1} on bounded X gives rise to a non-degenerate distribution of 𝑌 | 𝑋 for any 𝜃 such that we can consider soft label predictions 𝑝 : X × Θ → [0, 1] with 𝑝(𝑥, 𝜃) = 𝜎(𝑔(𝑋, 𝜃)) with 𝜎 : R → [0, 1] a sigmoid function. Further, assume that the loss is jointly smooth in these predictions. That is, ∇ 𝑝 ℓ(𝑦, 𝑝(𝑥, 𝜃)) exists and is Lipschitz-continuous in 𝑥 and 𝜃. Condition 3 (Stochastic Data Selection). Data is selected stochastically according to 𝑥 𝑠 by drawing from a normalized criterionexp(𝑐 ( 𝑥, 𝜃 𝑡 ) ) ∫ 𝑥 ′ exp(𝑐 ( 𝑥 ′ , 𝜃 𝑡 ) ) 𝑑 𝜇 ( 𝑥 ) , see definition 2.: X × Θ → R in the decision problem (Θ, A, L 𝜃 𝑡 )of selecting features to be added to the sample that ∇ 𝑥 𝑐(𝑥, 𝜃) and ∇ 𝜃 𝑐(𝑥, 𝜃) are bounded from above. Condition 5 (Linear Selection Criterion). The decision criterion 𝑐 :X × Θ → R in (Θ, A, L 𝜃 𝑡 ) is linear in 𝑥 and Lipschitz-continuous in 𝜃 with a Lipschitz constant 𝐿 𝑐 that is independent from 𝑥.We can interpret 𝑝 as 𝑃 𝜃 (𝑌 | 𝑋 = 𝑥) in condition 2, see also definition 1. In other words, soft labels in the form of probability distributions are available. Adding observations with soft labels to the data can be implemented either through randomization, i.e., by adding 𝑥 with label 1 with probability 𝑝 and vice versa, or through weighted retraining. Note that condition 4 implies condition 5 through characterization of Lipschitz-continuity by bounded gradients. We need two implications of these conditions to establish Lipschitz-continuity of the sample adaption in reciprocal learning. First, it can be shown that regularized data selection (condition 1) is Lipschitz-continuous in the model, see lemma 1. Second, the soft label prediction function (condition 2) is Lipschitz in both data and model, if the data selection, in turn, is Lipschitz-continuous in the model, see lemma 2.𝑥 𝑑,R : Θ → X; 𝜃 ↦ → argmax 𝒙∈X 𝑐(𝒙, 𝜃) + 1 𝐿 𝑠 R (𝒙)with 𝜅-strongly convex regularizer, see definition 3 and condition 1, is 𝐿 𝑠 •𝐿 𝑐 𝜅 -Lipschitz continuous, if 𝑐 is linear in 𝑥 (condition 5) and Lipschitz-continuous in 𝜃 with a Lipschitz constant 𝐿 𝑐 that is independent of 𝑥. Lemma 2 (Soft Label Prediction is Lipschitz). The soft label prediction function (condition 2)𝑝 : X × Θ → [0, 1]; ‫,)𝜃(ש(𝑝‬ 𝜃) = ∫ ∫ ŷ(‫,)𝜃(ש‬ 𝜃) p 𝑑𝑦 P‫ש‬ ‫ש𝑑‬ is Lipschitz-continuous in both 𝑥 ∈ X and 𝜃 ∈ Θ and (𝑥, 𝜃) ∈ X × Θ if ∫ ‫)𝜃(ש‬ P‫ש‬ ‫ש𝑑‬ is Lipschitz- continuous.Proofs of all results in this paper can be found in appendix F. With the help of lemma 1 and 2, we are now able to state two key results. They tell us under which conditions the sample adaption functions in both greedy and non-greedy reciprocal learning are Lipschitz-continuous, which will turn out to be sufficient for convergence. The proof idea is as follows. We relate the Lipschitz-continuity of 𝑓 𝑛 to the Lipschitzcontinuity of 𝑅 𝑛 via the dual characterization of the Wasserstein metric [43] . If 𝑓 𝑛 is Lipschitz with 𝐿 ≤ (1 + 𝛽 𝛾 ) -1 , we further show that 𝑅 𝑛 is a bivariate contraction. The Banach fixed-point theorem [4, 72, 17] then directly delivers uniqueness and existence of (𝜃 𝑐 , P 𝑐 ) as convergent fixed point, which means that it holds 𝜃 𝑐 = arg min 𝜃 E (𝑌 ,𝑋)∼ 𝑓 ( 𝜃 𝑐 ,P 𝑐 ) ℓ(𝑌 , 𝑋, 𝜃). A complete proof can be found in appendix F.5. Building on earlier work on performatively optimal predictions [73] , we can further relate this convergent training solution to the global solution of reciprocal learning, i.e., the optimal data-parameter fit, see definition 9. The following theorem 4 states that our convergent solution is close to the optimal one. It tells us that we did not enforce a trivial or even degenerate form of convergence (e.g., constant 𝜃 𝑡 ) by regularization and randomization. Theorem 4 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 on test data.𝑐 -𝜃 * || 2 ≤ 2𝐿 ℓ 𝐿𝛾 for 𝜃 𝑐 and 𝜃 * from the convergent data-parameter tuple 𝑅 𝑛,𝑐 = (𝜃 𝑐 , P 𝑐 ) and the optimal one 𝑅 * 𝑛 = (𝜃 * , P * ) if the loss is 𝐿 ℓ -Lipschitz in 𝑋 and 𝑌 . While theorem 1 and 2 guarantee that both greedy 𝑓 and non-greedy 𝑓 𝑛 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 an affirmative answer. Intuitively, there is no fixed point in Θ × P × N if data is constantly being added and not removed such that 𝑛 → ∞. Theorem 5. Greedy Reciprocal Learning does not converge in the sense of definition 8.We conclude this section with another negative result. It states that theorem 3 is tight in theorem 1 and 2. Summing things up, Lipschitz-continuity is all you need for non-greedy reciprocal learning to converge. Theorem 6. If the sample adaption 𝑓 𝑛 is not Lipschitz, non-greedy reciprocal learning can diverge.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The method for calculating the error bars should be explained (closed form formula, call to 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. • It 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 a 96% CI, if the hypothesis of Normality of 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 of range (e.g. negative error 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. 
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 a binary target variable and 𝐿 ≤ (1 + 𝛽 𝛾 ) -1 with 𝛾 and 𝛽 in the sense of assumption 1-3 throughout. First observe that any greedy (definition 6) algorithm that only adds data without removal does not converge in the sense of defintion 8 with respect to 𝜃, P, and 𝑛, see theorem 5. This provides a strong case for non-greedy self-training algorithms, often referred to as amending strategies [103] or 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 A.1.1. Corollary 1 (Self-Training). Amending self-training algorithms converge in the sense of definition 8, if predicted pseudo-labels are soft (condition 2) and data selection is regularized (condition 1) or randomized (condition 3).Furthermore, we shed some light on the debate [97, 120] in the literature on multi-armed bandits about whether to use deterministic strategies like upper confidence bound [10, 100, 42] or stochastic ones like epsilon-greedy [45, 54] search or Thompson sampling [89, 90] , see example 3. Note, however, that this insight relates to in-sample convergence only, see definition 8. Corollary 2 (Bandits). Non-greedy multi-armed bandits with Thompson sampling and epsilon-greedy 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, 114, 117] ; the latter assumes the oracle to have access to an undeniable ground truth via hard labels [26, 19, 20] . Corollary 3 (Active Learning). Active Learning from a strong oracle (i.e., providing hard labels) is not guaranteed to converge, while active learning from a weak oracle (soft labels) converges in the sense of definition 8 under additional condition 1 or 3. 
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, 11, 79, 96] . We refer to section 1 for a discussion and relate reciprocal learning to other fields in what follows.Continual Learning: 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 a greedy approximation of extended ERM, see section 2.Online Learning: In online learning and online convex optimization, the task is to predict 𝑦 by ŷ from iteratively receiving 𝑥. After each prediction, the true 𝑦 and corresponding loss ℓ(𝑦, ŷ) is observed, see [94] for an introduction and appendix B.2 for an illustration. Reciprocal learning can thus be considered a 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 a 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 a 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, 76, 69, 24, 68, 33] . It can be seen as a post hoc approach, while reciprocal learning algorithms directly learn a "parameter-efficient" sample on the go.Performative Prediction: The sample adaption functions in reciprocal learning are reminiscent of performative prediction, where today's predictions change tomorrow'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 𝑓 (or 𝑓 𝑛 ), see section 2. Contrary to performative prediction, however, 𝑓 ( 𝑓 𝑛 ) describes an in-sample (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 techniques as in [74, 61] , namely Lipschitz-continuity and Wasserstein-distance, our work is thus conceptually different. For an illustration of these differences, see appendix B.1.Safe Active Learning: 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 Lipschitz-continuity 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. 
discussion: 
 Summary: We have embedded a wide range of established machine learning algorithms into a 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 an approximately optimal model. We further applied these results to common practices in self-training, active learning, and bandits.Limitations: 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 in section 3 and appendix E. In particular, it needs to be 𝛾-strongly convex and have 𝛽-Lipschitz gradients, such that 𝐿 ≤ (1 + 𝛽 𝛾 ) -1 with 𝐿 the Lipschitzconstant of the sample adaption. This limits our results' applicability. From another perspective, however, this is a feature rather than a bug, since the described restrictions can serve as design principles for self-training, active learning, or bandit algorithms that shall converge, see below.Future Work: 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 𝛾 and 𝛽, see appendix E.2 for the example of Tikhonovregularization, the latter guarantees Lipschitz-continuity of the sample adaption through theorem 1.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, [8, 30] might serve as a bridge to future research.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.For ease of exposition, we will start by focusing on binary target variables, i.e., the image of 𝑌 is {0, 1}, with real-valued features 𝑋. Moreover, we will only consider cases where the sample changes through the addition of one instance per iteration. 5 Leaning on [106, 12, 103] , we describe SSL as follows. Consider labeled dataEQUATIONand unlabeled data 𝑥 ∈ X. The aim of SSL is to learn a predictive classification function ŷ(𝑥, 𝜃) parameterized by 𝜃 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 on the former. Self-training involves fitting a model on D by ERM and then exploiting this model to predict labels for X. In a second step, some instances {𝑥 𝑖 } 𝑚 𝑖=𝑛+1 ∈ X are selected to be added to the training data together with the predicted label, typically the ones with the highest confidence according to some criterion, see [2, 49, 80, 83, 53, 84, 18] for examples.Example 1 (Self-Training). Self-training is an instance of reciprocal learning with the sample adaption function (see definition 5) 𝑓 𝑆𝑆𝐿 : Θ × P × N → P; (𝜃, P(𝑌 , 𝑋), 𝑛) ↦ → P ′ (𝑌 , 𝑋) with P ′ (𝑌 , 𝑋) induced byP ′ (𝑌 = 1, 𝑋 = 𝑥) = ∫ ∫ 1(𝑥 = 𝑥(𝜃)) • ŷ(𝑥 𝑑 (𝜃), 𝜃) + 𝑛 P(𝑌 = 1, 𝑋 = 𝑥) 𝑛 + 1 P𝑌 | 𝑋 𝑑𝑦 P𝑋 𝑑𝑥where 𝑥 𝑑 (𝜃) (definition 2) selects data with highest confidence score, see [2, 80, 53] , according to the model 𝜃, and gives rise to P𝑋 . The prediction function ŷ : X × Θ → {0, 1} returns the predicted label of the selected 𝑥 𝑑 (𝜃) based on the learned model 𝜃 and gives rise to P𝑌 | 𝑋 .The averaging with respect to P𝑋 and P𝑌 | 𝑋 accounts for the fact that we allow stochastic inclusion of 𝑋 in the sample through randomized actions and for probabilistic predictions of 𝑌 | 𝑋, respectively. For now, however, it suffices to think of the special case of degenerate distributions P𝑋 and P𝑌 | 𝑋 putting point mass 1 on data with hard labels in the sample and 0 elsewhere. 6 Through averaging with respect to P𝑌 | 𝑋 we can describe the joint distribution of hard labels (𝑦 1 , 𝑥 1 ), . . . , (𝑦 𝑛 , 𝑥 𝑛 ) and predicted soft labels ỹ = p(𝑌 = 1 | 𝑥, 𝜃) ∈ [0, 1] of ( ỹ𝑛+1 , 𝑥 𝑛+1 ), . . . , ( ỹ𝑛+𝑡 , 𝑥 𝑛+𝑡 ). Summing up, both deterministic data selection and non-probabilistic (i.e., hard labels) predictions are well-defined special cases of the above with P𝑌 | 𝑋 and P𝑋 collapsing to trivial Dirac measures, respectively.Our corollaries in section 4 shed some light on the convergence of self-training methods in a semisupervised learning regime. Recall from above that the aim of these methods is to learn a predictive classification function ŷ(𝑥, 𝜃) parameterized by 𝜃 utilizing both labeled dataD = {(𝑥 𝑖 , 𝑦 𝑖 )} 𝑛 𝑖=1 ∈ (X × Y) 𝑛 and unlabeled data U = {(𝑥 𝑖 , Y)} 𝑚 𝑖=𝑛+1 ∈ X × 2 Y 𝑚-𝑛from the same data generation process. Self-training involves fitting a model identified with parameters 𝜃 on D by ERM and then exploiting this model to predict labels for U. In 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 𝑐 𝑟 (𝑥, 𝜃) = 𝑐(𝑥, 𝜃) + 1 𝐿 𝑠 R (𝑥), see example 1 and pseudo code below. Amending self-training does the same, but additionally removes instances from U, see below.The key insight from our analysis is that the sequence of 𝜃 converges at a linear rate in case of amending self-training and regularized data selection. D ← D ∪ {(𝑥 𝑖 * , ŷ𝑖 * )} \ {(𝑥 𝑗 † , 𝑦 𝑗 † )} update U ← U \ {(𝑥 𝑖 * , Y) 𝑖 * } end A. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conducted in the paper is, in every aspect, conform with the NeurIPS 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We do not foresee direct negative societal impact from the current work.Positive societal impact in form of making decisions based on reciprocal learning algorithms such as active learning or self-training more reliable and trustworthy are discussed in section 1, 2, and 6 of the paper.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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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 is used and, if 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 the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.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(𝑌 = 1, 𝑋 = 𝑥) = 1( 𝑥=𝑥 ( 𝜃 ) ) • ŷ ( 𝑥 𝑑 ( 𝜃 ), 𝜃 ) + 𝑛 P(𝑌 =1, 𝑋=𝑥 ) 𝑛+1.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(𝑌 = 1, 𝑋 = 𝑥) = 1( 𝑥=𝑥 ( 𝜃 ) ) • ŷ ( 𝑥 𝑑 ( 𝜃 ), 𝜃 ) + 𝑛 P(𝑌 =1, 𝑋=𝑥 ) 𝑛+1.It is usually directly defined in terms of action selection probabilities P ( 𝐴 𝑡 | H 𝑡 -1 ), see[115] for instance. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - The connections to practically relevant algorithm design is lacking
- It is unclear how this paper's result ties to generalization guarantees of various classes of these algorithms.
questions: 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?
- 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).
- 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?
- Can the authors maybe comment on how this framework connects to other learning paradigms such as distributionally robust optimization?

[1] Olivier Bousquet, André Elisseeff, "Stability and generalization"
[2] M Hardt, B Recht, Y Singer, "Train faster, generalize better: Stability of stochastic gradient descent"
limitations: limitations: N/A.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: adequately addressed
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.

2. How would you generalize Theorem 1 to multi-class classification? It would be a good practice to add to the Appendix.
limitations: limitations: Yes.

Comments: title: Reply to rebuttal
Response to Authors' Comments
Re: Author Reponse
comment: Likewise, thank you for the discussion, and I am looking forward to reading the updated future version of the manuscript.
Thanks a lot for getting back to us and for considering our rebuttal. We are glad to hear the reviewer still tends towards acceptance.
We would like to thank the reviewer for considering our answers, revisions, and simulations in their final assessment and for raising the overall score from 5 to 6. We could not agree more that an accessible presentation is key for the paper's aim of providing a unifying view on several branches of ML. Thus, we sincerely thank the reviewer -- once again -- for the concrete and very helpful suggestions on how to improve our writing and the general presentation of the paper.
Thanks a lot for getting back to us and for taking our rebuttal into account. We are happy to hear our replies confirm the reviewer's initial assessment, supporting acceptance.
I thank the reviewer for their clarification. I would like to maintain my score.
I would like to thank the authors for their thorough engagement with, and appreciativeness of, my review and the other reviews. Based on the shared snippet of the improvements to the paper's writing as well as the list of updates that would appear in the conference version; and also based on the couple of added experiments illustrating the convergence behavior in the bandit setting and in the self-training setting, I am raising my scores. Again, in my view the main part of the paper's appeal to the NeurIPS audience would be its informativeness and accessibility to as broad a collection of researchers as possible, and thus much care is warranted in terms of augmenting and restructuring the presentation --- so I am glad the authors took the comments asking for that and for more experiments seriously. Overall, to sum up, I found the paper to offer an interesting unifying perspective that I had not previously seen in the literature.
Thank you for your detailed responses to the review. I will retain my score as is, and will support the paper's acceptance.