acceptodds
Under review as a conference paper at ICLR 2027

From Dimension to Horizon: Krylov Coresets for Linear Regression

Abstract

Classical coresets for linear regression preserve the objective over the full parameter space, leading to sizes that depend on the dimension . We ask whether the optimization horizon can instead determine the amount of data needed. For any -step gradient descent (GD) trajectory, all iterates lie in an affine Krylov space of dimension at most . Since GD converges linearly in strongly convex settings, the required optimization horizon can be much smaller than . Motivated by this structure, we construct a strong Krylov coreset of size that preserves the objective throughout the corresponding affine Krylov space. To further reduce the coreset size and construction cost, we develop a weak Krylov coreset based on a blockwise approximation of the GD trajectory. It has size and returns a solution whose loss is within a factor of the best bounded affine combination of the exact GD iterates. With an appropriate block size, its construction requires only full-data passes in expectation. Experiments show that Krylov coresets closely match the regression loss of full-data GD, while the weak construction further reduces coreset size and computational cost.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Coreset, Gradient Descent, Linear Regression

Reviews

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

This paper proposes horizon-dependent coresets for linear regression by exploiting the observation that TT gradient descent iterates lie in an affine Krylov subspace of dimension at most TT. It develops a "strong Krylov coreset" that preserves the objective uniformly over this subspace, and a "weak Krylov coreset" that further reduces the coreset size and construction cost through trajectory approximation.

Critical strengths

The paper is generally well organized, and the theoretical contributions are clearly presented.

Critical weaknesses

Missing discussion and comparison with Conjugate Gradient (CG).

The connection to classical Conjugate Gradient methods is not sufficiently discussed. For quadratic objectives, CG operates in the same Krylov subspace and directly minimizes the objective over this subspace at each iteration. This raises a fundamental question about the practical advantage of the proposed approach over directly applying CG.

Questions for authors

See weakness.

3 comments

Weakness 1. Missing discussion and comparison with Conjugate Gradient (CG). The connection to classical Conjugate Gradient methods is not sufficiently discussed. For quadratic objectives, CG operates in the same Krylov subspace and directly minimizes the objective over this subspace at each iteration. This raises a fundamental question about the practical advantage of the proposed approach over directly applying CG.

Response. Thank you for pointing out the connection with CG. Constructing a weighted-row coreset that preserves the least-squares objective over the entire parameter space can require at least dd rows. Our work introduces a new perspective to regression coreset research by exploiting the finite optimization horizon to obtain coreset size bounds independent of dd. To the best of our knowledge, this is the first horizon-dependent weighted-row regression coreset construction that preserves the objective uniformly over the full-data Krylov space, with size O(Tε−2log⁡(T/δ))O(T\varepsilon^{-2}\log(T/\delta)). WeakKrylov further reduces the coreset size and construction cost, with a near-optimality guarantee over bounded affine combinations of exact GD iterates.

CG efficiently minimizes the objective over the same Krylov space and can be more efficient for a single solve. However, CG computes a solution, while StrongKrylov constructs a weighted subset of original rows that preserves the objective throughout this space. This subset can support subsequent objective evaluation and optimization within the same fixed space. Moreover, the strong coreset guarantee implies F(x^S)≤1+ε1−εF(xTCG)F(\widehat{x}_S)\leq\frac{1+\varepsilon}{1-\varepsilon}F(x_T^{\mathrm{CG}}), where x^S\widehat{x}_S minimizes the coreset objective over the original Krylov space.

Experimental comparison. We have added experiments in Appendix E. On the Synthetic dataset, StrongKrylov achieves a relative objective gap of 2.84%2.84\% to the full-data Krylov-space optimum with m=1000m=1000, demonstrating its ability to approximate optimization over the original Krylov space. On a dataset with one million rows, WeakKrylov reduces coreset construction time by approximately 7.57.5 times compared with StrongKrylov, while achieving similar regression loss.

These results show the optimization quality of StrongKrylov and the construction efficiency of WeakKrylov. We also discuss the distinction between CG and Krylov coresets in Appendix E of the revised manuscript.

Thank for you reply. I'll maintain my score.

AuthorsOpenReview ↗

Clarification of Our Coreset Contribution and Your CG-Related Concern

Thank you for following up. We appreciate your concern regarding the connection to conjugate gradient (CG), and we have addressed it in our response and expanded the discussion in Appendix E. We would like to further clarify the distinction between our contributions and CG.

Our central contribution is a horizon-dependent coreset formulation and construction, not a new solver intended to outperform CG on a single regression problem. Classical strong coresets preserve the objective over the full parameter space, with size bounds depending on the dimension dd. In contrast, our strong Krylov coreset preserves the objective throughout the entire affine Krylov space, with a size bound governed by the optimization horizon TT, which can be much smaller than dd in high-dimensional settings. We believe this shift opens an important research direction for the coreset community: exploiting finite-horizon optimization structure to construct compact data summaries with guarantees over optimization-relevant spaces.

We agree that CG minimizes the objective over the corresponding Krylov space. However, computing a minimizer and constructing a small weighted coreset that preserves the objective throughout that space are fundamentally different tasks. CG operating in the same space does not itself provide this data-compression guarantee.

We respectfully ask you to reconsider your assessment in light of this fundamental distinction. If the original CG-related concern remains, we would appreciate clarification of what specifically remains unaddressed by our response.

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

The paper considers the computational bottleneck of generating coresets for large-scale linear regression, where traditional data summaries scale with the parameter dimension dd. The authors propose Krylov coresets, which instead scale with the gradient descent (GD) optimization horizon TT. This is motivated by the observation that any TT-step GD trajectory is contained within an affine Krylov space of dimension at most TT.
The authors introduce two primary methods. First, they design a strong Krylov coreset of size O(Tϵ2log⁡(Tδ))O(\frac{T}{\epsilon^2}\log(\frac{T}{\delta})) that uniformly preserves the regression objective over the entire affine Krylov space. Second, to alleviate the cost of exact trajectory generation, they develop a weak Krylov coreset of size O(Tϵlog⁡(Tδ))O(\frac{T}{\epsilon}\log(\frac{T}{\delta})). This weak variant uses blockwise exact gradients combined with approximate Hessian corrections, limiting the solution class to bounded affine combinations of GD iterates. The weak coreset requires only O(T+log⁡(1δ))O(\sqrt{T} + \log(\frac{1}{\delta})) full-data accesses in expectation. Empirically, the algorithms match the optimization quality of full-data GD while reducing computational cost.

Critical strengths
  • Traditional coresets ask for preserving the objective over the entire parameter space. There were some works studying the weak coreset. However, the paper present a new and natural perspective that constrains the parameter space, which is new for me. Shifting the coreset dependency from the full dataset dimension dd to the finite optimization horizon TT is a highly original perspective for least-squares optimization.
  • The paper is mathematically sound and well-written. The experimental results clearly demonstrate the effectiveness of the proposed algorithm.
Critical weaknesses
  • Compared to traditional coresets, the coreset here is bound to a specific optimization algorithm, which limits the significance of the results. In fact, for a simple problem like linear regression, computing its coreset is inherently more interesting than solving it via gradient descent. The Krylov coreset is more like an acceleration method for solving linear regression with gradient descent.
  • The experiments fix the optimization horizon at T=32T=32, the block size at B=4B=4, and the stability radius at R=2R=2 without exploring how sensitive the coresets are to these specific values.
  • The motivation relies heavily on the fact that GD converges linearly in strongly convex settings, meaning TT can be much smaller than dd. However, linear regression problems are only strongly convex when ATAA^TA is positive definite, leaving the paper's empirical behavior on rank-deficient or ill-conditioned matrices somewhat underexplored.
Questions for authors
  • How does the empirical performance—both in runtime and regression loss—scale if the optimization horizon TT is significantly increased (e.g., T≥100T \ge 100), considering the coreset sizes directly depend on TT?
  • The theoretical guarantee for the weak coreset relies on an initialization step size of η\eta that strictly satisfies η∥A∥22≤1\eta\Vert{}A\Vert{}_2^2 \le 1. How is the exact smoothness parameter (∥A∥22\Vert{}A\Vert{}_2^2) computed or approximated in your experimental setup to satisfy the stringent theoretical step size requirement of η∥A∥22≤1\eta\Vert{}A\Vert{}_2^2 \le 1?
  • Given that the short horizon TT is motivated by linear convergence, how do Krylov coresets perform empirically on highly ill-conditioned design matrices where GD convergence degrades to sublinear rates?
  • Can introduced method be applied to other problems besides linear regression?
4 comments

Weakness 1. Compared to traditional coresets, the coreset here is bound to a specific optimization algorithm, which limits the significance of the results. In fact, for a simple problem like linear regression, computing its coreset is inherently more interesting than solving it via gradient descent. The Krylov coreset is more like an acceleration method for solving linear regression with gradient descent.

Response. Thank you for raising this concern. We agree that constructing regression coresets is an important research problem. A substantial body of prior work has studied regression coresets, whose size bounds typically depend on the feature dimension dd. For standard weighted row-subset least-squares coresets that preserve the objective over the full parameter space, at least dd rows are required in the worst case. However, a TT-step GD trajectory lies in an affine Krylov space of dimension at most TT. Our work exploits this structure to construct coresets with size bounds depending on TT and independent of dd.

StrongKrylov preserves the objective uniformly over the entire Krylov space, allowing optimization beyond the GD iterates. WeakKrylov further reduces the coreset size and construction cost, while providing a near-optimality guarantee over bounded affine combinations of exact GD iterates. Thus, our results concern constructing regression coresets with horizon-dependent size bounds and optimization guarantees, not simply accelerating GD.

Weakness 2 + Question 1. The experiments fix the optimization horizon at T=32T=32, the block size at B=4B=4, and the stability radius at R=2R=2 without exploring how sensitive the coresets are to these specific values. How does the empirical performance—both in runtime and regression loss—scale if the optimization horizon TT is significantly increased (e.g., T≥100T\ge 100), considering the coreset sizes directly depend on TT?

Response. Thank you for raising these questions. We have added sensitivity experiments for TT, BB, and RR in Appendix F. We consider T∈16,32,64,128T\in\\{16,32,64,128\\} with both fixed and increasing coreset sizes, using B=⌊T⌋B=\lfloor\sqrt{T}\rfloor, and vary BB and RR separately at T=32T=32.

As TT increases, StrongKrylov and WeakKrylov remain close to FullGD-Stable in regression loss, while WeakKrylov's running time grows more slowly. At T=128T=128, with a fixed coreset size of m=600m=600, WeakKrylov takes approximately 1.61.6 seconds, compared with 27.627.6 seconds for StrongKrylov. Increasing the coreset size with TT provides little additional improvement in regression loss on this dataset.

For B∈1,2,4,5B\in\\{1,2,4,5\\}, increasing the block size reduces WeakKrylov's running time with nearly unchanged loss. For R∈1,2,4R\in\\{1,2,4\\}, increasing the stability radius reduces regression loss, while WeakKrylov remains close to FullGD-Stable under the corresponding RR. The detailed comparisons are presented in Appendix F.

Weakness 3 + Question 3. The motivation relies heavily on the fact that GD converges linearly in strongly convex settings, meaning TT can be much smaller than dd. However, linear regression problems are only strongly convex when A⊤AA^\top A is positive definite, leaving the paper's empirical behavior on rank-deficient or ill-conditioned matrices somewhat underexplored. Given that the short horizon TT is motivated by linear convergence, how do Krylov coresets perform empirically on highly ill-conditioned design matrices where GD convergence degrades to sublinear rates?

Response. Thank you for raising this concern. To the best of our knowledge, StrongKrylov is the first horizon-dependent weighted-row regression coreset that uniformly preserves the objective over the full-data Krylov space, with a size bound independent of dd. This provides a new perspective on regression coreset construction.

We agree that poor conditioning can slow GD convergence and may require a larger TT to approach the global optimum. Our coreset guarantees concern finite-horizon optimization and remain valid for ill-conditioned and rank-deficient matrices, even for larger TT. Increasing TT may increase the coreset size and construction cost, but does not invalidate these guarantees. Moreover, ridge regularization can improve conditioning when appropriate, and Lemma A.2 establishes an extension of StrongKrylov to quadratic regularization. Adaptive choices of the regularization parameter and optimization horizon can be explored in future work.

We have added experiments on matrices with condition numbers up to 10610^6, including rank-deficient instances. For T∈32,64T\in\\{32,64\\}, the average regression losses of StrongKrylov and WeakKrylov differ by less than 0.180.18\\% from FullGD-Stable across the tested settings. These results demonstrate that both methods maintain accurate finite-horizon approximation under poor conditioning. Detailed results are provided in Appendix G.

Question 2. The theoretical guarantee for the weak coreset relies on an initialization step size of η\eta that strictly satisfies η∥A∥22≤1\eta\Vert A\Vert_2^2\le 1. How is the exact smoothness parameter (∥A∥22\Vert A\Vert_2^2) computed or approximated in your experimental setup to satisfy the stringent theoretical step size requirement of η∥A∥22≤1\eta\Vert A\Vert_2^2\le 1?

Response. Thank you for this question. We choose the step size using a computable upper bound on the smoothness parameter U=\min\left\\{\lVert A\rVert_F^2,\lVert |A|^\top |A|\rVert_\infty\right\\} \geq \lVert A\rVert_2^2, where ∣A∣|A| denotes the entrywise absolute value of AA, and the matrix infinity norm is the maximum absolute row sum. Our implementation uses the mean loss ∣Ax−b∣22/(2n)\\|Ax-b\\|_2^2/(2n) and sets the step size to 0.9n/U0.9n/U. This is equivalent to using η=0.9/U\eta=0.9/U for the objective in the paper, ensuring η∣A∣22≤0.9<1\eta\\|A\\|_2^2\leq 0.9<1. The upper bound is computed in one blockwise pass over the data, without forming A⊤AA^\top A or computing its eigenvalues.

Question 4. Can introduced method be applied to other problems besides linear regression?

Response. Thank you for this question. In Appendix, Lemma A.2, we extend our strong Krylov coreset extends to regularized quadratic objectives FQ(x)=12∣Ax−b∣22+12x⊤QxF_Q(x)=\frac12\\|Ax-b\\|_2^2+\frac12x^\top Qx, where Q⪰0Q\succeq0, including ridge regression. Moreover, the strong coreset might support constrained or other regularized optimization over the same fixed Krylov space. Extending the weak construction with the same computational guarantees is an interesting topic which deserves further study.

Thank you for your clarification and additional experiments. I agree that the presented method is practical. However, the theoretical contribution of this paper is still somewhat limited to my mind. Therefore I will keep my rating.

AuthorsOpenReview ↗

Clarification of Our Theoretical Contributions

Thank you for following up and for acknowledging the method's practical value. Our theoretical contribution combines a horizon-dependent coreset formulation with guarantees on coreset size and construction cost.

StrongKrylov preserves the objective uniformly over the entire affine Krylov space, with coreset size governed by the horizon TT rather than the full dimension dd. This can yield substantially smaller coresets when T≪dT \ll d. WeakKrylov avoids explicitly constructing the exact trajectory residual space: it uses approximate trajectory information while retaining near-optimality relative to the best bounded affine combination of the exact GD iterates. It further reduces coreset size and the expected number of full-data passes.

We hope this clarifies why we believe the horizon-dependent formulation and the accompanying constructions together constitute meaningful theoretical contributions.

Reviewer_b7seOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes to make coresets for linear regression that have sizes not dependent on the dimension of the query space dd but based on the number of iterations TT of a gradient descent-based solution approach. The intuition is that the GD iterates and residuals do not span the entire dd dimensional space but only the Krylov subspace whose span depends on the number of iterations TT. As a consequence, unlike classical coreset guarantees that should hold for all possible solutions in RdR^d, the Krylov strong coresets require the approximation guarantees to hold only over the solutions that lie in the span of the Krylov Subspace giving much smaller sized coresets using leverage score sampling when T<<dT <<d. The paper also builds a weak coreset that provides a good approximation only to the final solution obtained by the iterative method. This is done by approximating the gradient trajectory block wise. The weak coresets are smaller and computationally efficient. Theoretical claims are supported by experiments on both real and synthetic datasets.

I did not check the proofs in the appendices in details but as far as I could check they appear correct.

Critical strengths
  1. the paper makes smaller coresets for linear regression when solved using iterative methods and the idea is both interesting and intuitive and is supported by mostly clear writing.
  2. the technique to build the weak coreset is interesting.
Critical weaknesses
  1. The novelty in certain aspects is somewhat incremental in the sense the idea to use leverage scores to do subspace approximation is very well known and also the proofs of convergence and sample complexity follow well known methods.

  2. There are other coresets construction techniques that try to approximate the gradient at every iteration using subsampled data. They typically employ a submodularity based greedy selection scheme to construct coresets with separate guarantees. See works by Baharan Mirzasoleiman et al. and Rishabh Iyer et al. The paper does not comment on or compare with such techniques which I believe are relevant to this work

Questions for authors
  1. What is ξ\xi on lines 194-195? It is not defined as far as I could check.
3 comments

Weakness 1. The novelty in certain aspects is somewhat incremental in the sense the idea to use leverage scores to do subspace approximation is very well known and also the proofs of convergence and sample complexity follow well known methods.

Response. Thank you for this comment. We agree that leverage-score sampling and concentration bounds are standard tools. However, explicitly constructing the residual space induced by TT full-data GD iterates takes O(Tnd)O(Tnd) time, which can be computationally costly for large-scale datasets. Our contributions are the horizon-dependent coreset guarantees and an efficient weak coreset construction that avoids explicitly computing the full trajectory residual space.

The proposed StrongKrylov provides a horizon-dependent coreset by preserving the objective over the Krylov space. WeakKrylov uses blockwise gradient anchors, sampled Hessian corrections, and candidate-row reduction. This allows us to construct the residual basis and compute leverage scores on a reduced set of rows, without evaluating all trajectory residuals on the full data. The resulting coreset still provides a near-optimality guarantee over bounded affine combinations of the exact GD iterates. Under the stated conditions, the expected full-data processing term is reduced to O((T+log⁡(1/δ))nd)O((\sqrt{T}+\log(1/\delta))nd), with coreset size O(Tϵ−1log⁡(T/δ))O(T\epsilon^{-1}\log(T/\delta)).

Weakness 2. There are other coresets construction techniques that try to approximate the gradient at every iteration using subsampled data. They typically employ a submodularity based greedy selection scheme to construct coresets with separate guarantees. See works by Baharan Mirzasoleiman et al. and Rishabh Iyer et al. The paper does not comment on or compare with such techniques which I believe are relevant to this work.

Response. Thank you for pointing out these related works. CRAIG (Mirzasoleiman et al., 2020) uses submodular selection for gradient approximation, while GRAD-MATCH (Killamsetty et al., 2021) uses orthogonal matching pursuit for gradient matching. Their theoretical guarantees are based on gradient approximation. Our Krylov coresets exploit the finite-horizon structure of least squares. StrongKrylov preserves the objective over the Krylov space, while WeakKrylov provides a near-optimality guarantee over bounded affine combinations of exact GD iterates. Both have explicit coreset size bounds depending on TT. We have added a discussion of these differences in the Related Work section.

We also include additional experiments with CRAIG and GRAD-MATCH on the Synthetic dataset. The results show that StrongKrylov and WeakKrylov achieve lower regression losses and shorter running times than both baselines across the tested coreset sizes. Detailed results are provided in Appendix D.

Question 1. What is ξ\xi on lines 194-195? It is not defined as far as I could check.

Response. Thank you for pointing this out. This is a notation typo. The correct expression in Lines 194–195 is XR(X)=XT,R\mathcal X_R(X)=\mathcal X_{T,R}, where X=[x0,…,xT]X=[x_0,\ldots,x_T] is the exact GD trajectory and XR(X)={Xλ:λ∈ΛR}\mathcal X_R(X)=\{X\lambda:\lambda\in\Lambda_R\}. Both sets are defined immediately before Definition 2.2. The symbol ξ\xi does not denote an additional quantity here.

Thank you for your answers. The experiments do partially address the weakness. However, I am still not entirely convinced by the novelty of the paper and find it incremental. I will keep my score.

AuthorsOpenReview ↗

Clarification of Our Conceptual and Technical Contributions

Thank you for following up. We appreciate your consideration of our response. We would like to further clarify why we believe our contributions go beyond an incremental application of existing techniques. While leverage-score sampling is well established in the coreset community, the use of established techniques does not, by itself, make a new problem formulation or algorithmic construction incremental.

Our central contribution is a horizon-dependent coreset formulation and construction. Classical strong coresets preserve the objective over the full parameter space, with size bounds depending on the dimension dd. In contrast, our strong Krylov coreset preserves the objective throughout the entire affine Krylov space, with a size bound governed by the optimization horizon TT, which can be much smaller than dd in high-dimensional settings. This is not merely a different sampling rule for the same coreset problem; it changes the domain over which objective preservation is guaranteed. We believe this shift opens an important research direction for the coreset community. The accompanying weak construction further addresses how to build such summaries from approximate trajectory information while retaining near-optimality relative to the best bounded affine combination of the exact GD iterates.

We would appreciate your further thoughts on which aspects of these conceptual and technical contributions you consider incremental, particularly in relation to existing coreset formulations. We hope these distinctions can be taken into account in your assessment of the paper's novelty.

Comments on the paper

1 comment
Area_Chair_PyFcOpenReview ↗

Author–Reviewer discussion reminder

Dear reviewers,

Thank you all for your service to ICLR 2027. The author–reviewer discussion period is coming to an end. Could you please confirm if the authors' replies have resolved your questions?

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.