Active Labeling: Streaming Stochastic Gradients
Authors: Vivien Cabannes
Francis Bach
Vianney Perchet
Alessandro Rudi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Weak supervision
partial labeling
active learning
sgd

Abstract: The workhorse of machine learning is stochastic gradient descent.
To access stochastic gradients, it is common to consider iteratively input/output pairs of a training dataset.
Interestingly, it appears that one does not need full supervision to access stochastic gradients, which is the main motivation of this paper.
After formalizing the "active labeling" problem, which focuses on active learning with partial supervision, we provide a streaming technique that provably minimizes the ratio of generalization error over the number of samples.
We illustrate our technique in depth for robust regression.

Active Labeling: Streaming Stochastic Gradients
Vivien Cabannes' Meta
Francis Bach INRIA / ENS/ PSL
Vianney Perchet ENSAE
Alessandro Rudi INRIA / ENS PSL
Abstract
The workhorse of machine learning is stochastic gradient descent. To access stochastic gradients, common to consider iteratively input/output pairs of a training dataset. Interestingly, it appears that one does not need full supervision to access stochastic gradients. which is the main motivation of this paper. After formalizing the "active labeling" problem, which focuses active learning with partial supervision, we provide a streaming technique that provably minimizes the ratio of generalization error over the number of samples. We illustrate technique in depth for robust regression.
Introduction
A large amount of the current hype around artificial intelligence was fueled by the recent successes of supervised learning. Supervised learning consists designing an algorithm that maps inputs to outputs by learning from a set of input/output examples. When accessing many samples, and given enough computation power, this framework is able to tackle complex tasks. Interestingly, many of the difficulties arising in practice do not emerge from choosing the right statistical model solve the supervised learning problem. but from the problem of collecting and cleaning enough data (see Chapters 1 and 2 of Géron, 2017, for example). Those difficulties trends toward data privacy regulations (Council of European Union, 2016). This fact motivates this work, where we focus how to efficiently collect information to carry out the learning process.
not disjoint from the current
In this paper, we formalize the "active labeling" problem for weak supervision, where the goal is to learn target function by acquiring the most informative dataset given a restricted budget for annotation. We focus explicitly on weak supervision that comes as a set of label candidates for each input, aiming partially supervise input data in the most efficient way guide learning algorithm. We also restrict our study to the streaming variant where, for each input, only a single partial information can be collected about its corresponding output. The crux of this work is to leverage the fact that full supervision is not needed to acquire unbiased stochastic gradients, and perform stochastic gradient descent.
The following summarizes our contributions.
1. First, we introduce the "active labeling" problem, which is a relevant theoretical framework that encompasses many useful problems encountered by practitioners trying annotate their data in the most efficient fashion, as well as its streaming variation, in order to deal with privacy preserving issues. This is the focus of Section
2. Then, in Section 3, we give high-level framework to access unbiased stochastic gradients with weak information only. This provides simple solution the streaming "active labeling" problem.
3. Finally, detail this framework for a robust regression task in Section 4, and provide an algorithm whose optimality is proved in Section 5.
Work done while INRIA/ ENS/ / PSL. Contact the first author at vivi www.nnessggaill.commm
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

As proof of concept, we provide numerical simulations in Section 6. We conclude with a high-level discussion around our methods in Section 7.
Related work. Active query of information is relevant to many settings. The most straightforward applications are searching games, such as Bar Kokhba or twenty questions (Walsorth, 1882). We refer to Pelc (2002) for an in in-depth survey of such games, especially when liars introduce uncertainty, and their relations with coding on noisy channels. But applications are much more diverse, e.g. for numerical simulation (Chevalier et al., 2014). database search (Qarabaqi and Riedewald, 2014), or shape recognition (Geman and Jedynak, 1993), to name a few.
In terms of motivations, many streams of research can be related to this problem, such as experimental design (Chernoff, 1959), statistical queries (Kearns, 1998; Fotakis al., 2021), crowdsourcing (Doan et al., 2011), or aggregation methods in weak supervision (Ratner et al., 2020). More precisely, "active labeling" consists in having several inputs and querying partial information on the labels. is close to active learning (Settles, 2010; Dasgupta, 2011; Hanneke, 2014), where there are several inputs, but exact outputs are queried; and to active ranking (Valiant, 1975; Ailon, 2011; I; Braverman et al., 2019), where partial information is queried, but there is only one input. The streaming variant introduces privacy preserving constraints, a problem that is usually tackled through the notion of differential privacy (Dwork et al., 2006).
In terms of formalization, (2020), which casts weak supervision as sets of label candidates and generalizes semi-supervised learning (Chapelle et al., 2006). Finally, our sequential setting with a unique final reward similar to combinatorial bandits in a pure-exploration setting (Garivier and Kaufmann, 2016; Fiez et al., 2019).
build the partial supervision formalization of Cabannes al.
2 The "active labeling" problem
Supervised learning is traditionally modeled in the following manner. Consider X' an input space, y an output space, E y x y - IR loss function, and E Axxy a joint probability distribution. The goal is to recover the function
arg min R() = Exxx) (X(((),
(1)
パ-X-Y
yet, without accessing p. but dataset of independent samples distributed according to p. Dr (X,, Ydiis pp" In practice, accessing data comes at a cost, and it is valuable to understand the cheapest way to collect a dataset allowing to discriminate f"
We shall suppose that the input data (Xz)ssn are easy to collect, yet that labeling those inputs get outputs (Y))sn demands a high amount of work. For example, it is relatively easy to scrap the web or medical databases to access radiography images, but labeling them by asking radiologists to recognize tumors on zillions of radiographs will be both time-consuming and expensive. As a consequence, we assume the (Xi)sse given but the (Y))ss unknown. As getting information on the labels comes at a cost (e.g., paying a pool of label workers, or spending your own time), given a budget constraint, what information should we query on the labels?
To quantify this problem, we will assume that we can sequentially and adaptively query T information of the rype ir, ES. any index i, E {1..... nn} and any set of labels S. y (belonging to a specified set of subsets y)) Here, / E (1,.... .T) indexes the query sequence, and T E N is a fixed budget. The goal is to optimize the design of the sequence S,) in order to get the best estimate of f in terms of risk minimization (1). In the following, we give some examples to make this setting more concrete.
Example 1 (Classification with attributes). Suppose that a labeler is asked to provide fne-ggained classes on images (Krause et al., 2016; Zheng et al., 2019), such as the label "caracal" in Figure 6. This would be difficult for many people. Yet, it is relatively easy to recognize that the image depicts a "feline" with "tufted-ears" and "sandy color". As such, a labeler can give the weak information that Y belongs to the set "feline", , S = ["cat", "lion", "figer"....., and the set "tufted ears", " S2 = ("Great horned owl", "Aruacana chicken",. ..... This is enough to recognize that Y E S 0 S2 ("caracal"), }. The question lyes, corresponds to asking if the image depicts a feline.
"Note that the wording "active labeling" has been more or less used as synonymous of "active learning" (e.g.. Wang and Shang, 2014). In contrast, use "active labeling" design "active weakly supervised learning".

---

Literature on hierarchical classification and autonomic taxonomy construction provides interesting ideas for this problem (e.g. Cesa-Bianchi et al., 2006: Gangaputra and Geman, 2006).
Example 2 (Ranking with partial ordering). Consider problem where for given input x, character- izing a user, we are asked to deduce their preferences over m items. Collecting such a label requires knowing the exact ordering of the items induced by a user. This might be hard to ask for. Instead, one can easily ask the user which items they prefer in collection of a few items. The user's 's answer will give weak information about the labels, which can be modeled as knowing 1y,e5 of total orderings that satisfy this partial ordering. We refer the curious reader to active ranking and dueling bandits for additional contents (Jamieson and Nowak, 2011; : Bengs et al., 2021).
for S the set
consumer characterized by some features x, this consumer is ready to pay a price y E. R for this product. We price it f(x) E R. and we observe f())ey, that is if the consumer is willing buy this product at this price tag or not (Cesa- Dess-BBancchi et al., 2019; Liu et al., 2021). Although, in this setting, the goal is often to minimize the regret, which contrasts with our pure exploration setting.
Example 3 (Pricing product). Suppose that want to sell a product
As counter- counter-example, our assumptions are not set to deal with missing data, i.e. if some coordinates of some input feature vectors X, are missing (Rubin, 1976). Typically, this happens when input data comes from different sources (e.g., when trying to predict economic growth from country information that is selffrepprted).
Streaming variation. The special case of the active labeling problem we shall consider consists in its variant without resampling. This corresponds question by sample, formally i, = r. This setting is particularly appealing for privacy concerns, in settings where the labels (Y,) contain sensitive information that should not be revealed totally. For example, some people might be more confortable giving range over a salary rather than the exact value; or in the context of polling, one might not call back a previous respondent characterized by some features X, to ask them again about their preferences captured by Y, Similarly, the streaming setting is relevant for web marketing, where inputs model new users visiting a website, queries model sets of advertisements chosen by an advertising company, and one observes potential clicks.
the online setting where one can only ask one
3 Weak information as stochastic gradients
In this section, we discuss how unbiased stochastic gradients can be accessed through weak information.
Suppose that we model f fo for some Hilbert space θ e 0. With some abuse of notations, let us denote ((x, y, 0) == {(fox)).). We aim to minimize R(0) = Exxyy) [C(X, 0)] Assume that R is differentiable (or sub-differentiable) and denote its gradients by V,R.
Definition 1 (Stochastic gradient). A stochastic gradient of R is any random function G θ - θ such that EI (() (.). Given some step size function y N IK,, a stochastic gradient descent ) E O", initialized with some Og and updated as 01+1 = 0, ( (0,), where the realization of (0,)) given 0, is independent of the previous realizations of G(,,) given Og-
(SGD) is procedure, (0,)
In supervised learning. SGD is usually performed with the stochastic gradients V,l(X,Y, More generally, stochastic gradients are given by
G00) (xx((X T(T),
for r T 2 with T c 2 a set of subsets of O and a random variable on T, such that
V Er[ ((T)] =.
Stated otherwise, if you have way to image a vector 0 from partial measurements løe such that you can reconstruct this vector in a linear fashion (3), then it provides you a generic strategy to get an unbiased stochastic estimate of this vector from a partial measurement (2).
function from y O (e.g., v Vo (X.,,,00) 6)), question eg()er translates into question lyes for some set 5 = do ((T) c V. meaning that the stochastic gradient (2) can be evaluated from single query. As proof of concept, we derive generic implementation for T and r in Appendix B. This provides generic SGD scheme to learn functions from weak queries when there no constraints the sets query.
For V/ y
3

---

Remark 2 (Cutting plane methods). While we provide here a descent method, one could also develop seatiin--laan/eellpsso methods to localize 0 according to weak information, which corresponds to the techniques developed for pricing by Cohen et al. (2020) and related literature.
4 Median regression
In this section, we focus on efficiently acquiring weak information providing stochastic gradients for regression problems. In particular, we motivate and detail our methods for the absolute deviation loss.
Motivated by seminal works censored data (Tobin, 1958), we shall suppose that we query half- spaces. For an output y E y IR"", and any hyper-plane z + u- c. IR" for z E R' u 2 we can ask a labeler to tell us which half-space belongs to. Formally, for a given unit cost. Such an imaging scheme where one observes summations its components rather than a vector itself bears similarity with compressed sensing. To provide further illustration, this setting could help to price products while selling bundles: where the context characterizes some users, web-pages or/and advertisement companies; the label y R" corresponds the value associated to m different items, such as stocks composing an index, or advertisement spots; and the observation sign( (y, u) c) (with e ()) captures if the user x buys the basket with weights E 3 when it is priced
access the quantity sign( (y u))
Least-squares.
For regression problems, it is common to look at the mean square loss
((X,Y.0) = -I/o(X) -112, Va((X, Y, = 2(f((X) - -Y)
where (x)( E Y' @ denotes the Jacobian of 0 - fe(x). In rich parametric models, it is preferable ask questions on y rather than on gradients in @ which is potentially much bigger space. we assume that Y and fo(X) are bounded in fo-norm by M R2, we can adapt (2) and (3) through the fact that for any z V, such that |||||| s 2M, as proven in Appendix B,
3/2
Euy [Lauer U =1
where
01 Euyy (L)) (e1, U]. 2M + 4m +3)
for U uniform on the sphere s=-1 and V uniform on [0, 2M]. Applied = fo( Y, designs an SGD procedure by querying information of the type 1 (x,,0)<((6()),))
case for median regression. Motivated by robustness purposes, we will rather expand on median regression. In general, would like to learn function that, given an input, replicates the output of I/O samples generated by the joint probability p. In many instances, X does not characterize all the sources of variations of Y, i.e. imput features not rich enough to characterize unique output, leading to randomness in the conditional distributions (Y) When many targets can be linked to a vector x X, how define consensual f(x)? For analytical reasons, statisticians tend to the least-squares error which corresponds to asking for f() to be the mean of the distribution (YJ xx). Yet, means are known to be too sensitive to but large outputs (see e.g., Huber, 1981), and cannot be defined as good and robust consensus in a world of heavy-tailed distributions. This contrasts with the median, which, For instance, median income is preferred over mean income as a population indicator (see e.g., US Census Bureau, 2021).
consequence, is often much more valuable to summarize range of values.
Median regression. loss, leading
The geometric median variationally defined through the absolute deviation
fx( -
(X.Y. (XXY.0)=1lf(x)) Y!l
V,C(X,Y,0)
(X).
(4)
(X) -Y]
Similarly to the least- case, we can access weakly supervised stochastic gradients through the fact that for 2 e gm-1, as shown in Appendix B,
VTI m-1
Ey [sign ( (z, U)) U] = c2 2.
where
C2 = Ey [sign (()), [)]
(5)
m
where is uniformly drawn on the sphere sm-1, and I' is the gamma function. This suggests Algorithm 1.

---

Algorithm 1: Median regression with SGD.
Data: A model for 0 O some data (X)ss labeling budget 7, step size rule y N R,
Result: A learned parameter 0 and the predictive function f fā-
Initialize 0g-
for
to 7 do Sample U, uniformly on 9S-
Query & = sign( (Y, - z, U,) for 2 fa. (X1),
Update the parameter 0, f-1 + y(1) Ui (D fo (X)).
Output 0 fr, some average, e.g., 0 T Σ/ ,,
5 Statistical analysis
In this section, we quantify the performance of Algorithm by proving optimal rates of convergence when the median regression problem is approached with (reproducing) kernels. For simplicity, we will assume that f can be parametrized by linear model (potentially of infinite dimension).
Assumption
Assume that the solution f" X - Rem of the median regression problem (1) and (4)
can be parametrized by some separable Hilbert space H. and bounded feature map y X - H. such that, for any i [m], there exists some 0 E HH such that (f(().ei) = (0 (f,,(())) H where
(ei) is the canonical basis of R.. Written into matrix form, there exists 0 E y & H, such that f*(-) = (-).
The curious reader can easily relax this assumption the realm of reproducing kernel Hilbert spaces following the work of Pillaud-Vivien al. (2018a). Under the linear model of Assumption 1, Algorithm is specified with u f a @ (xx). Note that rather than working with y @ H which is potentially dimensional space y @ Span (4)()) and well approximated by dimessoim spaces to ensure efficient computations (Williams and Seeger, 2000; Mcanti al., 2020).
empirical estimates can be represented in the finite-
One of the key points of SGD that gradient descent is so gradual that one can use noisy or stochastic gradients without loosing statistical guarantees while speeding up computations. This is especially true when minimizing convex functions that are nor strongly-convex, i.e., bounded below by quadratic, nor smooth, i.e., with Lipschitz-continuuv gradient (see, e.g., Bubeck, 2015). In particular, the following theorem, proven in Appendix A. states that Algorithm minimizes the population risk at a speed at least proportional (TT-1/2).
Theorem (Convergence rates). Under Assumption 1, and under the knowledge of k and M two real values such that TE (X)()) s x² and ||0* s M, with budget T N, constant step size y <NT and the average estimate 7 Σ/-1 O,, Algorithm I leads to an estimate f that suffers from an excess of risk
E. (R)) R(()
2
2/2
C2VT
where the expectation is taken with respect to the randomness of Ô that depends on the dataset i, Y;) as well the questions (i,, S.)ST.
While we give here a result for fixed step size, one could retake the extensive literature on SGD to prove similar results for decaying step sizes that do not require to know the labeling budget in advance (e.g. setting (t) x 112 at the expense of an extra term in log(?) in front of the rates), as well as different averaging strategies (see e.g., Bach, 2023). In practice, parameter M but could nonetheless find the right scaling for based on cross-validation
might not know a priori the
The rate in 1/2) applies more broadly to all the strategies described in Section 3 as long as the loss l and the parametric model fo ensure that R(0) is convex and craschizz-ontinuuut Although the constants appearing front of rates depend on the complexity to reconstruct the full gradient Vol X; Y)) from the reconstruction scheme (3). Those constants correspond to the second moment of the stochastic gradient. For example, for the least-squares technique described earlier one would have to replace c2 by c₁ in (6).
5

---

Theorem 2. proven in Appendix A.3, states that any algorithm that accesses a fully supervised learning dataset of size 7' cannot heat the rates in 0(T-1/2), hence any algorithm that collects weaker information on (5)) cannot display better rates than the ones verified by Algorithm This proves minimax optimality of our algorithm up to constants.
Theorem 2 (Minimax optimality). Under Assumption and the knowledge of an upper bound on ||0'|| = M, assuming that yp is bounded by there exists a universal constant c3 such that for any algorithm A that takes as input Dr (X,, Yidisr ~ po for any T N and output a parameter
sup EDr-par [R(fAIDro)] -R((ppp)) cyMKT 1/2 PeMaa
The supremum over p MM has to be understood as the supremum over all distributions p Axxxy such that the problem defined through the risk R(f:p) == (x)(((()), Y)] is minimized for fo that verifies Assumption 1 with [|0 bounded by constant M.
The same theorem applies for least- with a different universal constant. It should be noted that minimax lower bounds are in essence quantifying worst cases of given class of problems. In particular, to prove Theorem 2, we consider distributions that lead to hard problems; more specifically, we assumed the variance of the conditional distribution (Y X) to be high. The practitioner should keep mind that it is possible to add additional structure on the solution, leverage active learning or seni-supervised strategy such uncertainty sampling (Nguyen et al., 2021), or Laplacian regularization (Zhu et al., 2003; Cabannes et al., 2021a), and reduce the optimal rates of convergence.
To conclude this section, let us remark that most of our derivations could easily be refined for practitioners facing slightly different cost model for annotation. In particular, they might prefer to perform batches of annotations before updating 0 rather than modifying the question strategy after each input annotation. This would be similar to mini-batching in gradient descent. Indeed, the dependency of our result on the annotation cost model and on Assumption 1 should not be seen as a limitation but rather as a proof of concept.
Numerical analysis
In this section, we illustrate the differences between our active method versus a classical passive method, for regression and classification problems. Further discussions are provided in Appendix Our code is available online at
active- labeling.
Let begin with the regression problem that consists in estimating the function f" that maps x E [0, 1] to sin(2xx) E R. Such a regular function, which belongs to any Hölder or Sobolev classes of functions, can be estimated with the Gaussian kernel, which would ensure Assumption and that corresponds to a feature map such that k(x,x') == (xx(x,, (xx)) = exp(- |x xx'I (()r²)) for any bandwidth parameter o 0. On Figure
focus on estimating f given data (X;)setr that are uniform on [0, 1J in the noiseless setting where Y; (X;), based on the minimization of the absolute deviation loss. The passive baseline consists in randomly choosing a threshold U, ~ (N 1) and acquiring the observations (iy() that can be cast as the observation of the half-space S; = {y e y 1y>u, uy } =: s(y, U/). In this noiseless setting, good baseline to learn f from the data (X, S,) is provided by the infimum loss characterization (see Cabannes et al., 2020)
f" = arg min Exx.s) inn e( (((()),)), yes
f:X-y
where the distribution over X corresponds to the marginal of p over X. and the distribution over (S) X = =x) is the pushforward of U (O, 1) under s(f" (x).-). The left plot on Figure 1 corresponds to an instance of SGD on such an objective based on the data (X,, S;), while the right plot corresponds to Algorithm 1. We take the same hyperparameters for both plots, a bandwidth o 0.2 and an SGD step size 0.3. We refer the curious reader to Figure 7 in Appendix E for plots illustrating the streaming history, and to Figure 10 for world" experiments.
To illustrate the versatility of our method, we approach classification problem through the median surrogate technique presented in Proposition 3. To do so, consider the classification problem
'A noteworthy computational aspect of linear models, often refer as the "kernel trick", is that the features map y does not need to be explicit, the knowledge of & X x X - IR being sufficient to compute all quantities of interest (Scholkopf and Smola, 2001). This "trick" can be applied algorithms.

---

Passive strategy
Active strategy
Above
Signal
Below
Reconstruction
Ourputs
Ourpurs
Inputs
Inputs
Figure 1: Visual comparison of active and passive strutegies. Estimation in orange of the original signal f" dashed hased on median regression a noiseless setting. Any orange point (x,u) IR2 corresponds to an ohservation made that a below f (x), while blue point corresponds to above (x) The passive strategy corresponds acquiring information based on (U [x) following normal distribution, while the active strategy corresponds (x) fx).. The active strategy reconstructs the signal much better given budget of 30 observations.
with m E N classes, X' = [0. 1] and the conditional distribution (Y X) linearly interpolating between Dirac in y1, y2 and y3 respectively for 0, 1/2 and and the uniform distribution for x = 1/4 and x = 3/4; and X uniform on \ (11/4- - e, 1 1/4 #] U [3/4- 6, 8/3/4 s)).
Regression task
Classification task
10
10-1
Risk
Risk
10-1
10:2
sctive
active
passive
passive
iteration T
iteration T
Figure 2: Comparison of generalization errors of passive and active strategies function of the annotation budget T. This error is computed by averaging over 100 trials. solid is represented the average error, while the height of the dark area represents one standard deviation on each side. In order to consider the streaming setting where 7 is not known in advance, consider the decreasing step size y(r) yo/ Vr; and smooth out the stochasticity due random gradients, we consider the average estimate 0, (01 + 0,)//. The left figure corresponds the noiscless regression setting Figure with yo 1. We observe the convergence behavior in (TT11/2) of our active strategy. The right setting corresponds the classification problem setting deseribed in the main text with 100, 1/20, and approached with the median surrogate. We observe Pillaud-Vivier et al. (2018b); Cabannes et al. (2021b); its kicks in earlier for the active strategy. The two plots are displayed with logarithmic scales on both axes.
exponential convergence phenomenon described by
7 Discussion
7.1 Discrete output problems
In this section, discuss casting Algorithm into procedure to tackle discrete-output problems, by leveraging surrogate regression tasks.
Learning problems with discrete output spaces are not as well understood as regression problems. This is a consequence the complexity of dealing with combinatorial structures in contrast with continuous metric spaces. In particular, gradients are not defined for discrete output models. The current state-of-the-an framework to deal with discrete output problems is to introduce a continuous surrogate problem whose solution can be decoded as a solution the original problem (Bartlett et al.,
7

---

2006). For example, one could solve a classification task with median regression surrogate problem, which is the object of the next proposition, proven in Appendix C.
Proposition 3 (Consistency of median surrogate). The classification setting where y is a finite space, and E y x y - IR is the zero-one loss z(y,z) = +yy+ can be solved as a regression lask through the simplex embedding of y in R² with the orthonormal basis (ey)yey. More precisely, if : X - R the minimizer of the median surrogate risk Rg(g) = E [llg -eyll], then f : X - y defined as f (x) arg y (x) minimizes the original risk R(f)= = E (e(f(X)
More generally, any discrete output problem can be solved by reusing the consistent eeastesuuares surrogate of Ciliberto et al. (2020). Algorithm I can be adapted to the least-squares problem based on specifications at the beginning of Section 4. This allows using our method an off-the-shelve fashion for all discrete output problems. For example, problem consisting in ranking preferences over items can be approached with the Kendall correlation loss ((y, Z) = -4(y) (((()) with y(y) = (Ly0)>y())
for j S m. where y and are permutations over [m] that encode the rank of each element in terms of user preferences. In this setting, the surrogate task introduced by Ciliberto et al. (2020) consists in learning gxx) = [
x least-squares problem. The half-space surrogate queries translate directly into the questions Lisrsm w(1, () y()z(()) > c for some ()). c in IR In particular, if U is chosen to be uniform on the canonical basis (rather than on the sphere), those questions translate into pairwise orderings (e.g., does user x prefer movie or movie j?). In terms of guarantee akin to Theorem 1, retaking the calibration inequality of Ciliberto et al. (2020), we get convergence rates of the form m 1/27-1/4 In terms of guarantee akin to Theorem 2, since need as least (m!) = m (o)(m) binary queries to discriminate between m!! permutations, we can expect a lower bound in 1/2 log(m) 1/27-1/2, More generally, many ranking problems can be approached with correlation losses and tackled through surrogate regression problems the convex hulls of some well-known polytopes such as the Birkhoff polytope or the permutohedron (e.g.. Ailon, 2014). Although their descriptions is oft-of-scope of this paper, linear cuts of those polytopes form well-structured queries sets e.g., the faces of all dimensions of the permutohedron correspond, in a one-to-one fashion, to strict weak orderings (Ziegler, 1995).
In those discrete settings, Theorem can be refined under low noise conditions. In particular, under generalization of the Massart noise condition, our approach could even exhibit exponential convergence rates as illustrated on Figure 2. For classification problems, this condition can be expressed as the existence of a threshold 5 > O such that for almost all E X and E V, we have F = x) - I = =|X = x) E (O, 8). Arguably, this assumption is met on well-curated images dataset such ImageNet CIFARIO, where for each input X the most probable class has always more than e.g. 60% of chance to be the target Y. When this assumption holds together with Assumption 1 (when the surrogate target g" belongs to the RKHS and the kernel is bounded), then the right hand-side of equation (6) can be replaced by exp(-c') for some constant c. The proof would be a simple adaptation of Pillaud-Vivien et al. (2018a); Cabannes al. (2021b) our case.
7.2 Supervised learning baseline with resampling
In this section, we discuss simple supervised learning baselines that compete with Algorithm I when resampling is allowed.
When resampling is allowed a simple baseline for the active labeling problem is provided by supervised learning. In regression problems with the query of any half-space, method that consists in annotating each (Y))ss((T,)) up to precision E, before using any supervised learning method to learn f from (X,, M))sm(T.)) could acquire n(T, æ) = Tmmm log, ()")) data points with a dichotomic search along all directions, assuming Y; bounded or sub-Gaussian. In terms of minimax rates, such procedure cannot perform better than in n1T, -1/2 + E, the first term being due to the statistical limit in Theorem 2, the second due to the incertitude & on each Y; that transfers to the same level of incertitude on f- Optimizing with respect to & yields bound in 0/2 log(?) Therefore, this not-so-naive baseline is only suboptimal by a factor 1/2 In the meanwhile, Algorithm can be rewritten with resampling, as well as Theorem 1, which we prove in Appendix A.2. Hence, our technique will still achieve minimax optimality for the problem "with resampling". In other terms, by deciding
As a side note, while we are not aware of any generic theory encompassing the of Proposition 3, we showease its superiority over least-squares on at least two types of problems on Figures 3 and 4 in Appendix C.
surrogate
8

---

to acquire more imprecise information, our algorithm reduces annotation cost for a given level of generalization error (or equivalently reduces generalization error for a given annotation budget) by a factor lTg(T) 1/2 when compared this baseline.
The picture is slightly different for discrete-output problems. If one can ask any question s 2 then with dichotomic search, one can retrieve any label with log)(m) questions. Hence, to theoretically beat the fully supervised baseline with the SGD method described in Section 3, one would have to derive gradient strategy (2) with small enough second moment (e.g., for convex losses that are non-smooth nor strongly convex, the increase in the second moment compared to the usual stochastic gradients should be no greater than log, 1/2) How to best refine our technique to better take into account the discrete structure of the output space is open question. Introducing bias that does not modify convergence properties while reducing variance eventually thanks to importance sampling is potential way to approach this problem. A simpler idea would be to remember information of the type Y; E s to restrict the questions asked in order to locate fe, (X;) - Y; when performing stochastic gradient descent with resampling. Combinatorial bandits might also provide helpful insights on the matter. Ultimately, we would like to build an understanding of the whole distribution (Y X) and not only of (X) as we explore labels in order refine this exploration.
7.3 Min-max approaches
In this section, discuss potential extensions of our SGD procedure, based on min-max variational objectives.
Min-max approaches have been popularized for searching games and active learning, where one searches for the question that minimizes the size of the space where a potential guess could lie under the worst possible answer to that question. A particularly well illustrative example is the solution of the Mastermind game proposed by Knuth (1977). While our work leverages plain SGD, one could build on the vector field point-of-view of gradient descent (sec, e.g., Bubeck, 2015) to tackle min-max convex concave problems with similar guarantees. In particular, we could design weakly supervised losses (x)(x, s; lyss) and min-max games where prediction player aims minimizing such a loss with respect to the prediction f. while the query player aims at maximizing it with respect to the question s, that is querying information that best elicit mistakes made by the prediction player. For example, the dual norm characterization of the norm leads to the following min-max approach to the median regression
arg min R(f) arg min -
Exx ()xx y))
fiX' Ue(ge-lyxxy
Such min-max formulations would be of interest if they lead to improvement of computational and statistical efficiencies, similarly to the work of Babichev et al. (2019). For classification problems, the following proposition introduces such a game and suggests its suitability. Its proof can be found in Appendix D.
Proposition 4. Consider the classification problem of learning f X + y where y is of finite cardinality, with the 0-1 loss E(z,y) = 1zzy, minimizing the risk (1) under distribution p on X x y Introduce the surrogate score functions g X - dy;x - v where v = (Vy)yey is a family of non-negative weights that sum to one, well as the surrogate loss function L x (v. = s(1 101-22 Eyes Vy), and the min-max game
max E(xyr>- Ex-ri-pSsppt (L(g()).S:1vee lyes)] g.X -yy p. -AS
min
(8)
When contains the singletons and with the low-noise condition that P + =xx) almost everywhere, then f can be learned through the relation f"xx) arg minyey g" (x), for the unique minimizer g" of (8). Moreover, the minimization of the empirical version of this objective with the stochastic gradient updates for saddle point problems provides natural "active labeling" scheme to find this g"
On the one hand, this min-max formulation could help to easily incorporate restrictions on the sets to query. On the other hand, it is not completely clear how to best update (or derive an unbiased stochastic gradient strategy for) the adversarial query strategy μ based on partial information.

---

8 Conclusion
We have introduced the "active labeling" problem, which corresponds "active partially supervised learning". We provided a solution to this problem based on stochastic gradient descent. Although our method can used for any discrete output problem, we detailed how it works for median regression, where we show that it optimizes the generalization error for a given annotation budget. In a near future, we would like to focus on better exploiting the discrete structure of classification problems, eventually with resampling strategies.
Understanding more precisely the key issues in applications concerned with privacy, and studying how weak gradients might provide good trade-off between learning efficiently and revealing too much information also provide interesting follow-ups. Finally, regarding dataset annotation, exploring different paradigms of weakly supervised learning would lead to diffrrntt active weakly supervised learning frameworks. While this work is based on partial labeling, similar formalization could be made based on other weak supervision models, such as aggregation (e.g., Ratner et al., 2020), or group statistics (Dietterich al., 1997). In particular, annotating a huge dataset is often done by bagging inputs according to predicted labels and correcting errors that can be spotted those bags of inputs (Deng et al., 2009). We left for future work the study of variants of the "active labeling" problem that model those settings.
Acknowledgments and Disclosure of Funding
While at INRIA/ ENS/ PSL, VC was funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' d'avenir" program, reference ANR-19-P3IA-000 (PRAIRIE 31A Institute). FR and AR also acknowledges support of the European Research Council (grants SEQUOIA 724063 and REAL 947908).
References
Nir Ailon. Active learning ranking from pairwise preferences with almost optimal query complexity. In Advances in Neural Information Processing Systems, 2011.
Nir Ailon. Improved bounds for online learning over the permutahedron and other ranking polytopes. In International Conference on Artificial Intelligence and Statistics, 2014.
Martin Anthony and Peter Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
Dmitry Babichev, Dmitrii Ostrovskii, and Francis Bach. Efficient primal- algorithms for large-scale multiclass classification. Technical Report 1902.03755, arXiv, 2019.
Francis Bach. Learning Theory from First Principles. To appear at MIT Press, 2023.
Francis Bach and Eric Moulines. Non-strongly-comwe smooth stochastic approximation with convergence rate O(1/n). In Advances in Neural Information Processing Systems, 2013.
Peter Bartlett, Michael Jordan, and Jon McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 2006.
Viktor Bengs, Róbert BukeeFekete, Adil El Mesaoudi-Paie Paull and Eyke Hüllermeier. Preference--asse online learning with dueling bandits: A survey. Journal of Maching Learning Research, 22(7): 1-108, 2021.
Lucien Birgé. Approximation dans les espaces métriques et théorie de l'estimation. Zeitschrift für Wahnscheinicchkeisshherre und Verwandte Gebiete, 65(2):181-23) 1983.
Salomon Bochner. Monotone funktionen, stieltjessche integrale und harmonische analyse. Mathema- fische Annalen, 108(1):378-41)) 1933.
Mark Braverman, Jieming Mao, and Yuval Peres. Sorted top-k in rounds. Conference on Learning Theory, 2019.
10

---

Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4))2313357, 2015.
Vivien Cabannes, Alessandro Rudi, and Francis Bach. Structured prediction with partial labelling through the infimum loss. In International Conference Machine Learning, 2020.
Vivien Cabannes, Loucas Pillaud- Pillaud-Vivien, Francis Bach, and Alessandro Rudi. Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning. In Advances in Neural Information Processing Systems, 202
Vivien Cabannes, Alessandro Rudi, and Francis Bach. Fast rates in structured prediction. In Conference Learning Theory, 2021b.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2006.
Nicolò Cesa- BiinsBBiacch... Claudio Gentile, and Luca Zaniboni. Incremental algorithms for hicrarchical classification. Journal of Machine Learning Research, 7(2):31-54 2006.
Nicolò Cesa-Bianchi Tommaso Cesari, and Vianney Perchet. Dynamic pricing with finitely many unknown valuations. In International Conference on Algorithmic Learning Theory, 2019.
Chih Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):1-27, 2011.
Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien, editors. Semi-Supervised Learning. MIT Press, 2006.
Herman Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3): 755-770, 1959.
Clément Chevalier, Julien Bect, David Ginsbourger, Emmanuel Vázquez, Victor Picheny, and Yann Richet. Fast parallel kriging-basee stepwise uncertainty reduction with application to the identification of excursion set. Technometrics, 56(4):455-465, 2014.
Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 11(98):1-67, 2020.
Maxime Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Management Science, 66(1 (6(11):4921449)) 2020.
Council of European Union. Regulation (EU) 2016/679 of the European parliament (General Data Protection Regulation), 2016.
Timothée Cour, Benjamin Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12042):550 2011.
Thomas Cover and Joy Thomas. Elements of Information Theory. Wiley, 1991.
Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 412(19):1777-1781, 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. Conference on Computer Vision and Pattern Recognition, 2009.
Thomas Dietterich, Richard Lathrop. and Tomás Lozano-Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial Intelligence, 99(1)))31-7,, 1997.
AnHai Doan, Raghu Ramakrishnan, and Alon Halevy. Crowdsourcing systems on the world-wide web. Communication the ACM, 54(4):86-96 2011.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, 2006.

---

Robert Fano. Transmission of Information: A Statistical Theory of Communications. MIT Press, 1968.
Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential Experimental Design for Transductive Linear Bandits. In Advances in Neural Information Processing Systems, 2019.
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Efficient algorithms for learning from coarse labels. In Conference on Learning Theory, 2021.
Sachin Gangaputra and Donald Geman. A design principle for coarse-to-fine classification. In Conference on Computer Vision and Pattern Recognition, 2006.
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, 2016.
Donald Geman and Bruno Jedynak. Shape recognition and twenty questions. Technical report, INRIA, 1993.
Aurélien Géron. Hands-On On Machine Learning with Scikit-Lears TensorFlow. O'Reilly, 2017.
Edgar Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 3143):004-522, 1952.
Steve Hanneke, Theory of disagreement-basee active learning. Foundations and Trends in Machine Learning, 7(2-3):131-309 2014.
Charles Harris, Jarrod Millman, Stéfan van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg. Nathaniel Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchamy Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis Oliphant. Array programming with NumPy. Nature, 585(7825);357-384 2020.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
Peter Huber. Robust Statistics. Wiley, 1981.
John Hunter. Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9(3): 90-95, 2007.
Il'dar Ibragimov and Rafail minski.. On the estimation of infinite-dimensionall parameter in gaussian white noise. Doklady Akademii Nauk SSSR, 10555) 1977.
Kevin Jamieson and Robert Nowak. Active ranking using pairwise comparisons. In Advances in Neural Information Processing Systems, 2011.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the Asoociation for Computing Machinery, 45(6):983-1000) 1998.
Donald Knuth. The computer as master mind. Journal of Recreational Mathematics, 9(1):16, 1977.
Andrey Kolmogorov and Vladimir Tikhomirov. g-entropy and e-capacity sets in functional spaces. Uspekhi Matematicheskikh Nauk, 14(2):3-88 86, 1959.
Jonathan Krause, Benjamin Sapp, Andrew Howard, Howard Zhou, Alexander Toshev, Tom Duerig, James Philbin, and Li Fei-Fei. The unreasonable effectiveness of noisy data for fine-grained recognition. European Conference on Computer Vision, 2016.
Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions. In Symposium Discrete Algorithms, 2021.
Andreas Maurer. vector-contraction inequality for Rademacher complexities. In International
Conference Algorithmic Learning Theory, 2016.
12

---

Giacomo Meanti, Luigi Carratino, Lorenzo Rosasco, and Alessandro Rudi. Kernel methods through the roof: Handling billions of points efficiently. In Advances Neural Information Processing Systems, 2020.
Vu-Linh Nguyen, Mohammad Hossein Shaker, and Eyke Hüllermeier. How to measure uncertainty in uncertainty sampling for active learning. Machine Learning, 111(1):89-12, 2021.
Alex Nowak-Vila. Structured prediction with theoretical guarantees. Phd thesis, Ecole Normale Supérieure, 2021.
Andrzej Pelc. Searching games with errors fifty years of coping with liars. Theoretical Compututer Science, 270(1):71-109, 2002.
Loucas Pillaud-Vivee Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, 20.
Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Exponential convergence of testing error for stochastic gradient methods. In Conference On Learning Theory, 2018b.
Bahar Qarabaqi and Mirek Riedewald. User-driven refinement of imprecise queries. In International Conference on Data Engineering, 2014.
Alexander Ratner, Stephen Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: rapid training data creation with weak supervision. The VLDB Journal, 29(2)7709-730, 2020.
Donald Rubin. Inference and missing data. Biometrika, 63(3):581-592) 1976.
Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco. Less is more: Nyström computational regularization. In Advances in Neural Information Processing Systems, 2015.
Bernhard Scholkopf and Alexander Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT press, 2001.
Burr Settls. Active learning literature survey. Technical report, University of Wisconsin-Maddison 2010.
Karthik Sridharan, Shai Shalev-shwartz, and Nathan Srebro. Fast rates for regularized objectives. In Advances in Neural Information Processing Systems, 2008.
James Tobin. Estimation of relationships for limited dependent variables. Econometrica, 26(1):24-36. 1958.
US Census Bureau. Income and poverty in the United States: 2020, 2021.
Leslie Valiant. Parallelism in comparison problems. SIAM Journal on Computing, 4(3):348-355, 1975.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag. 1995.
Rom Varshamov. Estimate of the number of signals in error correcting codes. Doklady Akademii Nauk SSSR, 117:739-741, 1957.
Anatoliy Vitushkin. On Hilbert's thirteenth problem. Proceedings of the USSR Academy of Sciences, 95(4):701-704, 1954.
John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.
Mansfield Tracy Walsorth. Twenty Questions: A Short Treatise on the Game. Holt, 1882.
Dan Wang and Yi Shang. A new active labeling method for deep learning. In International Joint Conference on Neural Networks, 2014.
Harold Widom. Asymptotic behavior of the eigenvalues of certain integral equations. Transactions of the American Mathematical Society, 109(2), 1963.
13

---

Christopher Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In Advances Neural Information Processing Systems, 2000.
Heliang Zheng, Jianlong Fu, Zheng-Jun Zha, and Jiebo Luo. Looking for the devil in the details: Learning trilinear attention sampling network for fine-grained image recognition. In Conference on Computer Vision and Pattern Recognition, 2019.
Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. supirsuper learning using Gaussian fields and harmonic functions. In International Conference of Machine Learning, 2003.
Günter Ziegler. Lectures on Polytopes. Springer-Verlag, 1995.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See discussion section.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work aims developping advanced techniques to learn without too much supervision. Such a quest of increasing Al systems capability at reduced human labor cost is associated with broad societal issues. Those questions being really generic, we did not mention them in the main text.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Ys]]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all thcoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material
URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] The experiments were run on personal laptop and did not require many charges. Indeed, the amount of compute for experiments were similar to the amount used to write this paper.
4. If you are using existing assets (e.g., code, data, models) or curating/releasngg new assets... (a) If your work uses existing assets, did you cite the creators? [Yes] Although we have not cited the creators of some I&TEX libraries we used such as Michael Sharpe and the newtx package which we used for fonts our text.
(b) Did you mention the license of the assets? [N/A] Numpy and LIBSVM are under Berkeley Software Distribution licenses (respectively the liberal and revised ones),
Python and matplotlib are under the Python Software Foundation license.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "k1GIGXfH-L", "reviewer": "Reviewer_1mW2", "summary": "This paper generalizes the standard active learning setup to \"active weakly supervised learning,\" where partial supervision is available instead of full supervision. This paper provides a way to estimate the stochastic gradient when a query of any half-space is given. Statistical analysis and numerical simulation are conducted for simple regression and classification problems to demonstrate the superiority of active strategy over passive strategy.", "questions": "- The weak information can give an unbiased gradient estimation. How about the variance?\n- Figure 2 (Left) shows that the passive strategy is better than the active strategy for the first 100 steps. Does it mean using a passive strategy is better at the beginning?\n- From a practical point of view, the half-space query can be transformed into a binary question, and \"Example 1 (Classification with attributes)\" can be transformed into multiple-choice questions. What other formats of questions can you think of to facilitate the data annotation process?\n\nMisc\n- Line 115: Typo, \"we aim at to minimizing\" -> \"we aim to minimize\"\n- Line 253: Typo: \"ot\" -> \"to\"", "limitations": "The authors discuss their limitations in the paper and point out several future directions.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: This paper is well-motivated and focuses on an interesting problem: how to query the label in a weakly-supervised scenario.\n- Quality: The proposed method is novel and supported by extensive theoretical analysis and proof-of-concept numerical simulation.\n- Clarity: This paper is well-written with minor flaws.\n- Significance: This paper's scope is narrow, mainly focusing on the noiseless median regression problem in a stream setting. But it depicts a potentially new way for the annotator to provide a label, which may lower the bar for the task where an expert is needed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WkD60q7HR35", "reviewer": "Reviewer_Byvs", "summary": "This paper introduces the ``active labeling'' problem, which aims at learning with weakly-supervised labeling information. An specific focus of the paper is to conduct SGD but without the full gradient. The authors show that how to query weakly-supervised information in the cases of least-squares and the median regression. The authors also provide minimax results regarding the convergence rate (in the online setting). Empirical evaluations show the efficacy of the proposed method compared to the passive counterpart.", "questions": "Since theorem 2 essentially says that the provided Algorithm 1 works as good as the SGD with full gradient information, I wonder if the authors can conduct an experiment to compare the performance of Algorithm 1 and standard SGD with full gradient information?", "limitations": "The authors discussed the limitation in Section 8.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. A newly proposed ``active labeling'' problem looks interesting and important.\n2. The authors provide an algorithm to handle the proposed problem under median regression, and prove its minimax optimality in the kernel/linear case.\n\nWeakness:\n1. While I found the discussion in Section 7 quite interesting, I believe it will be better if precise statements are provided as theorems/propositions, e.g., on line 267, the authors claim exponential convergence rates can be achieved under margin conditions but no formal theorems are provided.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Pqf8oY1mEaY", "reviewer": "Reviewer_Evw4", "summary": "This paper has two main contributions. First, the paper defines a problem setting known as \"active labeling\", that is, given a large output space $\\mathcal{Y}$, we can query an index $i \\in [n]$ of a dataset with a subset $S \\subset \\mathcal{Y}$ and receive the binary response of whether $y_i \\in S$ or $y_i \\not\\in S$. The paper gives a few compelling examples that fit in this setting and a generic way to produce sets $S$ to enable SGD. Second, the paper investigates two specific settings, least-squares regression and median regression, and provides an algorithm with analysis and a matching (in terms of dependence on number of samples) lower bound.", "questions": "I understand the \"active labeling\" setting is general and well-motivated. Can the authors provide a realistic use case of the algorithmic contributions?\n\nI wonder if this paper would be better written as a privacy paper without mention of \"acquiring the most informative dataset\". In the privacy preserving setting, the \"streaming setting\" is very realistic (as the authors point out) and the arbitrary sets $S$ is realistic as a user's device can evaluate if $y_i \\in S$ (no need for human computation). As written, the paper's area and scope seem a bit scattered.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - This paper provides a nice, meaningful analysis of median regression in the \"active labeling\" setting.\n - The paper is overall clear and easy to understand (perhaps with the exception of Section 3 which I feel could be expanded).\n\nWeaknesses:\n - While the motivation for \"active labeling\" is compelling, the algorithmic contributions seem to require arbitrary sets $S$ while the compelling examples hinge on \"a specified set of subsets of $\\mathcal{Y}$ \". For example, the classification with attributes example does not allow all 2^{number of attributes} subsets to be queried. It appears that the construction of stochastic gradients in Section 3 almost requires arbitrary queries.\n - It seems to me that a concrete use case of the algorithm is not fleshed out. In most papers, the experiments section ensures this, but the experiments are quite synthetic (there is \"real-world\" data in appendix E but perhaps not a realistic query model).\n - I'm not sure the setting \"generalizes active learning based on partial supervision\" and furthermore, the \"streaming technique\" is in a rather different setting (requiring information from each point in the stream) compared to standard streaming active learning.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3aSiRauBid", "reviewer": "Reviewer_yumH", "summary": "The authors (re-)coins the term \"active labeling\" as a general case of Active-Learning where to the case of weak/partial supervision.\nDuring training, the proposed method requires access only to the (stochastic) gradients deduced from the annotation, which allows some degree of privacy preserving training if used in a streaming regime.\nSince the problem statement might seem too abstract, the authors provide three concrete real-life examples for partial annotation in lines 78-98.\nThe authors choose, however, to exemplify the approach for the specific case of (robust) median regression where the supervision partiality is half-planes.", "questions": "The median regression problem is indeed a worthy one.\nJust to gain some sense on the next steps - what is the gap to present results on one of the three examples (or any other similar real-life problem)? ", "limitations": "Even though the authors claim they state the limitations of their method in the discussion section, I did not find any that apply to the specific method in the text, but rather to the lager problem of active learning or continuous gradient based optimization.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is rigorous and very well written, even if some parts are too math-intensive than needed (e.g. lines 121-123 might be easier to understand with some context or more verbosity). \nThe theoretic section seems sound - I read through some of the proofs and did not find any corrections or mistakes.\n\nThis is a good paper, imho, so any weaknesses I will point our might seem superficial:\nAs mentioned, the examples in lines 78-98 really give motivation. However, the particular case that the authors chose to address (median regression) is a bit underwhelming in comparison, and a bit harder to apply to real-life. Even more so, I think any one of the three examples are easy to test by holding out data from open datasets (like imagenet).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept