- 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 gradient descent iterates lie in an affine Krylov subspace of dimension at most . 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
Thank for you reply. I'll maintain my score.
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 . In contrast, our strong Krylov coreset preserves the objective throughout the entire affine Krylov space, with a size bound governed by the optimization horizon , which can be much smaller than 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.
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 d rows. Our work introduces a new perspective to regression coreset research by exploiting the finite optimization horizon to obtain coreset size bounds independent of d. 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/δ)). 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(xS)≤1−ε1+εF(xTCG), where xS 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% to the full-data Krylov-space optimum with m=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.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.