acceptodds
Under review as a conference paper at ICLR 2027

Uniform Spectral Bounds under Data-Dependent Sample Selection

Abstract

Concentration inequalities for sample covariance matrices are fundamental tools in high-dimensional probability. However, data-dependent sample selection prevents direct application of classical covariance concentration bounds. In this paper, we study the extreme eigenvalues of covariance matrices formed from arbitrary, possibly data-dependent subsets of random vectors. For i.i.d. Gaussian vectors, we establish simultaneous lower and upper bounds over all subsets satisfying prescribed cardinality constraints. The bounds depend explicitly on the retained proportion through central and tail-trimmed second moments, with finite-sample slack and complementary constructions establishing limiting tightness. We extend the results to sub-Gaussian vectors under additional distributional assumptions and obtain lower bounds for geometrically strong-mixing Gaussian sequences. For -subspace clustering under a low-rank Gaussian mixture model, we show that the clustering error of every global minimizer decreases polynomially with the signal-to-noise ratio under explicit sample-size conditions. For Gaussian robust regression, our analysis strengthens the uniformity of covariance and gradient-moment guarantees while improving the sufficient sample bound from to at constant confidence.

Primary area:
optimization
Keywords:
Concentration Inequality, Covariance Matrix, Arbitrary Subset, K-subspace clustering

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_HQf9OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies uniform spectral bounds for covariance matrices formed from arbitrary, potentially data-dependent subsets of random vectors. For i.i.d. Gaussian vectors, it derives simultaneous lower and upper bounds on the extreme eigenvalues in terms of trimmed Gaussian second moments, together with complementary constructions establishing limiting tightness.

The framework is further extended to sub-Gaussian vectors under additional assumptions and to stationary geometrically strong-mixing Gaussian sequences, where a uniform lower spectral bound is obtained. Applications to K-subspace clustering and Gaussian robust regression are also presented.

Critical strengths
  • Well-motivated problem setting: The paper addresses an issue that arises when the selected subset depends on the same data used to form the covariance matrix. The simultaneous nature of the bounds makes them applicable to optimization with data-dependent selection.

  • Coherent theoretical framework and presentation: The Gaussian bounds are expressed through explicit trimmed-moment curves and accompanied by complementary tightness constructions. The progression from i.i.d. Gaussian data to sub-Gaussian and temporally dependent observations, followed by applications, gives the paper a clear overall structure.

Critical weaknesses
  • Limited novelty of the main Gaussian result relative to prior work: Han and Xu already establish the correct κ3\kappa^3 scaling for the lower spectral coefficient under arbitrary erasures, with better small-κ\kappa sample dependence. The present paper contributes explicit trimmed-moment curves and limiting tightness constructions, but it is not clear to me that these refinements constitute a sufficiently substantial advance over the existing correct-order results.

  • The experimental section appears incomplete. Appendix D explicitly states that the parameter reconciliation is pending and that the reported experiment has not yet been verified. In addition, the reported SNR values appear inconsistent with the stated subspace affinity.

Questions for authors
  • Beyond providing the explicit curves, what substantive gain does the main theorem provide over existing results with the correct κ3\kappa^3 scaling? Are the exact curves essential for any of the applications?

  • It would be helpful to add citations directly when introducing the LRGMM and the K-subspace formulation, rather than only discussing related work later.

4 comments

Thank you for these comments. We have revised the manuscript; the corresponding changes are marked in blue.

1. Beyond explicit curves: improved sample dependence.

We have sharpened Theorem 1 from the submitted κ−6\kappa^{-6} sufficient sample dependence to κ−1\kappa^{-1}, up to logarithms, while preserving the lower spectral coefficient. Section 2.1 (Eqs. (7)–(8)) now states

M≳ηκ−1[mlog⁡(Cη/κ)+log⁡(1/ρ)]M\gtrsim_\eta\kappa^{-1}[m\log(C_\eta/\kappa)+\log(1/\rho)]

for fixed slack 0<η<1/20<\eta<1/2. This improvement concerns sample complexity and is distinct from the already known κ3\kappa^3 order of the lower spectral coefficient. Under the same Gaussian model and normalization, Han and Xu's full-sparsity specialization of Corollary 1.6 gives the sufficient condition M≳κ−3[m+log⁡(1/ρ)]M\gtrsim\kappa^{-3}[m+\log(1/\rho)]. We have updated this quantitative comparison in Section 2.1 and Appendix A.

The new Lemma 1 in Appendix F.1 sets p=(1−η)κp=(1-\eta)\kappa, Y=Z21{∣Z∣≤qp}Y=Z^2\mathbf1_{\{|Z|\le q_p\}}, Z∼N(0,1)Z\sim N(0,1), qp=Φ−1((1+p)/2)q_p=\Phi^{-1}((1+p)/2), and μ=EY=b(p)\mu=\mathbb EY=b(p). It proves EY2≤3μ2/p\mathbb EY^2\le3\mu^2/p, hence

\le e^{-\eta^2pM/6}.$$ Appendix F.2 derives the new sample bound using the existing net argument, preserving $(1-\eta)^2b((1-\eta)\kappa)$. The downstream clustering sample condition has also been updated in Theorem 5, Eq. (30). We have added Haddock et al., *Quantile-based Iterative Methods for Corrupted Systems of Linear Equations* (2022), and explicitly acknowledged that its Proposition 1 already achieves inverse-fraction sample dependence under its assumptions (Section 2.1; Appendix A). We claim the full central/tail curves and complementary limiting constructions together with the refined finite-sample lower guarantee, without claiming the inverse-fraction order itself as new. > **2. Role of the exact curves.** The order-level clustering guarantee only needs $b(\tau)\ge c\tau^3$; Appendix H.5 derives the retained conservative SNR rate from this bound. The full curve enters the explicit recovery thresholds in Theorem 5, Eqs. (27)–(30). Appendix D now evaluates these thresholds numerically. We have also specified the Gaussian concentration constants and added a separately calibrated spectral example with confidence exceeding $0.999$ (Section 2.1, Eq. (15); Appendix B.1). The original figures remain coefficient illustrations. > **3. Experimental validity and SNR.** We have replaced the unverified Appendix D table with a new experiment and explicit condition checks. Revised Theorem 5 applies to every feasible candidate satisfying $\widehat F\le F^\star+\Delta$, where $F^\star$ is the objective at the true model. The bound $S\le4W+2\Delta$, with noiseless residual $S$ and total noise energy $W$, removes the original Assumption 1's dimension restriction (Appendices H.3 and H.5). Thus this validation no longer requires a global-optimality certificate. The new experiment uses $K=2,n=4,d=1$, $N_1=N_2=10{,}000$, affinity $0.67$, and noise standard deviation $0.002$, giving the consistent SNR $(1-0.67^2)/0.002=275.55$. With $\tau=1/4$ and $\rho=0.001$, the sample requirement is $8697.47<10{,}000$, the separation inequality is $5.220786<10.819533$, and the analytic failure bound is below $0.000520$. All 100 outputs satisfy $\widehat F\le F^\star$; mean/max errors are $0.17065\%/0.25\%$, versus the conservative $25\%$ bound (Appendix D, Table 1). Fitting uses only unlabeled observations. Appendix D reports the initialization, seeds, and condition checks, and clarifies that confidence is per dataset. This controlled high-SNR experiment establishes applicability, without establishing general algorithmic superiority; the objective comparison uses simulation truth. > **4. First-use citations.** We have added citations directly at the LRGMM introduction (Section 4) and the K-subspaces formulation (Section 4.1, Eq. (23)).

Dear Reviewer HQf9,

We would like to once again sincerely thank you for your time and thoughtful feedback on our work.

As we approach the end of the rebuttal discussion period, we would appreciate hearing whether our response has addressed your concerns. We would also be happy to address any further questions or concerns whenever your schedule permits.

Thank you again for your time and consideration.

Authors

Thanks for the detailed responses. I see how the revision improves the sample complexity over Han and Xu. Since Haddock et al. already get the κ−1\kappa^{-1} dependence up to log factors under their assumptions, my understanding is that the main contribution here is pinning down the exact limiting gaussian curve for the worst-case lower bound. That still feels incremental to me.

As you point out, a cubic lower bound is enough to get the clustering rate. Is there a setting where using the exact curve (beyond the same asymptotic sample complexity of Haddock et al.) changes what you can guarantee? That would help me see how much the extra precision matters. For now, I'd keep my original score.

AuthorsOpenReview ↗

Exact Gaussian curves yield concrete algorithmic guarantees

Thank you for this follow-up. We agree that Haddock et al. already established the same asymptotic sample complexity, and that a cubic lower bound suffices for our clustering rate. The precise curves also enlarge the corruption range for which existing algorithms can be certified to converge in the following setting.

Robust regression: an explicit comparison of corruption thresholds.

Consider Gaussian covariates with arbitrary sparse response corruption:

x_i\overset{\mathrm{i.i.d.}}{\sim}\mathcal N(0,I_d),\qquad \|c\|_0\le\beta M.$$ The corruption support and values may depend on the data. TORRENT-FC [1] alternates least squares with retaining the $(1-\beta)M$ smallest residuals. With no additional dense noise, its deterministic theorem guarantees geometric convergence and exact recovery when $$(1+\sqrt2)\frac{\Lambda_\beta}{\lambda_{1-\beta}}<1,$$ where $\lambda_\kappa=\min_{|S|=\kappa M}\lambda_{\min}(\sum_{i\in S}x_ix_i^\top)$ and $\Lambda_\beta=\max_{|T|=\beta M}\lambda_{\max}(\sum_{i\in T}x_ix_i^\top)$. Our uniform bounds and complementary constructions give, in probability as $M\to\infty$ with fixed $d$, $$\lambda_{1-\beta}/M\to b(1-\beta),\qquad \Lambda_\beta/M\to u(\beta),$$ where $$b(\kappa)=\kappa-2q_\kappa\phi(q_\kappa),\qquad q_\kappa=\Phi^{-1}((1+\kappa)/2),\qquad u(\beta)=1-b(1-\beta).$$ Here $\phi,\Phi$ are the standard Gaussian density and distribution function. The limiting convergence condition becomes $$r(\beta)=(1+\sqrt2)\frac{u(\beta)}{b(1-\beta)}<1.$$ The table compares the original guarantee with substitutions into this same criterion. The last three rows use the same exact upper coefficient $u(\beta)$; their thresholds are computed in the large-sample limit. | Spectral analysis | Lower coefficient $\quad$ | Threshold| |---|---|---:| | Original Gaussian guarantee [1, Theorem 4] | Estimates in [1] | $1.54\\%$ | Gaussian specialization of Haddock et al.'s lower-bound proof [2] \$\quad \$ | $(\pi/288)(1-\beta)^3$ | $0.03\\%$ | | Strongest universal cubic lower bound [3, Eq. (0.9)] | $(\pi/6)(1-\beta)^3$ | $3.07\\%$ | | **Our exact Gaussian curves** | $b(1-\beta)$ | **$5.36\\%$** | The [2] row is our substitution of its spectral bound into TORRENT's criterion: squaring the factor $1/(24D)$ in Proposition 1 and specializing its proof to Gaussian rows, with $D=1/\sqrt{2\pi}$ and consistent scaling, gives $\pi/288$. The universal bound $b(\kappa)\ge(\pi/6)\kappa^3$ follows by applying [3, Eq. (0.9)] to $h(x)=\phi(x)\mathbf 1_{\{|x|\le q_\kappa\}}$. Its constant is optimal because $b(\kappa)/\kappa^3\to\pi/6$ as $\kappa\downarrow0$. Our threshold follows from $$u(\beta)<\frac{1}{2+\sqrt2},\qquad \beta<\beta_\star,\quad \beta_\star\approx0.05364712.$$ **Thus the certified range increases from the original $1.53846\%$ to $5.36471\%$, and exceeds the $3.06748\%$ achievable even with the optimal universal cubic coefficient.** These are sufficient convergence thresholds for the existing algorithm. **Finite sample** Take $\beta=0.04$, $d=10$, $M=6.4\times10^6$, $\eta_L=0.01$, $\eta_U=0.0375$. Our Theorems 1–2 yield $$\lambda_{0.96}/M\ge0.99^2b(0.9504)>0.708062,\quad \Lambda_{0.04}/M\le1.0375^2u(0.0415)<0.263889$$ with probability $>0.99979$. Hence $(1+\sqrt2)\Lambda_{0.04}/\lambda_{0.96}<0.9$, guaranteeing linear convergence of TORRENT-FC for every $\|c\|_0\le0.04M$, which is still higher than both the original and the strongest universal cubic lower bound. [1] Bhatia, Jain, and Kar. *Robust Regression via Hard Thresholding*. NeurIPS 2015, Theorems 3–4. [2] Haddock, Needell, Rebrova, and Swartworth. *Quantile-based Iterative Methods for Corrupted Systems of Linear Equations*. SIAM J. Matrix Anal. Appl. 43(2):605–637, 2022, Proposition 1. [3] Bobkov, S. G. and Chistyakov, G. P. and G{\"o}tze, F. Bounds for characteristic functions in terms of quantiles and entropy. Electronic Communications in Probability, 17, 1--9, 2012. ```
Reviewer_swUxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the extreme spectral bounds of sample covariance matrices for arbitrary data-dependent subsets of a Gaussian random vector. It provides both lower and upper bounds that hold simultaneously for all sufficiently large or small subsets, explicitly characterizing the influence of the subset proportion through truncated moments. Furthermore, the paper presents complementary constructions to demonstrate the tightness of these bounds in the asymptotic limit. The authors extend these results to sub-Gaussian variables and geometrically strongly mixing sequences, applying them to derive recovery guarantees for global optima in KK-subspace clustering, as well as to establish unified covariance and gradient moment controls for robust Gaussian regression. The validation consists primarily of theoretical proofs, illustrative coefficient analysis, and a limited number of exploratory experiments; the experiments do not verify the theoretical conditions or the attainment of global optimality.

Critical strengths
  1. The problem itself is significant; selecting subsets based on the data compromises independence, and uniform spectral bounds offer potential value for applications in clustering, robust regression, and erasure-robust analysis.

  2. The paper aims to establish a single event that encompasses all admissible subsets, which is an approach highly relevant to addressing the selection dependencies induced by global optima in KK-subspace clustering.

  3. The applications section demonstrates the transferability of these theoretical tools by employing the spectral bounds for global minimizers in KK-subspace clustering and for uniform moments in robust regression.

Critical weaknesses
  1. The incremental theoretical contribution is limited, and the sample complexity dependence is notably weak. For Theorem 1, the required sample size is approximately κ−6[mlog⁡(C/κ)+log⁡(1/ρ)]\kappa^{-6}[m\log(C/\kappa)+\log(1/\rho)]; the authors themselves acknowledge that Han and Xu [9] have already established a dependence of order κ−3\kappa^{-3}. If the primary contribution is merely the explicit derivation of curves and complementary constructions, it falls short of the novelty and rigor standards expected for a theoretical paper at a top-tier conference.

  2. The numerical examples do not explicitly guarantee a confidence level of 0.999. Furthermore, the constants c1c_1 and c2c_2 in Theorems 1 and 2 are left unspecified, which hinders the practical application of these theoretical results and complicates quantitative comparisons with existing literature.

  3. Theorem 5 only provides guarantees for a global minimizer and relies on Assumption 1, a high signal-to-noise ratio (SNR), and a sample size requirement of Nmin⁡⋆≳τ−6[dlog⁡(C/τ)+log⁡(K/ρ)]N_{\min}^\star\gtrsim \tau^{-6}[d\log(C/\tau)+\log(K/\rho)]. However, the experimental setup actually violates Assumption 1, and the sample-related conditions are not verified. The section on robust regression consists primarily of concentration results, failing to introduce any new estimator or provide guarantees on estimation error.

Questions for authors
  1. Is it possible to provide explicit or numerically calibratable lower bounds for c1c_1 and c2c_2 in Theorem 1/2, and, based on these, present at least one numerical example that genuinely satisfies the stated confidence level?

  2. Why are the experiments on K-subspace clustering used to support the theory even when Assumption 1 and the required sample conditions are not met? Could you either include experiments that satisfy the theoretical conditions or clarify that the existing experiments serve merely as exploratory observations?

  3. Does the comparison between Theorem 6 and [11] hold under the same noise model, the same confidence level, and the same "uniform-over-weights" condition? Could you provide the corresponding estimation errors or algorithmic-level guarantees?

4 comments

Thank you for these comments. We have revised the manuscript; the changes are marked in blue.

1. Sample complexity and prior work (Section 2.1, Eqs. (7)–(8); Appendices A, F.1–F.2).

We have replaced the coarse lower-tail estimate, improving the submitted sufficient sample dependence from κ−6\kappa^{-6} to

M≳ηκ−1[mlog⁡(Cη/κ)+log⁡(1/ρ)],M\gtrsim_\eta\kappa^{-1}[m\log(C_\eta/\kappa)+\log(1/\rho)],

while preserving the spectral coefficient (1−η)2b((1−η)κ)(1-\eta)^2b((1-\eta)\kappa). For Z∼N(0,1)Z\sim N(0,1), p=(1−η)κp=(1-\eta)\kappa, qp=Φ−1((1+p)/2)q_p=\Phi^{-1}((1+p)/2), and Y=Z21∣Z∣≤qpY=Z^2\mathbf1_{|Z|\le q_p}, Lemma 1 proves EY2≤3(EY)2/p\mathbb EY^2\le3(\mathbb EY)^2/p, giving lower-tail exponent η2pM/6\eta^2pM/6 in the same net argument. Eq. (8) provides an explicit sufficient sample count.

The revised comparison acknowledges Han and Xu's correct cubic spectral order and adds Haddock et al., whose Proposition 1 already has inverse-fraction sample dependence under its assumptions. Our refinement combines the full Gaussian trimmed-moment curves and complementary limiting constructions with this stronger finite-sample lower guarantee; we do not claim the inverse-fraction order itself as new.

2. Explicit constants and certified confidence (Section 2.1, Eq. (15); Appendices B.1 and F.3).

We have made the constants explicit. Lemma 2 proves, for Y=Z21Z∈EY=Z^2\mathbf1_{Z\in E} and μ=EY\mu=\mathbb EY,

Pr⁡(∣Y‾−μ∣≥t)≤2e−Mt2/(6+4t),\Pr(|\overline Y-\mu|\ge t)\le2e^{-Mt^2/(6+4t)},

so c1=c2=1/8c_1=c_2=1/8 is valid in the upper/complementary bounds. Theorem 1 now uses the sharper explicit lower-tail bound above.

For m=10m=10, M=20,000M=20{,}000, κ=1/2\kappa=1/2, and η=1/4\eta=1/4, the added example gives, simultaneously for every ∣Ω∣=10,000|\Omega|=10{,}000,

0.0162689Im⪯M−1∑i∈Ωaiai⊤⪯1.517309Im,0.0162689I_m\preceq M^{-1}\sum_{i\in\Omega}a_i a_i^\top\preceq1.517309I_m,

with failure probability below 3.31×10−73.31\times10^{-7}. Appendix B.1 gives the calculation. Both original figures are retained, with their illustrative status clarified; this certificate concerns the two displayed inequalities, not all four plotted curves.

3. Clustering assumptions and experiments (Section 4.2, Theorem 5; Appendices D, H.3 and H.5).

We agree that the original setup did not validate the stated theorem. We have replaced the unverified table and strengthened the theorem. Every feasible candidate satisfying F^≤F⋆+Δ\widehat F\le F^\star+\Delta obeys S≤4W+2ΔS\le4W+2\Delta, where SS is its noiseless residual and W=∑i∥ei∥2W=\sum_i\|e_i\|^2. This total-noise-energy argument removes the original dimension restriction. Theorem 5 states the separation condition and an explicit τ−1\tau^{-1} sample requirement in Eqs. (29)–(30); global minimizers are included when Δ=0\Delta=0.

Appendix D and Table 1 report a new 100-trial experiment with K=2,n=4,d=1K=2,n=4,d=1, N1=N2=10,000N_1=N_2=10{,}000, affinity 0.670.67, noise standard deviation 0.0020.002, and τ=1/4\tau=1/4. At ρ=0.001\rho=0.001, the required sample threshold is 8697.47<10,0008697.47<10{,}000, the separation check is 5.220786<10.8195335.220786<10.819533, and the analytic failure bound is below 0.00051970.0005197. All outputs satisfy F^≤F⋆\widehat F\le F^\star; mean/maximum errors are 0.17065%/0.25%0.17065\%/0.25\%, versus the conservative 25%25\% guarantee. Fitting uses only unlabeled data. The revised text explicitly states the per-dataset confidence and the limits of this high-SNR experiment; no global-optimality certificate or general convergence claim is used.

4. Regression comparison and estimator guarantee (Section 5, Corollary 2; Appendices E and I.2).

We now compare the quoted sample bounds at the same data-event confidence 0.90.9 on the common Gaussian-design/independent-Gaussian-noise specialization of Jambulapati et al. (2021). Their framework already permits data-dependent weights; our distinction is one clean set working for every parameter and admissible capped weight, without further parameter-dependent trimming.

Corollary 2 and its proof now verify the capped-weight FastRegression conditions. Under its inherited covariance/noise bounds, initialization and ERM-oracle requirements, and sufficiently small εκcond\varepsilon\kappa_{\rm cond},

N≥C[(d+log⁡(4/ρ))2+(d+log⁡(4/ρ))/ε]N\ge C[(d+\log(4/\rho))^2+(d+\log(4/\rho))/\varepsilon]

yields ∥θ^−θ⋆∥Σ≤C′σκϵ\|\widehat\theta-\theta^\star\|_\Sigma\le C'\sigma \sqrt{\kappa \epsilon} with probability 1−ρ1-\rho, allocating failure ρ/2\rho/2 each to data and algorithm. The improvement is the Gaussian sample bound; the estimator and error rate are inherited.

Reviewer_swUxOpenReview ↗

review

Thanks for your rebuttal.

Your response addresses some of the concerns, but certain issues remain, for instance, the experimental validity of some of the theorems and assumptions. Furthermore, I share the concern raised by other reviewers that the experimental validation is insufficient, and there are no results based on real-world data.

We thank the reviewer for the follow-up and for acknowledging that our rebuttal addressed some concerns. To address the remaining concern about real-world validation, we have completed two experiments corresponding to our two applications. They complement the revised synthetic experiment, which explicitly checks the model assumptions, sample-size condition, and analytical confidence bound.

1. Motion segmentation on Hopkins155.

Motivation and setup. Theorem 5 connects the K-subspaces objective to recovery despite data-dependent assignments. We examine this connection on all 155 Hopkins155 instances (120 with two motions and 35 with three) [1]. All methods use the same uncentered 4K4K-dimensional projection. KSS fits rank-4 subspaces with nested budgets of 1, 5, or 20 initializations, selecting exclusively by the residual objective; true memberships are used only for evaluation. SSC-ADMM is a Python port of the authors' implementation.

MethodMean error (%)Median error (%)At/below reference (%)
KSS, 1 start24.6828.4836.8
KSS, best of 519.2316.3553.5
KSS, best of 2015.899.5665.2
SSC-ADMM (Python port)2.420.0072.3

Here Fref=min⁡UF(U,CGT)F_{\rm ref}=\min_U F(U,C_{\rm GT}) refits each true-label group. The last column checks F(U^,C^)≤Fref+10−10∥X∥2F(\widehat U,\widehat C) \le F_{\rm ref} + 10^{-10} \|X\|^2. For the same fitting problem, if CGT=C⋆C_{\rm GT}=C^\star and the true subspaces are feasible, Fref≤F(U⋆,C⋆)F_{\rm ref}\le F(U^\star,C^\star), making this an observable sufficient condition for the objective-comparison premise in Theorem 5, up to numerical tolerance.

Conclusion. More objective-selected starts improve aggregate recovery and increase the fraction meeting the reference comparison. This supports the practical relevance of studying recovery through objective quality. SSC provides a strong accuracy baseline; our theoretical application concerns the recovery properties of the KSS formulation.

2. Robust regression on real Protein/CASP data.

Motivation and setup. Theorem 6 controls design and gradient moments under adaptive weighting. We test their practical relevance using the original nine predictors and RMSD responses of UCI Protein/CASP (45,730 records) [2]. Each of five fixed splits uses 20,000 training and 20,730 unchanged test records; 5,000 reserved validation records are unused. Training-only contamination affects either responses or both covariates and responses, with the latter creating high-leverage outliers. We test 0%, 1%, 2%, and 5% contamination, using five attack seeds per split at nonzero contamination.

OLS, Huber, residual trimming, and SEVER-style gradient spectral trimming [3] receive identical contaminated data. Both trimming methods use the known contamination fraction ε\varepsilon and delete 2εn2\varepsilon n observations over ten rounds. Preprocessing uses contaminated training data only; the test set is never used for tuning.

The table reports the clean and 5% cases. RMSE entries are mean ± SD across five split-level means, averaging attack seeds within each split.

MethodClean RMSE5% response RMSE5% joint RMSE
OLS5.178 ± 0.0206.586 ± 0.03014.490 ± 0.265
Huber5.209 ± 0.0205.220 ± 0.02023.759 ± 5.199
Residual trimming5.178 ± 0.0205.259 ± 0.06529.834 ± 9.835
SEVER-style spectral trimming5.178 ± 0.0205.231 ± 0.0305.231 ± 0.025

Conclusion. Under joint corruption, gradient spectral filtering maintains prediction close to the uncontaminated baseline, while Huber performs slightly better under response-only corruption. These results demonstrate the usefulness of the adaptive filtering setting studied in our regression application and motivate control of the design and gradient moments throughout selection.

Together, these experiments establish relevance to real motion-segmentation and prediction tasks. The calibrated synthetic study checks the theorem conditions; the real-data studies complement it with application-level evidence.

[1] Tron and Vidal, "A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms," CVPR 2007.

[2] Rana, "Physicochemical Properties of Protein Tertiary Structure," UCI, 2013. https://doi.org/10.24432/C5QW3H

[3] Diakonikolas et al., "SEVER: A Robust Meta-Algorithm for Stochastic Optimization," ICML 2019.

Dear Reviewer swUx,

We would like to once again sincerely thank you for your time and thoughtful feedback on our work.

As we approach the end of the rebuttal discussion period, we would appreciate hearing whether our response has addressed your concerns. We would also be happy to address any further questions or concerns whenever your schedule permits.

Thank you again for your time and consideration.

Authors

Reviewer_6YcbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper establishes concentration inequalities for the extreme eigenvalues of sample covariance matrices formed from arbitrary subsets of i.i.d. Gaussian random vectors. The bounds make the dependence on the retained proportion explicit through central and tail trimmed moments, with complementary bounds establishing their limiting tightness. Extended results to sub-Gaussian random vectors under additional distributional assumptions are established. Further applications to K subspace clustering and robust regression are discussed.

Critical strengths
  1. The paper establishes max and min eigenvalue bounds for covariance of arbitrary subets of iid Gaussian distribution vectors which are asymptotically tight.

  2. The paper demonstrates applications of established bounds to K-subspace clustering and robust regression by proving the optimality and error bounds respectively.

Critical weaknesses
  1. The major weakness is the paper's main Theorem 1 and its proof are highly correlated with an earlier paper "Quantile-based Iterative Methods for Corrupted Systems of Linear Equations"(which the authors did not seem to cite), where Proposition 1 of that paper already provided a singular value lower bound for arbitrary row subset selection for a row iid random matrix. The current manuscript's results seem to be obtainable by directly checking and adapting to the assumption 1 and 2 of the earlier paper under the Gaussian distribution case. In the same earlier paper, it was also stated that "..The prototypical example of a matrix satisfying both assumptions is a normalized Gaussian matrix.." Furthermore, the proof of Theorem 1 also follows a similar anti-concentration bound and then an epsilon net argument as that of Proposition 1 of the earlier paper.

  2. An additional weakness is that the established framework and theoretical bounds seem to yield limited practical implications. For example, there is no experiment or proof showing applying data dependent sampling yields better performance or make existing algorithms more robust.

Questions for authors
  1. Can the authors discuss the main technical challenge and resolutions to proving Theorem 1 and Theorem 2 on top of existing literature, in particular the paper "Quantile-based Iterative Methods for Corrupted Systems of Linear Equations".

  2. Can the authors provide more insights into how the data dependent sampling and bounds can be significant in practice. For example, if it leads to a more performant algorithm or makes existing algorithms more robust? Can authors also provide experimental justifications?

2 comments

Thank you for pointing out the missing reference. We have revised the manuscript; the changes are marked in blue.

Q1. Relation to prior work and technical contribution.

We have added Haddock et al., Quantile-based Iterative Methods for Corrupted Systems of Linear Equations, and a direct comparison in Section 2.1 and Appendix A. Its Proposition 1 already establishes arbitrary-subset lower singular-value bounds, the cubic covariance order, and inverse-retained-fraction sample dependence under its assumptions. We explicitly acknowledge the shared anti-concentration/net strategy and do not claim these features as new.

Our Gaussian results identify the full central and tail trimmed-moment curves b(κ)b(\kappa) and u(κ)u(\kappa), together with complementary constructions showing their limiting tightness (Theorems 1–2 and Corollary 1, Section 2.1). Recovering these coefficients requires controlling both the number and energy of the truncated observations; a coarse anti-concentration estimate alone does not identify them.

We have also strengthened Theorem 1: its sufficient sample dependence improves from κ−6\kappa^{-6} to κ−1\kappa^{-1}, up to logarithms, while preserving the lower coefficient (1−η)2b((1−η)κ)(1-\eta)^2b((1-\eta)\kappa). The revised conditions are Eqs. (7)–(8), with proofs in Appendices F.1–F.2. Specifically, for p=(1−η)κp=(1-\eta)\kappa, Y=Z21{∣Z∣≤qp}Y=Z^2\mathbf1_{\{|Z|\le q_p\}}, qp=Φ−1((1+p)/2)q_p=\Phi^{-1}((1+p)/2), Z∼N(0,1)Z\sim N(0,1), and μ=EY=b(p)\mu=\mathbb EY=b(p), the new Lemma 1 proves EY2≤3μ2/p\mathbb EY^2\le3\mu^2/p. Thus

\le e^{-\eta^2pM/6},$$ and the existing net argument gives $$M\gtrsim_\eta\kappa^{-1} \left[m\log(C_\eta/\kappa)+\log(1/\rho)\right].$$ For Theorem 2, the tail-truncated variable is unbounded. The new Lemma 2 in Appendix F.3 supplies the required upper-tail estimate with explicit constants; Appendix F.4 uses it for the complementary constructions. These refinements retain the full curves with quantified finite-sample guarantees; the inverse-fraction sample order itself already appears in Haddock et al. > **Q2. Practical implications and experimental evidence.** The common event covers subsets selected by optimization. We have strengthened Theorem 5 (Section 4.2) from global minimizers to every feasible candidate satisfying $\widehat F\le F^\star+\Delta$, where $F^\star$ is the objective at the true model and $\Delta\ge0$. Writing $W=\sum_i\|e_i\|^2$ and $S$ for the candidate's noiseless residual gives $$S\le(\sqrt{W+\Delta}+\sqrt W)^2\le4W+2\Delta.$$ The total-noise-energy argument removes the original Assumption 1's extra dimension restriction. The revised theorem includes explicit separation and sample conditions; the latter scales as $\tau^{-1}$ up to logarithms for error at most $(K-1)\tau$ (Eq. (30); Appendices H.3–H.5). We have replaced the unverified experiment with a calibrated 100-trial experiment in Appendix D and Table 1. It uses $K=2,n=4,d=1$, $N_1=N_2=10000$, affinity $0.67$, noise standard deviation $0.002$, and $\tau=1/4$. The sufficient sample threshold is $8697.47<10000$, the separation check is $5.22079<10.81953$, and the analytic failure probability is below $0.000520$. All outputs of the alternating assignment/eigenspace algorithm satisfied $\widehat F\le F^\star$. Mean/maximum misclassification were $0.17065\%/0.25\%$, versus the conservative $25\%$ guarantee. Fitting used only unlabeled observations. This verifies applicability to computed outputs without a global-optimality certificate. Appendix D explicitly distinguishes its per-dataset analytic confidence from the empirical success frequency and limits the conclusion to this controlled high-SNR setting. In regression, the added Corollary 2 (Section 5; Appendix I.2) transfers the improved Gaussian sample bound to FastRegression while preserving its existing estimation-error rate.

Dear Reviewer 6Ycb,

We would like to once again sincerely thank you for your time and thoughtful feedback on our work.

As we approach the end of the rebuttal discussion period, we would appreciate hearing whether our response has addressed your concerns. We would also be happy to address any further questions or concerns whenever your schedule permits.

Thank you again for your time and consideration.

Authors

Comments on the paper

2 comments
AuthorsOpenReview ↗

Clarification of contributions and summary of revisions

We sincerely thank the reviewers for their careful assessment and constructive suggestions. We have revised the manuscript accordingly, with changes highlighted in blue. We first clarify three issues shared across the reviews.

  • 1. Sharp limiting coefficients and computable finite-sample guarantees. Our Gaussian results identify the central and tail trimmed moments b(κ)b (\kappa) and u(κ)u(\kappa) as sharp limiting coefficients, with matching subset constructions. The comparison below separates this characterization from sample dependence and confidence calibration.
PropertyHan and Xu [1], Thm. 1.4 / Cor. 1.6Haddock et al. [2], Prop. 1Ours, revised
Spectral informationLower/upper estimates with correct small-κ\kappa ordersDensity-based uniform lower boundFull Gaussian lower/upper curves b(κ),u(κ)b(\kappa),u(\kappa)
SharpnessMatching orders as κ→0\kappa\to0No matching coefficient characterization in Prop. 1Matching coefficient limits at each fixed κ\kappa
Sufficient samples for the lower boundO~(mκ−3)\widetilde O(m\kappa^{-3})O~(mκ−1)\widetilde O(m\kappa^{-1})O~(mκ−1)\widetilde O(m\kappa^{-1})
Numerical finite-sample confidenceSpecified in Cor. 1.6C1,c2C_1,c_2 not numerically specifiedAll constants specified; joint lower/upper certificate

Here mm is the dimension and κ\kappa the retained fraction. Sample orders use fixed slack, confidence, and distributional parameters. Han-Xu is specialized to full sparsity, and each result retains its own model assumptions. Matching limits hold as the slack vanishes and the stated failure probabilities tend to zero (Corollary 1).

The revision improves our lower-bound sample dependence from κ−6\kappa^{-6} to κ−1\kappa^{-1} while preserving the trimmed-moment coefficient (Section 2.1, Eqs. (7)-(8); Appendices F.1-F.2). The contribution combines sharp limiting Gaussian coefficients, inverse-fraction lower-bound sample dependence, and fully specified finite-sample confidence. We have clarified the comparison in Appendix A.

In particular, we now specify c1=c2=1/8c_1=c_2=1/8 and provide an analytically certified example. For m=10m=10, M=20000M=20000, κ=1/2\kappa=1/2, and η=1/4\eta=1/4, simultaneously for every subset of size 1000010000,

\preceq 1.517309 I_{10},$$ with joint failure probability below $3.31\times10^{-7}$. This calculation includes both spectral bounds and all admissible subsets, and exceeds the requested $0.999$ confidence (Appendix B.1). [1] Han and Xu. Robustness properties of dimensionality reduction with Gaussian random matrices. Science China Mathematics, 2017 [2] Haddock et al. Quantile-based iterative methods for corrupted systems of linear equations. SIAM Journal on Matrix Analysis and Applications, 2022 - **2. Extensions beyond independent Gaussian observations.** Data-dependent subset selection is already covered by arbitrary-subset uniformity, including in prior work. Our extensions concern the observation model: sub-Gaussian vectors under explicit nondegeneracy and tail assumptions (Section 2.2), and a uniform lower spectral bound for stationary, geometrically strong-mixing Gaussian observations (Section 3). The latter accommodates both dependence between observations and selection based on those observations. These extensions retain their own assumptions and probability bounds. - **3. Applications with explicit guarantees and verified conditions.** For K-subspace clustering, revised Theorem 5 applies to every feasible candidate satisfying an objective comparison with the true model, including all global minimizers. A total-noise-energy argument removes the previous extra dimension restriction, and the refined spectral bound improves the required sample dependence. Appendix D now reports a reproducible experiment that verifies the sufficient sample and separation conditions and checks the objective comparison for all 100 computed outputs. Its confidence guarantee is analytic and applies per dataset, and global optimality is not assumed for the computed solutions. For robust regression with Gaussian design and independent Gaussian noise, we have added an estimator consequence (Corollary 2; Appendix I.2). Under the inherited initialization and oracle requirements, the stated covariance/noise assumptions, and sufficiently small $\varepsilon\kappa_{\mathrm{cond}}$, the Gaussian sample bound $N=O(d^2+d/\varepsilon)$ at constant confidence supports FastRegression's existing error guarantee $O(\sigma\sqrt{\kappa_{\mathrm{cond}}\varepsilon})$. Here $\kappa_{\mathrm{cond}}$ bounds the covariance condition number. The improvement concerns sufficient samples, while the estimation-error rate is preserved. The proof verifies the required uniform conditions over parameters and capped weights on the same clean set. In the following, we address each reviewer’s other questions one by one.
Area_Chair_iAMcOpenReview ↗

Thank you

Thank you for the detailed rebuttal. I'll make sure it's taken into account when we make our final recommendation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.