Batch List-Decodable Linear Regression via Higher Moments

We thank the reviewer for their effort and positive assessment of our work. We reply to the points mentioned individually below:

(Applicability of the SoS-certifiability Assumption) SoS certifiability of moments is by now a well-studied condition that is known to hold for broad families of interest such as sub-Gaussian distributions and all distributions satisfying the Poincare inequality. Please see our response to Reviewer ez6k on this.

(Comparison of runtime with Das et al. 2023) As discussed in lines 91-107, the runtime of Das et al. 2023 is $\mathrm{poly}(d,n,m,1/\alpha)$. Their theorem statement does not specify what is the absolute constant in the exponent of that runtime. In comparison, our algorithm is also polynomial time but the parameter $k$ appears in the exponent (order of the higher moment information used) instead of just an absolute constant.

(Quasi-polynomial runtime for very small batch sizes) It is indeed true that the algorithm is no longer polynomial-time when the batch size becomes very small (e.g., when $k$ is on the order of $\log^2(1/\alpha)$). As discussed after the main theorem statement (lines 115–131), there is evidence (based on previously known Statistical Query lower bounds from Diakonikolas et al. 2021) that this phenomenon is inherent. We view this as an interesting conceptual conclusion: The tradeoff between complexity and batch size appears to be smooth. Specifically, for $n = 1/\alpha$, the complexity of our algorithm matches the previously known algorithm of Das et al., 2023, while for $n = \log^2(1/\alpha)$, it matches known SQ hardness results. In the intermediate regime, our results suggest a continuous interpolation rather than a sharp phase transition at a specific point.

We thank the reviewer for their time and the positive evaluation of our paper. We respond to the points raised individually below:

(Assumptions on $X$) The SoS certifiability of moments is a well-established condition, known to hold for various important distribution families, including sub-Gaussian distributions and those satisfying the Poincaré inequality. Please see our response to Reviewer ez6k for more details.

(Sample and Time Complexity) There is a tradeoff between the batch size and the complexity of the algorithm: Before this work, we only knew that for batch size $n=1$ the problem exhibits exponential complexity hardness results and for $n=1/\alpha$ it becomes feasible in polynomial time, but we did not know anything in between: Is the complexity interpolating in a smooth way or there is some phase transition phenomenon? One of the main goals of this paper is to quantify this tradeoff and show that it is indeed smooth, which we view as an interesting theoretical insight. As explained in lines 114-131 (first column) although this tradeoff means that for extremely small delta the algorithm becomes efficient, this matches the prior known SQ lower bounds, thus in this sense, this behavior is unavoidable. Moreover, there is a wide range of regimes where the algorithm is efficient. For example setting $\delta$ to be a constant like $¼$, already gives a polynomial time algorithm that works only under 4-th bounded moment distributions and has better error guarantee than prior work (any algorithm before our work would either have larger error or run in exponential time).

(Technical contributions) One of our main technical contributions is a novel pruning procedure to reduce the candidate list size to $O(1/\alpha)$. This procedure is optimal, and uses techniques that differ significantly from prior work. The procedure is critical for the success of the iterative algorithm as the number of candidate lists will grow exponentially with the number of iterations without pruning. Moreover, although robust mean estimation using SoS is by now a standard tool, our work requires a novel iterative framework where each iteration improves the accuracy of the estimators. Lastly, in order to apply the result from Kothari & Steinhardt (2017), we need to show that the fact that the covariate has certifiably bounded moments implies that the regressor estimator we use also has SoS certifiably bounded moments, which is technically non-trivial. Finally, in order to apply SoS robust mean estimators for the variable $yX$ we need to ensure certifiability of moments, for the purpose of which we prove an SoS version of the famous Marcinkiewicz Zygmund Inequality, that might be useful independently of the result of this paper.

(Motivation of Studying Batch-size in Robust Statistics Tasks) Once again, we would like to emphasize the importance of studying the role of batch size in robust statistics. While the common assumption in robust statistics is that an arbitrary subset of data points (with a certain size bound) is corrupted, in the crowdsourcing setting, adversarial corruption naturally happens at a user-level, leading to corrupted batches of data instead of corrupted data points. As shown in Diakonikolas et al. (2021) and Das et al. (2023), such batch structure in corruption may lead to drastic change in the computation landscape of the statistical estimation task, and we believe it is a natural as well as important research direction to explore the quantitative relationship between batch size and other algorithmic resources needed in robust estimation tasks. Our work is the first revealing a smooth quantitative tradeoff between batch sizes and the computation/statistical resources needed for the concrete application of list-decodable linear regression.

On the practical side, we believe that optimizing the batch-size is crucial to any crowd-sourcing setting. In particular, if only 1% of users were reliable, prior work would roughly require one of the following: Either each user provides one data point, but the learning algorithm has exponential complexity Karmalkar et al. (2019), or (ii) each user will have to contribute at least $100$ data points Das et al. (2023) (which may well be unrealistic). On the other hand, we give an efficient algorithm that succeeds with much fewer data points per user; prior to our work, it was not clear if this is even possible in polynomial time. In particular, even if we use only the first $k=4$-th order of moment information, our algorithm will have already improved upon the prior work with substantially smaller batch sizes and achieved better error. We thus view our work as an important first step towards building practical algorithms for smaller batch sizes.

We thank the reviewer for their time and positive assessment of our work. We respond to their points below:

(Distributional assumptions) The condition of having SoS certifiably bounded moments is standard (in the algorithmic robust statistics literature) for leveraging higher-order moment information in the algorithm. This condition holds for all distributions satisfying the Poincare inequality (Kothari & Steinhardt (2017)), which results in a large family of distributions: it includes Gaussians, product distributions, strongly log-concave distributions, and any sum or uniformly continuous transformation of such distributions. There are also other non-Poincare distributions with SoS certifiably bounded moments, i.e., distributions over discrete points sampled from Gaussians. Moreover, via recent results (Diakonikolas et al. (2024) cited at the end of this rebuttal), it is known that the class of all sub-Gaussian distributions also satisfies the SoS certifiably bounded moments condition. Finally, regarding practicality, if having bounded $k$-th moments for very large $k$ is viewed as unrealistic in practice, we point out that even if we use only the first $k=4$-th order of moment information, our algorithm will have already improved upon the prior work with substantially smaller batch sizes and achieved better error. We thus view our work as an important step towards building practical algorithms for smaller batch sizes.

(Experimental evaluation) While we acknowledge the reviewer's interest in experiments and the importance of developing practical algorithms, we would like to emphasize that our primary contribution is to characterize the computational-statistical landscape for this fundamental learning task—in terms of error guarantee, batch size complexity, and batch number, and the tradeoff between them. That being said, there are practical regimes (like $k=4$) where we already get improved error compared to Das et. al. 2023 in poly-time and any other previously known alternative for the same error would require exponential runtime.

References:

Diakonikolas, Ilias, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel. "SoS certifiability of subgaussian distributions and its algorithmic applications." arXiv preprint arXiv:2410.21194 (2024).

We thank the reviewer for their time and effort in reading our paper. We respond to the points raised individually below:

(Tradeoff between batch size and algorithm complexity is not discussed) There indeed is a tradeoff between batch size and algorithm complexity. However, this is not a hidden aspect of the result. Rather, it is explicitly stated, and it is part of the conceptual take-away point of the paper. We reiterate the main points below for completeness: The tradeoff is clearly presented in Theorem 1.3, where all parameters (batch size, number of batches, and runtime) are formally stated. Specifically, the batch size $n = \Omega_{\delta}(\alpha^{-\delta})$ and the number of batches $m = \text{poly}((nd)^{1/\delta}, \alpha^{-1})$, referenced by the reviewer, are explicitly given there. The tradeoff is discussed in detail directly after the theorem (lines 93-131). Specifically the discussion paragraph states “Our result essentially shows that there is a smooth tradeoff between the batch size provided and the computational resources required”. The subsequent text points out that if the parameter $\delta$ is superpolynomial then the algorithm is no longer efficient and that there is evidence in the form of known Statistical Query lower bounds, (discussed further in Appendix F) suggesting that this tradeoff is unavoidable. Quantifying this tradeoff is part of the main conceptual contribution of the work: On the one hand, SQ lower bounds from Diakonikolas et al., 2021 suggest that the problem is hard for batch-size equal to one; while Das et al. (2023) gives an efficient algorithm when the batch-size is $\approx 1/\alpha$ (see lines 69-81). It is natural to ask what happens in between (lines 91-97). Is there a sharp phase transition (in terms of the existence of a poly-time algorithm) when the batch-size goes from constant to linear in $1/\alpha$ or does the tradeoff happen smoothly? Our result suggests the latter: when the batch-size is $1/\alpha^c$, for $c>0$, there exists an algorithm using $O(1/c)$-degree SoS to achieve a small error for the task (lines 112-131). If the reviewer’s concern stems from our use of the term “efficient”, such as in lines 104–108 (“Is there a computationally efficient algorithm […] with improved batch size and/or error guarantees?”), we clarify that “efficient” there refers to poly-time algorithms in general, which is the standard convention in the learning theory literature. This does not imply the absence of trade-offs within the space of poly-time algorithms. If this was the source of confusion, we will revise the phrasing to ensure this distinction is explicit.

(Clarifications on the algorithmic approach) We respond to the specific questions below:

• (Which mean estimation framework is being used?) As stated in line 166 of our paper, either Theorem 5.5 from Kothari & Steinhardt (2017), or Theorem 6.17 from Diakonikolas & Kane (2023) suffices for our purpose of list-decodable mean estimation. In general, any list-decodable mean estimation algorithm satisfying the guarantee in Lemma 3.5 suffices for our purpose, and the exact implementation is not important for our algorithm.
• (“It is not true that there exists no multi-filter framework using high-moment information. Actually, the very beginning of the multi-filter framework proposed by Diakonikolas et al. 2018 already considered higher moments”). The proof strategy in Diakonikolas et al. 2018 requires exact Gaussianity of the data (also listed in the their theorem statement). The subsequent work of Diakonikolas et al. 2020 was able to adapt the proof strategy for the case of just bounded covariance data but it did not extend for higher moment boundedness. We refer to Chapter 6 of the book Diakonikolas & Kane (2023) where the difficulties of using higher information is described. To the best of our knowledge SoS based algorithms are the only ones that work with higher moments beyond Gaussian distributions. Thus, we apply an SoS list-decodable mean estimation to the regressor estimator $\frac{1}{|B|}\sum_{(X,y) \sim B} Xy$. Even if $X$ were Gaussian, this estimator would not be, making Diakonikolas et al. (2018) inapplicable. To address this, we show SoS certifiability of the moment bounds by deriving a novel SoS proof of the Marcinkiewicz-Zygmund inequality that may be of independent interest. Finally, we highlight that the biggest difficulty in our paper is not finding the right algorithm to apply as a black-box but the subsequent issue that applying this algorithm iteratively may result in a number of hypotheses that blows up (see the paragraphs after line 194). Making that iterative framework work is where our novel pruning procedure is used. This procedure is optimal, and uses techniques that differ significantly from prior work of Diakonikolas et al. 2020.

I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. STOC 2018.