Robust Sparsification via Sensitivity

We thank the reviewer for the questions. Below are our responses.

Not very new problem. For example, the outlier problem as proposed in Question 1.1 has been commonly studied, which can be
traced back to [RL87].

We agree that robust estimation [RL87] is classical work in the field. However, our work addresses the distinct and more recent challenge of constructing coresets for robust objectives. This specific problem of robust coreset construction is not addressed in [RL87], and the theory significantly lags behind that of standard (non-robust) coresets. Our paper makes novel contributions specifically to this direction.

Lack of novelty and more closely related papers should be referred. The paper [WGD21] also studies robust coresets for 
continuous-and-bounded learning, which already includes applications like regression, PCA, and clustering, as covered in 
submitted paper. They share some similar technical ideas.

We thank the reviewer for pointing out [WGD21]. We will add a detailed discussion comparing our work in the revised manuscript. There are crucial differences:

(1) The definition of a coreset in [WGD21] differs fundamentally from ours. Their coreset preserves the loss function within a ball, closer to the notion of a "weak coreset" in the literature. In contrast, a "strong coreset" preserves the loss function for all parameters, which is the standard, more powerful notion of a coreset in related work and is significantly harder to achieve in the robust setting. It also allows for arbitrary additional constraints in the optimization problem as it preserves the loss function for all parameters. Our work is the first to achieve this for a general class of loss functions.

(2) The approximation guarantee in [WGD21] requires relaxing $m$ (allowing more points to be removed than specified) or depends on an implicit problem-dependent parameter $\epsilon_0$. Our guarantee holds for the precise given $m$ without such a relaxation or hidden dependencies.

(3) While both [WGD21] and our algorithm use two stages, the techniques differ substantially due to the different definitions of coresets. The first stage of [WGD21] identifies all local potential outliers (with respect to a fixed solution), while our first stage identifies all global "contributing functions" (regardless of the solution) through a novel process that combines uniform sampling with sensitivities. While both methods use a vanilla coreset in the second stage, we introduce an additional sensitivity-flattening step to satisfy the requirements of a strong coreset, which is absent in [WGD21].

Therefore, while related in appearance, [WGD21] tackles a different (weaker) coreset definition with distinct techniques. Our work provides the first strong robust coreset for this general setting, marking a significant theoretical advance.

We thank the reviewer for the questions. Below are our responses.

This is a large running time when m  is large, and may prohibit realistic application of the algorithm to practical problems.

We acknowledge the exponential dependence on $m$. However, many existing robust algorithms, including practical ones like FastLTS or theoretical approaches, involve computations with worst-case complexities like $\binom{n}{m} = \exp(O(m\log\frac{n}{m}))$. Using our coresets, the runtime would become $\exp(O(m\log d))$ (assuming that $\epsilon$ is a constant). In typical large-scale scenarios where $n\gg d$ and $n\gg m$, this is a significant improvement in the base of the exponent.

 In the proof for Lemma 4.4, Line 212, why is the number of functions added not dependent on m?

The reviewer is correct to note the number of functions added in a single execution of Line 4 (Algorithm 3) does not explicitly depend on $m$. This line calls Algorithm 1, which adds functions whose sensitivity relative to the sampled set $B$ is at least $\epsilon/4$. By definition of total sensitivity, the sum of sensitivities is at most $T$, meaning at most $4T/\epsilon$ functions can satisfy this $\geq \epsilon/4$ condition. The threshold is $\epsilon/4$ to ensure that each contributing function (defined with $\epsilon/m$) is caught with sufficient probability ($1/(5m)$ as in Lemma 4.3), but the number of functions added in one execution of Algorithm 1 is bounded only in terms of $T$ and $\epsilon$. As explained above, the dependence on $m$ lies in the probability that each contributing function is captured, and this dependence enters the number of repetitions $R$ (Lines 2 and 3 of Algorithm 3).

Comparison with the paper "Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA, by I. Diakonikolas, D. Kane, A. Pensia, T. Pittas (ICML 2023)."

Yes, the reviewer is correct. The crucial difference is that Diakonikolas et al. (2023) achieve nearly-linear time by leveraging assumptions about the data distribution. Our work provides guarantees in the worst-case setting without such distributional assumptions, which inherently makes the problem harder and often necessitates complexities exponential in parameters like $m$ or $d$.

If possible, could you also comment on your current running time in terms of how optimal it is?

Regarding optimality for robust PCA: Simonov et al. (2019) established that no polynomial-time algorithm exists under standard complexity assumptions, suggesting that exponential dependency on some parameters is likely necessary for worst-case guarantees. They provide a lower bound of $m^{\Omega(k)}$ and an upper bound of $n^{O(d^2)}$. Our coreset construction takes $d^{O(m)}$ time. While not directly comparable to their upper bound (better for small $m$, worse for large $m$), plugging our coreset (size $\approx md$ assuming a constant $\epsilon$) into their algorithm improves their runtime dependence on $n$, yielding roughly $(md)^{O(d^2)}$. This significantly reduces the base compared to $n^{O(d^2)}$ when $n\gg md$. While there remains a theoretical gap between our exponential runtime and known lower bounds, our approach offers a concrete improvement over existing worst-case algorithms by mitigating the dependence on $n$.

We thank the reviewer for the questions. Below are our responses.

[1] also explores the robust coreset within a broader context. And their robust coreset also consists of a vanilla 
coreset and a sampling-based component of size $O(m/\varepsilon)$ (can be improved with bounded doubling dimension).
However, in their study, the coreset property only holds for local $x$. And it includes a relaxiation of $m$, which
aligns with the result in [2]. Regrading the generality of this paper, I am curious whether their work can be
incorporated into your framework as a special case.

[1] Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems. [2] Near-optimal Coresets for Robust Clustering.

We generally agree with the reviewer's comment on [1]. We note that the framework in [1] is based on assumptions that the loss functions satisfy the Lipschitz condition and the boundedness property, which are not assumed in our paper. Therefore, the two papers are not directly comparable. We also refer to our response to the second point of Reviewer YNPP for a detailed comparison.

From a practical standpoint, the robust coreset is less critical. This is because robust algorithms for optimization
problems with outliers often lack guaranteed approximation, leading to a reliance on heuristic methods for solutions. 
In such cases, compressing the data as a preprocessing step becomes less significant, particularly when the compression
method is relatively complex and time-consuming.

We understand the concern regarding practicality, especially when heuristics are common. However, our robust coreset offers a significant advantage: it enables the use of, or accelerates, algorithms on datasets previously too large. For example, as detailed in the appendix, applying FastLTS for trimmed least squares to the full dataset took 7.543 seconds. By using our coreset, sized at only approximately 2.7% of the original data, the same FastLTS implementation achieved good accuracy in just 0.4 seconds.

More generally, for computationally intensive algorithms with potentially prohibitive runtimes (e.g., scaling as $\binom{n}{m} = \exp(O(m\log\frac{n}{m}))$ in the worst case), we reduce the effective input size from $n$ to $O(md)$ (assuming $\epsilon$ is a constant), making these algorithms more feasible for larger-scale problems.

The effectiveness of the proposed algorithm depends on a bound of total sensitivity  T and a running time of sensitivity 
oracle t1. In other words, the algorithm is suitable for such problems that (1) total sensitivity is not large (2) The
time of computing sensitive is limited. Is there a large class of problems satisfying such condition besides the cases
presented?

While current prominent applications of sensitivity sampling focus on regression, PCA, and clustering, the framework itself is general. We emphasize that approximate sensitivities, rather than exact ones, are sufficient for coreset construction, making this approach adaptable to a wider range of problems where exact sensitivities might be intractable. Just as efficient algorithms were developed for approximating leverage scores, we anticipate similar progress for sensitivity estimation in other problems, and hope our work encourages such research by demonstrating the utility of sensitivity in the robust setting.

Line 098, “The total sensitivity of $\mathcal{F}$” should be “The sensitivity of $\mathcal{F}$” 
Line 159, “A function $f$ is” , missing “$\in A$" 
Line 217, $F$ in the Uniform() should be $A$ 

We agree with the reviewer on all these points. We will correct them in the revised version.

We thank the reviewer for the questions. Below are our responses.

this scheme is only compared with uniform sampling. I understand that core sets are carefully designed preferential 
sampling. So, are the results of such sampling better than those of random sampling?

We compared against uniform sampling as it is a standard and widely used baseline in the coreset literature. However, we acknowledge the reviewer's point regarding other sophisticated sampling methods. We will incorporate a comparison with leverage score sampling and a discussion in the revised manuscript.

The article assumes that the m to be removed is known. m is a parameter used to control the number of functions to be
removed, which has not been effectively discussed.

Our formulation assumes a given $m$, consistent with the standard definition of problems like trimmed least squares and much of the existing robust coreset literature. Determining the value of $m$ is indeed a different and challenging problem, often tackled with heuristics that lack the strong guarantees our coreset framework enables. This falls outside the scope of this work, which is focused on guaranteed approximation for fixed $m$.

relative error of the experiments in the appendix is slightly worse than that in the main text

We agree with this point. The observed difference in relative error is dataset-dependent. Specifically, the Emission dataset (appendix) is nearly 1.8 times the size of the Energy dataset (main text). Since we compared performance using coresets of similar sizes for both, it is understandable that the relative error would be slightly higher when applied to the much larger Emission dataset.

With the robust formulation, has the context of facility been satisfactorily solved? What I mean is that we often take
advantage of the loopholes in other people's theoretical research and continue to conduct theoretical research on the 
problem, but ignore the most real needs in the modeling process of this problem. Maybe this kind of theoretical 
research is not practical.

While constructing the coreset is a preprocessing step, it directly enables the application of robust algorithms to much larger datasets. For instance, established algorithms for trimmed least squares like FastLTS, while considered practically effective, have worst-case runtimes depending exponentially on $m$ and polynomially on $n$. Our coreset significantly reduces this dependency on $n$, replacing it with a much smaller $md$ (our coreset size is $O(md)$, assuming $\epsilon$ is a constant). This allows applying such robust methods (with their existing guarantees or practical performance) in large-scale settings where they were previously intractable.

Why was robust coresets first proposed under the condition of clustering? What are the essential differences between the 
PCA and regression promoted in this article and clustering?

We note that the concept of a coreset was first introduced by Har-Peled and Mazumdar in their seminal work as a tool for addressing clustering problems. Over the past two decades, coresets for clustering have received considerable attention, making it unsurprising that robust coresets were initially developed in this context. Our work provides a unifying framework for constructing robust strong coresets (guaranteeing approximation for all $x$) applicable to regression, PCA, and potentially clustering. To our knowledge, prior work on robust coresets for regression and PCA either did not exist or considered different, weaker definitions (e.g., local guarantees, like [WGD21], as discussed further in response to Reviewer YNPP) which do not provide the same level of worst-case theoretical guarantees as our strong coreset definition.

[WGD21] Zixiu Wang, Yiwen Guo, and Hu Ding. Robust and fully-dynamic coreset for continuous-and-bounded learning (with outliers) problems. Advances in Neural Information Processing Systems 34 (2021): 14319-14331.