Adaptive Data Collection for Robust Learning Across Multiple Distributions
Authors: Chengbo Zang
Mehmet Kerem Turkcan
Gil Zussman
Zoran Kostic
Javad Ghaderi
Venue: ICML 2025 poster (2025)
Keywords: online learning
adaptive data collection
multi-armed bandits
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We propose a framework for adaptive data collection aimed at robust learning in multi-distribution scenarios under a fixed data collection budget.

Abstract: We propose a framework for adaptive data collection aimed at robust learning in multi-distribution scenarios under a fixed data collection budget. In each round, the algorithm selects a distribution source to sample from for data collection and updates the model parameters accordingly. The objective is to find the model parameters that minimize the expected loss across all the data sources. Our approach integrates upper-confidence-bound (UCB) sampling with online gradient descent (OGD) to dynamically collect and annotate data from multiple sources. By bridging online optimization and multi-armed bandits, we provide theoretical guarantees for our UCB-OGD approach, demonstrating that it achieves a minimax regret of $O(T^{\frac{1}{2}}(K\ln T)^{\frac{1}{2}})$ over $K$ data sources after $T$ rounds. We further provide a lower bound showing that the result is optimal up to a $\ln T$ factor. Extensive evaluations on standard datasets and a real-world testbed for object detection in smart-city intersections validate the consistent performance improvements of our method compared to baselines such as random sampling and various active learning methods.

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Chengbo Zang' Mehmet Kerem Turkcan
Gil Zussman' Zoran Kostic" Javad Ghaderi!
Abstract
healthcare (Moody & Mark, 1992; Zang et al., 2023), and object detection in smart cities (Cordts et al., 2016; Turkcan et al., 20244)necessitare the collection and annotation of custom datasets to address the unique characteristics of their respective problem.
We propose framework for adaptive data collec- tion aimed at robust learning in multi-distribution scenarios under fixed data collection budget. In each round, the algorithm selects a distribution source to sample from for data collection and updates the model parameters accordingly. The objective is to find the model parameters that min- imize the expected loss across all the data sources. Our approach integrates opper-confideece-bboe (UCB) sampling with online gradient descent (OGD) to dynamically collect and annotate data from multiple sources. By bridging online opti- mization and multi-armed bandits, we provide the- oretical guarantees for our UCB- UCB-OGD approach, demonstrating that it achieves a minimax regret of O (K In T) over K data sources after T rounds. We further provide a lower bound show- ing that the result is optimal up to a In T factor. Extensive evaluations on standard datasets and a real-world testbed for object detection in smart- city intersections validate the consistent perfor- mance improvements of our method compared to baselines such as random sampling and various active learning methods.
As a motivating example in smart-city applications, consider the task of vehicle detection at an urban traffic intersection. The objective is to develop robust vehicle detection model that is capable of operating effectively under varying condi- tions, such as changes in lighting, occlusions, and weather variations. Three strategically placed cameras, each provid- ing a unique perspective of traffic flow, are available for data collection. The trained model will be deployed across all three cameras, with the goal of optimizing the worst-case de- tection performance among them. However, annotating data for complex tasks such detection, tracking, and segmen- tation is particularly expensive. This involves meticulous labeling of bounding boxes, object identities across frames, and pixel-level masks to generate accurate ground truths. Given a limited annotation budget (e.g. 2,500 images), it is crucial strategically allocate the annotation budget across the three cameras maximize the worst-case detection performance at the intersection.
In this paper, we present framework for adaptive data collection and model training in multi-distribution scenar- ios under a fixed data annotation budget. The proposed framework operates iteratively, alternating between data col- lection (annotation) and model optimization in each round. Our objective is devise a budget allocation strategy across the distribution sources such that the trained model achieves performance guarantee across all the distributions.
1. Introduction
In modern deep learning systems, sufficient and high-quality data is essential for robust model performance (Hestness al., 20.7). Although numerous standard datasets and pre- trained models are publicly available, they could fail to meet the diverse and specific requirements of applications, espe- cially when applied to novel or previously unseen scenarios. Consequently, many applications- such as languale modeling (Laurençon et al., 2024), intelligent monitoring in
1.1. Related Work
Active Learning. The challenge of data annotation has driven significant advancements in the field of active learn- ing (AL). The key idea of AL is to let the learning algorithm interactively query an annotator to label a subset of data points from a set of unlabeled data (Settles, 2009). In par- ticular, pool-based methods assume that pre-existing pool of unlabeled data is available and aim to select the most relevant samples from the pool to query for their labels. The relevance of sample is often determined by criteria such as uncertainty measure (Lewis & Catlett, 1994) or
'Dppartment of Electrical Engineering. Columbia Univer- sity. New York NY, USA *Department of Civil Engineering, Columbia University, New York NY, USA. Correspondence to: Chengbo Zang <cz2678 @wo.umbia..uuu........ Javad Ghaderi <jg3465 @columbia.cdu>>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
committee votes (Seung al., 1992). On the other hand, stream-based methods observe a consecutive stream of sam- ples and decide for every sample whether to query for its label or discard it. A similar branch of work is active class selection, where the learner is allowed to query a known class label for new samples (Lomasky et al., 2007; McClurg et al., 2023). AL methods are widely applied to Deep Neural Networks (DNNs) (Ren et al., 2022) in tasks such as clas- sification (Ranganathan et al., 2017; Yoo & Kweon, 2019; Sinha et al., 2019) and object detection (Aghdam et al., 2019; Feng et al., 2019; Choi et al., 2021).
shifts during training and testing (Ahuja al., 2020). Specif- ically, distributionally robust optimization (DRO) formalizes this by minimizing the worst-case loss over a pre-defined uncertainty set of distributions, often characterized via met- rics like Wasserstein distance or f-divergence (Duchi & Namkoong, 2021; Agarwal & Zhang, 2022). In such spirit, group- explicitly incorporates group annotations to en- sure uniform performance across subgroups, and utilizes bandit algorithums address robustness and fairness (Hagh- talab et al., 2022; Zhang et al., 2023).
Particularly, Multi- Bandit (MAB) studies sequen- tial decision problem that seeks to maximize cumulative reward over time, where the action at each time step is se- lected from multiple fixed choices with unknown reward distributions (Robbins, 1952; Gittins, 1979). Popular algo- rithms, such as e-Greedy and UCB, have been extensively studied and analyzed for stochastic bandits (Auer et al., 2002). While adversarial bandits (Bubeck & Nicolò, 2012) are typically utilized in group-DRO literature. such algo- rithms often disregard the notion of a dataset by considering an oracle- setup, where the algorithm samples directly from the data distribution to obtain an unbiased loss (and gradient) estimator. Despite its theoretical convenience, di- rectly sampling from the data distribution every time is not always feasible due to practical limitations. In contrast, this work seeks to utilize the information contained in the collected dataset by leveraging algorithms from stochastic bandits and perspectives from contextual bandits (Langford & Zhang, 2007: Slivkins, 2011). 1).
Despite their empirical effectiveness, AL methods are re- stricted by the quality of the generated queries. In a scenario with a trivial initial sample pool or a biased initial model, AL algorithms can exhibit unstable behavior by overfitting to specific region of the data space or exacerbating the initial bias (Baldridge& & Palmer, 2009; Karamcheti et al., 2021). Moreover, the existing theoretical analysis of AL is mainly restricted to linear hypothesis classes or basic prob- lem setups like binary classification (Dasgupta, 2005; Wang et al., 2021; Gentile et al., 2022). Whereas some studies have derived coarse sample complexity bounds (Dasgupta, 2005) or analyzed convolutional neural networks using core- set techniques (Sener& & Savarese, 2018), general theoretical guarantees remain elusive when it comes to more complex problem setups, such as those involving DNNs
Estimating the Dataset Size. The relationship between DNN performance and the amount of available training data can be empirically characterized by the neural scaling law (Bisla al., 2021; Hestness al., 2017; Mahmood al., 2022a). As a result, recent work models DNN training as a Markov Decision Process (Mahmood et al., 2022b) or a Gaussian Process (Tejero et al., 2023) with respect to (w.r...) the dataset size. The amount of data required given a specific performance metric can therefore be empirically predicted, although the composition of multiple data sources often not explicitly accounted for.
1.2. Contributions
Our main contributions can be summarized as follows.
We introduce an adaptive data collection framework for robust learning across multiple distributions under limited data collection and annotation budget, without relying on an initially collected set of annotated or unannotated samples.
The theoretical guarantees on dataset size can also be estab- lished by leveraging predefined data quality metrics, such as information functions (Xu & Zheng, 2017), submodular functions (Akein et al., 2023a; Mirzasoleiman et al., 2016), or a target data distribution (Akein et al., 2023b). Many centralized AL algorithms (e.g. uncertainty- or entropy- based sampling) share similar intuitions by selecting the most relevant data to annotate using such metrics. However, the robustness of real-world applications are often measured in terms of the worst-case model performances rather than the quality of the data itself. Therefore, it is more common in robust learning to directly minimize the worst-case loss, which we mainly discuss in this paper.
We propose the UCB-OGD algorithm that combines UCB sampling and online gradient descent which achieves O(T's (K In T) minimax regret, matching the theoretical lower bound up to a In T factor.
We conduct experiments on both standard datasets and a rorl-world testbed for complex tasks and demonstrate that the proposed UCB-OGD algorithm achieves com- parable or higher minimax performance on multiple tasks compared to well-known AL algorithms.
2. Problem Statement
Notations. We consider a data space X with K data sources and a parametrized model we wish to train for some task. This can be classification, multi-class object detection and
Robust Learning and Multi-Armed Bandits. Robust learning focuses on model generalization under distribution
2

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
segmentation, or even single-class tasks where the data can be obtained from different sources (e.g. see our motivat- ing smart-city example in Section 1). Each data source k E 2 } is associated with an unknown data dis- tribution Dj over X. Let 0 be the parameter of the train- able model in some parameter space O. Let x(O,X) x be the loss function for data point X E X!. Let (0) := [X]] denote the expected loss associated with (Vol,, [V, X]] be the gradient of μa (0) w.r.t. the parameter 0.
Algorithm I General Framework of Online Optimization
with Adaptive Data Collection
Require: Total training rounds T, batch size M, randomly initialized 0
1: Xo + Ø
2: for 1 1.2 do
3:
k + SELECT N(-1)
Ex-D, [f(0, Ex<D,[[(O,_X))
4: B. + {XI,... XM ~
] 5: X, t XB-IBB:
data source k and (0) == Ex-D,,
Oc+1 <- UPDATE(O,,
end for
For instance, in the motivating smart-city example in Sec- tion 1, there are K- = 3 data sources, one for each camera, X is an image randomly obtained from a camera with cor- responding data source index, object classes, and bounding boxes, 0 the parameter vector of an object detection model, and ((,, X) is the loss of the model prediction over the input X given its annotation.
and is less prone to overfitting towards particular data source. Minimax learning is also preferred for its robustness to distributional uncertainties (Farnia & Tse, 2016), since we want to train model that works well across range of data distributions one might encounter during real-world deployment.
Let S be a set of samples and denote Sy :- {x E S
X ~ D as the subset of S that belongs to data source k.
A Algorithm Framework. We propose a general framework by combining adaptive data collection and online optimiza- tion as presented in Algorithm 1. The algorithm starts with empty training set X, = Ø and an initialized 0j. In every round f, in the SELECT step, the algorithm selects data source Ke E {1, 2....... K, to collect and annotate a batch of samples B, The decision is made based on the current model parameter 9₂ and the existing training set X--1. The batch of new samples B, then added to X,- to get the updated training set XG For the simplicity of the analysis, assume the batch size is fixed, i.e., |B, M 2 1. Then, in UPDATE step, the algorithm updates the model parameter 6g based on the updated training set X' and the selected data source ki, and obtains 0z-1 for the next round.
Then the empirical estimate of pu (0) over the set of samples S can be computed as (0; := Exes, E(0, ()/ where |-| denotes the set cardinality. Similarly, the empirical estimate of V Fux(() over the set of samples S is computed as V S0 == Exes, Vo X)/|Sx)-
Optimization Objective. If S is fixed training set that ex- ists in advance, a natural objective is to minimize the empiri- cal loss over the training set, i.c., Exes t(0, X) (a.k.a. empirical risk minimization). This objective function can be interpreted the weighted average of the empirical losses of all data sources, where each data source is weighted by the ratio of its samples in S, i.e Σx= (1Sa i/ iz (0; S). However, the construction of the training set itself may worth more careful considerations, especially in woal-world applications where the annotation budget is limited. As opposed to allocating the budget of training samples among the data sources in a predefined way (e.g. uniformly), we allow the samples to be actively collected and annotated dur- ing the training process. In this scenario, the requirement of a preexisting training set S is alleviated. Since no prior exists for the ratio Sx we consider an objective that is independent of this ratio through minimax optimization:
Performance Metric. After T rounds of execution, an online algorithm A generates a sequence of data source indices kı, h ,KT and sequence of model parameters 0 0y. A natural metric to quantify the performance of an online algorithm that solves the optimization problem (I) is based on the minimax regret, which is defined as the cumulated gap between the global optimal loss and the maximum loss achieved by the current model in each round.
Definition 2.1 (Minimax Regret). The minimax regret of an algorithm A over T rounds is defined as
min max k= K
(0).
(1)
Note that the expected loss functions (0), for i I.... K, are unknown. The objective (1) is of particu- lar interest for the purpose of optimizing data collection. It
T
R(AT) = Σ max Ma (0:) - T min max Ma (0), (2)
0 k
focuses on optimizing the worst-case expected loss which ensures the faimees of the algorithm (Papadaki et al., 2022)
where we use Ar = (ks, 0z). = 1,..., the sequence of data source indices and model parameters generated by algorithm A after T rounds.
...,, T) to denote
'To be precise. X = (z,y) y) where x is the input, and y is the target output (annotation) from the model with input 2. Then E(0, X) measures how different the prediction of the model with parameter is from the target output y.
We mainly focus on the expectation of the minimax regret, E E(((Ar)), since the trajectory Ar is random.
3

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
The minimax regret metric can be connected to the conver- gence of fime-averaged model parameter under algorithm A, defined as Az := Vi= 0r/T.. The time-average con- vergence is commonly adopted in the literature of online and stochastic algorithms, as it facilitates more straightforward theoretical guarantees (Hazan, 2016; Tejero et al., 2023). While there is no direct equivalence between the average parameter Ay and the final parameter 0r (which is a more common choice in actual implementations), advanced opti- mizers such as SGD with Momentum and Adam (Polyak, 1964; Kingma& & Ba, 2017) run moving average over the gradients V jú to improve the robustness of the algorithm. These two concepts are analogous in terms of promoting smoother update steps for the model.
we fix the batch size M and the total number of rounds T, the algorithm collects total number of MT samples from all data sources, allowing for uniform comparisons between different algorithms based on their minimax regret.
For the optimization step (Line 6 of Algorithm 1), we con- sider Online Gradient Descent (OGD) (Hazan, 2016). Re- call that Ky is the data source selected for the current round t. Denote Xt,,, := {X E X₂ X Dba } the subset of X collected from data source ky Let S be a batch of data points uniformly sampled from Ar, Then OGD updates the model parameter of the next round by taking a step in the direction of the estimated gradient of the mean loss of source kt at the current round, i.e.,
B.t1 < 0₂ T) Pr, (0g:))
(4)
When the loss functions are convex, we can build an intuitive relationship between the minimax regret and the optimality gup as follows.
where 77 := 1/(2 the learning rate.
For the data source selection step (Line 3 of Algorithm 1), we consider the following three methods.
Proposition 2.2 (Optimality Gap). Let p1,,... PK be con- vex in 0. Then any algorithm A satisfies
Random Selection. The simplest baseline is to pick the data
E [[(( (3)
source uniformly at random, i.e., K2 ~ U(f1..... K})²
E max Ne (B((A)) min max (=)
T
This is equivalent to uniformly allocating the budget of MT
samples among the K data sources, yielding approximately MT/K samples per data source. We refer Algorithm I with random selection and OGD as Rand-OGi
where A = =I-,000 O./T.
The proof of Proposition 2.2 follows from the convex- ity of max; Mi and application of Jensen's inequality, i.c., max: pa (0A)) S Ei= max; pa (0.)/T.
Intuitively, Rand-OGD is not designed for the minimax ob- jective in Equation (I), since all data sources are queried in a balanced way regardless of their losses (see Appendix A.4). A more viable selection method that addresses the minimax problem to greedily select the data source that incurs the highest loss, i.e., hi. < maxx (0.). However, the true expectation (8.) is unknown and we can only measure its empirical estimate (0;; X2-1) which is random variable. Moreover, the deviation of fa from its expectation can be particularly large with a small number of samples.
As result of Proposition 2.2, to show that algorithm converges to the minimax optimum, it is sufficient to show that its (expected) minimax regret is sublinear in T.
We adopt the following assumptions for the analysis pre- sented in this paper.
Assumption 2.3 (Bounded Lipschitz Loss). There exists some C 2 0 s.t. 8(0, X) E [0, C1 for all X and Also, the expected loss 1l (0) is L-Lipschitz in 0 for all k.
While we need to focus on optimizing the maximum loss associated with the data source that incurs as much as pos- sible (i.e., exploitation), we also need ensure that enough samples are collected from other data sources in order to re- duce the variance of the estimated losses (i.e., exploration). This resembles the cexooraaiioneeplioitttionn trade-off in MAB (Multi-Armed Bandit) problems. We consider the following two data source selection methods inspired by MAB algorithms (Auer et al., 2002).
Assumption 2.4 (Finite Domain). The model parameters generated by Algorithm 1 in all rounds, fI...., Or, lie in bounded subset of θ with diameter D 0.
Assumption 2.5 (Finite Gradient Noise). There exists some a 2 s.t. the variance of the gradient is finite, i.c., EX ()) - Vuu
< o² for all k, O.
Assumption 2.6 (IID Sampling). Data collected from every data source k is sampled i.i.d. from the associated data distribution Dr-
Decaying c-Greedy Selection. For >> 1, define explo- ration probability c
1 6 == 2 VoKlni/2M(
3. Algorithms and Main Results
(5)
We present three specific algorithms within the framework of Algorithm and their corresponding performances. Since
where a 2 1/2 is constant. We specially define 61 := 1. Then, in every round t, with probability e,, we select k ~
"Tiis will be defined more rigorously in Appendix A.3.
*U(S) denotes the uniform distribution over set S.
4

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
U(II...., otherwise, we select
A natural question is whether the bounds in Theorem 3.1 can be improved. We can establish the following lower- bound for the minimax regret of any algorithm which shows UCB- OEBDOGDAAA is optimal, up to a in T factor.
k f arg max (be( (11)).
(6)
We refer Algorithm 1 with G--Gredy selection and OGD as Eps-OGD.
Proposition 3.3 (Minimax Lower-Bound), The minimax
regret of any online algorithm A satisfies [[[((TT]] Z O(T in the worst case.
Upper- Ceee--oooneneeBBouue (UCB) Selection. UCB is an- other popular balances the the empirical estimate and its uncertainty. De- fine a confidence radius for each data source given some set of samples S as
strategy in MAB that
The proof of Proposition 3.3 is based on simple case and is provided in Appendix A.6.
(S( = C (()nn
(7)
4. Proof of Main Results (Theorem 3.1)
where C' is defined in Assumption 2.3, 2 1/2 is a con- stant, and [S&] is the number of samples in S that belongs to data source k. Then, in every round t, we pick the data source with the maximum UCB value, i.e.,
In Algorithm both the SELECT step and the UPDATE step seek to utilize the information within the collected training set X₁, rather than generating fresh samples from the data distribution (Haghtalab et al., 2022; Zhang et al., 2023). The intuition is that discarding previous samples will result in the model being trained on every data point only once, which is infeasible for most modern DL tasks such as object detection. Instead, it is conventional to reuse past samples while maintaining a training set, at the cost of potential complexities in generalization during theoretical analysis.
kt f arg max (o + (X
(8)
We refer to Algorithm with UCB selection and OGD UCB-OGD.
The following theorem states our main result regarding the minimax regret of Eps-OGD and UCB-OGD for convex loss functions.
Formally, consider the empirical loss (0g; X2) for some k 6g and a training set X, When 0g is trained over the collected samples in X, optimization steps like OGD in Equation (4) introduces implicit dependency between 0, and X, which makes the empirical loss estimator (thus the empirical gradient estimator) biased, i.e..
Theorem 3.1 (Minimax Regret). Let Ju...., be convex in 0. Then Eps-OGD and UCB-OGD achieve the following minimax regrets:
E[R[Eps-OGDy)] = 0 (T)+ E[R(UCB-OGDr)) O(T' (K (Klr(()
(9)
I Tun (0.) = (o)) (0.).
(10)
Indeed, (0)) tends to underestimate μu (0;) due to poten- tial overfitting. In practical DL training, this is mitigated empirically by techniques such as data augmentation and regularization, which we also adopt in the experiments in Section 5.
Note that, by Proposition 2.2, we can subsequently conclude that the expected minimax optimality gap of Eps-OGD and UCB-OGD diminishes at the rate O & (K In +)) and O(T (K In +)),, respectively.
Remark 3.2. When the loss functions are non-comee, it is generally not feasible to converge to the global optimum of (1). In this case, we can only show convergence to a pareto-stationary point (Sener & Savarese, 2018). For- mally, 0, is called Pareto Stationary if there exists set of .1,..., OKK S.t. ΣK 0g (O.) 0, where ouk 2 for all and Σ 02 = 1. We can use time-smoothing w.r.t. a non-trivial window < w < T and corresponding sime-smoothed OGD algorithms from the online non-convex optimization (Hazan al., 2017: Hallak al., 2021). Then can show that asymptotically, as T, + 20, any time- smoothed OGD-based algorithm A converges to pareto- stationary point 0, where Σk1 ag pu = O, and ag is the fraction of rounds that data source l: is selected in the long run under A. We provide the formal statement of this result and its proof in Appendix A.5 for completeness.
To characterize the minimax regret (Definition 2.1) of the algorithms, we present several standard regret definitions from the literature.
Optimization Regret. Recall that Algorithm 1 picks one data source k in every round and generates ot+1 for the next round (t + 1) based on the updated data set X, After T rounds of execution, we define optimization regret for algorithm AA based on the cumulated gap between the expected empirical loss fik, (9t) achieved by the algorithm in round and the best fixed model parameter chosen in hindsight given the sequence of data sources kj, kg.... ..., kT (Hazan, 2016), i...
T Pua (0).
(AT) = Σ jun (0x) min Σ t=1
(1I)
5

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Bandit Regret. Consider K-armed contextual bandit, where the reward of each arm k is {(O, X); X ~ U(X with expectation (0) under context 0. In our problem, the arms are the data sources and the context 0 is the model parameter. Further, the reward distribution of every arm- context pair is stationary". After rounds, we define the bandit regret of an algorithm A based on the cumulated gap between the expected empirical loss when the arms are chosen optimally in context-aware manner and the actual expected empirical loss achieved by the algorithm in each round (Slivkins, 2011), 1), i.e.,
Proposition 4.2 (Optimization Regret). Let pis-... PK be convex in t. With step sizes hnt =1/(2T/L), the optimiza- tion regret of any OGD-based algorithm A over T rounds satisfies
([R)( S L(D2 + +IVT+
(15)
where L, D, and a are defined in Assumption 2.3, Assump- tion 2.4, and Assumption 2.5, respectively.
Proof of Proposition 4.2 follows from the analysis of stan- dard OGD (Hazan, 2016) with modifications to account for Lipschitz loss function (Assumption 2.3) and the gra- dient noise (Assumption 2.5) in our stochastic setting. We also alleviate the dependence of the learning rate de on the diameter D (Assumption 2.4) to be more in line with the conventions in stochastic optimization literature (Garrigos & Gower, 2024). The complete proof of Proposition 4.2 provided in Appendix A.I.
(s(AA) = Σ max Pa (O.) -ik, (0.)) k
(12)
Generalization Regret. We further define the generaliza- tion regret as the cumulated gap between the expected worst- case empirical loss and the worst-case true loss, i.e.,
For the bandit regret Rg, problem adopts the structure of contextual bandit in rigorous manner. However, we are not necessarily playing the bandit game here. When a new context 0, arrives in round f, the player in a rigorous bandit game can only learn about the context from the specific problem structure (e-g. similarity information the context space), or by pulling the arms for new samples. In contrast, both Ops-OGG and UCB-OGD in case are allowed to learn about the new context 6, directly by evaluating the loss over the collected samples, i.e., computing the empirical loss júx (0+l-). This provides us with information about the new context Og even if no new samples are collected in the current round. We can take this advantage to bypass the challenge of navigating through arm-context pairs based on similarity and directly utilize the empirical loss as more informative source of knowledge about 0:.
(AT) == Σ max pa(O.) max in((O)): (13)
Using the definitions above, the minimax regret (Defini- tion 2.1) can be decomposed follows.
Proposition 4.1 (Regret Decomposition). Let Equation (10) hold. Then the minimax regret of any algorithm A over T roundy satisfies R(AT) S R. R.(AA) Ro(AA) Rg(AT)
Proof. By definition, we can write
(AT) + Ro (AT))) + (AT)
T
max (xx(0)) - min 6
tus (0)
We sketch the outline of the bandit regret analysis below and provide the detailed proofs in Appendices A.2 and A.3. The core steps involve establishing the concentration inequality and characterizing the bandit gap.
max pz (0t) - min
Mkc (0)
(14)
1=1
Lemma 4.3 (Loss Concentration). Let S ~ U(X)) be a batch of training data sampled uniformly at random from the training set Xx- Then it holds for any constants l (1...., K) and r > 0 that
max (kx( - T min max pa, (0)
&
R(AT)
The first incquality in Equation (14) follows from Equa- tion (10), and the second inequality from the fact that
PrIlix (0:; - (b.) > r]
(_2[Sp]
(16)
Ms. (0) S max; (0) for any ky, O.
< 2exp
,,2
where |Sxl denotes the number of samples in S that belongs to data source k and C is defined in Assumption 2.3.
For the optimization regret R,, we can establish the follow- ing result for both Eps-OGD and UCB-OGD.
The proof of Lemma 4.3 follows from constructing a mar- tingale over the sequence of E(O,, X,) for each X, E S2 and applying the Azuma's 's inequality, detailed in Appendix A.2.
"This means, at any two time steps t1 E (1..... T}. if hr hr. l and 0r, deg. then E(0e, X1), and E(0e2) X2) for X,, X2 ~ U(Z+)) are itd.
6

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Using the tail bound provided in Lemma 4.3, now we show the concentration of the empirical loss on expectation, ex- pressed in terms of a confidence radius. While the UCB algorithm directly defines its confidence radius in Equa- tion (7), we similarly define the confidence radius of the e-Greedy algorithm given some set of samples S as
every partition and incurs the regret O(T शनर ) where H is the covering dimension of the context space O Since usually H >> 1 for modern DNNs (Mao et al., 2024), the uniform partition algorithm and other similar contextual bandit algorithms (Slivkins, 2011) may struggle to obtain a meaningful regret in our setting.
()) = CV aK CacKKt//te (2
(17)
The final step is to bound the generalization regret Rg, which has been studied extensively in robust learning literature (Dziugaite & Roy, 2017; Arora et al., 2018; Cao & Gu, 2019). While this is out-of-scope for the purpose of this paper, the takeaway is that the generalization bound takes the form of
Further denote (² == maxk (Oe) the maximum ex- pected empirical loss, and (S) the corresponding confi- dence radius defined in Equations (7) and (17). Let ji (0,; S) be the empirical estimate of (0x) given S. The following a direct consequence of Lemma 4.3.
Lemma 4.4 (Bandit Gap). Ler Ax (0,) (0.) (ix(0)) and Au S) = j (0,; - pu S):; Then for any constant a 2 1/2 and confidence radius r defined in Equa- tions (7) and (17), it holds that
(AT T
C(O) |
O +),
(21)
where C(0) is a constant determined by the complexity of the model. Intuitively, the generalization better when the size of the dataset is sufficiently large, and when the model is not too over-parametrized. This is indeed true for a wide range of complex DL tasks, including our motivating example of urban vehicle detection described in Section 1.
(( S) S (x((S) +r
(18)
5)(0):)=0((1))
This indicates that, by following the decision rules of the bandit algorithms that carefully controls A.. -0) with appropriately chosen confidence radius, the estimation of the worst-case loss is accurate with high probability. Since the bandit regret in Equation (12) is accumulation of the bandit gaps Ax, (0t) in each round, Lemma 4.4 effectively provides a provable probability bound on the concentration of the empirical estimation of the bandit gaps, which also guarantees the quality of the OGD updates.
Proof of Theorem 3.1. The proof is a direct consequence of Proposition 4.1 and the fact that the optimization regret in Proposition 4.2, the bandit regrets in Proposition 4.5, and the generalization regret in Equation (21) are all sublinear.
5. Experimental Results
In this section, we present the experimental results of the three algorithms described in Section 3, compared to other state-of-the-arr AL (active learning) algorithms. We con- sider the following tasks with different notions of data source, demonstrating the flexibility of our framework in practical settings.
The following results on the bandit regret match the standard regret bounds of stationary stochastic bandits (Auer al., 2002) despite the non-stationary setting of our problem. The detailed proof is given in Appendix A.3.
Proposition 4.5 (Bandit Regret), The bandit regret (Equa- tion (12)) is O(T's (K TT 8) for Eps-OGD, i.e.
Classification. We perform image classification on the CIFARIO dataset (Krizhevsky et al., 2009) with a budget of 10,000 images, where every class is data source. We also report the results the MNIST dataset (Lecun et al., 1998) to test different optimizer configurations and get more insight into the distribution of collected samples from dif- ferent classes under different algorithms. The metric are the mean and minimum class wise accuracies among all classes We use a simple three-layer convolutional neural network (CNN) architecture with ReLU activations for this task.
3(2/2+1)C
aKT2
E| E|[((EpsOG)D/)]] <
2
2M
(19)
and O(3 (K UCB-OGD, i.e.
2aKT I
E[R((UCB-OGDD)] S 2
(20)
M
Multi-class Object Detection. We perform object detection the PASCAL VOC2012 dataset (Everingham et al.) with budget of 3,000 images. Since each image may contain a mixture of objects from different classes, we define the data source as a set of different classes whose objects are likely to appear in the same image, i..., indoor, wildlife, transport, and human. Then we partition the dataset into four subsets,
Remark 4.6. In the rigorous contextual bandit setting where one can only learn about the new context from the problem structure, it is common to assume that the reward function is Lipschitz w.r.t. to the context. The uniform partition al- gorithm (Hazan& & Megiddo, 2007) proposes to partition the context space and run a stationary bandit algorithm on
7

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
each containing a collection of images from one of the four data sources. Details of data source assignment is given in Appendix B. We use mean Average Precision with intersection ronrection-over-uiiinn (IOU) threshold of 0.5 (mAP@ 50) to measure the performance of the algorithms within each subset. The metrics are the mean and minimum mAP@ 50 among all subsets of images. We use the SSD300 (Liu et al., 2016) architecture with input image size of 300 for this task. The backbone network is VGG16 (Liu & Deng, 2015) pretrained on ImageNet (Deng et al., 2009).
Table I. Performance of the proposed algorithms, UCB-OGD and Eps-OGD, compared to Rand-OGD and active learning algorithms standard datasets and complex real-world tasks.
DATASET (BUDGET)
MIN ACC
MEAN
MODEL
ALG
AcC
Uc
49.3
68.7
EN
53.0
68.1
BALD
45.0
66.5
CIFAR (10K)
DBAL
52.7
68.6
CNN
BADGE
40.0
61.0
RAND-OGD
36.3
63.3
Vision-Language Modeling. We perform a simple Vi- sual Question Answering (VQA) task under budget of 1,000 question-answer pairs from the VQAv2 dataset (Antol et al., 2015) using the proposed algorithms. We partition the dataset into three data sources based on the type of the questions, i... yes/no questions, numerical questions, and descriptive questions. The metrics are the mean and mini- mum per-token accuracies of each data source. We adopt pretrained 2025) for this task.
EP5-OGD
48.9
64.5
UCB-OGD
52.3
66.5
MDN
42.2
47.2
Voc2012 (3K)
SSD300
RAND-OGD
40.6
51.3
UCB-OGD
44.7
53.0
VQAv2 (IK)
RAND-OGD
20.9
20.9
SMOLVLM
UCB-OGD
22.6
22.9
TESTBED (2K5)
RAND-OGD
57.0
66.7
model (Marafioti et al.,
SSD300
UCB-OGD
61.7
69.2
Single-class Object Detection. We further implement the proposed algorithms on the COSMOS testbed (Raychaud- huri al., 2020) for detecting vehicles in urban intersec- tion (our motivating example in Section 1) with budget of 2,500 images. The COSMOS testbed includes traffic intersection in New York City, with three cameras overlook- ing the traffic flows from different angles. Further details of the testbed setup is given in Appendix B. We collect and annotate the captured images from the three cameras in the testbed and consider each camera as data source. The metrics are the mean and minimum Average Precision with IOU threshold of 0.5 (AP@ 50) among all cameras. We use the same model architecture as the one used for the above multi-class task but with an input image size of 320.
pared to Eps-OGD, Other details of the implementation are given in Appendix B.
We also draw comparisons with several state-of-the-arr AL algorithms. For the classification task, we consider several well- AL algorithms in the literature (Mun- jal et al., 2022), i.e., Uncertainty-based Sampling (UC), Entropy-based Sampling (EN), Bayesian Active Learning by Disagreement (BALD), Deep Bayesian Active Learning (DBAL), and Deep Batch Active Learning (BADGE) (Ash et al., 2020). All AL algorithms are given an initial labeled pool of 1,000 samples (10% of budget), and proceeds to collect 3,000 samples in each episode from the remaining dataset for three episodes. For the multi-class object detec- tion task, we consider the Mixture Density Network (MDN) that takes a probabilistic approach for uncertainty measure- ment (Choi et al., 2021). The MDN algorithm is given an initial labeled pool 600 samples (20% budget), and pro- ceeds to collect 800 samples per episode for three episodes. We note that the sizes of the initial labeled pool for both tasks are typically smaller than the common setup in AL literature in order to emulate data-scarce scenarios. The results are summarized in Table 1.
To understand how the three algorithms differ from each other and what training configurations use, we run the classification task on the MNIST dataset under various tups. Each algorithm executes 1,000 rounds and collects a batch of 8 samples every 4 rounds under a total budget of 2,000 training images. The results are depicted in Fig- ure It can be observed that Eps-OGD and UCB-OGD con- sistently outperform Rand-OGD (Figure I (a)), with UCB- OGD exhibiting comparatively better accuracy. The colored band associated with each line represents the range of mini- mum and maximum class-wise accuracy of each algorithm. We also observe from Figure 1(b) that the Adam optimizer with cosine-annealing learning rate scheduler (LRS) and L2 regularization (Reg) provides the smoothest trajectory, which we adopt for the following experiments. Figure ((c) shows the distribution of the samples collected from each digit. It can be seen that UCB-OGD tends to explore the data sources with fewer samples more aggressively com-
For CIFAR1O, it can be seen that while all algorithms outper- form the Rand-OGD baseline, DBAL and UCB-OGD give similar minimum accuracies of 52.7 and 52.3, surpassing other algorithms by noticeable margin. Meanwhile, two AL methods, UC and DBAL, give higher mean accuracy of 68.7 and 68.6 over all classes.
For VOC2012, UCB-OGD outperforms both Rand-OGD and MDN in both minimum and mean mAP@ 50. Further- more, we inspect the effect of the initial pool size on MDN.
8

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
0.7
Mic MDN
UCpp-00 Axcmary
0.90
Min MDN
0.5
0.75
0.75
Meac UCB
0.50
Rand OGD
0.50
0.45
Adam
SGD
mAA
0.5
Miaat Rand
Mit LSB
Adam- LLRS
UCB-OGD
0.30
Adamn -L Ray
0.4
Rani
0.00
200
400
600 Rounds
800
1000
200
400
Rounds
600
500
1000
500
Initial Sample Pool Size
1000
1500
(a) Validation accuracy
(b) Optimizer configs
(c) Collected samples
Figure/ 1. Comparisons of Rand-OGD, Eps- OGD, and terms of validation accuracy, optimization configurations, and the distribution the number of samples collected from each data source (i.e., digit).
on MNIST over 1,000 rounds
Figure 2. Initial MDN pool size v.s. the final mAP@50 compared to Rand-OGD and UCB-OGD.
We fix the total budget of 3,000 samples and change the number of samples allocated during each episode. The re- sults are shown in Figure 2. It can be observed that MDN requires 1,200 initially labeled samples (40% of budget) in order to top UCB-OGI on both the minimum and mean mAP@50. 50. This finding affirms that pool-based AL algo- rithms like MDN can be sensitive to the initial sample pool, and our proposed method is more suitable when the amount of labeled samples is limited.
lines, including random sampling and several well-known Active Learning (AL) approaches. By optimizing data col- lection decisions, our framework achieves comparable or better model performance with fewer (labeled and unla- beled) samples, effectively reducing annotation costs while improving generalization across heterogeneous distributions in real-world deployment. These results highlight the po- tential of integrating online optimization and bandit-based sampling for efficient data acquisition, offering a scalable solution for robust learning in real-world applications.
We further note that AL. methods achieve the reported perfor- mances by incrementally sampling from the entire unlabeled pool, while our methods only make decisions based on the annotated portion of the dataset, which is much smaller. Appendix C provides other experimental results such as the performances of new models trained on the collected data.
An important direction for future work is to further tighten the regret bounds for more restrictive types of objective fune- tions and verify their applicability in DNNs. Incorporating Bayesian perspective could further improve the efficiency during sampling. For the experimental verifications, larger- scale evaluations on diverse, real-world datasets with more complex multi-modal distributions would provide deeper insights into the effectiveness of the proposed framework. Expanding experiments to include dynamic environments, such as continuously evolving traffic patterns in smart cities, would further validate the framework's 's robustness and scal- ability to broader applications.
For the VQA task, UCB-OGD outperforms Rand-OGD on both mean and minimum accuracy. Although larger experiments are still required, we believe the results are able to demonstrate that our proposed framework can be applied to complex tasks like vision-languag modeling where the training data incorporates various modalities. This is especially beneficial for training small models (such as Smol-VLM) under scenarios where the data budget and computational resources are both limited.
A Acknowledgements
Finally, our experiments on the testbed show that UCB- OGD achieves a 4.7 improvement in minimum AP@ 50 compared to Rand-OGD. Moreover, while Rand-OGD re- ports 57.0 AP@ 50 after collecting 2,500 samples, UCB-
This work was supported in part by NSF grant CNS- 1827923 and EEC-2133516, NSF grant CNS-2038984 and corresponding support from the Federal Highway Admin- istration (FHA). MediaTek Inc USA, NSF grant CNS- 21481 28 and by funds from federal agency and industry part- ners as specified in the Resilient & Intelligent NextG Sys- tems (RINGS) program, ARO grant W91 INF2111110 and compute resources from NVIDIA Academic Grant "Edge AI for Equitable and Safe Intersections in Urban Metropolises". We would also like to thank the anonymous reviewers for their suggestions and insights that improved this work.
OGD achieves the same milestone with only 2, 1, samples, saving more than 13% of the total budget.
6. Conclusions and Future Work
We introduce adaptive data collection framework that enables robust learning across multiple distributions under fixed data collection budget constraint. Our theoretical anal- ysis establishes a general minimax regret guarantee. More- over, our method consistently outperforms existing base-
9

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Impact Statement
Uncertain Gradient Lower Bounds. In 8th International Conference on Learning Representations, ICLR 2020, Ad- dis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Auer, P., Cesa-Bianchi N., and Fischer, P. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47 2002. ISSN 08856125. doi: 10. 10.1023/A:10113889045355
References
Agarwal, A. and Zhang, T. Minimax Regret Optimization for Robust Machine Learning under Distribution Shift.
Baldridge, J. and Palmer, A. How well does active learning actually work? Time-based evaluation of cost-reduction strategies for language documentation. Koehn, P. and Mihalcea, R. (eds.), Proceedings of the 2009 Conference Empirical Methods in Natural Language Processing, pp. 296-305, Singapore, August 2009. Association for Computational Linguistics.
In Loh, P.-L. and Raginsky. M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 1 178 of Proceedings of Machine Learning Research, pp. 2704 2729. PMLR, July 2022.
Aghdam, H. H., Gonzalez-Garcia A., Weijer, J. v. d., and Lopez, A. M. Active Learning for Deep Detection Neural Networks. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
Bisla, D., Saridena, A. N., and Choromanska, A. Entoretical-Empiricnn Approach to Estimating Sample Complexity of DNNs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, pp. 3270-3280 June 2021.
Ahuja, K., Shanmugam, K., Varshney, K., and Dhurandhar, A. Invariant Risk Minimization Games. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pp. 145-155. PMLR, July 2020.
Bubeck, S. and Nicolò, C.-B. Regret Analysis of Stochastic and Nonstochastic
Bandit Problems. 2012.
Cao, Y. and Gu, Q. Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks. In Wallach, H., Larochelle, H., Beygelzimer, A., Alché- Buc, F. d., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Akein, O., Li, P.-h., Agarwal, S., and Chinchali, S. P. De- centralized Data Collection for Robotic Fleet Learning: A Game-TThoreete Approach. In Liu, K., Kulic, D., and Ichnowski, J. (eds.), Proceedings of The 6th Conference on Robot Learning, volume 205 of Proceedings of Ma- chine Learning Research, pp. 978 1188988.7788 PMLR, Decem- ber 2023a.
Choi, J., Elezi, I., Lee, H.-J., Farabet, C., and Alvarez, J. M. Active Learning for Deep Object Detection via Probabilistic Modeling. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 10264-10273, October 2021.
Akcin, O., Unuvar, O., Ure, O., and Chinchali, S. P. Fleet Active Learning: A Submodular Maximization Approach. In Tan, J., Toussaint, M., and Darvish, K. (eds.), Proceed- ings of The 7th Conference on Robot Learning, volume 229 of Proceedings of Machine Learning Research, pp. 1378-1399, PMLR, November 2023b.
Cordts, M., Omran, M., Ramos, S., Rehfeld, T., Enzweiler, M., Benenson, R., Franke, U., Roth, S., and Schiele, B. The Cityscapes Dataset for Semantic Urban Scene Under- standing. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Antol, S., Agrawal, A., Lu, J., Mitchell, M., Batra, D., Zitnick, C. L., and Parikh, D. VQA: Visual Question Answering. In Proceedings of the IEEE International Conference Computer Vision (ICCV), December 2015.
Dasgupta, S. Coarse sample complexity bounds for active learning. In Weiss, Y., Schölkopf, B., and Platt, J. (cds.), Advances in Neural Information Processing Systems, vol- ume 18. MIT Press, 2005.
Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. Stronger Generalization Bounds for Deep Nets via a Compression Approach. In Dy. J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 254-263. PMLR, July 2018
Deng, J., Dong, W., Socher, R., Li, L.-.,, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-254 245, Miami, FL, June 2009. IEEE ISBN 978-1-4244-3992. CVPR,2009.5200
Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. Deep Batch Active Learning by Diverse,
doi: 10.1109/
10

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Duchi, J. C. and Namkoong, H. Learning models with uniform performance via distributionally robust optimiza- tion. The Annals of Statistics, 49(3), June 2021. ISSN 0090-5364. doi: 10. A/022000000044
of Machine Learning Research, pp. 4008-4017. PMLR, July 2021.
Hazan, E. Introduction to Online Convex Optimization. Foundations and Trends@ in Optimization, 2(3-4): 325, 2016. ISSN 2167-3888, 2167-3918. doi: 10.1561/ 2400000013.
Dziugaite, G. K. and Roy, D. M. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Net- works with Many More Parameters than Training Data, October 2017. arXiv: 1 703. 1008 [cs].
Hazan, E. and Megiddo, N. Online Learning with Prior Knowledge. In Bshouty, N. H. and Gentile, C. (eds.), Learning Theory, volume 4539, pp. 499-513, Springer Berlin Heidelberg, Berlin, Heidelherg. 2007. ISBN 978- 4-540-72925-9. doi: 10.
Everingham, M., Van Gool, L., Williams, C. I., Winn, J., and Zisserman, A. The PASCAL Visual Object Classes Challenge 2012 (VOC2012) Results.
36.
Series Title: Lecture Notes in Computer Science
Farnia, F. and Tse, D. A Minimax Approach to Supervised Learning. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Hazan, E., Singh, K., and Zhang, C. Efficient Regret Mini- mization in Non-Convex Games. In Precup. D. and Teh, Y. W. (eds.), Proceedings of the 34th International Con- ference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1433-1441. PMLR, August 2017.
Feng, D., Wei, X., Rosenbaum, L., Maki, A., and Dietmayer, K. Deep Active Learning for Efficient Training of
Hestness, J., Narang, S., Ardalani, N., Diamos, G., Jun, H., Kianinejad, H., Patwary, M. M. A., Yang, Y., and Zhou, Y. Deep Learning Scaling is Predictable, Empirically, December 2017. arXiv: 171.::0001000 [cs].
LiDAR 3D Object Detector. In 2019 IEEE Intelligent Vehicles Symposium (IV), pp. 667-674, Paris, France, June 2019, IEEE. ISBN 978-1-72810-560-4, doi: 10. 1109/AVS.2019.88144
Karamcheti, S., Krishna, R., Fei-Fei, L., and Manning, C. Mind Your Outliers! Investigating the Negative Impact of Outliers on Active Learning for Visual Question An- swering. In Zong, C., Xia, F., Li, W., and Navigli, R. (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I Itth International Joint Conference on Natural Language Pro- cessing (Volume I: Long Papers), pp- 7265-7281, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v 1/2021 longllll--oo.444.
Garrigos, G. and Gower, R. M. Handbook of Convergence Theorems for (Stochastic) Gradient Methods, March 2024. arXiv:2301.1123: [math]]
Gentile, C., Wang, Z., and Zhang, T. Achieving Minimax Rates in Pool-Based Batch Active Learning. In Chaud- huri, K., Jegelka, S., Song, I.., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th Interna- tional Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 7339- 7367. PMLR, July 2022.
Kingma, D. P. and Ba, J. Adam: A Method for Stochastic Optimization, January 2017. 14Xx:1141..6980 [cs].
Gittins, J. C. Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society Series B: Statistical Methodology, (1): 44-1 January 1979. ISSN 1369-7412, 1467-9868. doi: 10. 10.11111,2517-616.1 1979.bb01068.x.
Krizhevsky, A., Hinton, G., and others. Learning multiple layers of features from tiny images. 2009, Publisher: Toronto, ON, Canada.
Langford, J. and Zhang, T. The Epoch-Greedy Algorithm for Hulti-armed Bandits with Side Information. In Platt, J., Koller, D., Singer, Y., and Roweis, S. (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Haghtalab, N., Jordan, M., and Zhao, E. On-Demand Sam- pling: Learning Optimally from Multiple Distributions. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Informa- tion Processing Systems, volume 35, pp. 406-419. Curran Associates, Inc., 2022.
Laurençon, H., Tronchon, I.., Cord, M., and Sanh, V. What matters when building vasion-language models?, 2024. eprint: 2405.02246.
Hallak, N., Mertikopoulos, P., and Cevher, V. Regret Minimization in Stochastic Non-Convex Learning via a Proximal- Gradiient Approach. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Confer- ence on Machine Learning, volume 139 of Proceedings
Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Pro- ceedings of the IEEE, 86(11):227-2334 1998. doi: 70.179....

---

Ranganathan, H., Venkateswara, H., Chakraborty, S., and Panchanathan, S. Deep active learning for image clas- sification. In 2017 IEEE International Conference on Image Processing (ICIP), pp. 3934-3938, 2017. doi: 10. 1..10/9/1..2001789777000 Adaptive Data Collection for Robust Learning Across Multiple Distributions
Lewis, D. D. and Catlett, J. Heterogeneous Uncertainty Sampling for Supervised Learning. In Machine Learning Proceedings 1994, pp. 148-156. Elsevier, 1994. ISBN 978-1-55860-33544 doi: 10.1016/B978---550---333 50026-X.
McClurg, C., Ayub, A., Tyagi, H., Rajtmajer, S. M., and Wagner, A. R. Active Class Selection for Few-Shot Class-Incremental Learning. In Chandar, S., Pascanu, R., Sedghi, H., and Precup, D. (eds.), Proceedings of The 2nd Conference on Lifelong Learning Agents, volume 232 of Proceedings of Machine Learning Research, pp. 811-827. PMLR, August 2023.
Liu, S. and Deng, W. Very deep convolutional neural net- work based image classification using small training sam- ple size. In 2015 3rd IAPR Asian Conference on Pat- ter Recognition (ACPR), pp. 730-734, Kuala Lumpur, Malaysia, November 2015. IEEE. ISBN 978-1-4799- 6100-9. doi: 20.1009/ACPR.211...00 7.78669...
Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed Submodular Maximization. Journal of Machine Learning Research, 17(235):1 2016.
Moody, G. B. and Mark, R. G. The MIMIC Database, 1992.
Liu, W., Anguelov, D., Erhan, D., Szegedy, C., Reed, S., Fu, C.-Y., and Berg. A. C. Ssd: Single shot multibox detector. In Computer Vision-ECCV 2016: 14th European Con- ference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part I 14, pp. 21-37. Springer, 2016.
Munjal, P., Hayat, N., Hayat, M., Sourati, J., and Khan, S. Towards Robust and Reproducible Active Learning Using Neural Networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 223-232, June 2022.
Lomasky, R., Brodley, C. E., Acmecke, M., Walt, D., and Friedl, M. Active Class Selection. In Kok, J. N., Ko- ronacki, J., Mantaras, R. L. D., Matwin, S., Mladenič, D., and Skowron, A. (eds.), Machine Learning: ECMI. 2007, volume 4701, pp. 640-647. Springer Berlin Heidel- berg. Berlin, Heidelberg, 2007. ISBN 978-3-540-749577- 978-3-540-74958-5.
Papadaki, A., Martinez, N., Bertran, M., Sapiro, G., and Rodrigues, M. Minimax Demographic Group Fairness in Federated Learning. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 142-159, Seoul Republic of Korea, June 2022. ACM. ISBN 978-1- 4503-9352-2. doi: 10.1 35.33300..
Mahmood, R., Lucas, J., Acuna, D., Li, D., Philion, J., Alvarez, J. M., Yu, Z., Fidler, S., and Law, M. T. How Much More Data Do I Need? Estimating Requirements for Downstream Tasks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 275-284, June 2022a.
Polyak, B. T. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964. Publisher: Elsevier.
Mahmood, R., Lucas, J., Alvarez, J. M., Fidler, S., and Law, M. Optimizing Data Collection for Machine Learning. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances Neural Informa- tion Processing Systems, volume 35, pp. 29915-29928. Curran Associates, Inc., 2022b.
Raychaudhuri, D., Seskar, I., Zussman, G., Korakis, T., Kilper, D., Chen, T., Kolodziejski, J., Sherman, M.. Kostic, Z., Gu, X., Krishnaswamyy H., Maheshwari, S., Skrimponis, P., and Gutterman, C. COSMOS: A city- scale programmable testbed for experimentation with advanced wireless. In Proceedings of the 26th Annual International Conference on Mobile Computing and Net- working, MobiCom '20, New York, NY, USA, 2020. As- sociation for Computing Machinery. ISBN 978-1-4503- 7085-1. doi: 10. 145/33722244338889 event-place: London, United Kingdom.
Mao, J., Griniasty, L., Teoh, H. K., Ramesh, R., Yang, R., Transtrum, M. K., Sethna, P., and Chaudhari, P. The training process of many deep networks plores the same low-dimensional manifold. Proceed- ings of the National Academy of Sciences, 121(12): e23 1030000211, March 2024. ISSN 0027-8424, 1091-6490. doi: 10. 137.1/0as...331 230000212.
Marafioti, A., Zohar, O., Farré, M., Noyan, M., Bakouch, E., Cuenca, P., Zakka, C., Allal, L. B., Lozhkov, A., Tazi, N.. Srivastav, V., Lochner, J., Larcher, H., Morlon, M., Tunstall, L., Werra, L. v., and Wolf, T. SmolVLM: Redefining small and efficient multimodal models, April 2025. arXiv:2504.052 0009999999990 [cs].
Ren, P., Xiao, Y., Chang, X., Huang, P.-Y., Li, Z.,, Gupta, B. B., Chen, X., and Wang, X. A Survey of Deep Ac- tive Learning. ACM Computing Surveys, 54(9):1-40, December 2022. ISSN 0360-0300, 1557-7341. doi: 10.1 14/1449/347
12

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Robbins, H. E. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527-535, 1952.
Wang, Z., Awasthi, P., Dann, C., Sekhari, A., and Gentile, C. Neural Active Learning with Performance Guarantees. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P. S., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp- 7510- 7521. Curran Associates, Inc., 2021.
Sener, O. and Koltun, V. Multi-Task Learning as Multi- Objective Optimization. In Bengio. S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Gar- nett, R. Advances in Neural Information Process- ing Systems, volume 31. Curran Associates, Inc., 2018.
Xu, Q. and Zheng, R. When data acquisition meets data an- alytics: A distributed active learning framework for opti- mal budgeted mobile crowdsensing. In IEEE INFOCOM 2017 IEEE Conference on Computer Communications, pp. 1-9, 2017. doi: 10. 100//N/OOO...200.....0. 2017800
Sener, O. and Savarese, S. Active Learning for Convo- lutional Neural Networks: A Core-Set Approach. In International Conference on Learning Representations, 2018.
Yoo, D. and Kweon, I. S. Learning Loss for Active Learn- ing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Settles, B. Active learning literature survey. 2009. Pub- lisher: University of Wisconsin-Madison Department of Computer Sciences.
Zang, C., Turkcan, M. K., Narasimhan, S., Cao. Y., Yarali, K., Xiang, Z. Szot, S., Ahmad, F., Choksi, S., Bitner, D. P., and others. Surgical Phase Recognition in Inguinal Hernia Sepair-Al-Busse Confirmatory Baseline and Exploration of Competitive Models. Bioengineering, 10 (6):654, 2023. Publisher: MDPI.
Seung, H. S., Opper, M., and Sompolinsky, H. Query by committee. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 287-294, Pitts- burgh Pennsylvania USA, July 1992. ACM. ISBN 978-0- 89791-497-0. doi: 10.11145/30385..34447
Zhang, L., Zhao, P., Zhuang, Z.-H., Yang, T., and Zhou, Z.-H. Stochastic Approximation Approaches to Group Distributionally Robust Optimization. In Oh, A., Nau- mann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Pro- cessing Systems, volume 36, pp. Associates, 2023.
Shamir, O. and Zhang, T. Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th Interna- tional Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp- 71-79, Atlanta, Georgia, USA, June 2013. PMLR. Issue: L.
Curran
Sinha, S., Ebrahimi, S., and Darrell, T. Variational Adver- sarial Active Learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
Slivkins, A. Contextual Bandits with Similarity Information. In Kakade, S. M. and von Luxburg, U. (eds.), Proceed- ings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pp. 679-702, Budapest, Hungary, June 2011, PMLR.
Tejero, J. G., Zinkernagel, M. S., Wolf, S., Sznitman, R., and Márquez-Neila, P. Full or Weak Annotations? An Annotation
Adaptive Strategy for Budget-Constraiie Campaigns. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 11381-1139, June 2023.
Turkcan, M. K., Narasimhan, S., Zang, C., Je, G. H., Yu, B., Ghasemi, M., Ghaderi, J., Zussman, G., and Kostic, Z. Constellation dataset: Benchmarking high-altitude object detection for an urban intersection. arXiv preprint arXiv:2404. 16944, 2024.
13

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
A. Proofs
A.1. Proof of Proposition 4.2
We first restate Assumption 2.4 on the domain 0.
.a....,,7 Or, satisfies Assumption A.1 (Finite Domain). The model parameters generated by Algorithm in all rounds, i.c., 01,..., E| 0' |]] - D for some D 2 O, where == arg ming Ei=1 Mkc (6).
We further state the following lemma (Garrigos & Gower, 2024). Lemma A.2 (Gradient Norm). Let Assumplion 2.3 and Assumption A.I hold. Then for some set of inputs S, we have
2(L2 + =²)
E| (i; [ux(0)1
|8
Now prove Theorem 3.1.
Proof. By the property convex functions,
1kk, (0x) - Pk, (0-) S (Vus, (0t), 00),
where 0* is defined in Assumption A.1 and (x, y) is the inner product between vectors in O Since 0111 = 0
iu, () we have
|0 0-11 = 110, 00 + V1l iu, (0.; 21J. iVik, (0:: 0*).
By rearranging and taking the expectation, we have
(B.. (0.).
| Arrl
0 10] -, Bil10++1 101] + n. Väx, (0c: (11)
Further let No
Then the optimization regret in Equation (11) writes
T Elūn, (0.) Tux, (Ō*)
( =
t=1
2
Σ
E3 [i (0e), 0, 0->1
t=1
17 EE100 - --1
1E11 1
- (0c3 (03)))
2
(m n-1) + 2(L + 03) nt
where the inequality is result of Assumption A.I and Lemma A.2 with S 2 1. Setting m 1/(2LVT) for fort 2 1 and recalling that ΣT 1/v2 < 2/T, we have
2 (Ar) -
This concludes the proof.
A.2. Proof of Lemma 4.3 and Lemma 4.4
For Lemma 4.3, we construct the martingale as follows.
14

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Proof. For each X; E&S S 23 and some k; let
Z: == E(O,, X;) (0.), i= 1......, |Sk)
is easy to verify that the sequence {Z = 1,.... |Sk } martingale difference sequence, i.e.,
A [( X,) Pi (6:)
Applying the Azuma's inequality on {Z, i 15..1,||11|] gives the statement of the lemma.
To prove Lemma 4.4, simply note that any confidence radius rs(() round is adapted to the algorithm decisions Ar and apply Lemma 4.3.
Proof. We start by writing
(x))) = 13" (0:) (ax(
= =(xx(Or;S) - (0))) - (a' (()( + (a(O:))
For the term (0;;; ju (6:), denote
5z = Pr [inn(Or:)) -ix(00) 2 A..]
Taking its expectation conditioned on A, and S, we have
():; - Eljx (1-6))ra( + Co. rr((S) C8..
And similarly for (0;; (0t).
pr (6.;
- - - C5.-
Plugging back into the first equation in the proof gives the result of the lemma, where the value of d, can be obtained by applying the definition of the confidence radius in Equations (7) and (17) to Lemma 4.3, which are of order (t
A.3. Proof of Proposition 4.5
First we prove the bandit regret for Eps-OGD, which is adapted from the proof of the e-Greedy algorithm for stochastic bandits (Auer et al., 2002).
Proof. Since greedy step picks k to be arg max, (1=(61 we have Pux, (0.1 ji (0, This implies that we observe ÅR, (0.]
with probability 1 - Otherwise, an e-exploration step picks k, U((1..... (((1....,)) K}) and Dc, (0, 1 S C' (Assumption 2.3). More formally, when t = 1, we set & = 1 and the data source is selected randomly with E A (0:)] < C. For > 1, we can write
EI (0,; Nz-; S Ce
According to Lemma 4.4, we have
E Ar. (.. <ra(d-1) +r (0; + 2C8,
Combining the two equations gives
B|A,, (0.][A)) S rr(((-1) +r 208, + Cen.
For the Eps-OGD algorithm, the confidence radius defined in Equation (17) writes
aKInt
a Int
(&G == -C
CV
1 1.
2/
2M(1 - 1)e,
15

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
R18, L.k Then the concentration probability given by Lemma 4.3 is d, = =t 3r(--1)s Assume that é, decreases monotonically with Then 1 2 (t 1)er/ K for all k, yielding E[6,] S t Thus,
aK Int 2M 1)) + 2Ct + Bc.
[1 & 2C,
This is minimized by taking = aak lnt((2M2 - 1))/2 2 as in Equation (5), which gives
aK Inl 2C
B|A,, (0.) - (2v2+
2M 1)
To compute the total expected regret, we first bound the following summation
Σ Int S VIT
1=2
VnT
x do
3
In
2
For any a 2 1/2, we have Σ &c < 2.T. Thus, we can write
T
3(2/2 + 1)C
aKTT
[[R)(Ar)] = C Σ
E El (0.) sC+
+ 40VT.
2
2M
1=2
This concludes the proof.
Now prove the bandit regret of UCB-OGD.
Proof. Since UCB selection picks k; to be arg max; (0.1/ + (x(
we have
A +r (1.) + rx. (&),),
or, equivalently,
År. 1 - -
Combining with Lemma 4.4, we have
E AA (0,))A,,,,.. < 2rk, (X, + 208,-
Recall the definition of confidence radius rx (A in Equation (7), with o, tt given by Lemma 4.3. Further let (t)
denote the number of times a data source & is selected up to time L. We can write (R = Mnx(() for any k, L. Then the equation above can written as
a Int
E E (0.) < 2C
+ +C6,
2M
nx 1)
Let Ar, = [(k, E Ar: : k k). We assume that the algorithm iterates over every data source during the first K
16

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
rounds for initial warm-up. Then, the regret incurred by some arm k can be written
([R,(AA,))]
Σ
B (k+
k} A.. (0.)]
T
SC+
Σ
E (k+ = Ax, (0))
t=k+1
a Ini E
1 tki = k}
SC+
Σ
20
200
2M
[V - 1)
t=K+1
T
fk+ = k7
T
cC+CV
E
+ 2CE
Σ
6,1
{kr
k}
M
/x 1)
t= K+1
L K+1
Notice that between any consecutive rounds - and (t()) is increased by if and only ha ls (i.e., the data source is selected and new samples are added), or the numerator is zero otherwise, hence,
Σ k=
T
1 1ike =
1
0
0
1
0
1R(1-1)
V2
V2
0
1
+
Vnn (T - 2)
Vnn (T - 1).
(T-)
Σ
Vn
< 2 22 n4 1T 1)
Then expected regret can be written as
K [[Ro(Ar)] = Σ (TT,A))
1=1
2a T
K
< KC 2
E
V nT -1
2CE
8.1 fkk =b}
M
LKmi
i=1
2x In
K (T 1) k=1
T
$ KC + V
K
+ 2CE
Σ
M
where the last line follows from the inequality between arithmetic mean and quadratic mean, and the fact that
ΣK 1 (he kt) = 1 for all f. Further recall that Σk k= nx(() = t. Then, for any 1/2, we have
2aKThT 4CVT.
$ S KC 2CC
M
This concludes the proof.
A.4. Mean Convergence
For the Rand-OGD algorithm, since it enforces that the data sources are queried in balanced way, the algorithm reduces standard stochastic gradient descent for minimizing the average loss over the data sources, i.e., ΣK (0) K. We have the following result.
Theorem A.3. Let p J.K be convex in 0. The Rand-OGD algorithm satisfies
K
K
1
E
Pa (
min
Σ (0)
(22)
K
K
1=
k=1
17

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Proof. Denote pi(0== Ex=1 (4 ( the definition of the optimization regret (Equation (11)) and the generalization regret (Equation (13), defined on single source p).,
K. Since & -U( K}), it holds for any fixed 0 that El (0) ii)). By
T
Σ ((0)) T min (0)
=
E
E El (0:) - min a())
T
T
Bluu, - mmin Σ
B Blu (0)
1=1
E (8)) Pkc (0:)
Σ
Blisk: (6:)]
min Σ
E Bla (0)
t=1
((R)(Ar) + Ro(Ar:)
where the inequality follows from Equation (10). By the convexity of μt and Jensen's inequality, we have m(OAz) <
Et= p(O.)/T. Recalling the upper bound of optimization regret in Proposition 4.2 and the generalization regret in
Equation (21) concludes the proof.
A.5. Proof of Pareto-Stationarity
Theorem A.4 (Pareto Staionarity). Let A be time-smoothed OGD-based algorithm. Then for some U((L.... ..... T7), 0. (asymptotically) Pareto-stationary for pa,-... MK T,
Proof. In this proof, we adopt the time-smoothed OGD framework (Hazan al., 2017). The time-smoothed gradient round w.r.t some window E ['] is defined
1e (0)
V 7kk_((0p) (0.).
W
All Hi, where / < 0 are set to 0 for uniformity. The w-local regret is defined as
T
R (AT)
=
V pg (0.)1l²
proper time-smoothed OGD algorithm Ar incurs w-local regret order O(T/w²) (Hazan et al., 2017; Hallak et al., 2021). Further, the relationship between individual Viy (9t) and the local regret can be given by
F. [0)] < E[RT (Ar) 0(1/w²).
E.JU(L,....T)
Let n (t) : Em' 1 (ke- = 1} the number times an arm & selected from round w + 1 to round t. Then we can rewrite
K
2 (0.) =
(0.)
It follows that
(1)
E TH)
V pkk (O:)
0(1/u²).
Note that 0, is called Pareto siteto-statioary (Sener & Koltun, 2018) if there exists a1 ........ OK IR s.t.
K
K
(0) = 0, where Σ
az - az 2 0.
Indeed, this the case for our problem by setting as = no (t) wn and taking the limit for both and w.
18

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
A.6. Proof of Proposition 3.3
Proof. Consider problem with K data source. Thus the problem reduces standard single-objective stochastic optimization problem. Denote the objective function as p(0). Then for any saaseett-based algorithm A after T rounds, have
R(AT) - Σ ((,) T min (00)
(23)
2T T (1(0,)) min m(
where recall Jensen's inequality. Note that p(0 ming p(0) the optimality gap of algorithm A. Let p(0) be T-LLipshitz (Assumption 2.3) but non-smooth (e.g. a DNN with ReLU activations). The optimality gap of gradient methods in general is lower bounded by O (Shamir & Zhang, 2013). Thus the minimax regret is at least of order O(T O
19

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
B. Implementation Details
B.1. The COSMOS Testbed
The COSMOS (Cloud-enhanced Open Software-defined MObile wireless testbed for city-Scale deployment) testbed (Raychaudhuri et al., 2020), part of the NSF PAWR program, being deployed in West Harlem in New York City. supports research ultra-high bandwidth and ultra-low latency wireless technologies in real-world urban environments. The testhed features programmable infrastructure across multiple layers, including software-defined radios, 28 GHz mm Wave modules, optical transport, edge/core cloud components, and comprehensive control software. Its phased urban deployment enables diverse experimental research and serves valuable educational platform.
Source
Annotation Budget
Data Source
Camera
Figure 3. Camera setup of intersection in the COSMOS Testbed.
The testbed includes multiple cameras deployed the exterior of a multi- building, illustrated in Figure 3. Each of the cameras provides a distinct viewpoint of the traffic flow, three of which were used as separate data sources for data collection in this paper. These strategically positioned cameras enable comprehensive coverage for urban object detection, facilitating cross-view analysis of vehicles, pedestrians, and street activity.
B.2. Data Collection Schedule
CIFAR10: We execute our algorithms for 20,000 rounds and collect a batch of 32 samples every 60 rounds until reaching the budget.
PASCAL VOC2012:
We execute our algorithms by pretraining for 10,000 rounds (freezing the backbone), collecting batch of 8 samples every 50 rounds. Then we finetune for 20,000 rounds, collecting batch of samples 100 rounds until reaching the budget.
We execute our algorithms by pretraining for 10,000 rounds (freezing the backbone), collecting batch of 8 samples every 50 rounds. Then we finetune for 20,000 rounds, collecting batch of samples 200 rounds until reaching the budget.
Testbed:
B.3. Data Processing for VOC2012
We partition the images in PASCAL VOC2012 data set into the following data sources based on their concurrence within the same image:
Indoor: cat, dog, TV monitor, sofa, bottle, potted plant, chair, and dining table.
Transport: aeroplane, train, boat, motorbike, bicycle, car, and bus.
20

---

Adaptive Data Collection for Robust Learning Across Multiple Distributions
Wildlife: bird, horse, cow, and sheep.
Human: person only.
An image is partitioned to the human data souree only if no other classes appear. If objects of multiple sources appear in the same image, then the upper one in the list above takes priority (e.g. if an image contains both a sofa and a bird, then is partitioned the indoor data source).
Further, for every data source, a class is removed from mAP calculation if has less than 20 objects in all the images from that source in the validation set.
C. Generalization Results
We inspect the generalization ability of the proposed data collection framework by training other models using classical training loops on the data collected by uniform allocation strategy and the UCB-OGD strategy. The chosen model is SSD300 for the PASCAL VOC2012 dataset and YOLOv8 for the testbed dataset.
Table 2. Comparisons of the performance of models trained the data collected different strategies.
DATA SOURCE (BUDGET)
MIN Acc
MEAN Acc
MODEL.
ALLOCATION
Voc2012 (3K)
UNIFORM
35.0
51.7
SSD300
UCB
36.2
52.2
TESTBED (2K5)
UNIFORM
62.2
72.5
YOLOV8
UCB
63.7
72.9
21


Reviews:
[{"review_id": "1JWy9zdZpi", "reviewer": "Reviewer_7Pps", "summary": "This paper presents a new online framework (UCB-OGD) for data collection and model training in a multi-distributional setting with a constraint on sample labeling. In particular, the purpose UCB-OGD is shown to achieve a sublinear minimax regret with a lower-bound showing algorithmic completion, guaranteeing performance in comparison with traditional active learning methods. Additionally, the paper also presents a well-designed experimental setup to validate the UCB-OGD's effectiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 7Pps,\n\nThank you for your feedback.\n\nWe have provided additional experimental results in an *[anonymous Github](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F)*. There are three active learning curves (model performance *v.s.* number of annotated samples) for three different tasks.\n\n**Vision-Language Modeling:** We finetune a SmolVLM-256M-Base model [1] on a subset of VQAv2 dataset [2] for visual question answering using Rand-OGD and UCB-OGD, respectively. We partition the dataset into three data sources based on the type of the questions (i.e. yes/no questions, numerical questions, and descriptive questions). The active learning curve of per-token accuracy *v.s.* the number of training samples is illustrated in *[Figure 5](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig5-alcurve-vqav2.pdf)*. Although the time frame is very limited for experiments on a larger scale, we believe the results are able to demonstrate that our proposed framework can be applied to complex tasks like VLM where the training data incorporates various modalities. We will add more detailed experiments in the final version should the paper be accepted.\n\n**Classification and Object Detection:** For the experiments on CIFAR10 and VOC2012 in the paper (*Section 5*), we summarize the performances of the proposed algorithms compared to several active learning baselines in *[Figure 3](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig3-alcurve-cifar10.pdf)* and *[Figure 4](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig4-alcurve-voc2012.pdf)*, respectively. The main takeaway we want to emphasize is that, while active learning algorithms can be *task-specific* and are *not necessarily* robust learners, our proposed framework is flexible to apply to a wide range of different tasks and is able to behave robustly. The flexibility is due to the fact that the proposed algorithm solely relies on the losses when making sampling decisions.\n\nWe appreciate your insights and welcome any further questions or feedback. We will be continuously seeking to add further experiments in support of our theoretical claims.\n\n**References:**\n[1] Marafioti et al., \"SmolVLM: Redefining small and efficient multimodal models\". 2025.\n[2] Antol et al., \"VQA: Visual Question Answering\". ICCV 2015.", "claims_and_evidence": "The paper claims theoretical guarantees of their UCB-OGD alongside claims of empirical improvements in a multi-distributional setting with a budget on sample labeling. In this regard, the reviewer found the evidence convincing with both theoretical analysis under traditional bandits and online optimization. Additionally, the experimental evaluations are intuitive and, from the reviewer's perspective, fair.", "methods_and_evaluation_criteria": "The reviewer found the proposed UCB-OGD method to be an intuitive method for addressing the raised active learning problems. Subsequently, the experimental setup is well-designed and the comparative methods chosen are also largely appropriate and fair.", "theoretical_claims": "The authors provide extensive theoretical analysis that show their proposed UCB-OGD algorithm achieves a sublinear minimax. The paper also provides a lower-bound showing no algorithm can do asymptotically better which matches the known multi-armed bandits theory. The author also clearly state their theoretical assumptions (i.i.d sampling, loss convexity in the model parameters, and bounded loss with Lipschitz continuity). To the reviewer's knowledge the theoretical proofs and claims are compelling with no visible incorrections.", "experimental_designs_or_analyses": "The authors evaluate UCB-OGD using a well-designed proposed setting with three distinct tasks. However, the reviewer would like to see more high resolution datasets in particular for the Classification tasks.", "relation_to_broader_scientific_literature": "Algorithmically, UCB-OGD is built on existing algorithms and do not provide too many novel ideas to the broader field. However, the reviewer does find the proposed framework on data collection, bridging ideas from active learning, multi-armed bandits, and online optimization, to be novel and potentially very helpful for the broader active learning field.", "essential_references_not_discussed": "The reviewer is unaware of any necessary references which are omitted.", "other_strengths_and_weaknesses": "See sections above.", "other_comments_or_suggestions": "Minor typos of note:\n- line 373 \"Detailed of data source assignment is given in Appendix B\" -> \"Additional details of data source assignment are given in Appendix B\"", "questions_for_authors": "See the \"experimental designs Or analyses\" section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iGneQiSUhN", "reviewer": "Reviewer_y1y9", "summary": "This paper proposes a framework for adaptive data collection and model training considering the multiple data distributions with the fixed annotation budget, where the goal is to come up with an optimized model that can perform well on all distributions. Through the integration of the upper-confidence bound (UCB) for effective sample collection and online gradient descent  (OCG) for the model optimization, the paper proposes a theoretically guaranteed approach called UCB-OGD that shows superior performance on benchmarks compared to existing active learning and random sampling strategies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer y1y9,\n\nThank you for your detailed feedback. We have provided additional experimental results in an *[anonymous Github](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F)* and further clarified the results and our contributions below.\n\n**Additional Active Learning (AL) Baselines (weakness 1,3,4):** We add the results of BADGE algorithm (suggested reference [1]) and entropy-based sampling (*Munjal et al., 2022*) on the CIFAR10 dataset, summarized with other algorithms using an AL curve in *[Figure 3](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig3-alcurve-cifar10.pdf)* as suggested by the reviewer. In terms of our main metric, the minimum class-wise accuracies are 39.5 for BADGE and 53.0 for entropy-based sampling. The latter is comparable to the results of 52.7 by DBAL and 52.3 by UCB-OGD. We also provide the AL curve on the VOC2012 dataset in *[Figure 4](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig4-alcurve-voc2012.pdf)*, which shows superior performance of our algorithm compared to MDN (*Choi et al., 2021*), a SOTA AL baseline. The BatchBALD algorithm (suggested reference [2]) is not tested for now due to its significant computation overhead given the limited time frame. We will also make sure to add the suggested references to the related work of our paper. The main takeaway of these comparisons (also *Table 1* and *Figure 2* of the paper) we want to emphasize is that:\n- AL algorithms are *not necessarily* robust learners. They can be sensitive to initializations, especially for complex tasks like object detection (*Figure 2* of the paper and new *[Figure 4](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig4-alcurve-voc2012.pdf)*).\n- On the other hand, our proposed framework can achieve *similar or superior* performance compared to AL baselines for both classification and detection. Meanwhile, the framework is flexible to apply to a wide range of different tasks, since the proposed algorithm solely relies on the losses when making sampling decisions.\n\n**Advanced Sampling Strategies (weakness 1):** While the proposed algorithm can potentially benefit from employing more advanced sampling strategies, provable theoretical guarantees of a general adaptive data collection framework that can incorporate DL models remains elusive even under the simple setup that we discussed in the paper (where the algorithm only selects and optimizes one data source with the highest plausible loss in each round). The outline of the proposed algorithms and the implementations have been set up to resemble the theoretical claims as much as possible, at the price of having more basic algorithmic components (e.g. a simpler sampling scheme). Nonetheless, the experiments already demonstrate the capability of our proposed framework under these basic setups.\n\n**VLM Experiments (weakness 5):** We finetune a SmolVLM-256M-Base [1] model on a subset of VQAv2 [2] dataset and provide the AL curve of per-token accuracy v.s. the number of training samples in *[Figure 5](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig5-alcurve-vqav2.pdf)*. We kindly refer to our response to reviewer 7Pps for further details on the experimental setup. Although the time frame is very limited for experiments on a larger scale, we believe the results are able to demonstrate that our proposed framework can be applied to complex tasks like VLM where the training data incorporates various modalities. We will add more detailed experiments in the final version should the paper be accepted.\n\n**Our Novelty and Contributions (weakness 2):** While OGD and UCB are both established algorithms, we believe the combination of these techniques for the studied problem is novel. We want to emphasize that UCB has been proposed for *stationary stochastic bandits*, while our problem is a *non-stationary contextual bandit* where vanilla UCB is not applicable (details in *Section 4*). In this paper, we prove that, by maintaining an adaptively collected dataset and leveraging its information, UCB (and other stationary bandit algorithms like $\\epsilon$-Greedy) can be combined with online optimization algorithms such as OGD to provide *provable minimax regret bounds* despite the non-stationary nature of our problem. We further note that the proposed framework can be easily extended to various bandit and optimization algorithms for different problems at hand. We believe that our paper shows that adaptive data collection with robust theoretical guarantees can be a promising approach applicable to a wide range of tasks.\n\nWe appreciate your suggestions and insights, and hope that the updates above could address your concerns. We welcome any further questions or feedback.\n\n**References:**\n[1] Marafioti et al., “SmolVLM: Redefining small and efficient multimodal models”. 2025.\n[2] Antol et al., \"VQA: Visual Question Answering\". ICCV 2015.", "claims_and_evidence": "1. This paper lacks key baselines in the active learning domain [1,2]. The authors should compare their approach with these baselines in the evaluation. If a direct comparison is not feasible, they should at least discuss these methods in the related works section. Additionally, the authors should explore a sampling strategy based on evidential learning uncertainty and report the performance improvements achieved over this approach [3]. To facilitate comparison, they could consider a pool consisting of samples from all data sources and select samples with the highest uncertainty based on evidential learning uncertainty from that pool.\n2. The pure entropy-based sampling strategy is not included in the comparison. The authors should include its performance in Table 1. To select samples, they may consider using a single pool of samples from all the data sources under consideration.\n3. The evaluation is limited to computer vision tasks. To increase the impact of this work, the authors should consider natural language tasks (e.g., from the VLM space [4]) and demonstrate how the proposed technique reduces the number of samples from each data source while maintaining comparable performance to using all samples from all data sources.\n\n\n**References** \n1. Ash et al. “Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds”. ICLR2020\n2. Kirsch et al. “BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning”. NeurIPS2019\n3.  Sensoy et al “Evidential Deep Learning to Quantify Classification Uncertainty”. NIPS2018\n4. Liu et al. “Visual Instruction Tuning”. NeurIPS2023.", "methods_and_evaluation_criteria": "**Proposed Methodology**: Although the authors provide a detailed theoretical proof for the proposed technique, its novelty is limited. Upper-confidence bound (UCB) and online gradient descent (OGD) are well-established concepts in machine learning, and this paper primarily adapts these techniques for active learning. Specifically, it employs UCB-based uncertainty to guide data source selection.\n**Evaluation Criteria**: Strength: This paper has considered multiple computer vision tasks including classification and object detection with multiple datasets.  Weakness: To enhance the impact of this work, authors consider the natural language tasks (e.g., from VLM space [4]) and showcase how this technique helps to reduce the number of samples from each data source with the comparable performance as that of the one considering all sample from all data sources.", "theoretical_claims": "I have checked the correctness of the theoretical claims  made in the main paper as well as corresponding proofs in the supplementary materials. I don't see any issue in the theoretical claims.", "experimental_designs_or_analyses": "Yes, I have reviewed the experimental designs and analysis in the main paper (Experimental Results section). The dataset design and analysis appear valid. However, my concerns are as follows: (a) the paper lacks important active learning baselines, (b) the evaluation is limited to computer vision tasks, (c) entropy-based sample selection results are missing from the table, and (d) the active learning (AL) curve is absent. Including an AL curve, with performance (accuracy) on the y-axis and the number of training samples on the x-axis, would provide a clearer comparison of different baselines, including the proposed method, and better illustrate its effectiveness.", "relation_to_broader_scientific_literature": "In the field of active learning, selecting informative samples within a fixed annotation budget is crucial, especially in critical domains like healthcare and road traffic. Unlike prior work, this paper introduces a novel upper-confidence bound (UCB)-based approach for selecting data distributions to enable effective sampling within the given budget. Additionally, the paper provides extensive theoretical analysis to demonstrate how the proposed technique outperforms existing methods. Furthermore, in addition to standard benchmarks, the paper evaluates the approach on a real-world urban intersection dataset, which could serve as an important testbed for future active learning techniques.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "I have reiterated Strengths and Weaknesses as follow: \n\n**Strengths**:\n1. This paper presents a comprehensive theoretical proof demonstrating the effectiveness of the proposed technique in achieving strong performance across K data sources with effective minimax regret across these sources.\n2. The experiments are conducted across multiple tasks, including classification and object detection.\n3. Demonstrates the effectiveness of the proposed technique by evaluating its performance on real-world vehicle detection at urban intersections.\n\n**Weaknesses**:\n1. This paper lacks key baselines in the active learning domain [1,2]. The authors should compare their approach with these baselines in the evaluation. If a direct comparison is not feasible, they should at least discuss these methods in the related works section. Additionally, the authors should explore a sampling strategy based on evidential learning uncertainty and report the performance improvements achieved over this approach [3]. To facilitate comparison, they could consider a pool consisting of samples from all data sources and select samples with the highest uncertainty based on evidential learning uncertainty from that pool. \n2. Although the authors provide a detailed theoretical proof for the proposed technique, its novelty is limited. Upper-confidence bound (UCB) and online gradient descent (OGD) are well-established concepts in machine learning, and this paper primarily adapts these techniques for active learning. Specifically, it employs UCB-based uncertainty to guide data source selection.\n3. The pure entropy-based sampling strategy is not included in the comparison. The authors should include its performance in Table 1. To select samples, they may consider using a single pool of samples from all the data sources under consideration.\n4. The authors should consider providing an active learning (AL) curve, with the y-axis representing performance (accuracy) and the x-axis showing the number of samples used during training. Comparing different baselines, including their proposed method, would provide a clearer understanding of the technique's effectiveness.\n5. The evaluation is limited to computer vision tasks. To increase the impact of this work, the authors should consider natural language tasks (e.g., from the VLM space [4]) and demonstrate how the proposed technique reduces the number of samples from each data source while maintaining comparable performance to using all samples from all data sources.\n\n**References**\n1. Ash et al. “Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds”. ICLR2020\n2. Kirsch et al. “BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning”. NeurIPS2019\n 3. Sensoy et al “Evidential Deep Learning to Quantify Classification Uncertainty”. NIPS2018\n4. Liu et al. “Visual Instruction Tuning”. NeurIPS2023.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please refer to Other Strengths and Weaknesses section", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GLNUdtp2Vx", "reviewer": "Reviewer_p2BW", "summary": "This paper proposes a framework for adaptive data collection aimed at robust learning in multi-distribution scenarios under a fixed data collection budget. The proposed algorithm dynamically selects a data source for sampling in each round, updates the model parameters using gradient descent, and repeats the process to minimize the expected loss across all data sources. \n\nWhile the paper addresses an interesting problem and provides theoretical guarantees, the lack of significant technical contribution, unclear motivations, and questionable performance metric design weaken its overall impact. The authors should provide stronger justification for their approach, clarify the baseline comparisons, and consider tailoring their algorithm to better address the specific challenges of adaptive data collection in multi-distribution scenarios.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer p2BW,\n\nThank you for your questions. We would like to further clarify the intuitions of the problem and our contributions.\n\n**Necessity of Adaptive Data Collection (Q1):** In our motivating example of vehicle detection in a smart city intersection (*Section 1*), DL models such as SSD and YOLO require a large amount of annotated data for training. However, annotation for complex tasks such as object detection can be quite expensive, and is often subject to budget or resource constraints in a real-world application like ours. Therefore, it is essential to understand how the limited data budget can be utilized *efficiently* to maximize the performance. This is also the core idea of active learning (AL), which we also add as baselines for experimental comparisons. The improvement of the proposed algorithms (Eps-OGD and UCB-OGD) over static (or uniform) sample selection (Rand-OGD) is two-fold:\n- *Data Efficiency:* Models trained on adaptively collected data are able to achieve better performance using the same amount of annotated samples. This is shown in Table 1 and illustrated by the additional results we provided in an *[anonymous Github](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F)*. We kindly refer to our response to reviewer 7Pps for further descriptions of these results.\n- *Robustness:* Adaptive data collection is especially suited for distributionally robust learning (minimax objective). In terms of our main metric, the minimum class-wise accuracies for classification and the minimum mAP of each data source for detection, the advantage of the proposed algorithms (and other AL baseline) is significant over Rand-OGD which uses uniform sampling.\n\n**Motivation of Minimax Objective (Q2):** One of the main reasons we consider the minimax objective is that many real-world applications (including our smart intersection example) is *safety-critical*, i.e. we are more concerned with the *worst-case* detection performance among all cameras instead of their average performance. This is essential because the quality of the data and the model accuracy can be largely affected by the specific camera hardware or its geometric location. This motivates our choice of a *minimax objective*, which is standard in robust learning literature. In this context, it is natural to minimize the worst-case loss among all data sources, i.e. $\\min_\\theta\\max_k\\mu_k(\\theta)$, rather than focusing on the mean loss. In fact, as we show in *Theorem A.4*, algorithms that uniformly collect samples from all data sources (such as Rand-OGD) eventually converge to the optimum of the *mean objective*, i.e. $\\min_\\theta\\frac{1}{K}\\sum_{k=1}^K\\mu_k(\\theta)$, under the same assumptions stated in the paper. We also note that many active learning baselines are also more focused on the mean objective rather than the minimax objective studied by our problem. We believe our proposed framework can fill this important gap of building robust real-world applications under a limited data budget.\n\n**Accounting for Distributional Heterogeneity (Q3):** It is indeed the case that a uniform sampling scheme overlooks the heterogeneous nature of the loss distributions of different data sources, which is why Rand-OGD is only suited for the mean objective. On the other hand, the proposed algorithms like UCB-OGD and Eps-OGD incorporate bandit sampling, which learns the importance of different data distributions from the collected samples in the training set. This provides powerful information about which data source is suffering from worse performance and guides the algorithm to obtain more training samples from it. In this way, algorithms like UCB-OGD and Eps-OGD are able to behave *robustly* and eventually converge to the optimum of the minimax objective (*Theorem 3.1*).\n\n**Our Novelty and Contributions (Q4):** While OGD and UCB are both established algorithms, we believe the combination of these techniques for the studied problem is novel. We want to emphasize that UCB has been proposed for *stationary stochastic bandits*, while our problem is a *non-stationary contextual bandit* where vanilla UCB is not applicable (details in Section 4). In this paper, we prove that, by maintaining an adaptively collected dataset and leveraging its information, UCB (and other stationary bandit algorithms like $\\epsilon$-Greedy) can be combined with online optimization algorithms such as OGD to provide *provable minimax regret bounds* despite the non-stationary nature of our problem. We further note that the proposed framework can be easily extended to various bandit and optimization algorithms for different problems at hand. We believe that our paper shows that adaptive data collection with robust theoretical guarantees can be a promising approach applicable to a wide range of tasks.\n\nWe appreciate your insights and hope that the answers above could address your concerns. We welcome any further questions or feedback.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "The paper tackles an important and practical problem—adaptive data collection for robust learning across multiple distributions. This topic is relevant to applications in domains where data is collected from diverse sources with limited budgets.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\nThis paper tackles an interesting problem and provides theoretical guarantees.\n\nWeaknesses:\n- The proposed method appears to be a direct application of existing approaches—minimizing the maximum loss via UCB sampling combined with OGD. This makes the novelty and technical contribution of the paper seem limited, as no significant algorithmic innovation or optimization is introduced.\n\n- The paper does not clearly articulate why adaptive data collection is necessary or advantageous in this specific context. The problem studied seems to deviate from the original objective of minimizing the expected loss across multiple distributions.\n\n- The algorithm relies on standard stochastic gradient descent without any specific optimization tailored to the adaptive data collection problem in multi-distribution scenarios. This further limits the novelty of the proposed approach.", "other_comments_or_suggestions": "See my questions.", "questions_for_authors": "1. What is the motivation for considering adaptive data collection in this specific setting? How does this approach improve over simpler methods that do not rely on dynamic sample selection?\n\n2. The regret is defined based on the $T\\min_\\theta \\max_k \\mu_k(\\theta)$. However, if we do not employ dynamic sample selection. The baseline should be $T\\min_\\theta \\frac{1}{K}\\sum_k \\mu_k(\\theta)$. It seems that comparing with this baseline can better prove the advantage of your adaptive data allocation.\n\n3. Uniform sampling from all distributions seems to overlook their varying importance. How does the method take into account the relative significance of different distributions in the overall objective function?\n\n4. The algorithm appears to be a straightforward integration of UCB and OGD. Are there any specific innovations or adaptations made to optimize the method for robust learning across multiple distributions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p0yq21GDDO", "reviewer": "Reviewer_WqSu", "summary": "This paper considers a multi-round decentralized training method with a limited annotation budget to label data from multiple distributions from various locations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer WqSu,\n\nThank you for your questions. We would like to further clarify the problem and our contributions.\n\n**Problem Definition and Connection to Decentralized Data Collection:** The adaptive data collection problem is indeed related to many topics in active learning (AL), including the suggested line of work on decentralized data collection. Particularly, the theoretical guarantees of decentralized data collection are often achieved by leveraging *predefined* data quality metrics, such as information functions [1], submodular functions [2,4], or a target data distribution [3]. Many centralized AL algorithms (e.g. uncertainty- or entropy-based sampling) share similar intuitions by selecting the most relevant data to annotate using such metrics, which we compare as baselines in *Section 5*. However, the robustness of real-world applications are often measured in terms of their worst-case performances rather than the quality of the data itself. Therefore, it is more common in robust learning to directly minimize the worst-case loss, which is the *minimax objective* employed by our paper. We further discuss the advantages of the proposed framework in the following paragraph. We will also make sure to add the suggested references to the related work of our paper.\n\n**Advantage of The Proposed Framework (question 1):** One of the major advantages of the proposed framework is its high flexibility to apply to a wide range of different tasks without relying on predefined data quality metrics (as in decentralized data collection). This is especially useful in data-scarce scenarios where a target dataset is absent, or in complex tasks (e.g. object detection or VLM training) where the data quality function is hard to define. Although numerous AL algorithms exist for specific tasks such as classification and detection, to the best of our knowledge, there isn't a general framework of adaptive data collection with *provable minimax regret bounds* that incorporates DL models. In fact, we demonstrated in the experiments (*Section 5*) that the same algorithmic framework of UCB-OGD can be utilized to train robust DL models for classification, object detection, and vision-language modeling (VLM) for which we have provided experimental result in *[Figure 5](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig5-alcurve-vqav2.pdf)*. We kindly refer to our response to reviewer 7Pps for further descriptions of these results. Therefore, although UCB-OGD shows lower mean accuracy than AL on the CIFAR10 dataset, it achieves similar minimum accuracy (which is our main performance metric), while also yielding superior performances in object detection and VLM tasks (*Table 1* and new *[Figure 4](https://anonymous.4open.science/r/icml2025-adaptive4robust-CB0F/fig4-alcurve-voc2012.pdf)*).\n\n***I.I.D.* Assumption (weakness 1, question 2):** In *Assumption 2.6*, independence is only assumed *within* each data source, i.e. we assume that the images collected from a single camera are *i.i.d.*, while no assumptions are made with respect to the relationships between the data distributions of different cameras. This is the standard assumption of bandit problems, where the per-arm rewards are required to be *i.i.d.*, but different reward distributions can be arbitrary. In the smart city intersection example, *Assumption 2.6* states that the images from different cameras can be correlated *spatially* (when the locations are close) but not *temporally*. This is the case for the testbed dataset, since the images are sporadically collected during an extended period of time with minimal temporal dependence. We also note that the data sources defined in the VOC2012 experiment indeed admit correlations due to overlapping object classes (details in *Section 5*).\n\n**Our Novelty and Contributions (weakness 2):** While OGD and UCB are both established algorithms, we believe the combination of these techniques for the studied problem is novel. We want to emphasize that UCB has been proposed for *stationary stochastic bandits*, while our problem is a *non-stationary contextual bandit* where vanilla UCB is not applicable (details in *Section 4*). In this paper, we prove that, by maintaining an adaptively collected dataset and leveraging its information, UCB (and other stationary bandit algorithms like $\\epsilon$-Greedy) can be combined with online optimization algorithms such as OGD to provide *provable minimax regret bounds* despite the non-stationary nature of our problem. We further note that the proposed framework can be incorporated with various bandit and optimization algorithms tailored to different problems at hand. We believe that our paper shows that adaptive data collection with robust theoretical guarantees can be a promising approach applicable to a wide range of tasks.\n\nWe appreciate your suggestions and hope that the answers above could address your concerns. We welcome any further questions or feedback.", "claims_and_evidence": "Yes, the claims have theoretical proofs besides empirical experiments.", "methods_and_evaluation_criteria": "Yes, the paper shows results in multiple domains, such as classification tasks.", "theoretical_claims": "The paper mainly leverages existing results from bandit algorithms.", "experimental_designs_or_analyses": "Yes, I checked all the results and raised my question in the \"questions\" section.", "relation_to_broader_scientific_literature": "This paper is an add-on to existing bandit and decentralized data collection problems.", "essential_references_not_discussed": "In other application domains, there's a thread on decentralized data collection with theoretical guarantees compared to the optimality gap. Some use optimization-based methods, and some use submodular methods, which have pretty straight-forward proofs on the optimality gap. Please compare them in the paper and add them as baselines.\n\n\n[1] When data acquisition meets data analytics: A distributed active learning framework for optimal budgeted mobile crowdsensing. Qiang Xu; Rong Zheng, INFOCOM 2017\n[2] Decentralized Data Collection for Robotic Fleet Learning: A Game-Theoretic Approach. Oguzhan Akcin, Po-han Li, Shubhankar Agarwal, Sandeep P. Chinchali, CoRL 2022\n[3] Fleet Active Learning: A Submodular Maximization Approach. Oguzhan Akcin, Orhan Unuvar, Onat Ure, Sandeep P. Chinchali, CoRL 2023\n[4] Distributed Submodular Maximization. Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, Andreas Krause. JMLR 2016", "other_strengths_and_weaknesses": "# Strengths\n1. The proposed method can be combined with other existing bandit algorithms.\n2. The paper clearly stated the assumptions and the claims.\n\n# Weaknesses\n1. The IID assumption (Assumption 2.6) is not so realistic since in the real world, the data distributions are correlated if the locations are close enough (following the example in the intro). Please justify.\n2. The paper mainly leverages existing results on bandits to their data collection problem.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. In Table. 1, UCB-OGD is not actually on par with DBAL since the MEAN ACC of DBAL is much better. Then, what is the point of proposing UCB-OGD? Maybe try them on a more complicated dataset (ImageNet) to demonstrate their capability.\n2. The definition of data sources is strongly related to the core definition of a task. In the TestBed experiment, the cameras are correlated in some ways we do not even know and the algorithms still work. It thus adds complexity to the setting and worth investigating. Can you do the same with the other two experiments such that the objects appear in the data sources are correlated, and conduct performance analysis on them? Also, it may reflect the assumptions made earlier.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers generally found the contribution setting meaningful and the theoretical results well supported. In the rebuttal stage, the reviewers requested adding more baselines, and more experiments in the vision-language setting, and the authors added new experiments to show the versatility of the framework. The reviewers were all in support of acceptance.
Decision: Accept (poster)