Real-Time Selection Under General Constraints via Predictive Inference

Authors: yuyang  huo
lin  lu
haojie  ren
changliang  zou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 11:07:44

Abstract: Real-time decision-making gets more attention in the big data era. Here, we consider the problem of sample selection in the online setting, where one encounters a possibly infinite sequence of individuals collected over time with covariate information available. The goal is to select samples of interest that are characterized by their unobserved responses until the user-specified stopping time. We derive a new decision rule that enables us to find more preferable samples that meet practical requirements by simultaneously controlling two types of general constraints: individual and interactive constraints, which include the widely utilized False Selection Rate (FSR), cost limitations, and diversity of selected samples. The key elements of our approach involve quantifying the uncertainty of response predictions via predictive inference and addressing individual and interactive constraints in a sequential manner. Theoretical and numerical results demonstrate the effectiveness of the proposed method in controlling both individual and interactive constraints.

Main paper: 
 introduction: 
 In recent times, the field of real-time decision has flourished significantly, primarily driven by the exponential growth of available data in both the tech industry and computer science. We consider here a typical application of real-time decision, the problem of online sample selection [2, 5] . For instance, online recruitment systems utilize machine learning algorithms to sequentially choose qualified candidates rather than waiting for all (future) candidates' information to be collected [14] . Additionally, recommendation systems have now become commonplace in providing real-time suggestions for content (e.g., news articles, short videos) with potential high click-through rates to users [24] . Common situations also can be found in real-time precision marketing [43] .We describe the online sample selection problem as follows: samples (individuals) characterized by covariates X t ∈ R d arrive sequentially while their responses Y t ∈ R remain unobserved throughout the process. The data pairs (X, Y ) of each time are i.i.d. random vectors. At each time point, the analyst is faced with the task of deciding whether to select the current observation based on certain predetermined criteria related to Y t , and this selection process continues until a specific stopping rule is triggered. For example, Y t is the score that measures how one candidate fits a given job position in the recruitment system and the human resource agencies aim to prioritize candidates with higher Y t , such as Y t ≥ b. Or Y t is a binary variable where Y t = 1/0 means accepting or rejecting the offer, and the companies wish to find those individuals with Y t = 1 based on the X t .Our Goal and Motivation. Our goal is to sequentially select samples whose unobserved responses Y t 's are in the specified target region. A natural idea is to make decisions based on the prediction value of Y t from models associated with (X, Y ) built on some historical data. However, neglecting the uncertainty in predictions could result in numerous false decisions, i.e., selecting those samples whose true responses are beyond the specified region. To measure the selection uncertainty, some existing works reformulate sample selection as a hypothesis testing problem and focus on controlling the online false discovery rate (FDR) [16, 33] ; see more discussions and literature in Section 1.2. However, in addition to quantifying statistical uncertainty, online selections often need to take into account various constraints to find informative samples in practice, for example, cost limitations, the impacts of some covariates or the diversity of candidates in the online recruitment [39] . Hence, it's necessary to explore the covariate space to satisfy these requirements. This motivates us to investigate how to efficiently implement online sample selection with statistical guarantees under various constraints.To address this issue, we summarize common constraints into two types, i.e., individual constraints and interactive constraints. The former one is relevant to the cost of selected samples, and one typical example is the fundamental and crucial criterion, false selection rate (FSR), which quantifies the proportion of falsely selected samples and is equivalent to the well-adopted FDR. The latter constraint captures the interactive influence among selected samples and is regarded as some kind of quadratic constraint on some pairwise functions, such as the similarity or diversity among selected samples.While the individual constraint associated with online FDR control has gained some attentions [16, 18] , it alone fails to capture the nuanced pairwise relationships among different samples. To bridge this gap, we introduce interactive constraints, which are pivotal within our framework. Building upon individual constraints, the interactive criteria significantly expand the range of constraints our method can control. Integrating two distinct types of constraints into a unified framework makes it easier to create practical algorithms and ensures theoretical guarantees.A motivating example: candidate screening. As an example, in recruitment, screening from the resumes arriving sequentially to determine viable candidates who can get into interview processes is an important problem in human resource management [13, 35] . In this case, one may be interested in: (1) controlling the online FSR to enhance resource efficiency [21] , and (2) maintaining a desired level of candidate diversity during the screening process, thereby reducing bias [23, 44] . The individual and interactive constraints and the novel real-time sample selection procedure we propose can solve this problem precisely. See Section 4.2 for the details and more real data examples.In this paper, we design a novel and flexible online selection rule to effectively ensure the above two types of constraints are under control at pre-specified levels simultaneously, named as "Individual and Interactive Constrained Online Selection" (II-COS). The main idea stems from an oracle model based on the local false discovery rate (lFDR) [12, 38] , which is involved in offering valid evidence on whether Y t is our interest at each time point. With some appropriately chosen evaluating functions, the II-COS procedure entails validating whether the estimates of constraints are controlled. Simulated and real-data examples clearly demonstrate the superiority of the II-COS in terms of both online individual and interactive criteria control.To the best of our knowledge, this is the first work to systematically bridge the predictive inference and online selection procedure with various constraints. Our contributions are summarized as follows:• Under a unified framework, the II-COS addresses how to implement online predictive selection sufficiently in consideration of both individual and interactive constraints. It is flexible to characterize the selective uncertainty and trade-off the sampling efficiency and practical limitations in the covariate space.• Under mild conditions, we establish the theoretical guarantee that the II-COS is able to control both individual and interactive constraints simultaneously and asymptotically under one given stopping rule.• The II-COS is model-agnostic in the sense that its implementation is applicable to any (appropriate) learning algorithms. Extensive numerical experiments indicate that the II-COS can significantly outperform existing ones while yielding effective constraints control.unqualified candidates or the average loss when hiring someone who rejects the offer. In such cases, we can assign each selected sample a cost associated with some pre-specified function of the covariate X and control the expected cost associated with time T at the target level. We refer to this requirement as individual constraint and write it as:EQUATIONwhere a∨b = max{a, b} and G 0 (X) ≥ 0 and G 1 (X) ≥ 0 with G 0 ̸ = G 1 are the costs corresponding to θ = 0 and θ = 1, respectively. Here, we take expectation due to the randomness of θ 1 , • • • , θ t .For example, when we simply choose G 0 (X) = 1 and G 1 (X) = 0, the individual constraint is the popular false selection rate (FSR), i.e.EQUATION)The FSR is essentially equivalent to the well-adopted FDR in multiple testing literature, which is a useful tool to maintain the ability to reliably select samples of interest without excessively false selections [9] . Some works on online FDR control have been well studied. [16, 1] .The individual constraints alone cannot capture the pairwise relationship among different samples.We address this by introducing interactive constraints below.Interactive Constraint Another common concern is the interactive constraint, which involves choosing more preferable samples. For example, companies would like to retain candidates with a diverse range of backgrounds and experiences in online recruitment, or real-time suggested contents are required to avoid homogeneity in recommendation systems. Here, we introduce a bi-variate weight function g(X, X ′ ) to evaluate the interaction between selected samples. Denote PC(δt ) = 1≤i<j≤t g(X i , X j )θ i θ j δ i δ j , PS(δ t ) = 1≤i<j≤t θ i θ j δ i δ j .We define the interactive constraint asEQUATIONHere, since only the correctly selected samples are of interest, the constraint is concerned with the average mutual effects between the correctly selected ones rather than all selected ones. When choosing the function g as some similarities, controlling C2 (δ t ) at a specified constant K, i.e., C2 (δ t ) ≤ K, is controlling the expected similarity (ES). It is equivalent to requiring that correctly selected samples exhibit certain diversity and rich information in the covariate space of interest.Typically, one useful choice for g(X, X ′ ) is the weighted RBF kernel g(X,X ′ ) = exp -1 σ 2 d k=1 w k (X k -X ′ k ) 2with parameter σ > 0 to measure the similarity between two independent X and X ′ . The RBF kernel is a common and widely embraced choice in machine learning [49, 28] . Here, {w 1 , . . . , w d } are some given weights per users' needs. For instance, if one is just interested in the effects of the k-th feature, then simply w k = 1 and w j = 0 for j ̸ = k. Specifically, the case that w k = 1 for all k = 1, . . . , d is chosen in Section 4. We also consider other similarity choices of g(X, X ′ ), such as the cosine similarity g(X,X ′ ) = X ⊤ X ′ /(∥X∥ 2 ∥X ′ ∥ 2 ) [52].Due to the randomness in the denominator, it turns out controlling (3) directly is not easy. Instead, we employ a modified interactive constraint,EQUATION)The constraint (4) aims to control a ratio of expectations, which is still a reasonable interactive measure. In numerical studies, we see that C2 (δ t ) in (3) and C 2 (δ t ) in (4) yield almost identical patterns. An illustrative example can be found in Appendix D.1.In sum, the goal is to select samples of interest by a decision rule δ T controlling both the individual and interactive constraints until stopping time T , i.e., C 1 (δ T ) ≤ α and C 2 (δ T ) ≤ K. We emphasize that C 1 (δ T ) and C 2 (δ T ) as well as their pre-specified levels α and K can be chosen up to the practical applications. 
oracle selection procedure: 
 To design a general rule that is valid for any arbitrary stopping time T , we consider controlling the constraints at each time t in an online fashion, such that sup t∈N C 1 (δ t ) ≤ α and sup t∈N C 2 (δ t ) ≤ K.Since Y t is unavailable, we consider utilizing predictive inference to measure the suspicious patterns. Let µ(x) := Y | X = x be the regression or classification model associated with (X t , Y t ), and one reliable estimate as µ(•), being estimated on the labeled data D with some machine learning algorithm. Denote W t = µ(X t ) as a predicted value of Y t and assume that µ(•) is a bijection almost surely. The bijection assumption is considerably mild and widely adopted for the identyification of each X t in the predictive inference framework [45] . The θ t = I(Y t ∈ A) is Bernoulli(π) distributed with π = Pr(Y t ∈ A), and W t can be viewed as generated from one two-group modelW t | θ t ∼ (1 -θ t )f 0 + θ t f 1, where f 0 and f 1 denote the probability distribution functions of W t conditional on Y t / ∈ A (i.e., θ t = 0) and Y t ∈ A, respectively. Then, the conditional probability of Y t / ∈ A isEQUATIONwhere f = (1 -π)f 0 + πf 1 . The L t coincides with the local FDR in multiple testing literature [12, 17] . With the two-group model ( 5), we have E[θ t | X t ] = 1 -L t and further notice that the individual constraint C 1 (δ t ) in ( 1) can be exactly satisfied ifV t R t := i≤t {L i G 0 (X i ) + (1 -L i )G 1 (X i )}δ i ( i≤t δ i ) ∨ 1 ≤ α,holds. Here, we denote 2) can be exactly controlled.V t = i≤t {L i G 0 (X i ) + (1 -L i )G 1 (X i )δ i } and the number of selected ones as R t = i≤t δ i ∨ 1 for notational convenience. Especially, when G 0 (X) = 1, G 1 (X) = 0, then FSR(δ t ) in (Accordingly, the interactive constraint C 2 (δ t ) ≤ K in (4) can be achieved ifTS t NS t := 1≤i<j≤t g(X i , X j )(1 -L i )(1 -L j )δ i δ j 1≤i<j≤t (1 -L i )(1 -L j )δ i δ j ≤ K,where the expected total mutual effects conditional on {X i } i≤t and the expected number are denoted as TS t and NS t , respectively.Therefore, if L t is known, when a new sample X t arrives at time point t, we can perform the decision rule as follows. Note that there is no need to consider interactive effects before the first selection. When t comes before the first selection (i.e, R t-1 = 0), the decision rule isEQUATIONholds; otherwise, δ t = 0 which means X t is not selected. When X t arrives with R t-1 ≥ 1, then δ t = 1 if (6) andEQUATIONhold simultaneously; otherwise, δ t = 0. Note that if we set C 1 (δ t ) as FSR(δ t ) and choose K = +∞, then our method essentially reduces to the same manner as the controlling step of the SAST in Gang et al. [17] . Our proposed method can be seen as a much more generalized and flexible framework for controlling both the individual and the interactive constraints simultaneously in an online fashion.We call this method the oracle II-COS (Individual and Interactive Constrained Online Selection). The workflow in Figure 1 shows the procedure of the oracle II-COS. The following result shows that it can exactly achieve our goal. Proposition 2.1. Assume L t values are known. Then the oracle II-COS selection rule controls both constraints at any stopping time T , i.e., C 1 (δ T ) ≤ α and C 2 (δ T ) ≤ K.Oracle II-COS Input:, , As L t is unknown in practice, we propose a data-driven II-COS procedure, which uses a reliable estimation L t for implementation. We resort to a data-splitting strategy: randomly split historical data D into two parts, the training set D tr and the calibration one D cal of sizes n 0 and n 1 respectively, where D tr is used for training a predictive model and D cal is to estimate those unknown parameters. Specifically, we first fit a regression or classification model µ(•) on D tr , and then obtain predicted values on D cal , i.e. { µ( Xi ) : ( Xi , Ỹi ) ∈ D cal }. Note that conditional on D tr , { µ( Xi ) : ( Xi , Ỹi ) ∈ D cal } are i.i.d. random variables and have the same distribution as W t = µ(X t ), so that it can be utilized to estimate (5) .Therefore, the estimators of f 0 and f , f 0 and f , can be obtained by applying the kernel density estimation method to the data { µ( Xi ) : ( Xi , Ỹi ) ∈ D cal , Ỹi / ∈ A} and { µ( Xi ) : ( Xi , Ỹi ) ∈ D cal }, respectively. And the probability π = Pr(Y t ∈ A) can be approximated by π = n -1 1 ( Xi, Ỹi)∈Dcal I( Ỹi ∈ A). Further the L t in (5) can be estimated byEQUATIONThe data-driven II-COS procedure is summarized in Algorithm 1, and it indeed consists of two phases: offline estimation and online decision. The running time of offline estimation is not critical. At each time t, the computational complexity is a linear function of the currently selected number R t . More implementation details can be found in Section 4 and Appendix B.1.In fact, the proposed II-COS is flexible to trade off the individual and interactive constraints by adjusting the thresholds α and K. If one is concerned only with individual cost control, then we can set K = +∞, with which the interactive constraint is out of work. Similarly, only the interactive effect is of interest when α = 1. Appendix D.2 provides a toy example to illustrate this.Before further pursuing, we would discuss the stopping time in practice. It's worth noting that the specific choice of stopping rule (and thus stopping time) is completely up to the user. For example, when m ≥ 2 is the desired number of selections, one can set T = inf t {t :t i=1 δ i = m}.Or when s is the total wages for recruitment, one can set T = inf t {t : t i=1 δ i s i = s} where s i is the payroll for each selected candidate. Or T is just chosen as one given deadline. With the use of II-COS, practitioners have the flexibility to design diverse stopping strategies that can adapt seamlessly to their specific applications. In brief, our method is flexible and is appropriate for various goals based on the user's requirements by choosing different G 0 (X), G 1 (X), g(X i , X j ) and varied target levels (α, K) and a user-specified stopping time.The data-driven II-COS procedure Input: Target levels α and K, pairwise function g, cost G 0 (X) and G 1 (X), stopping time T , interested region A, labeled data D, prediction algorithm H. Initialization: t = 0, V t = R t = 0, TS t = NS t = 0; Decision rule δ t = ∅ Estimation: Randomly split D into training set D tr and calibration set D cal . On D tr , fit µ(x) with H. Obtain π, f 0 and f from D cal .Online decisions: while t ≤ T do Set t = t + 1. Compute W t = µ(X t ), L t by ( 8) and the similarities g(X i , X t ) for those δ i = 1.Replace L t by L t in ( 6) and (7) . if R t-1 < 1 and (6) holds then δ t = 1;EQUATIONand (7) hold then δ t = 1; else δ t = 0; Update:δ t = δ t-1 {δt}; Rt = Rt-1 + δt; Vt = Vt-1 + { LtG0(Xt) + (1 -Lt)G1(Xt)}δt; TSt = TSt-1 + i<t g(Xi, Xt)(1 -Li)δi (1 -Lt)δt; NSt = NSt-1 + i<t (1 -Li)δi (1 -Lt)δt; end Output: Selection set {X i : δ i = 1, δ i ∈ δ T }.Extension to varying proportion case. In practice, the distribution of (X t , Y t ) may vary smoothly over time. In Appendix C, we consider the probability of Y t ∈ A (i.e. the proportion of samples in the specified region) varying over time and extend the proposed II-COS to learn π t = Pr(Y t ∈ A) continuously over time and we also construct the corresponding theoretical guarantees. 
statistical performance guarantees: 
 In this section, we provide statistical guarantees for the data-driven II-COS procedure. The main difficulties lie in the quantification of data-driven estimation error of L t and we utilize the classical kernel density estimation theory along with the structure of our online procedure to effectively characterize it. For simplicity, we consider that the training data set is given such that the estimated model µ is fixed. Before presenting our theoretical results, we state the following regularity conditions. (2) The f 0 and f 1 are Hölder-continuous, i.e. |f 0 (w) -f 0 (w ′ )| ≤ c β |w -w ′ | β for any w, w ′ ∈ R, and the same for f 1 with some fixed 0 < β ≤ 1 and constant c β .(3) Kernel K(•) is a bounded symmetric function and enjoys exponential decay.). There exists constants c G > 0 and c g > 0 such that 0 < G 0 (X) ≤ c G , 0 < G 1 (X) ≤ c G for any X and 0 < g(X, X ′ ) ≤ c g for any X ̸ = X ′ . Assumption 3.1 is considerably mild and widely adopted in the uniform convergence of kernel density estimation [36] . If f 0 and f 1 have bounded first-order derivatives, the Hölder-continuous assumption would hold with β = 1. The lower bound of f is to ensure the uniform convergence of the estimated lFDR. Assumption 3.2 is mild since the weight functions are required only to be positive and bounded. It can be satisfied by a large category of G 0 , G 1 and g. For example, we can take G j (X) = a j ∥X∥ 2 2 for j = 0 or 1 and c G exists when X is bounded. And we can set g as the RBF and orthogonal similarities with c g = 1.With those regularity conditions, we establish the validity of the II-COS procedure for the individual constraint control. Theorem 3.3 (Bound for individual constraint). Suppose Assumptions 3.1 and 3.2 hold and take the bandwidths for estimating f and f 0 in the order of n -1/(2β+1) 1. Then for any given time t, the individual constraint of the II-COS procedure (Algorithm 1) satisfies C 1 (δ t ) ≤ α + ∆ n1 , where∆ n1 = Dn -β 2β+1 1 √log n 1 and D is a constant depending on M , ℓ, c β , β, π, c G and K(•).Although the C 1 (•) of II-COS might be slightly larger than the target level in finite samples, this gap converges to 0 asymptotically as n 1 increases. In the numerical studies, we find that a small calibration size of around 200 is enough to control the C 1 in a reasonable range. Taking the FSR as an individual constraint, Theorem 3.3 indicates that our method can provide asymptotic online FSR control similar to an online FDR control procedure [16] .The next theorem examines the performance of the II-COS in terms of interactive constraint.Theorem 3.4 (Bound for interactive constraint). Suppose Assumptions 3.1-3.2 hold and take the bandwidths for estimating f and f 0 in the order of n -1/(2β+1) 1. Let T s = inf{t : t i=1 δ i = s} for s > 2 and assume there exists a constant α ′ ∈ (0, 1) such that i≤t L i δ i /(1 ∨ R t ) ≤ α ′ . Then for any given time t ≥ T m , the interactive constraint of the II-COS satisfiesC 2 (δ t ) ≤ K + (K + c g )∆ n1 0.5 -mα ′ m-1 -∆ n1.The term mα ′ /(m -1) is used to characterize the lower bound of the denominator term of the interactive constraint. Specifically, when we choose FSR as the individual constraint, we have α ′ = α, which demonstrates the interdependence between controlling individual and interactive constraints. Furthermore, under arbitrary stopping strategies with a stopping time T , we can have the asymptotic guarantee.Corollary 3.5. Suppose the conditions in Theorem 3.4 hold, the stopping moment T ≥ T m and α ′ < (1 -1/m)/2. Then the II-COS procedure controls the individual and interactive constraints asymptotically at T , i.e. lim n1→∞ C 1 (δ T ) ≤ α and lim n1→∞ C 2 (δ T ) ≤ K.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: For the theory assumptions, see Assumption 3.1-Assumption 3.2 in Sect. 3.For the proofs of each theoretical result, see Appendix E in the Supplementary material. 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs 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 to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiments and evaluation: 
 We illustrate the breadth of applicability of the II-COS procedure by experiments on simulated data and real-data applications. As an example, we set the stopping rule as selecting total m = 100 samples, i.e., T = T m = inf t {t :t i=1 δ i = m}.Additional experiments including the extended II-COS in Appendix C are shown in Appendix D.9. Code for implementing II-COS and reproducing the experiments and figures in our paper is available at https://github.com/lulin2023/II-COS.Implementation of II-COS. To our best knowledge, online selection with uncertainty qualification has only been studied in the field of online multiple testing, which aims to control online FDR. Hence, we focus on using FSR as the individual criterion and modified ES as the interactive criterion. As X may be measured on scales with widely differing ranges in different dimensions, we assume that X's have been properly scaled in each dimension before computing g. We choose g as the weighted RBF kernel with σ = 1, w k = 1 here. Other choices for individual and interactive constraints are considered in Appendix D.5.Benchmarks. We compare the II-COS procedure with four benchmarks from online multiple testing. The first one is a structure-adaptive sequential testing rule, the SAST [17] , which is implemented with L t . It can achieve the FSR control but ignore the interactive constraint. As mentioned earlier in Section 2, SAST can also be considered as a special case of our II-COS with K = +∞. Its details are deferred to Appendix B.2. The other competitors are three well-known online FDR control algorithms LOND [18] , SAFFRON [30] and ADDIS [40] implemented with the conformal p-values suggested by Bates et al. [7] . Refer more information in Appendix B.3. All the benchmarks can only control FDR, which demonstrates the flexibility of our method for different constraints.Performance Measures. The empirical FSR, ES and stopping time (T m ) are evaluated using the average values of the false selection proportions, the similarity and the stopping time from 500 replications, respectively, where T m serves as a criterion for assessing selection efficiency.Data Description. We consider a classification model:X | Y = 0 ∼ N 4 (µ 1 , I 4 ), and X | Y = 1 ∼ N 4 (µ 2 , I 4 ), where µ 1 = (5, 0, 0, 0) ⊤ , µ 2 = (0, 0, -3, -2) ⊤ . We set Pr(Y = 1) = 0.2. The information set is A = {1}. The predictor H is taken as random forest with defaulted parameters. We also consider a regression setting and conduct additional experiments in Appendix D.Firstly, we observe that methods relying on conformal p-values, such as LOND, SAFFRON, and ADDIS, encounter the alpha-death (stop early) issue [29] . These methods struggle to select an adequate number of samples, especially in small calibration sets. In contrast, II-COS ensures the control of both individual and interactive constraints even with a small n cal (e.g., 200). See more details and results in Appendix D.3. Hence, to make a fair comparison, we consider a relatively large size of the calibration set, n cal = 4, 000. We fix training data size n tr = 1, 000. Results. Figure 2 presents the online FSR (false selection rate) and ES (expected similarity) values of five methods against time t, which are individual and interactive constraints, respectively. The FSR levels of II-COS and SAST are closer to the nominal level than the other three methods. As expected, only the empirical ES levels of II-COS are controlled under the pre-specified level K over time t.The LOND and SAFFRON lead to slightly conservative FSR values, while the FSR levels of ADDIS are inflated compared to the target level. Figure 3 further displays the boxplots of empirical FSR, ES at stopping time T m . We observe that only II-COS achieves satisfactory ES values compared to the nominal level. Moreover, the II-COS has a relatively larger value of T m compared to those of other benchmarks. This is consistent with the fact that the II-COS spends more time exploring the structure information inside the covariate space due to the requirement of interactive constraint. Similar conclusions for the regression example in Appendix D.4 can be drawn.Regarding efficiency, we also conducted an experiment to compare the effectiveness of II-COS with an oracle method possessing knowledge of true state θ t . The T m of II-COS is very close to the oracle. This close proximity indicates the high efficiency of II-COS. See Appendix D.8 for the details.We next demonstrate the performance of the II-COS in two real-world applications. Since those online multiple testing methods based on conformal p-values yield few selected individuals, we focus on comparing the II-COS with the SAST. For comparison, we also include the offline method using conformal p-values, where δ t = 1 if p t ≤ α. We denote it as CP.Datasets. We consider the recruitment dataset from Kaggle [22] that contains 45,372 candidates after removing the missing data and records a binary response indicating whether the candidate passes the job interview, and other 11 attributes including education status, handicapped or not, and gender. The other problem is to use 1994 Census Bureau dataset [8] to select a subset of individuals who may have high incomes in precision marketing. This census dataset records 32,561 individuals with their 14 attributes, including gender, race, marriage, education length and so on.For each dataset, we randomly partition the data into three parts: n tr = 1, 000 training data, n cal = 1, 000 calibration data and the rest which are used as the online observations. The categorical attributes are converted into one-hot codes and then are treated as numerical attributes for computing similarity measures. The prediction algorithm H is random forest with defaulted parameters.Results. Table 1 reports the results among 500 repetitions. Both the II-COS and SAST enjoy valid FSR control, but CP yields an inflated FSR level in income investigation. The II-COS performs well in terms of similarities. To further compare the diversities, we present the proportions of different education status in in Figure 4 . It can be seen that the proposed II-COS demonstrates its superior diversity in the specific attributes. See Appendix D.6 for more results for the real data. In summary, the proposed II-COS works well for selecting individuals of interest to achieve various constraints in practical applications. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: See Appendix B for the implementation details to reproduce our experimental results.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 a 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 a 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 to 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 to replicate the results, access to a hosted model (e.g., in the case of a 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 all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , 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 to 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 be possible for other researchers to have some path to reproducing or verifying the results. 
concluding remarks: 
 Broader Impacts. This work focuses on creating reliable machine learning tools for making real-time decisions. One key achievement is a new algorithm called II-COS, designed to select informative samples in real-time while meeting two types of general constraints. II-COS allows for both individual and interactive control, validated through theoretical analysis and numerical tests. Our method is model-agnostic and easily applicable to many real-world cases such as producing diversified results while controlling FSR for online recruitment. One potential negative impact of our work is that researchers will apply the algorithm without sufficient scrutiny. We emphasize that it's important to use caution when applying this method to complex real-world scenarios to prevent misuse.Limitations. Firstly, we mainly consider binary functions as the interactive constraint. How to adapt the II-COS to other popular constraints, such as the Gini index, deserves further study. Secondly, in certain practical scenarios, it is possible to obtain feedback after decisions. Incorporating the feedback information into our method to enhance its performance warrants future research.This supplementary material contains:• Preliminary terms for self-containment (Appendix A);• Implementation details (Appendix B);• An extension algorithm to varying proportion case (Appendix C);• Additional experiments (Appendix D);• The proofs of all the theoretical results. (Appendix E).Here, we list the preliminary terms we use in the paper for the sake of clarity and self-containment.• FDR [9] , false discovery rate, a widely-adopted error rate notion in the field of multiple testing, is defined as the expected proportion of incorrectly rejected null hypotheses as follows:FDR(t) = E |H 0 ∩ R(t)| |R(t)| ∨ 1 ,where H 0 is the unknown set of true null hypotheses, R(t) represents the set of rejected null hypotheses until time t and then H 0 ∩ R(t) is the set of false discoveries.• FSR, false selection rate, defined as the expected proportion of individuals being not of interest among the selected subset of individuals. It is in fact equivalent to the definition of FDR. In our framework in this paper, we describe it equivalently as: FSR(t) = E i≤t (1 -θ i )δ i ( i≤t δ i ) ∨ 1 .Figure 5 shows the implementation flowchart of our proposed data-driven II-COS procedure, including the offline estimation step and online decision step. Here we introduce more implementation details to reproduce the results.About the classifier. For the classification problem, we use the predicted conditional probability Pr(Y t = 1 | X t = x) as µ(x) in the procedure of II-COS. Many commonly used algorithms such as random forest and neural networks can provide such probability estimators. In fact, the choice of µ is not restricted to probability. For example, the support vector machine outputs the distance to the separating hyperplane for classification, and such distance can be chosen as µ.However, for probability estimators, one potential problem is that when the classifier is quite accurate, most of W i 's are concentrated at 0 or 1 and few of them take values between (0, 1). In such a situation, it is difficult to accurately and stably estimate lFDR L i 's since the density functions f 0 (w) and f (w) are not smooth enough and are not lower bounded. This yields that our assumptions are violated, but the II-COS can still perform satisfactorily with some corrections on the estimation L i 's. Notice that the larger W i is, the more likely Y i ∈ A and hence the smaller L i is. That is L i should be monotonically decreasing as W i increases. Observing this, we can make a monotonization correction on L i 's. To be specific, we rearrange L i by the decreasing order ofW i . If L(W (i-1) ) < L(W (i) )which violates the monotonicity, we revise it by L(W (i-1) ) = L(W (i) ), where W (i) is the ith smallest among W . This monotonization correction enables us to avoid obvious errors due to unstable estimation and improve the performances of all the methods utilizing L i 's.Choice of K. A useful interactive constraint needs an appropriate specification of K. For any two i.i.d. observations X and X ′ with corresponding θ and θ ′ respectively, the expected C 2 of the individuals of interest is given asC 2 := E[g(X, X ′ ) | θ = 1, θ ′ = 1], which can be estimated by C 2 = i<j;i,j∈L g( Xi , Xj )/{|L|(|L| -1)}, where L = {i : Ỹi ∈ A}. It is reasonable to set K = a C 2 ,where a > 0 is user-specific to control the interactive constraint level. Our numerical evidence reveals that a ∈ (0.1, 0.5) works generally well.Gang et al. [17] proposed a structure-adaptive sequential testing (SAST) rule for online false discovery rate control. In their work, the rejecting rule is as follows:If L t < γ t and {|R t-1 | + 1} -1 i∈Rt-1 L i + L t ≤ α, then δ t = 1. Otherwise δ t = 0, where R t-1 = {i ≤ t -1 : δ i = 1}and γ t is a barrier estimated from an "offline" procedure.The implementation details of SAST for comparisons in our simulations in Section 4 are different from the original one. Firstly, the original SAST assumes the null density function f 0 is already known while in our setting f 0 remains unknown. Secondly, in our predictive inference setting, the density functions and the null proportion are directly estimated via calibration set as the offline estimation procedure in Algorithm 1, not from current rejection sets. Besides, considering the time-varying structures of the data stream in their setting, Gang et al. [17] incorporated the barrier strategy in their method, which is not necessary to be adopted here.The notion of conformal p-values was originally proposed by Vovk et al. [42] to construct prediction interval. Recently, there exist some works to apply conformal p-values to implement sample selection from a multiple-testing perspective, such as Bates et al. [7] , Rava et al. [31] and Jin and Candès [21] . In the sample selection problem, the hypothesis has the following form for each t,H 0t : Y t ∈ A c v.s. H 1t : Y t ∈ A.There are two types of conformal p-values and we adopt the one in Bates et al. [7] which utilizes the same class calibration. Recall that for W t , its conformal p-value p t is defined asp t = 1 + i∈Dcal I{Q( Wi ) ≤ Q(W t )} 1 + |D cal | .The nonconformity score function Q(W t ) is used to indicate the possibility of θ t = 0. For example, in regression settings, if A = [b, +∞), we can useQ(W j ) = b -W j . If A = (-∞, a] ∪ [b, +∞), then we can choose Q(W t ) = max{W t -a, b -W t }. And in binary classification settings, if A = 1 and W t indicates the probability of Y t = 1, we set Q(W t ) = 1 -W t .Even though conformal p-values are correlated, using conformal p-values to conduct multiple testing can control the FDR level with finite sample guarantee since they are positive regression dependent on a subset (PRDS) [10] . However, the conformal p-values are lower bounded by 1/(|D cal | + 1), which leads to unsatisfactory performance for online multiple testing methods based on p-values. Since these methods require sufficiently small p-values to make rejections.In our simulations, we implement LOND, SAFFRON and ADDIS for online sample selection by R package OnlineFDR [32] with α = 0.1. Other parameters are defaulted. Here we introduce the details about these online FDR control methods. Ramdas et al. [29] proposed a "statistical perspective" to control FDR in online setting, which is to keep an estimate of the FDP less than α similar to the offline setting. Specifically, for offline FDR, let the rejection set R(s) = {i|p i ≤ s}.An oracle estimate for FDP is given by FDP * (s) := |H0|•s |R(s)|∨1 . For online FDR, an oracle estimate of FDP * (t) is j≤t,j∈H 0 αj R(t)∨1. Table 2 lists a comparison of estimating FDP in classical offline methods and online methods for FDR control in multiple testing. For the online methods, denote the decision rule as δ t = {p t ≤ α t }, where p t is the corresponding conformal p-value at time t for our problem. The test levels {α t } for LOND [18] , SAFFRON [30] and ADDIS [40] are listed as follows: n•s |R(s)|∨1 j≤t αj R(t)∨1LOND [18] Storey-BH [37] n•s•π0 |R(s)|∨1 , π0 = n i=1 1(pi>λ) n(1-λ) j≤t αj 1{p j >λ j } (1-λ j ) R(t)∨1SAFFRON [30] j≤t αj 1{λ j <p j ≤τ j } τ j -λ jADDIS [40] • LOND: α t = γ t (R(t -1) + 1), where {γ t } ∞ t=1 is a given infinite non-increasing sequence of positive constants that sums to α and R(n) = n t=1 R t denotes the number of discoveries in the first n hypotheses tested.• SAFFRON: At each time t, define C j+ = C j+ (t) = t-1 i=τj +1 , where C t = I{p t ≤ λ}. For t = 1, α 1 = min{γ 1 W 0 , λ}; For t = 2, 3, . . . , α t := min{λ, αt }, where αt = W 0 γ t-C0+ + ((1 -λ)α -W 0 )γ t-τ1-C1+ + (1 -λ)α j≥2 γ t-τj -Cj+ .• ADDIS: The testing levels for ADDIS are given by α t = min{λ, αt }, whereαt = (η -λ)[ω 0 γ S t -C0+ + (α -ω 0 )γ S t -τ * 1 -C1+ + α j≥2 γ S t -τ * j -Cj+ ]and S t = i<t I{p i ≤ η}, τ * j = i≤τj I{p i ≤ η}.All the experiments were conducted on 3.11 GHz Intel Gen i5-11300H processors with 16 Gb memory at a Lenovo personal computer and the R platform with version 4.2.1. The time of execution for each of the individual experimental runs is about 6.686 seconds. And the total compute time for the synthetic classification example in Section 4 for 500 replications is about 63.877 minutes.We illustrate the idea of the II-COS procedure via a binary classification example. We aim to select m = 50 data points of a specific class from unlabeled data arriving sequentially. We choose FSR as the individual constraint and mES as the interactive constraint.The data is generated as follows. The 4-dimensional covariates X = (X 1 , X 2 , X 3 , X 4 ) ⊤ are generated from a mixture of multivariate normal distributions with mean (0, 0, 0, 0) if Y = 0 and mean (-3, -3, 0, 0) if Y = 1. The proportions of Y = 0 and Y = 1 are 80% and 20% respectively. In this illustrative example, we set the historical data size n = 1, 000 with calibration size n 1 = 500 and would like to select m = 50 data points from the interest region A = {1} with the target FSR level α = 0.1. The mES threshold K is set at 0.01 for II-COS.Figure 6 depicts the scatterplot of the first two dimensions of the covariates X, with green dots and red triangles denoting correctly selected points and falsely selected ones, respectively. The SAST method proposed by Gang et al. [17] is taken as one benchmark, which considers only the FSR control. We observe that the selected points of II-COS enjoy significant diversity among the covariate space and only a few false selections are contained. In contrast, the SAST is inclined to choose similar samples concentrated at the center of the concerned group and stops too early to fully explore the covariate space with sequentially arriving samples.Correctly-selected Falsely-selected In practice, the distribution of (X t , Y t ) may vary smoothly over time. Due to the unknown Y t , it is unrealistic to re-estimate parameters (i.e., Estimation Step in Algorithm 1) on both labeled data and the most recent data. To mitigate this problem, we consider the probability of Y t ∈ A (i.e. the proportion of samples in the specified region) varying over time and extend the proposed II-COS to learn π t = Pr(Y t ∈ A) continuously over time.Let Q(W t ) be one score function, which is high when the possibility of θ t = 0 is large and otherwise low. For example, in regression settings, if A = [a, +∞), we can take Q(W t ) = a -W t . And in binary classification, if A = 1 and W t indicates the probability of Y t = 1, we can set Q(W t ) = 1-W t . One valid conformal p-value for Q(W t ) can be obtained as Bates et al. [7] ,p t = 1 + i∈Dcal I{Q( Wi ) ≤ Q(W t )} 1 + |D cal | .Inspired by the techniques for null proportion estimation in multiple testing literature [37] , we note that Pr( p t ≥ λ) ≈ Pr( p t ≥ λ, θ t = 0) ≈ π t (1 -λ) for large λ ∈ (0, 1) (i.e., λ = 0.5).Thus, we consider using some recent p t to estimate a reliable π t . Denote q as the size of a neighborhood {t -q, . . . , t -1} and fix λ. We employ an exponential weighted scheme to estimate π t where the more recent samples will contribute more to the estimation:π λ t = 1 - t-1 j=t-q κ b (j -t)I{ p j > λ} (1 -λ) t-1 j=t-q κ b (j -t), where κ b (s) = exp{-|s|/b} and b is the bandwidth parameter. Then, we can compute the distribution of W t asf t = f 0 (w)(1 -π t ) + f 1 (w) π t and estimate L t by L λ t = (1-π λ t ) f0(Wt) f t (Wt) ∧ 1.The extended II-COS is to substitute L λ t for L t in Algorithm 1. The following theorem establishes the guarantee by assuming the slow change of distribution [6] . Theorem C.1. Assume π t satisfies |π t+1 -π t | ≤ η for any t, and the bandwidth pa- rameter b satisfies b ζ ≤ q for some ζ > 1. Denote ∆ ′ = c 1 n -β/(2β+1) 1 √ log n 1 + c 2 max{b -1/3 , (log n 1 /n 1 ) 1/6 , (bη) 2/3 } with constants c 1 ,(δ t ) ≤ K + (K+cg)∆ ′ 0.5-mα ′ m-1 -∆ ′ .Besides the part similar to ∆ n1 in Theorem 3.3, the bound ∆ ′ owns an additional term that can be decomposed into three parts. The b -1/3 indicates how many valid samples we use to estimate π t . The second part comes from the approximation error of p-values. The last one characterizes the effects of distribution shift. If we properly choose b such that bη = o(1), this term is negligible. Thus when b and n 1 both tend to infinity, ∆ ′ converges to 0 and the individual and interactive constraints will be controlled asymptotically. There exists some trade-off of stopping time and two criteria. In fact, II-COS could result in a short stopping time when only one criterion is considered. Typically, one could choose K = +∞ for the case the interactive constraint is out of work and only individual criterion control is considered, and meanwhile one can set α = 1 with which the interactive constraint is the only concern. The results in Table 3 evaluated this conclusion where C 1 is the FSR and C2 is the ES. We perform some additional simulations under the classification setting, to study the stopping early issue for those methods based on the conformal p-values.Take α = 0.1 and K = 0.045 for FSR and mES, respectively. In Table 4 , we first fix n tr = 1, 000 and m = 100 and vary n cal from 500 to 2,500 to compare the average numbers of selected samples of these three methods with II-COS until stopping. It is clear that all the three benchmarks are unable to select enough samples across all the settings, especially with a small calibration set. As the calibration size n 1 increases, their selected numbers tend to be close to the target. This can be understood because a larger calibration size would generally yield more accurate detection of the individual of interest and thus alleviate the alpha-death issue to some extent. In contrast, the performances of II-COS, in terms of the number of selected samples until stopping, would be much less influenced by the size of calibration data. The II-COS only stops when m samples are obtained under all the scenarios.Furthermore, to verify that II-COS can guarantee both FSR(δ Tm ) and ES(δ Tm ) control with a relatively small calibration size n cal (such as 200), we apply II-COS in synthetic data. The details of the data generation process can be found in Section 4 and D.4.We fix n tr = 1000, m = 100 and n cal varies from 200 to 800. The average of FSR(δ Tm ) and ES(δ Tm ) with II-COS for both scenarios are calculated from 500 replications. The results are summarized as Table 5 . It's obvious that for different n cal , both FSR(δ Tm ) and ES(δ Tm ) are controlled under the pre-specified constant α and K respectively under all scenarios with our II-COS method. The following regression setting is considered: Y = -7X 2 1 + 5 exp X 2 + 10(X 3 + X 4 ) 2 + ε, with X ∼ N 4 (0, I 4 ) and ε ∼ N (0, 1). The informative set is A = (c, ∞), where c is the 80% quantile of Y . The FSR and mES are considered as C 1 and C 2 , respectively. The prediction algorithm H is taken as neural network, with a single hidden layer and 10 hidden neurons, implemented by R package nnet, and K is chosen as 0.015.The simulation results are summarized in Figure 8 and 9 from 500 replications. The results are similar to those for classification setting. It's further verified that our proposed II-COS outperforms all the benchmarks under both classification and regression scenarios. Other individual constraints To better illustrate the performance of our proposed method, we also conduct an experiment for the general individual constraint. We chooseG 0 (X) = | d i=1 X i |, G 1 (X) = | d i=1 X i |/2for EC (expected cost), and choose G 0 (X) = 1, G 1 (X) = 0 for FSR. Other settings are the same as the classification model. The results are shown in Figure 10 . We can see that only the proposed II-COD can guarantee all EC (expected cost), FSR and ES control, while all the benchmarks are out of control for EC or ES.Other pairwise function g. Besides the RBF kernel, popular choices include the cosine similarity [47, 52] with adjustment g(X, X ′ ) = X ⊤ X ′ /(∥X∥ 2 ∥X ′ ∥ 2 ) + 1, and the absolute value of cosine similarity, i.e., g(X, X ′ ) = |X ⊤ X ′ |/(∥X∥ 2 ∥X ′ ∥ 2 ) which characterizes the orthogonality between X and X ′ and is often considered in the field of design of experiments [15] . The similarity functions mentioned above all satisfy Assumption 3.2. As a supplement to the experiments in the main text, we choose the cosine similarity with adjustment g(X, X ′ ) = X ⊤ X ′ /(∥X∥ 2 ∥X ′ ∥ 2 ) + 1 for classification setting. Notice that the original cosine similarity X ⊤ X ′ /(∥X∥ 2 ∥X ′ ∥ 2 ) can be negative sometimes.Hence we add a constant 1 which guarantees g(X, X ′ ) ≥ 0 and does not change the final results. The simulation results are summarized in Figure 11 from 500 replications. As can be seen, the simulation results are similar to those when choosing the RBF kernel in Section 4.1. for II-COS, SAST, LOND, SAFFRON and ADDIS. The similarity function g is chosen as the cosine similarity with adjustment g(X, X ′ ) = X ⊤ X ′ /(∥X∥2∥X ′ ∥2) + 1. The black dashed lines are the corresponding FSR level α = 0.1 and the ES level K = 1.0.In Table 6 , the average proportions of handicapped and female in the selected candidates are in the last two columns of (a). The average proportions of minority and female among the correctly selected individuals are in the last two columns of (b).Except for the random forest algorithm, we further apply two different learning algorithms H for classification setting to estimate the model μ(X): Support vector machine (SVM) and Neural network (NN) with a single hidden layer and 10 hidden neurons, which are implemented by R packages kernlab and nnet, respectively. For NN algorithm, the entropy fitting is used for classification setting. The empirical FSR(T m ) and ES(T m ) levels are estimated by the average of the false selection proportion and the expected similarity respectively from 500 replications. The results are summarized in Figure 12 . As can be seen, the simulation results are similar as those when applying random forest in Section 4.1.Table 6 : Average values with candidate dataset and income dataset: FSR(δ Tm ), ES(δ Tm ) (×10 -3 ) and stopping time Tm. The average proportions of handicapped and female in the selected candidates are in the last two columns of (a). The average proportions of minority and female among the correctly selected individuals are in the last two columns of (b). The target FSR level is α = 0.2 for both. For the candidate data, the target ES level K = 1 × 10 -3 ; For the income data, K = 6 × 10 -3 .(a) Candidate dataset [22] Method Regarding efficiency, we conducted an experiment to compare the effectiveness of II-COS with an oracle method possessing knowledge of true state θ t . This can be succinctly formulated as follows. At time t, δ t = 1 if θ t = 1 and PC(δ Tm )/PS(δ Tm ) ≤ K,the process halts when i≤t δ i = m. To ensure a fair comparison, we fix α = 0.01 for II-COS and choose K = 0.045 for both methods. The results are shown in Table 7 . The FSR of the oracle procedure is 0 as expected. The T m of II-COS is very close to the oracle. This close proximity indicates the high efficiency of II-COS. Both FSR and ES are effectively controlled by II-COS. Let N be a prespecified large integer denoting the number of samples arriving sequentially. Denote n as the size of available labeled history dataset D. We fix N = 5000, n = 5000. Consider three different varying patterns for π t :2. Linear pattern: Vary π t linearly from 0 to 0.5, π t = 0.5t/N .3. Sine pattern: π t = {sin(8πt/N ) + 1}/4, π t ranges between 0 and 0.5.The other settings are the same as those in classification setting. For the historical dataset, we fix π t = 0.2.In simulation we generate 500 data points prior to t = 1 to form an initial proportion estimate. The varying proportion estimates are updated every 200 time points. The bandwidth parameter b for estimating π λ t are chosen based on normal reference rule. We set b = 38. The window size q are chosen by a rule of thumb in practice. Let q = Cb, where C is a fixed constant between 10 and 20. In our simulations, we fix q = 500 and λ = 0.5. As for the density estimation, we first estimate f 0 and f 1 on the calibration data, then computef t = f 0 (w)(1 -π t ) + f 1 (w) π t . Thus accordingly, we estimate L t by L λ t = (1-π λ t ) f0(Wt) f t (Wt) ∧ 1.As for those methods based on conformal p-values, they do not need modification since they only require the exchangeability of data in the null hypothesis. The varying proportion case does not violate such a condition.The simulation results are shown in Figures 13 14 15 , from which we can observe that the extended version of II-COS performs better than the benchmarks under all three different varying settings for both C 1 (FSR) and C 2 (ES) control. The following results include a standard uniform bound for kernel density estimator [36, 20] and a simple corollary from the central limit theorem [11] .Lemma E.1. If Assumption 3.1 hold and we take the bandwidth h = n -1/(2β+1) 1, then with probability at least1 -1/n 1 sup w∈R | f (w) -f (w)| ≤ D 1 n -β 2β+1 1 log n 1 ,where D 1 = D 1 (M, c β , β, K) is a positive constant depending on M and β, c β of Hölder continuity and the kernel K(•).Lemma E.2. The estimation π satisfies| π -π| ≤ π(1 -π)n -1 2 +γ 1 , with probability 1 -n -2γ 1 for any constant 0 < γ < 1/2.Next lemma characterizes the uniform convergence of L(w).h = n -1/(2β+1) 1, then we havesup w∈R | L(w) -L(w)| ≤ D 2 n -β 2β+1 1 log n 1 , for some positive constant D 2 = D 2 (M, D 1 , ℓ, π) with probability 1 -2/n 1 -1/n 1/3 1 . Proof. Note that L(w) = (1 -π) f0(w) f (w) ∧ 1 and sup w∈R | L(w) -L(w)| ≤ sup w∈R (1 -π) f 0 (w) f (w) -L(w) = sup w∈R (1 -π) f 0 (w)f (w) -(1 -π)f 0 (w) f (w) f (w)f (w) ≤ sup w∈R 1 f (w)f (w) (1 -π)f (w)| f 0 (w) -f 0 (w)| + |π -π|f 0 (w)f (w) + (1 -π)f 0 (w)| f (w) -f (w)| ≤ sup w∈R | f 0 (w) -f 0 (w)| + f 0 (w)|π -π| f (w) + sup w∈R L(w)| f (w) -f (w)| f (w) (i) ≤ 1 inf w∈R f (w) {D 1 n -β 2β+1 1 log n 1 + M π(1 -π)n -1 2 +γ 1 + D 1 • n -β 2β+1 1 log n 1 } (ii) ≤ 2 ℓ {D * 1 n -β 2β+1 1 log n 1 + M p(1 -p)n -1 2 +γ 1 + D 1 • n -β 2β+1 1 log n 1 } (iii) ≤ D 2 n -β 2β+1 1 log n 1 , where D * 1 = D * 1 (D 1 , π) is a positive constant depending on D 1 and π because f 0 is estimated by about n 1 (1 -π) samples. The (i) follows the results directly in Lemma E.1 and Lemma E.2 and the bounds of f (w) and f 0 (w) in Assumption 3.1-( 1) with probability 1 -2/n 1 -1/n 2γ 1 . The (ii) holds sincef (w) ≥ f (w) -D 1 n -β 2β+1 1 log n 1 ≥ ℓ -D 1 n -β 2β+1 1 log n 1 > ℓ/2for sufficiently large n 1 . Due to the fact β ≤ 1 and taking γ = 1/6 in Lemma E.2, the (iii) holds withD 2 = 2{D * 1 + M π(1 -π) + D 1 }/ℓ.Hence we verify the conclusion. □The next lemma shows the property of data-driven II-COS procedure which is useful to give the bound of the mES gap.Lemma E.4. Suppose δ t is the decision result at time t ≥ T s by the data-driven II-COS procedure with i≤t L i δ i /1 ∨ i≤t δ i ≤ α ′ , where T s = inf{t : t i=1 δ i = s} and s ≥ 2. Then we haveE( 1≤i<j≤t δ i δ j ) E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) ≤ 1 - 2s s -1 α ′ -1 .Proof. It suffices to show1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) ≥ (1 - 2s s -1 α ′ ) 1≤i<j≤t δ i δ j .By the selection procedure, we haveEQUATIONSquaring both sides of ( 9) and making some decomposition, we have1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) ≥ (1 -α ′ ) 2 1≤i<j≤t δ i δ j + 1 2 t i=1 {(1 -α ′ ) 2 -(1 -L i ) 2 }δ i . Notice that t i=1 δ i = 2 s -1 1≤i<j≤t δ i δ j .We have(1 -α ′ ) 2 1≤i<j≤t δ i δ j + 1 2 t i=1 {(1 -α ′ ) 2 -(1 -L i ) 2 }δ i ≥(1 -α ′ ) 2 1≤i<j≤t δ i δ j + 1 2 t i=1 {(1 -α ′ ) 2 -1}δ i ≥(1 -α ′ ) 2 1≤i<j≤t δ i δ j - α ′ (2 -α ′ ) 2 2 s -1 1≤i<j≤t δ i δ j ≥(1 - 2s s -1 α ′ ) 1≤i<j≤t δ i δ j .The next two lemmas will be used in the analysis of the extended II-COS for varying proportion case.Lemma E.5. Assume that random variables Y 1 , Y 2 , have density functions bounded by a constant c > 0, and other two random variables Y 3 , andY 4 satisfy P(|Y 1 -Y 3 | ≤ ε) ≥ 1 -ζ and P(|Y 2 -Y 4 | ≤ ϵ) ≥ 1 -ς, where ε > 0, ϵ > 0, ζ > 0 and ς > 0.Then for all t > 0,|P(Y 1 > t, Y 2 > t) -P(Y 3 > t, Y 4 > t)| ≤ 2c(ε + ϵ) + 3(ζ + ς).Proof. Define the eventsEQUATIONP(Y 2 + ϵ > t, E 2 ) ≤ P(Y 4 > t, E 2 ) ≤ P(Y 2 -ϵ > t, E 2 ),we haveP(Y 1 > t, Y 2 > t) -P(Y 3 > t, Y 4 > t) ≤ |P(Y 1 > t, Y 2 > t) -P(Y 3 > t, Y 4 > t, E)| + P(E c 1 ) + P(E c 2 ) ≤ |P(Y 1 > t, Y 2 > t) -P(Y 1 -ε > t, Y 2 -ϵ > t, E)| + |P(Y 1 > t, Y 2 > t) -P(Y 1 + ε > t, Y 2 + ϵ > t, E)| + P(E c 1 ) + P(E c 2 ) ≤ |P(Y 1 > t, Y 2 > t) -P(Y 1 -ε > t, Y 2 -ϵ > t)| + 3P(E c 1 ) + 3P(E c 2 ) + |P(Y 1 > t, Y 2 > t) -P(Y 1 + ε > t, Y 2 + ϵ > t)| ≤ 2c(ε + ϵ) + 3(ζ + ς),the last inequality holds because the density function is bounded.□ Lemma E.6. If b ζ ≤ q for some ζ > 1 and b is sufficiently large, the exponential weight κ b (s) = exp{-|s|/b} satisfies q s=1 κ 2 b (s) { q s=1 κ b (s)} 2 ≤ C b 1 b and q s=1 sκ b (s) q s=1 κ b (s) ≤ C b b, where C b > 0 is constant determined by b. Proof. Take Z b = exp{-1/b}. Notice that j s=i κ b (s) = exp{-(i + 1)/b} -exp{-(j + 1)/b} 1 -exp{-1/b} = Z i+1 b -Z j+1 b 1 -Z b .Thus for a constant C b > 0. we haveq s=1 κ 2 b (s) { q s=1 κ b (s)} 2 = Z 4 b -Z 2q b 1 -Z 2 b / Z 4 b -2Z q+2 b + Z 2q b 1 + Z 2 b -2Z b (i) ≤ C b (1 -Z b ) (ii) ≤ C b 1 b ,where (i) holds since b is sufficiently large such that Z q b = exp{-q/b} ≤ exp{-b ζ-1 } can be eliminated and Z b < 1. The last inequality (ii) holds by exp{x} ≥ x + 1.By the same discussion, we haveq s=1 sκ b (s) q s=1 κ b (s) ≤ ∞ 1 sZ s b ds/ Z 2 b -Z q b 1 -Z b ≤ Z b (1 -Z b ) 2 / Z 2 b -Z q b 1 -Z b ≤ C b 1 1 -Z b ≤ C b (b + 1).The last inequality holds since exp{x} ≤ 1/(1 -x) for x < 1. For simplicity, we use the same notation C b to denote the constants. □Proof. For the part of individual constraint control, note that L i is defined asL i = Pr(θ i = 0 | W i ) = E [(1 -θ i ) | W i ] . Define W * = σ(W 1 , • • • ).The stopping time T is measurable respect to W * . The individual constraint at time T satisfiesC 1 (δ T ) = E i≤T {(1 -θ i )G 0 (X i ) + θ i G 1 (X i )}δ i ( i≤T δ i ) ∨ 1 = E   E (R T ∨ 1) -1 i≤t {(1 -θ i )G 0 (X i ) + θ i G 1 (X i )}δ i | W *   (i) = E   (R t ∨ 1) -1 i≤t {E (1 -θ i ) | W i G 0 (X i ) + E θ i | W i G 1 (X i )}δ i   = E (R t ∨ 1) -1 i≤t {L i G 0 (X i ) + (1 -L i )G 1 (X i )}δ i .The (i) holds since X i 's are independent of each other. By construction of the selection rule, we have that at the stopping time T ,EQUATION)Taking expectations on both sides of inequality (10) and by double expectation theorem, we finally obtainE 1≤i<j≤T g(X i , X j )δ i δ j θ i θ j ≤ K × E 1≤i<j≤T δ i δ j θ i θ j .It follows that for every time t ≥ T 2 ,C 2 (δ T ) = E 1≤i<j≤T g(X i , X j )δ i δ j θ i θ j E ( i≤T δ i θ i )( i≤T δ i θ i -1) ≤ K □ E.3 Proof of Theorem 3.3Proof. In the data-driven II-COS procedure, δ i is determined by the estimated lFDR L i and we have1 R t i≤t { L i G 0 (X i ) + (1 -L i )G 1 (X i )}δ i ≤ α.Note thatC 1 (δ t ) = E 1 R t i≤t {L i G 0 (X i ) + (1 -L i )G 1 (X i )}δ i = E 1 R t i≤t { L i G 0 (X i ) + (1 -L i )G 1 (X i )}δ i + E 1 R t i≤t {(L i -L i )G 0 (X i ) + ( L i -L i )G 1 (X i )}δ i ≤ α + E 1 R t i≤t {(L i -L i )G 0 (X i ) + ( L i -L i )G 1 (X i )}δ i .It suffices to bound the absolute value of the second term. We haveE 1 R t i≤t {(L i -L i )G 0 (X i ) + ( L i -L i )G 1 (X i )}δ i ≤E 1 R t i≤t {|L i -L i ||G 0 (X i )| + | L i -L i ||G 1 (X i )|}δ i ≤E 1 R t i≤t { sup w∈R |L i -L i ||G 0 (X i )| + sup w∈R | L i -L i ||G 1 (X i )|}δ i ≤2c G D 2 n -β 2β+1 1 log n 1 + 2n -1 1 + n -1 3 1 .The last inequality follows from Lemma E.3 andEQUATIONThe (i) holds by Assumption 3.2 and L(w), L(w) ≤ 1 even when t is random, as the uniform convergence of L(w). And (ii) follows from Lemma E.3. By the similar arguments we haveEQUATIONDenote 11) and ( 12), it follows that for every time t ≥ T s ,∆ n1 = Dn -β 2β+1 1 √ log n 1 . Combining (C 2 (δ t ) = E 1≤i<j≤t g(X i , X j )δ i δ j (1 -L i )(1 -L j ) E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) (i) ≤ E 1≤i<j≤t g(X i , X j )δ i δ j (1 -L i )(1 -L j ) + 2c g ∆ n1 E( 1≤i<j≤t δ i δ j ) E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) (ii) ≤ K + 2c g ∆ n1 E( 1≤i<j≤t δ i δ j ) E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) × E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) (iii) ≤ K + 2c g ∆ n1 1 -2mα ′ m-1 × E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) (iv) ≤ K + 2c g ∆ n1 1 -2mα ′ m-1 × 1 -2∆ n1 E( 1≤i<j≤t δ i δ j ) E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) -1 (v) ≤ K + 2c g ∆ n1 1 -2mα ′ m-1 1 - 2∆ n1 1 -2mα ′ m-1 -1 .The (i) follows from (11) , and (ii) comes from the operation of our algorithm, whereE 1≤i<j≤t g(X i , X j )δ i δ j (1 -L i )(1 -L j ) ≤ K • E 1≤i<j≤t δ i δ j (1 -L i )(1 -L j ) .The (iii) and (v) are directly from Lemma E.4. The (iv) holds due to (12) . Thus we haveC 2 (δ t ) ≤ K + (K + c g )∆ n1 0.5 -mα ′ m-1 -∆ n1 □ E.5 Proof of Corollary 3.5Proof. Define the C 1 constraint conditional on W asC ′ 1 (δ t ) = 1 R t i≤t {(L i -L i )G 0 (X i ) + ( L i -L i )G 1 (X i )}δ i .By the proofs of Theorem 3.3, we have for any tC ′ 1 (δ t ) ≤ α + 2c G sup w∈R | L(w) -L(w)|.Hence at stopping time T m , we haveC ′ 1 (δ Tm ) = E[C ′ 1 (δ Tm )] ≤ E[sup t C ′ 1 (δ t )] ≤ α + 2c G E[ sup w∈R | L(w) -L(w)|] ≤ α + ∆ n1 .By the proof of Theorem 3.4, we can also drop off the expectation and replace ∆ n1 withEQUATIONHence at stopping time t = T m , (13) still holds. Take expectations at both sides and we will getC 2 (δ Tm ) ≤ K + (K + c g )∆ n1 0.5 -mα ′ m-1 -∆ n1.Notice that ∆ n1 = Dn Proof. We first denote some notations. For notational simplicity, we use c to denote constants in the following proofs.Recall the conformal score function Q(X t ). The conformal p-value isp t = 1 + i∈L I{Q( Wi ) ≤ Q(W t )} 1 + |L| = F n2 (Z t ),where n 2 = |L|.Denote the population p-value as p t = F (Q(W t )), where F (•) is the distribution of Q(W t ) conditional on θ t = 0. Denote π t = Pr(θ t = 1) andπ λ t = 1 - Pr(p t > λ) 1 -λ .The corresponding local FDR is defined asL λ t = π λ t f 0 (W t ) f t (W t ) .It follows the definition of C λ 1 (δ t ) and C λ 2 (δ t ).C λ 1 (δ t ) = E 1 R t i≤t {L λ i G 0 (X i ) + (1 -L λ i )G 1 (X i )}δ i and C λ 2 (δ t ) = E{ 1≤i<j≤t g(X i , X j )δ i δ j (1 -L λ i )(1 -L λ j )} E{ 1≤i<j≤t g(X i , X j )δ i δ j } .The estimated proportion is defined asπ λ t = 1 - t-1 j=t-q κ b (j -t)I{ p j > λ} (1 -λ) t-1 j=t-q κ b (j -t) .And denote the ideal estimated proportion via population p-values asπλ t = 1 - t-1 j=t-q κ b (j -t)I{p j > λ} (1 -λ) t-1 j=t-q κ b (j -t), where κ b (s) = exp{-|s|/b} and q is the size of a neighborhood for estimation before time t.We first claim the following proposition and the proof is deferred in Section E.7.Proposition E.7. Suppose the assumptions in Theorem 3 hold. ThenEQUATIONwith probability 1 -max 1/b, logn 1 /n 1 , (bη) 2 2γ, where c > 0 is a constant and 0 < γ < 1/2.Notice thatsup w | f t (w) -f t (w)| = sup w | f 0 (w)(1 -π t ) + f 1 (w) π t -f 0 (w)(1 -π t ) -f 1 (w)π t | ≤ sup w | f 0 (w) -f 0 (w)| + sup w | f 1 (w) -f 1 (w)| + 2M | π t -π t |.The last inequality holds since π t ∈ [0, 1] and f 0 (w) and f 1 (w) are upper bounded by M .Thus by Lemma E.1 and take γ in Proposition E.7 at 1/6, with probability 1 -EQUATIONwe haveEQUATION.By the procedure of Lemma E.3 directly, with probability 1 -c max 1/b, log n 1 /n 1 , (bη) 2 1/3we haveEQUATION.It follows thatEQUATION.EQUATION. By our assumption, bη = o(1). So lim b,n1→∞∆ ′ n1 = 0.By the additional assumption that Pr(p t > λ | θ t = 1) = 0, we have π λ t = π t . Thus Hence the first part of Theorem 3 is completed.At last, we can use the same procedure to prove thatC λ 2 (δ t ) ≤ K + (K + c g )∆ ′ n1 0.5 -mα ′ m-1 -∆ ′ n1 . Since π λ t = π t , C λ 2 (δ t ) = C 2 (δ t) and the results directly follow.Proof. Notice thatPr(| π λ t -π λ t | > ε) ≤ Pr | π λ t -πλ t | > ε 2 + Pr |π λ t -π λ t | > ε 2 .We discuss for the two parts respectively. For the first term of the above inequality, it suffices to show the upper bound of the second moment of | π λ t -πλ t |. For convenience, denote U j = I(p j > λ), and V j = I( p j > λ). It followsE{| π λ t -πλ t | 2 } = 1 { t-1 j=t-q κ b (j -t)} 2 (1 -λ) 2 E   t-1 j=t-q κ b (j -t)(U j -V j )   2 = t-1 j=t-q κ 2 b (j -t)E{(U j -V j ) 2 } { t-1 j=t-q κ b (j -t)} 2 (1 -λ) 2 + i,j∈Nq(t),q̸ =j κ b (i -t)κ b (j -t)E{(U i -V i )(U j -V j )} { t-1 j=t-q κ b (j -t)} 2 (1 -λ) 2 = 1 { t-1 j=t-q κ b (j -t)} 2 (1 -λ) 2 t-1 j=t-q κ 2 b (j -t) Pr(p j > λ) + Pr( p j > λ) -2 Pr(p j > λ, p j > λ) +2 t-q≤i<j≤t-1 κ b (i -t)κ b (j -t) Pr(p i > λ, p j > λ) -2 Pr( p i > λ, p j > λ) + Pr( p i > λ, p j > λ) .Now we check the upper bound of |p j -p j |. We can rewrite them as p j = F (Q(W j )) and p j = F n2 (Q(W j )).-p j | ≤ ε 1 ) = E Pr |p j -p j | ≤ ε 1 | { θi } i∈C ≤ E Pr sup z F (z) -F n2 (z) ≤ ε 1 | { θi } i∈C ≤ E 1 -2 exp{-n 2 ε 2 1 } ≤ 1 -2 exp{-(1 -π)n 1 ε 2 1 } -4π/{n 1 (1 -π)}.The last inequality holds since n 2 ≥ (1 -π)n 1 /2 with probability 1 -4π/{n 1 (1 -π)}.Thus by Lemma E.5 and the fact that p j has a bounded density function, we obtain|Pr(p j > λ) -Pr( p j > λ)| ≤ 2ε 1 + 6 exp{-(1 -π)n 1 ε 2 1 } + 12π/{n 1 (1 -π)}. Take ε 1 = log n 1 /{n 1 (1 -π)}, for sufficient large n 1 such that √ n 1 log n 1 ≥ 6 + 6π we have |Pr(p j > λ) -Pr( p j > λ)| ≤ 2 √ log n 1 (1 -π)n 1/2 + 6 + 12π/(1 -π) n 1 ≤ 3 √ log n 1 (1 -π)n 1/2 .Again by Lemma E.5 and the same ε 1 , for any i, j ∈ {t -q, . . . , t -1} := N q (t), we have|Pr(p j > λ, p i > λ) -Pr( p j > λ, p i > λ)| ≤ 4ε 1 +12 exp{-(1-π)n 1 ε 2 1 }+ 24π n 1 (1 -π) ≤ 6 √ log n 1 (1 -π)n 1/2 1 .Therefore by Lemma E.6, we haveE(| π λ t -πλ t |) ≤ 9C b √ log n 1 bn 1/2 1 (1 -π)(1 -λ) 2 + 12 √ log n 1 n 1/2 1 (1 -π)(1 -λ) 2 .So by definition and Markov' inequality, we havePr | π λ t -πλ t | > ε 2 ≤ 4E(| π λ t -πλ t |) ε 2 ≤ 36C b √ log n 1 bn 1/2 1 (1 -π)(1 -λ) 2 ε 2 + 48 √ log n 1 n 1/2 1 (1 -π)(1 -λ) 2 ε 2For the second part, we haveEQUATIONThe Above all, we finally conclude that for all ε > 0 and sufficiently large n 1 , we havePr(| π λ t -π λ t | > ε) ≤ C b bε 2 (1 -λ) 2 + 36C b √ log n 1 bn 1/2 1 (1 -π)(1 -λ) 2 ε 2 + 48 √ log n 1 n 1/2 1 (1 -π)(1 -λ) 2 ε 2 + 16(C b bη) 2 ε 2 (1 -λ) 2 ≤ max 1 b , √ log n 1 n 1/2 1 , (bη) 2 c ε 2for some constant c > 0.Thus take ε = max 1/b, √ log n 1 /n 1/2 1 , (bη) 2 1/2-γ √ c and we obtain | π λ -π λ | ≤ c max 1 b , √ log n 1 n 1/2 1 , (bη) 2 1/2-γ with probability 1 -max 1/b, log n 1 /n 1 , (bη) 2 2γ, where 0 < γ < 1/2. Hence we complete the proof. 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide the data and code in the supplemental materials, including sufficient instructions in the zip file. Guidelines:• The answer NA means that paper does not include experiments requiring code. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: We calculate the standard error across 500 replications and show the error bars in experimental results, which is calculated by mean +/se. 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• 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] 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] Justification: We have cited and provided the URL of the dataset we use in the paper, see Sect. 4 and the references. 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.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset'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] Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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 is used. • 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. 
 
 Appendix:  


Decision: This paper explores an online sample selection problem with both individual constraints (e.g., false selection rate) and interactive constraints (e.g., diversity). The authors propose a simple yet effective algorithm, supported by strong theoretical analysis and numerical experiments. The reviews were generally positive, and the rebuttals effectively addressed the reviewers' questions. Therefore, I recommend acceptance.

For the camera-ready version, I encourage the authors to incorporate their discussions with the reviewers and enhance the presentation as suggested by reviewer vWkU.

Reviews: review: paper_summary: paper_summary: This paper introduces a framework to perform online sample selection such that the unseen outcomes are in specific target range while also optimizing for constraints like diversity that are dependent on the input covariates. The additional constraint involving input covariates can help ensure properties like the diversity of candidates when selecting individuals for interviews while also guaranteeing that most of the interviewed individuals accept the offer. The paper proposes a data-driven procedure to select the subset of candidates in an online fashion by implementing the proposed algorithm. Under reasonably weak assumptions, the paper provides theoretical guarantees on satisfying both the above constraints in online sample selection. The experiments confirm that this framework ensures low false selection rates (i.e. unseen outcomes are in a specific target range) while optimizing for the additional covariate-dependent constraints like diversity on synthetic and real data.
strength_weakness: strength_weakness: It would be interesting to understand the gaps between an ideal diversity profile and the profile obtained by the proposed method in Fig 3. Analysing the gap w.r.t changing g(X_i, X_j) function choice could be helpful. Would it be helpful to increase the weight of the g(X_i, X_j) term to reduce this gap and understand its implications on the satisfaction of individual constraints?

It is evident that the SAST baseline outperforms the proposed method in terms of FSR sometimes, which is understandable given there; 's a tradeoff with the interactive constraints (Table 2b, Fig 1).  It would be helpful to learn if we can reduce the gap between SAST and the proposed method by balancing the tradeoff (perhaps using a tunable hyperparameter that balances the two constraints?).
questions: questions: See weaknesses
limitations: limitations: Yes, limitations and broader impacts are discussed in the last section of paper.
paper_summary: paper_summary: The paper studies online sample selection with individual and interaction 
constraints simultaneously. Specifically, the goal is to control (variants) of 
the false selection rate (FDR) and the expected similarity (ES) under the 
empirical bayes framework. Under distributional conditions, the proposed method 
controls the target quantities asymptotically. The method is evaluated on synthetic 
and real data.
strength_weakness: strength_weakness: Please see my comments in the questions section.
questions: questions: 1. **The model.** In the motivating examples such as candidate selection, it appears to me 
that we get to observe the ground truth, i.e., $Y_t$, after time step $t$.
This is briefly mentioned in the discussion section, but I think it is reasonable 
to use the observed $Y_t$'s to update the estimation.

2. **The choice of interaction constraints.** It is not well-motivated why 
the changing ES to (4) is reasonable. As illustrated in the simulation, 
although these two quantities seem to coincide as the time step goes 
to infinity, they do differ quite a lot with smaller time steps (this could happen 
when $m$ is small).

3. What is the principle for choosing K in general? In particular, for the real data example, 
why is K taken to be $1\times 10^{-3}$ in the fist example and $6\times 10^{-3}$ in the second?

4. In the numerical experiments, a fairer comparison with offline CP would be with [1], i.e., 
thresholding the p-values with BH-adjusted p-values as opposed to the fixed threshold. 

[1] Jin, Ying, and Emmanuel J. Candès. "Selection by prediction with conformal p-values." Journal of Machine Learning Research 24.244 (2023): 1-41.
limitations: limitations: The authors have partically addressed the limitations.
paper_summary: paper_summary: In this paper, the authors quantify the uncertainty of response predictions using predictive inference; and systematically addressing individual and interactive constraints in a sequential manner.  An online selection rule is developed to ensure the above two types of constraints are under control at pre-specified levels simultaneously.  Simulated and real-data examples  are used to evaluate and illustrate their approach in terms of both online individual and interactive criteria control.
strength_weakness: strength_weakness: See questions below.
questions: questions: Section 4.1 would be good to tell reader how many replications are used.
limitations: limitations: Comments are needed on the practicality of \hat\mu being a bijection.  How critical is this assumption to the method and the theoretical analysis.  If critical then this is a limitation.
paper_summary: paper_summary: The paper proposes a method for online sample selection. The authors introduce the concepts of _individual_ and _interactive constraints_, and demonstrate theoretically and empirically that their method satisfies both.
strength_weakness: strength_weakness: I am not familiar with the FDR control literature, and had to read parts of the paper (specifically sections 2.2, 2.3 and 4) multiple times to get a gist for the logic of the method and its empirical perfomance. This is reflected in my confidence score. If the paper is accepted, I highly recommend the authors revise the paper to make it easier to follow. A flowchart to illustrate the steps of the algorithm and/or to illustrate the differences between the Oracle and Data-driven selection procedures may be helpful; a toy example could also help. I also suggest including a longer description and/or table of the benchmark methods against which the empirical performance of II-COS was compared.
questions: questions: - Interactive constraint: Why is this defined only with respect to the correctly selected samples? In the case of, e.g., the diversity of selected samples, is the constraint not intended to represent the diversity of all selections?
- Line 159: Should $R_t = \left( \sum_{i \leq t} \delta_i \right) \lor 1$?
limitations: limitations: The authors discuss limitations of their work.

Comments: comment: Thank you for the detailed response and additional work on experiments. 

I am increasing my rating to accept (7).
Thank you for these clarifications.
Thanks for your response.  I maintain my rating of 8.