acceptodds
Withdrawn from ICLR 2027

Which Task Differences Matter? The Geometry of Optimal Shared Iteration

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

A solver that reuses one learned coefficient schedule across many tasks can underperform because of insufficient training, a restrictive update rule, or missing task information, but its loss cannot identify the cause. For positive-definite quadratics, we separate these sources of excess risk and characterize which task differences change the optimal program, the residual polynomial the schedule implements. Task laws with different spectra and oracle risks can require the same program. Given the population risk of every depth- program (equivalently, moments through degree ), moment vectors sharing an optimal depth- program form affine fibers of dimension through each interior point. Across fibers, the leading oracle-relative cost of sharing a program is the squared radius of the smallest ball enclosing the linearized optimal programs in the local risk metric. Under this criterion, the minimax program is optimal for a least-favorable mixture of laws; we prove a sharp worst-case bound, attained by smooth positive densities, on how many laws this mixture needs. A momentum recurrence implements this program while preserving the optimal first steps shared by all laws in the family.

Primary area:
optimization
Keywords:
learned optimizers, polynomial acceleration, spectral uncertainty, minimax design, moment problem, optimal experimental design, value of information

Reviews

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

This paper studies first order iterative optimization for optimizing positive definite quadratic objectives, characterizing when different populations of instances use the same optimal solver after kk-steps, given access to the best solver for tt-steps where t<kt < k. When such populations do not have the same optimizer, it finds the best compromise and estimates the added error.

Critical strengths

None

Critical weaknesses

Readability: This paper is extremely difficult to parse and understand. The paper introduces countless phrases and terms that have no proper definition, and relies heavily on symbols and jargon. This includes the first sentence of the abstract which mentions a solver, a learned coefficient schedule, and task information, all before we have even been introduced to the motivation behind the problem. This continues in the abstract, "spectra of task laws" has no prior definition and requires reading until page 3 of the paper to understand. This continues with statements like Theorem 1, which uses terms like "fibers", "unresolved moment domains", "local information price", and uses at least 10 unique symbols.

Scope and Novelty: The problem the authors tackle also appears artificial. There is no justification for why one would have access to the first KK-moments and not more, or less. The mathematical framework has some nice elements, but there is no finite sample or even asymptotic results (which the paper does state in the limitations section). This leads to a paper primarily talking about moments of depth-t programs, rather than learning, which is a different problem than the one mentioned in the abstract. Additionally, it seems difficult to convert these ideas into algorithms, as finding the moments in general is quite difficult.

Questions for authors

See weaknesses section.

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

This paper investigates iterative solvers accross PSD quadratic programs that share one sequence of step sizes and momentum cofficients. The paper then defines the program as a residual polynomial that the solver implements. The paper then questions the when the different task distributions necessitate different optimal programs. The paper proves that moment vectors form affine sets (but with the same optimal program). The paper then characterizes the minimax program and proves a bound to certify the optimality.

Critical strengths
  1. I find the same program characterization valuable as it differentiates the optimal computation from those changing the risk.
  2. It seems that the minimax characterization is sharp.
Critical weaknesses
  1. It seems that the theory assumes that they have access to the population risk function of every depth T program. This seems to be a highly strong assumption.
  2. The paper has a pretty inaccesible presentation. The language used in the paper reminds me of dry, and robotic language of language agents. I am not against the use of LLMs to write or prove. However, the papers are written for humans to read. I believe any reviewer will have difficulty reading, and carefully assessing the merit of this work due to the issues in presentation. I suggest authors to revise the manuscript to be more accessible, and be mindful of LLMs use of language.
Questions for authors

How robust is geometry when moments are estimated from data? Also, I am wondering whether the theory you developed in this paper can guide and actual information selection decision.

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

This paper investigates a theoretical question: when an iterative solver must share a common set of update coefficients across different tasks, what specific differences in task distributions actually influence the optimal iterative strategy?

The core argument of the paper is that differing task distributions do not necessarily imply different optimal computational strategies. What truly matters is not the variation in the task distributions themselves, but whether these variations alter the optimal iterative program.

Focusing on positive-definite quadratic optimization problems, the authors employ spectral laws, the method of moments, and minimax optimization to characterize the optimality of shared iterative strategies, the costs incurred by a lack of information, and which specific pieces of additional information about the tasks are truly valuable.

Critical strengths

A theoretical framework is proposed for understanding shared iterative algorithms through the lens of decision geometry. The authors demonstrate that distinct task spectral distributions can share an identical optimal residual polynomial, and they employ affine fibers to precisely characterize which higher-order moment directions leave the optimal program invariant. Regarding uncertainties that do affect the program, the paper defines a local "minimax information price"—quantified as the squared radius of the smallest enclosing ball within a risk-weighted program space—and further utilizes "least-favorable mixtures" to construct minimax momentum recurrences that preserve a common optimal prefix.

Critical weaknesses

I have several concerns about the assumptions and practical relevance of the results. First, the analysis is limited to positive-definite quadratics and scalar-coefficient iterations. The authors mention connections to learned optimizers and linear attention, but I am not convinced that the current theory tells us much about more general nonlinear optimization or practical Transformer models. More importantly, the paper assumes that the population risks of all depth-TT programs are known, or equivalently, that the first 2T2T moments are available exactly. This seems like a strong assumption, since in practice these moments have to be estimated from finite samples. I would like to see some discussion of how sensitive the main results are to estimation errors, especially the fiber characterization and the minimax construction. I am also concerned about the dependence on the uncertainty family. Figure 7 and Appendix F show that the empirical minimax method can perform substantially worse than the mean-trained schedule on held-out tasks. This makes me wonder how useful the minimax guarantees are when the spectral family is not accurately specified. Finally, while the characterization of least-favorable mixtures and the certificate size bounds are interesting, I am not sure what the practical advantage of the proposed approach would be over existing adaptive Krylov methods, or how one would construct a reliable uncertainty family from real data.

Questions for authors

I have several questions regarding the theoretical analysis and the proof of the main results. In particular, the transition from the minimax polynomial characterization in Appendix B.1 to the prefix-preserving momentum implementation in Appendix B.2 deserves a more detailed justification. Theorem 2 establishes not only the existence of a minimax shared program but also its attainability through a continuation that preserves the previously executed optimal iterations. I would appreciate a more explicit construction of the recurrence coefficients and a clearer explanation of how singular Gram matrices and degenerate cases are handled.

I also think the distinction between exact results and local approximations should be emphasized more carefully. The minimum-enclosing-ball characterization in Theorem 1(b) describes the leading-order information price under small moment perturbations, rather than a general characterization of the minimax risk for arbitrary spectral uncertainty. It is unclear how informative this approximation remains outside the local regime.

Finally, the empirical results raise questions about the practical consequences of the theory. The minimax construction is optimal relative to a specified family of spectral laws, yet the experiments show substantial deterioration under spectral misspecification. It would be useful to understand whether the proposed geometric characterization can be extended to account for uncertainty in the estimated moments or the spectral family itself.

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

Related papers

Discussion (0)

Sign in to comment.