Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The goal of this paper is to investigate a coreset approach for robust supervised learning specifically with outliers. The authors study this for logistic regression and k-means clustering. This paper is mainly theoretical and the empirical results are mainly in the appendix.
main_review: Pros:
a)	Paper provides an extensive theoretical study analyzing the robust coreset selection framework and proved a theorem stating that the proposed framework can successfully compute a (beta, epsilon) coreset.
b)	Provided experimental results show that the proposed coreset selection framework achieves better speedup and accuracy computer to other coreset selection methods.

Cons:
a)	The theoretical assumption of boundedness is too restrictive for deep networks. Hence, the proposed framework may not work well in a deep learning scenario. It would be nice to have some results using deep models even if the proposed method does not work so that others have an understanding of the limitations of the proposed approach.

b)	In the experimental section (in the appendix), the authors mentioned speedups and accuracies achieved. It would be interesting to know how many actual outliers the proposed framework was able to select or filter during training.

c)	The used coreset selection methods for experiments are simple. Hence, it would be interesting to know how the proposed coreset selection framework compare to other robust coreset selection frameworks like GLISTER (https://arxiv.org/abs/2012.10630), Coresets for Robust Training of Neural Networks against Noisy Labels (https://arxiv.org/pdf/2011.07451.pdf) and Grad-Match (https://arxiv.org/pdf/2103.00123.pdf)  in terms of speedups and accuracies. It would also be interesting to find if the proposed approach can also be applied with the above-mentioned robust coreset selection methods.

d)  The major limitation of this work is the lack of solid experiments. I would have expected more empirical results particularly given the nature of the problem and not have the experiments relegated to the Appendix. I would encourage the authors to discuss how their approach compares to other subset selection and coreset approaches for robust learning (like those mentioned above).

Post Rebuttal Update:
The authors have clarified a few of the issues pointed out. However, a major criticism of this work is the lack of experiments. This, in my opinion, can be a limiting factor for the impact of this work, mainly because a lot of work in this area is empirical and an understanding of how an approach like this performs empirically is critical in understanding its place among the state-of-the-art. However, I do think this paper contributes from a theoretical perspective, and I'll keep my score of weak acceptance. I would strongly encourage the authors to add empirical evaluation in the main text if given a chance.
limitations_and_societal_impact: This paper is mainly theoretical.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies coresets for continuous-and-bounded learning problems. In the optimization version of the problem, given a weighted input data set X with weight w : X \to \mathbb{R}_+, the goal is to find a parameter \theta in some parameter space P such that \sum_{x \in X} w(x) \cdot f(\theta, x) is minimized where f : P \times X \to \mathbb{R}_+ is a cost function. Furthermore, the continuous-and-boundedness condition requires that the parameter space P form a metric space (so there is an implicit associated distance function on the parameters), and that a) there exist l, \alpha > 0, such that all parameters in P are contained in a ball of radius l, and b) f(\cdot, x) is \alpha-Lipschitz.

An \epsilon-coreset for this problem is defined as a weighted subset S \subseteq X of the data set with weight u : S \to \mathbb{R}_+, such that for every parameter \theta \in P, the total cost on S is close to that on X, i.e., \sum_{x \in S} u(x) \cdot f(\theta, x) \in (1 \pm \epsilon) \sum_{x \in X} w(x) \cdot f(\theta, x). 

The paper also studies coresets for the outlier version of the problem, where we are additionally given a parameter z (the number of outliers) and the cost becomes f_z(\theta, X) = \min_{O \subset X, |O| = z} f(\theta, X \setminus O). Coresets are defined similarly for the outlier version, except that this paper allows bi-criteria guarantee: a (\beta, \epsilon)-coreset preserves the cost for every \theta, such that the cost is within [f_{(1+\beta)z}(\theta, X), f_{(1-\beta)z}(\theta,X)] (the exact definition is subject to proper normalization).

Several results are presented. For the outlier version, the first result shows that uniform sampling yields a (\beta, 0)-coreset of size \tilde{O}(n / (\beta z))^2, provided that the VC-dimension for the (metric ball) range space induced by {f(\cdot, x) : x} is bounded. This result is weak and is inadequate for small z (even for moderately small z = O(\sqrt{n})). The second result is more interesting and it gives a reduction that reduces the outlier version to the non-outlier version. Intuitively, it “glues” a black-box coreset for the non-outlier version and a uniform sampling based coreset. Specifically, it yields a (\beta, \epsilon) coreset of size T + min{ O((\beta\epsilon)^{-2} vcdim), O(z / epsilon)}, where T is the size of some \epsilon-coreset in the non-outlier setting, and vcdim is the VC-dimension for the range space induced by {f(\cdot, x) : x}. The paper also gives a fully-dynamic algorithm that maintains the “glued” coreset.

Besides, two coreset results for the non-outlier version are presented. The first one is based on the well-known importance sampling framework [11], but instead of analyzing the VC-dimension of the range space, this paper shows that the VC-dimension term could be replaced by the doubling dimension of the parameter space P. However, the authors were not able to give an upper bound for the total sensitivity, and therefore this first result does not yield an explicit coreset size bound. Then the other result is based on a spatial partition method proposed in [9], which helps to gets rid of the total sensitivity bound, but it introduces a log n factor.

main_review: Originality & significance:

The main novelty is the initiative of a unified framework for coresets for continuous-and-bounded learning with outliers. The main result which reduces the outlier version to the non-outlier version is novel, and I do think this reduction seems to be strong enough to imply interesting new bounds for concrete instances of continuous-and-bounded learning problems. Unfortunately, authors did not give any such examples, which makes me uncertain about the usefulness of this new unified theory. In particular, the theorem requires the VC-dimension of the f-induced range space to be bounded – can you show an interesting example of continuous-and-bounded learning problem that has VC-dimension bounded? It also makes it hard to tell whether this result can improve previous works without such examples.

An additional comment is that, your coreset is bi-criteria for the outlier problems – is the violation in the number of outliers necessary? Can you possibly justify this?

As another contribution, several coreset constructions for general continuous-and-bounded learning (without outliers) are given, and all of the proposed coresets depend on the doubling dimension of the parameter space. But I’m not sure if considering doubling dimension on the parameter space makes sense – indeed, doubling dimension is an intrinsic dimensionality measure, but it is usually applied on data set instead of parameter space. In fact, parameter space is data-independent and usually depends on the problem itself, which does not seem to benefit from low intrinsic dimension.

Technically, many results are obtained by combining existing techniques in a straightforward way, and I don’t see much novelty. For instance, the dynamic algorithm follows almost immediately from previous works, and it doesn’t add much to the paper; also, the two coresets for non-outlier version of the problem are very much standard and follows from previous framework with only minor modifications.


Quality:

I think the paper is technically sound, and all major claims are reasonably supported by proofs. However, a key missing part of the paper is some concrete applications of the unified theory – maybe some new bounds for specific learning problems? Or experiments that validate the theory in a certain way? (I do see some experiment results were reported in the supplementary, but unfortunately the findings of the experiments are not discussed in the main text at all.) This would make the theory more useful to the machine learning community.

Clarity:

The paper is overall very well written. It does a good job to provide necessary information for (at least expert) readers to understand why each claim holds, without needing to read proofs.

Other comments:

1.	Line 31 “noise” -> “noisy”
2.	Line 61 should be “continuous-and-bounded”
3.	In Definition 2, why use a different font for f? In general, please make sure you use the font consistently (which seems not the case in the paper).
4.	In Definition 4, why do we need the assumption that \mathcal{X} is a metric space? I don’t think you need this.
5.	Line 164, what do you mean by “\delta-approximate subset”? I didn’t find the definition.
6.	Line 165, the use of O in “O = ab” seems not a good idea, since O is usually used as in the big O notation.
7.	Line 168, what is Y?
8.	Theorem 2, line 223, what’s the third parameter 2\xi(l)? I think the notation only has two parameters?
9.	Line 228, can you explain why f_z(\theta, C) = f(\theta, C_I + C_{II})? In particular, why don’t we need C_{III} and C_{IV}?
10.	In the statement of Theorem 3, the VC dimension should be a uniform upper bound for weighted range spaces over all weights.
11.	In the statement of Theorem 4, line 321, you mentioned the hidden constant depends on \inf_{\theta} f(\theta, X) – why this is bounded?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents an approach for constructing outlier-resilient coresets for continuous-and-bounded learning problems, which include logistic regression and k-means clustering. The authors build on recent work in dynamic coresets so that the constructions can be maintained in a fully-dynamic setting where input points can be inserted, deleted, and updated. The main idea of the outlier-resistant approach is to partition the original data set into two sets: one consisting of suspected outliers and the other for the “inliers.” For the outliers, the authors sample uniformly at random, and for the inliers, an existing coreset construction is used; these two subsamples are then merged to generate the outlier-resistant coreset. Under the assumptions of continuous and bounded learning, the authors also outline general QP-based and spatial-partition based methods to construct coresets.
main_review: Strengths

- The authors tackle an interesting and relevant problem of constructing coresets in the context of outliers. I also appreciate their effort in trying to make their approach as widely applicable as possible to common optimization problems and scenarios in large-scale machine learning.

- The technical results of the paper seem sound to the best of my knowledge.

- Although the approach of partitioning the input set and sampling from each set separately is not new in importance sampling (cf., stratification [2]), I found its application to outlier-resistant coresets to be interesting and novel.


Weaknesses

- The paper is quite dense and the organization and exposition could use improvements. Crucial details in certain parts of the paper (see comments regarding QP & SDP below) are not provided at all or deferred to the supplementary, but yet proofs of technical results (e.g., Lemma 2, Theorem 1, and Theorem 2) are provided inline -- taking up almost 2 pages total in the main paper. To me, this seems to distract from the flow of the paper, and also leads to important omissions. For example, the (only) empirical results of the work can only be found at the end of the supplementary material and additional details regarding the implementation of the method in practice are not provided (e.g., for a given sample size as in Sec. D of the supplementary, what $\varepsilon$ is used for the hybrid approach?). I would suggest deferring some of the technicalities to the supplementary in order to make room for further clarifying text around the main ideas and the experimental results (currently in Sec. D of the supplementary).

- Computing the sensitivities as described in Sec. 4.1 requires a reduction from a fractional Quadratic Program (QP) to a Semi-definite Program (SDP), with an overall running time of $O(n \text{poly}(d))$. Solving an SDP for every single point to compute the sensitivity upper bound seems to be highly costly in practice. Moreover, no details of how the sensitivity can be bounded via a QP formulation and SDP reduction are provided in the supplementary (despite the promise of additional details in Lines 307-310). Overall, I have difficulty seeing the added benefit of the sensitivity bounding approach presented in Sec. 4.1 relative to existing techniques for those specific problems (e.g., [3]). This also seems disjointed given the context of outlier-resistant coresets. Given the iterative SDP requirement, I am not sure how to make sense of the speed-up claims of up to $\approx 250$ in Fig. 4(c) (in the supplementary) relative to “training logistic regression on the original data” given that logistic regression training is quite efficient in practice and theory (e.g., via a gradient-based method).

- Relatedly, I am unclear about the connection to the GEL algorithm and why it is presented in conjunction with the QP-based method. Could we not bound the sum of sensitivities assuming that we have the optimizer for the sensitivity expression in Eq. 19 to obtain a data-independent upper bound on S? It seems to me that leaving the sum of sensitivities to be data-dependent and then theoretically bounding this quantity would yield better practical performance than an alternative approach that, in a sense, forces this sum to be data-independent. The sampling complexity of Theorems 4 and 5 also ignore factors $\alpha$ and $\inf_{\theta \in \mathcal{B}} \mathbb{f}(\theta, X)$, and it is not immediately clear to me when the bound would be vacuous: e.g., what happens if $\inf_{\theta \in \mathcal{B}} \mathbb{f}(\theta, X) \approx 0$?

- A more thorough discussion of the sampling complexity of Theorem 2 relative to that of related work in coresets with outliers would be illuminating (e.g., those of [1]).

- Lack of experimental details: the method requires knowing epsilon and $\tilde \theta$, among other hyperparameters that are required by the proofs and technical results. Yet, these values are not reported for the evaluations in the paper, and from the point of view of a practitioner, I am left confused as to what $\tilde \theta$ should be or how I would obtain it in practice. How were the results in Fig. 4 generated given a specified sample size?

- The experiments do not compare to prior work in coresets with outliers (e.g., [1]), among other related work that was cited in the introduction. Moreover, no computation time figures are reported for the offline setting, which makes it difficult to conclude that the proposed outlier-resilient approach leads to more accurate models (efficiently) in practice. Fig. 4(c) of the appendix reports the speedup in the dynamic setting as a function of the merge-and-reduce tree height, but only for the enhanced methods (with an “+” appended). It would have been illuminating to see computation time (x-axis) vs. normalized accuracy for the compared methods (similar to Fig. 4(b)). A discussion of why Uniform+ outperforms competing approaches in terms of the computational speedup (while performing on par with the coreset-based approaches) in Fig. 4 would be insightful.


Overall, I find the paper interesting and technically rigorous. However, I have qualms about the clarity and exposition of the paper and the practical merits of the proposed approach relative to prior work. At times, I felt like the paper tried to achieve too many things at once and some of the contributions seemed either disjointed or weren't well-motivated or emphasized (e.g., Sec. 4). I would suggest a clearer exposition in light of the comments above and more rigorous empirical evaluations that appear in the main paper.

[1] https://arxiv.org/pdf/1804.02530.pdf 

[2] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf

[3] https://proceedings.neurips.cc/paper/2018/file/63bfd6e8f26d1d3537f4c5038264ef36-Paper.pdf 

limitations_and_societal_impact: Please discuss limitations and potential negative societal impacts in Sec. 5 as reported in the Checklist.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work provide coreset construction framework for functions that are Lipschitz continuous, smooth, and has Lipschitz continuous Hessian. The coreset in this paper is robust, i.e., it aims to handle outliers such that the coreset will be less biased than traditional coreset schemes.
main_review: I enjoyed reading the paper, which suggests a robust coreset construction framework for multiple problems such like logistic regression and k-means clustering. The coreset uses sensitivity sampling for inliers, and $\delta$-sample for outliers. The ideas in this work are not trivial and the paper is well written, however I have some comments :
1) Line 177, what do you mean by "not integral"? did you mean integer?
2) I suggest moving the graphs to the paper. The graphs at supplementary material presents your efficiency against multiple candidates of coreset construction schemes.  
3) I noticed some missing definitions, for example, in Theorem 1, line 168, what is Y? I did not completely understand the proof because of missing definitions in this Theorem.
4)Shouldn't the upper bound in Lemma 2 include $5 \epsilon$ instead of $3 \epsilon$ ?

limitations_and_societal_impact: The authors adequately addressed the limitations, i.e., the coreset in this paper handle bounded learning (the candidate solution set for the problems discussed in the paper is bounded)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper suggests a coreset construction framework for a family of functions that are Lipschitz continuous, smooth, and has Lipschitz continuous Hessian. The framework considers only continuous-and-bounded learning, i.e., optimization problems concerning bounded space of candidate solutions.
main_review: The paper suggests a robust coreset construction framework for several problems, including logistic regression and $k$-means clustering, under the umbrella of continuous-and-bounded learning. The method entails sensitivity sampling for "inliers" while using $\varepsilon$-sample for "outliers" to obtain a robust coreset. The ideas are interesting in nature and the work is not trivial.

I enjoyed reading the paper and the results are sound yet there are some misclarifications. Due to time constraints, I have managed to go over some of the proofs and they were sound other than the proof of Theorem 1 and Lemma 2; see my comment section below.

Comments:
- What is $Y$ at Line 168? It seems that $Y$ is the set $B$.
- There is an additional "s" at Line 300.
- It is very interesting that the sensitivity can be solved using quadratic fractional programming via a relaxation towards semi-definite programming. My question is, what is the total sensitivity in this case? what is the exponent in the $\mathrm{poly}(d)$ term at the time complexity?
- At Lemma 2, the bounds are not tight since the coreset is a robust coreset. This means that some of the transitions need to involve an additional multiplicative term of $O(1\pm\varepsilon)$. This is due to the fact that you end up dividing the sum of weights of instances of $C$ by the number of points in $X$. Through the literature of $\varepsilon$-coresets, and robust coresets as well, this term is in the range of $\left[ 1-\varepsilon, 1+\varepsilon\right]$.
- The proof of Theorem 1 is not clear as some of the transitions are not clear (see my first comment)
- Some of the coresets that you have mentioned handled instances of the problems that the paper discusses, e.g., logistic regression. However, I believe that the related work can be further enhanced, e.g., "Coresets for Near-Convex Functions" which proposes a unified framework for coreset construction for various loss functions including logistic regression, SVMs, and even robust $\ell_p$-regression. Using this paper as a black box to bound the sensitivity, how well your model will perform in terms of normalized loss error?
- Please move some of the graphs to the main manuscript to further enhance your results in the paper.



limitations_and_societal_impact: One of the limitations of this work is that it handles bounded learning. It is interesting to show that under the umbrella of robust coresets, such limitation is somewhat necessary. Please provide a brief explanation of why it is not possible to remove such limitation, or where exactly in your method (or analysis), the necessity of this assumption is crucial? 

In addition, Theorem 4 imposes an additional limitation. Specifically speaking, the total sensitivity that is being squared at the sample size. In recent works, e.g., "On coreset for Logistic Regression" and "Coresets for Near-Convex Functions", the total sensitivity was bounded from below $\Omega\left(\sqrt{n}\right)$ . This means the sample size in your case is $\Omega(n)$. I wonder if the total sensitivity that is obtained using your method is much smaller than the bounds achieved in the papers above due to the bounded learning assumption. Please briefly discuss this.
review_title: null

Meta-review: This is a beautiful paper about coresets for handling outliers which will probably inspire many future related papers.
While there are concerns regarding experimental results (that are hidden in the supp. material), the theoretical contribution with an algorithm that it is not hard to implement is strong enough for such a fundamental problem in machine learning.
Please move some more experiments to the main paper in order to attract the practitioners.

Also please add the following references and maybe some more:
https://www.mdpi.com/1999-4893/13/12/311
https://dl.acm.org/doi/10.5555/1347082.1347173

Decision: Accept (Spotlight)