Thank you for your positive review! We hope to address your questions below:

1. [The paper adopts an upper-bound surrogate loss function. Although this is reasonable due to the hardness in characterizing instance-specific convergence behavior of iterative methods, this still results in potential gap between theory and practice.]
   This is indeed a limitation of the results, although note we also study the non-surrogate case in Sec. 3 under a “semi-stochastic” assumption; please also see our section “On assumptions” in the general response for a more thorough discussion.
2. [This paper focuses on online learning algorithms. In practice this may still be inefficient in the exploration phase. Is it possible to adopt a static learning model and prove learnability result using tools from statistical learning theory? (e.g., train a classifier/regressor to predict the best.]
   Yes, while our paper focuses on online learning in the main part we do show sample complexity bounds obtained by doing offline training in App. A.1. Our approach leads to comparable bounds to those that can be obtained by directly applying the GJ framework (Bartlett et al., 2022), but unlike them we also provide an efficient learning algorithm to do it.
3. [The paper assumes iterative methods start from scratch. When solving a sequence of linear systems that are potentially from the same distribution, a common practice is to warm-start with previous solutions, and it often speeds up convergence. Is it possible also to incorporate this into your analysis?]
   Yes, the near-asymptotic results can handle a warm-started vector; in fact if ${\bf x}_t$ is the warm-start vector at step $t$ it is as simple as replacing ${\bf b}_t$ by ${\bf b}_t-{\bf A}_t{\bf x}_t$ when defining $\tau_t$ via Ass. 2.1. Note that this does assume the warm-starts do not depend on previous settings of $\omega$, which is not strictly true; however, the dependence is quite small ($O(\varepsilon)$).

References

Bartlett, Indyk, Wagner. Generalization bounds for data-driven numerical linear algebra. COLT 2022.

Thank you for your positive review! We appreciate the thoughtful suggestions and hope to address some of your concerns below:

1. [As mentioned by the authors, some of performance guarantees seem to be very loose (mainly the ones in section 3 with the dependency on dimension)]
   Yes, especially for the Sec. 3 results we might hope for logarithmic or better dependence on the dimension. At the same time, we were quite happy to get a logarithmic dependence on $1/\varepsilon$, which we view as important and non-trivial.
2. [could you expand a bit on the poor dependency on the spectral properties of the instances in theorem 2.3 (and maybe 2.2)? The authors mention that these dependencies are not ideal, but I do not have enough context to know what are dependencies that would be more "acceptable”]
   Apologies: we assume by “not ideal” you are referring to what we say in the first sentence of the last paragraph of the Conclusion. The phrasing there is a holdover from when Sec. 2 only had one main result. In fact we view all of the results in Sec. 2 as having “reasonable” dependence on spectral quantities (although it is unclear what the “correct” dependence is) while the results in Sec. 3 are perhaps less reasonable because of high (4th-order) powers in various spectral quantities. At the same time, we do view the main theoretical challenge as overcoming the dimension-dependence in Sec. 3.
3. [It seems to be that having stochastic target vectors with independent entries is a very strong assumption [...] it was not clear if mild correlation between the entries (positive definite correlation matrix with small off-diagonal entries?) would make the analysis break down [...] Moreover, how much do you depend on $b_t$’s being exactly the distribution you have?]
   In general we agree that it is restrictive, but at the same time we do view the stochastic target vector assumption as a fairly reasonable simplification; please see the second paragraph in the “On assumptions” section in our general response for a more thorough discussion. On whether one could extend the analysis to general (truncated) Gaussians: we believe that this might be doable, and that the resulting Lipschitz constant (and thus also the regret bound) might be the existing one multiplied by $O(1/\lambda_{\min}(\Sigma))$, i.e. it will be worse by roughly a factor of the reciprocal of the smallest eigenvalue of the covariance matrix. On whether there is an extension to more general distributions: Gaussianity is crucial to the anti-concentration component of the Lipschitz result ((46) and (47)), but perhaps the conversion from the truncated Gaussian in (45) can be generalized to conversions from other distributions.
4. [Although the experiments are not the focus of the paper, I do believe they are a bit too simplistic. I do no think the authors should spend time coming up with more experiments, but I think that discussing the limitations of the experiments would be helpful.]
   We had already been thinking about additional experiments and so have included them in the update; please see the general response for more details. While limitations naturally remain—the variant of the heat equation being solved does not obviously correspond to a specific known task, and the simulation is not truly large-scale—the sequence of linear systems is generated by an actual numerical simulation, and the size of the matrices is much larger (are high as $n\ge100,000$).
5. [A few times the authors mention that they provide "end-to-end" guarantees [...] Could your briefly mention that do you mean by this?]
   By “end-to-end guarantees” we mean guarantees that consider the full learning pipeline, from collecting data to optimizing to running the learned algorithm. In particular, end-to-end guarantees do not just treat learned advice as an oracle without considering whether it can be learned from data (as is often in the case in the algorithms with predictions literature) and do not just show learnability of an algorithm without providing a computationally efficient learning algorithm (as is often the case in the data-driven algorithm design literature). Note that we do provide a brief definition of this on the second line of page 2, although we can expand upon that.
6. [Suggestions]
   Thank you for the clarity suggestions: we will continue working on the descriptions of “asymptocity” and of the figures, and we have fixed the Lemma 2.1 reference. In Fig. 2 (left in the update, center before), we aim to show how by using a degenerate target, we can make the objective be optimal at and vary strongly around a specific $\omega$ (here we do $\omega=1.4$ by setting ${\bf b}$ to the be the smallest eigenvector of the iteration matrix corresponding to $\omega=1.4$). This suggests that assumptions on ${\bf b}$ might be necessary for learning.

Thank you for your positive review! We agree that the setting lends itself to future work, and hope to address some of your concerns below:

1. [The results are either about the surrogate loss, or under the assumption that part of the input is stochastic and not adversarial.]
   This is indeed a limitation of the work; please also see our section “On assumptions” in the general response for a more thorough discussion.
2. [Experiments are very basic. It is not a huge weakness as this paper can be positioned as a pure theory paper. However, since the solver seems to be used in practice, it seems it would not be difficult to get some actual input data it is run on, and results of such experiments would be very interesting to see.]
   We have updated our paper to include experiments where the sequence of linear systems is generated by an actual numerical simulation, and the size of the matrices is much larger (as high as $n\ge100,000$). Please see our general response for a summary and discussion of these results.
3. [Do you have any (even soft) argument that the limitations imposed (surrogate loss or stochastic input) are necessary to prove sublinear regret bounds?]
   Please see the second half of the second paragraph in the “On assumptions” section of the general response for a soft argument on the possible necessity of some type of restriction. There we note that Fig. 2 (left) shows that degenerate target vectors can generate objective functions reminiscent of those used to show lower bounds in online learning.
4. [It seems that learning optimal parameters for iterative methods (LP solvers, linear systems solvers, GD, etc.) should be similar and explainable with a single theory. Do you have any understanding why it does not seem to be the case, and we have separate results for each of these methods?]
   Interesting question. If one is mainly interested in sample complexity bounds then there do exist very general frameworks (e.g. dual function analysis (Balcan et al., 2021) or GJ (Bartlett et al., 2022)) that likely provide guarantees for some of these algorithms (we make a direct comparison to GJ in App. A.1). However, they do not always yield efficient algorithms or regret guarantees, which is what we were mainly interested in. While we are not familiar enough with LP solvers to know the relevant tunable parameters (barrier coefficient schedules for interior point methods?) and their effect, the difficulty of adjusting a continuous parameter for a discontinuous response is that one then has to make sure the discontinuities are controlled somehow (otherwise learning is hard since learning thresholds is hard). As a result, proofs end up depending on properties of the algorithm that make them behave reasonably but do not extend to other algorithms; for example, the step-size tuning result of Gupta & Roughgarden (2017) depends crucially on the guaranteed progress of GD, which does not hold for SOR. Similarly, our results in Sec. 3 depend on each iterate being a deterministic matrix power times a random vector; however, in Chebyshev semi-iteration each iterate is a matrix polynomial multiplied by a vector, which is also the case for conjugate gradient except now the polynomial coefficients depend on the vector as well. Thus studying iterative algorithms has so far involved making technical leaps, but perhaps a more general framework exists here as well.
5. [How your work compares to what people do in practice? Is it clear why they are not using similar methods? Would it be feasible to compare empirical performance of your approach to what is already done in practice?]
   When SOR and SSOR-preconditioned CG are used in practice, $\omega$ is usually set to a fixed parameter such as 1 or 1.5. Methods similar to those proposed may not yet be being used because of a preference for simplicity or a concern that learning is not robust. In our updated paper, we include experiments that compare to a setting more similar to what is done in practice (c.f. the general response).
6. [Minor remarks]
   Thank you for these notes; we have fixed all of them except the one about the abstract, as while the statement is not technically true in the near-asymptotic setting (Sec. 2), it is true in the semi-stochastic setting (Sec. 3).

References

Balcan, DeBlasio, Dick, Kingsford, Sandholm, Vitercik. How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. STOC 2021.
Bartlett, Indyk, Wagner. Generalization bounds for data-driven numerical linear algebra. COLT 2022.
Gupta, Roughgarden. A PAC approach to application-specific algorithm selection. SIAM J. Computing, 2017.

Thank you for your positive review! Below, we make one clarification and then respond to your weakness/question:

1. [The critical observation is that the SOR iteration is bounded by a convex surrogate function with the parameter.]
   While bounding the iteration cost of SOR by a surrogate function is indeed a key component of our approach, we note that the surrogate is not convex; instead the crucial properties of the surrogate are semi-Lipschitzness and unimodality.
2. [Maybe a weakness of the paper is that the reduction to OCO is restricted to a certain type of algorithm (SOR) only so far. […] Is it possible to extend this framework to other algorithms for solving linear equations?]
   It is indeed possible to extend the results to algorithms other than SOR; for example, in Sec. 2.5 we show similar guarantees for the widely used preconditioned conjugate gradient algorithm, although the parameter being tuned is still the relaxation parameter of the (Symmetric) SOR preconditioner. Future work could consider studying parameters other than the relaxation, such as the spectral bound of the Chebyshev semi-iterative method.