acceptodds
Under review as a conference paper at ICLR 2027

Predicting Block-Coordinate Performance via Cross-Curvature

Abstract

Simultaneous and sequential block updates are two basic optimization strategies used across machine learning, such as neural-network training, federated learning, and low-rank adaptation. Choosing between them is difficult because their relative advantage depends on both the objective geometry and the number of iterations. We develop a unified theory for comparing Jacobi (JC), Gauss–Seidel (GS), and partially sequential deterministic block-gradient updates. Our analysis expresses the one-step loss difference through cross-block curvature, with an remainder, where is the learning rate. We derive a signed loss comparison after iterations with error under regularity conditions and for fixed , identifying the better method when the predicted difference exceeds this error. We evaluate these formulas along observed training trajectories across different machine learning settings. Over 500 iterations, our theory correctly identifies the lower-loss method in 98.0% of iterations for the neural network, 83.4% for federated learning, and 97.6% for LoRA. Applying the loss recursion at each step using the measured parameter difference raises these rates to 100.0%, 93.2%, and 99.6%, respectively.

Primary area:
optimization
Keywords:
Coordinate descent, Gauss-Seidel update, Jacobi update, Cross-Curvature

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_rAE7OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

In this work, the authors develop a cross-curvature based theory which allows to compare Jacobi and Gauss–Seidel block-gradient updates, extending one-step loss comparisons to multiple iterations. This allows to estimate a priori which iterate is a better choice up to third order in the learning rate. The work is complemented with a small series of numerical experiments

Critical strengths
  1. The problem studied by the authors is of interest for the community and well-motivated.
  2. The multi-step theoretical analysis is supported by positive empirical results
Critical weaknesses
  1. The proposed analysis, while being informative from a theoretical perspective, are not clearly applicable as this would require computing gradient Hessian products from both observed trajectories, which can be fairly expensive in large-scale optimization problems.
  2. The theoretical analysis is strongly based on known theory, and the overall key idea relies on a Taylor expansion and a standard trajectory perturbation analysis.
  3. In the main paper there is no empirical validation of the Kη3K\eta^3 result presented in Theorem 3.
Questions for authors

Do the authors believe this criterion can be used or adapted to a scalable criterion for online update selection in block coordinate methods? What would be the computational overhead?

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

The authors consider the question of when it is better to use simultaneous (Jacobi) or sequential (Gauss-Seidel) block-gradient updates. They derive a cross-curvature condition to predict whether one update step will yield a lower loss. In particular, for the gradient gg and Hessian HH, if 2∑i<jgiTHijgj2 \sum_{i < j}g_i^TH_{ij}g_j is positive, then the Jacobi scheme is better, whereas if it is negative, then Gauss-Seidel is better. They then extend this analysis to multiple steps. Under strong assumptions (bounded gradient, bounded Hessian, Lipschitz Hessian) they derive a criterion for choosing the scheme for this setting. They also consider hybrid update approaches. They validate their criterions in a wide range of experiments, demonstrating that the theory holds.

Critical strengths

The question is interesting and highly relevant, and the consideration of hybrid methods is very pertinent as well.

Critical weaknesses
  1. The method for identifying the superior scheme relies on computing the Hessian, which is computationally expensive.
  2. The multistep analysis requires extremely strong assumptions that do not hold in practice.
  3. The theory is shown to work in practice, but requiring significant computational efforts. It is also not surprising that the theory works, because it follows rather straightforwardly from Taylor expansions of the functions. The manuscript would be significantly stronger if it showed a more practical version of the method for predicting the superior update scheme.
  4. It appears in the experiments that the differences between JC and GS are actually minimal, as each scheme outperforms the other at some point during the training period. This somewhat undermines whether this choice is important at all, suggesting that one should just pick based on the hardware constraints rather than because of performance.

Minor issues

  1. Typo on the first line "widely used in machine learning. Across deep learning, federated" there is an extra period.
  2. Mathematical terms should be defined before using, for example in the bullets 082-094, the terms KK, gg, HH are not defined.
Questions for authors

It would be interesting to consider gradient descent ascent as well. For this setting, it is known that simultaneous updates can diverge, whereas alternating updates may converge or oscillate.

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

The paper compares simultaneous Jacobi-style and sequential Gauss–Seidel-style block-gradient updates, including partially sequential acyclic update patterns. It derives a one-step loss difference governed by cross-block curvature and extends the comparison to multiple iterations by propagating parameter differences along the optimization trajectories. Under regularity assumptions and a fixed time horizon with eta K <= T, the terminal loss estimate has an O(K eta^3) remainder. Experiments on a neural network, personalized federated learning, and LoRA evaluate how accurately the formulas reproduce the sign and magnitude of observed loss differences.

Critical strengths
  1. The theory gives a geometric account of the difference between simultaneous and sequential updates. The one-step expansion isolates signed interactions between block gradients and cross-block curvature. The multi-step analysis also accounts for the propagation of earlier parameter differences, connecting the local comparison to the evolving trajectories.

  2. The experiments directly examine the theoretical formulas under controlled conditions. The three settings cover different block structures. Reporting loss-gap errors and class-specific winner counts, alongside overall winner agreement, provides useful evidence about where the approximations work and fail.

Critical weaknesses

1. My main concern is what practical guidance the theory provides.

Which tasks, block structures, or training stages should use JC, and which should use GS? Section 5.1 explicitly states that both estimates use derivatives along the actual JC and GS trajectories, with the recursive estimate also using measured parameter differences. These are useful formula diagnostics, but once both trajectories are available, their losses can already be compared directly. Identifiable structural conditions or a decision rule using one trajectory or a short pilot would make the significance clearer. A transferable explanation would also be valuable without requiring a new optimizer.

2. The theory's relevance to longer training remains unclear.

The results require sufficiently small learning rates and a fixed effective time horizon, eta K <= T. The trajectory bound in Lemma 2 also grows with exp(TL), so the error control can deteriorate as the training horizon increases. These restrictions leave unclear whether the theory remains informative over long training runs at a fixed learning rate. Do the learning rates and training durations used in the experiments fall within a regime where the approximations are reliable?

3. The benefit over simply choosing one method is unclear.

In federated learning, always predicting that GS wins is correct at 472/500 = 94.4% of iterations, above the two estimates' 83.4% and 93.2%. The estimates do identify 25 of the 28 JC wins, so they provide information beyond this simple baseline. However, the experiments do not show whether that information leads to better choices in terms of loss. Does using the criterion offer a meaningful benefit over always choosing JC or GS, after accounting for its extra computation?

Questions for authors
  1. What concrete guidance does the theory provide about when to use JC or GS? Can the sign or evolution of cross-curvature be related to identifiable task or block-structure properties? Alternatively, can a useful decision be made using one trajectory or a short pilot, with its computational cost reported?

  2. Does the theory cover the learning rates and training durations used in the experiments? Given the small-learning-rate requirement, eta K <= T, and the exp(TL) factor in Lemma 2, how long does the theoretical comparison remain informative at the chosen learning rate? Please clarify how these restrictions relate to the reported training runs.

  3. Does using the criterion lead to better choices than always choosing JC or GS? In particular, how should we interpret the federated-learning results when always predicting GS already gives 94.4% agreement? Can the authors show a benefit in the resulting loss after including the criterion's computational cost?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.