acceptodds
Under review as a conference paper at ICLR 2027

When Do Worst Cases Align? Exact Covariance Contact in Volume Sampling

Abstract

We give the exact contact geometry of the universal covariance ceiling in volume-sampled least squares. Consider ordinary fixed-size volume sampling for unweighted least squares. Only the subset draw is random, while the design and response are fixed. We assume positive residual loss and no rank-critical row. The full contact space is the kernel of an explicit positive semidefinite operator. This space is unchanged across all strict-interior subset sizes. We show that varying the residual yields a finite orthogonal family of nonzero contact spaces. This family gives exact criteria for whole-query contact and the existence of a contact direction. Beyond exact contact, we quantify departure from the covariance ceiling. A leave-one-out quantity gives two-sided bounds on the normalized gap across all such subset sizes. These bounds also apply to designs with no contact direction. We also use this geometry to build certificates for expected query-MSE excess over the full-data fit. On fixed regression workloads, added information reduces sufficient sample sizes on fixed grids. Lower bounds can also certify that selected sizes exceed the risk allowance.

Primary area:
learning theory
Keywords:
volume sampling, least squares regression, randomized numerical linear algebra, covariance bounds, worst-case analysis, risk certification

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_VKLMOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies volume sampling for least squares regression. In this problem setting, we wish to solve a least squares regression task with nn data points, and we are assuming that the responses (real-valued labels) are not initially provided to us. We then sample a subset of the data points, query the responses for these data points, and solve the subsampled least squares problem. Volume sampling has been suggested by several prior works as an effective sampling technique for this task, primarily because it ensures that the produced solution is an unbiased estimator of the solution to the full regression task. The authors study the covariance structure of the volume sampled least squares estimator, showing a number of theoretical results that are supported by a few experiments.

Critical strengths

Sub-sampling for least squares regression is an interesting and important topic.

Critical weaknesses

Unfortunately, the paper is essentially incomprehensible. Depite the fact that I consider myself an expert in the area of sub-sampled least squares, and in the area of volume sampling, and am familiar with the prior works cited by the authors, I was entirely unable to understand the language of the paper. The terminology used by the authors is not properly defined, and the paper seems to jump into the topic midway through without any proper justification or motivation for what is being done, why it is being done, and what significance it has. I am entirely at a loss for what is the point of the theoretical results (I have not found any specific issues with the mathematics, but that is mainly because I was not able to get through the very dense notation).

Questions for authors

Could you provide a clear motivation for the theory developed in the paper, and how it advances state-of-the-art?

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

The paper studies fixed-size volume sampling with unweighted least squares for fixed designs and responses. It characterizes the directions attaining the universal covariance bound and proves that this contact space is invariant across interior sample sizes. It also relates covariance deficits to leave-one-out quantities and derives query-risk bounds for sample-size certification.

Critical strengths
  1. The exact contact characterization and its invariance across sample sizes provide a substantive structural refinement of the universal covariance bound.

  2. The analysis handles zero-volume subsets carefully and extends beyond exact contact through two-sided deficit bounds. The experiments distinguish rigorous risk bounds from Monte Carlo estimates.

Critical weaknesses
  1. The quantitative bounds remain conservative. On Tetouan at s=11,757, the upper bound is about 25 times the separate Monte Carlo risk estimate. The factor bsb_s in Theorem 6 is approximately 1.08e-5 at this size. These results establish sufficient sample sizes but provide limited guidance on how close those sizes are to what is actually needed. The practical value of the sharper risk analysis therefore remains insufficiently established.

  2. The cost-benefit trade-off of second-moment certification is unclear. It requires the full-data fit, and the dense construction has O(d^4) storage and d^5 work terms (Appendix J.3). The timing study covers d=10, K=2 and reports a 16.75% increase in numeric-prefix cost (Appendix Q.6). It remains unclear when the reduced certified subset sizes justify these preparation costs, particularly in higher dimensions.

Questions for authors
  1. Given the small value of bsb_s, how much does Theorem 6 tighten the risk bounds on the experimental datasets?

  2. For the existing higher-dimensional workloads, when do the reduced certified subset sizes justify the full preparation and certification costs?

Reviewer_VoCnOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper presents theoretical results about statistical linear models contact geometry and derived bounds on this contact geometry.

Critical strengths

Lots of math and theory.

Critical weaknesses

Very little intuition about the theory, no practical applications. Theory is low effort. There's no evidence this paper wasn't one shotted by an AI. There's no discussion of why any of this theory has any importance to anyone.

Questions for authors

Why is your paper useful to society?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.