Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
- Quality: The proposed method is novel and supported by extensive theoretical analysis and proof-of-concept numerical simulation.
- Clarity: This paper is well-written with minor flaws.
- 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.
questions: - The weak information can give an unbiased gradient estimation. How about the variance?
- 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?
- 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?

Misc
- Line 115: Typo, "we aim at to minimizing" -> "we aim to minimize"
- Line 253: Typo: "ot" -> "to"
limitations: The authors discuss their limitations in the paper and point out several future directions.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
 - This paper provides a nice, meaningful analysis of median regression in the "active labeling" setting.
 - The paper is overall clear and easy to understand (perhaps with the exception of Section 3 which I feel could be expanded).

Weaknesses:
 - 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.
 - 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).
 - 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.

questions: I understand the "active labeling" setting is general and well-motivated. Can the authors provide a realistic use case of the algorithmic contributions?

I 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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. A newly proposed ``active labeling'' problem looks interesting and important.
2. The authors provide an algorithm to handle the proposed problem under median regression, and prove its minimax optimality in the kernel/linear case.

Weakness:
1. 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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors (re-)coins the term "active labeling" as a general case of Active-Learning where to the case of weak/partial supervision.
During 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.
Since the problem statement might seem too abstract, the authors provide three concrete real-life examples for partial annotation in lines 78-98.
The authors choose, however, to exemplify the approach for the specific case of (robust) median regression where the supervision partiality is half-planes.
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). 
The theoretic section seems sound - I read through some of the proofs and did not find any corrections or mistakes.

This is a good paper, imho, so any weaknesses I will point our might seem superficial:
As 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).
questions: The median regression problem is indeed a worthy one.
Just 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.
review_title: null

Meta-review: metareview: This paper studies “active labeling”, which can be seen as active learning with weak supervision, and proposes an active labeling algorithm based on SGD. The reviewers found that the idea of this paper is innovative. After author response and reviewer discussion, the paper receives generally unanimous support from the reviewers. Thus, I recommend acceptance. 
confidence: Less certain
Decision: Accept