PaperlayerView exact revision on arXiv

Source-linked AI summary

Predicting Block-Coordinate Performance via Cross-Curvature

Shengkun Zhu, Jinshan Zeng, Zhiqiang Kou, Yongxin Tong, Yang Liu

arXiv:2609.33489v1cs.LG

TL;DR

Choosing between simultaneous and sequential block updates is difficult because their relative advantage depends on objective geometry and iteration count. The paper compares Jacobi, Gauss–Seidel, and partially sequential updates using cross-block curvature and trajectory recursions. Across three settings, recursive estimates improve winner agreement and loss-gap accuracy over cumulative estimates.

  • Problem

    The paper addresses the lack of a unified theory for predicting which block-update scheme performs better for a given objective, partition, and iteration budget.

    Source: §1 · p. 2

  • Method

    The framework compares deterministic block-gradient schemes using cross-block curvature for one-step loss differences and trajectory and loss recursions for multi-step comparisons.

    Source: §1 · p. 2, §4.1 · p. 5, §4.2 · p. 5

  • Results

    Recursive estimates using measured parameter differences achieve higher winner agreement and lower loss-gap errors than cumulative estimates in all three evaluated settings.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The preferred update scheme can change as optimization progresses, so the comparison is state-dependent rather than a claim of universal superiority.

    Source: §1 · p. 2

    The multi-iteration comparison assumes bounded gradient, Hessian, and Hessian variation along both trajectories and intermediate updates, with ηK ≤ T for fixed T.

    Source: §4.2.1 · p. 5

Abstract

from arXiv · show

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 $O(\eta^3)$ remainder, where $\eta$ is the learning rate. We derive a signed loss comparison after $K$ iterations with $O(K\eta^3)$ error under regularity conditions and $\eta K\le T$ for fixed $T$, 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.

1 INTRODUCTION

The relative advantage of simultaneous and sequential block updates can change during training, yet existing theory offers limited guidance for choosing between them. The paper develops a curvature-based comparison and evaluates its predictions across three machine-learning settings.

1 INTRODUCTION

  • Choosing simultaneous or sequential updates remains difficult because classical linear-system results do not extend to nonlinear objectives or predict instance-specific performance gaps.Existing optimization theory emphasizes asymptotic guarantees rather than which scheme makes more progress at a given iterate.Source: §1 · pp. 1–2
  • Recorded training losses favor sequential updates early and simultaneous updates later in an MLP, federated ResNet-18, and LoRA fine-tuning.This reversal motivates a criterion for predicting when relative advantage changes.Source: §1 · p. 1
  • The framework compares simultaneous, sequential, and partially sequential updates through block-gradient interactions and cross-block curvature, accounting for how earlier updates change later trajectories.It yields a cumulative comparison after a prescribed number of iterations.Source: §1 · p. 2
  • The one-step GS–JC loss gap is determined by signed cross-curvature, with the sign identifying the lower-loss update when the leading term dominates the remainder.The comparison starts both methods from the same point.Source: §1 · p. 2
  • Across 500 iterations, cumulative winner agreement is 98.0% for the neural network, 83.4% for federated learning, and 97.6% for LoRA.The recursive estimate improves winner agreement and loss-gap accuracy in all three settings.Source: §1 · p. 2

2 RELATED WORK

Prior work establishes convergence guarantees, characterizes iterative dynamics, and develops application-specific update rules. This paper addresses the complementary question of comparing signed terminal losses for fixed Jacobi and Gauss–Seidel methods at a prescribed iteration budget.

2 RELATED WORK

  • Coordinate-descent research studies convergence across block-selection rules, smooth and composite objectives, and inexact surrogate updates.These results characterize how objective structure, selection, and subproblem accuracy affect convergence.Source: §2 · p. 2
  • Prior iterative-method work analyzes stability and convergence, asynchronous delays, game-update discretization, and neural-network training dynamics around initialization.The cited application literature also studies coupled blocks in neural networks, federated learning, and low-rank adaptation.Source: §2 · p. 3
  • For deterministic block-gradient updates, cross-curvature gives a one-step comparison with O(η^3) remainder, and trajectory propagation extends it to a prescribed number of iterations.The comparison concerns signed terminal losses and does not assert universal superiority of either scheme.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define Jacobi and Gauss–Seidel updates by whether block gradients use the shared current state or partially updated values. A delay pattern generalizes these extremes by specifying which blocks use fresh values, allowing acyclic hybrid schedules to be analyzed.

3.1 BLOCK-COORDINATE OPTIMIZATION

  • Jacobi updates all blocks in parallel using gradients at the current iterate, whereas Gauss–Seidel updates blocks sequentially using the freshest available values.The gradient approximation relates the GS gradient to the current gradient through the Hessian and lower-triangular block interactions.Source: §3.1 · pp. 3–4

3.2 GENERAL UPDATE SCHEMES VIA DELAY PATTERNS

  • A delay pattern S records which block updates use fresh values from other blocks, covering Jacobi, full Gauss–Seidel, and intermediate schedules.For three blocks, examples include a partial-GS pattern and a chain pattern.Source: §3.2 · p. 4
  • A pattern is acyclic when its dependencies admit an ordering in which each source block is updated before the block that uses its fresh value.For acyclic patterns, the first-order gradient correction is selected by the schedule and shaped by the retained Hessian blocks.Source: §3.2 · p. 4

4 THE MAIN THEOREM

The main theorem compares block-update schemes through cross-block curvature, then extends the comparison across iterations by tracking trajectory and loss differences. The resulting signed estimate identifies the lower-loss scheme when its predicted gap exceeds the error bound.

4.1 MAIN RESULT

  • Acyclic block-update schemes share the same first-order decrease, while cross-curvature supplies a second-order correction that can favor either scheme.For full Gauss–Seidel versus Jacobi, negative cross-curvature favors Gauss–Seidel and positive cross-curvature favors Jacobi when the leading term dominates the remainder.Source: §4.1 · p. 5

4.2 MULTI-STEP DYNAMICS

  • The one-step criterion compares methods from a common iterate, so it does not by itself determine which method has lower loss after multiple iterations.The multi-step analysis tracks the trajectory difference as a state variable and reads the loss difference from coupled recursions.Source: §4.2 · p. 5

4.2.1 STANDING ASSUMPTIONS AND NOTATION

  • The multi-step guarantees assume ηK ≤ T for fixed T and regularity bounds along both trajectories and their intermediate block updates.The stated conditions bound the gradient, Hessian, and Hessian variation.Source: §4.2.1 · pp. 5–6

4.2.2 TRAJECTORY AND LOSS RECURSIONS

  • The trajectory recursion propagates earlier parameter differences and adds fresh block-update effects, while the loss recursion separates inherited differences from current-update effects.The methods’ parameter difference remains O(η), allowing higher-order trajectory and loss terms to be bounded by O(η^3).Source: §4.2.2 · p. 6

4.3 MULTI-STEP CUMULATIVE LOSS DIFFERENCE

  • After K iterations, the signed loss comparison accounts for how earlier differences propagate through later updates and has O(Kη^3) accumulated error under the stated assumptions.A negative estimate favors scheme S; a positive estimate favors Jacobi, and the estimate connects local block interactions to the loss gap along the trajectories.Source: §4.3 · p. 7

5 EXPERIMENTS

The experiments compare cumulative and recursive loss-gap estimates with measured Jacobi and Gauss–Seidel outcomes over 500 iterations in three settings. Both estimates track changes in the lower-loss method, while the recursive estimate is more accurate overall.

5.1 EVALUATION PROTOCOL AND THEORETICAL ESTIMATES

  • The evaluation uses matched deterministic full-batch trajectories from a shared initialization, with losses measured after each of 500 complete block sweeps.The DNN, federated, and LoRA settings use fixed data subsets and constant learning rates without momentum or adaptive preconditioning.Source: §5.1 · p. 7, §5.2 · p. 8

5.2 VALIDATION ACROSS BLOCK-COUPLING STRUCTURES

  • 98.0%, 83.4%, and 97.6% winner agreement for cumulative estimates rise to 100.0%, 93.2%, and 99.6% with recursive estimates in the DNN, federated learning, and LoRA, respectively.The recursive estimate matches all 500 DNN winners; in federated learning it reduces errors during GS-favored intervals, and in LoRA it errs only at K = 79 and K = 133.Source: Table 1 · p. 8, Figure 2 · p. 8, §5.2 · p. 9

5.1 EVALUATION PROTOCOL AND THEORETICAL ESTIMATES

  • The recursive estimate uses the actual parameter difference from the preceding iteration, whereas the cumulative estimate propagates an approximation from the common initialization.Both estimates use gradients and Hessians evaluated along the observed JC and GS trajectories.Source: §5.1 · p. 8

5.2 VALIDATION ACROSS BLOCK-COUPLING STRUCTURES

  • JC and GS each achieve lower loss at different training stages in all three settings, and both estimates capture these changes.The measured winner changes from JC to GS in the DNN, while LoRA alternates from GS to JC and back to GS.Source: §5.2 · p. 9
  • The recursive estimate has lower mean absolute loss-gap error than the cumulative estimate in all three settings.The cumulative and recursive MAEs are 5.58 × 10^-4 and 1.15×10^-4 for the DNN, 0.295 and 0.0179 for federated learning, and 5.31×10^-2 and 5.97×10^-4 for LoRA.Source: §5.2 · p. 9, Figure 3 · p. 9

6 CONCLUSION AND FUTURE WORK

The paper develops a unified comparison of simultaneous, sequential, and partially sequential block-gradient updates. Across observed neural-network, federated-learning, and LoRA trajectories, recursive estimates outperform cumulative estimates in winner agreement and loss-gap error.

6 CONCLUSION AND FUTURE WORK

  • The recursive estimate, which uses measured parameter differences, achieves higher winner agreement and lower loss-gap errors than the cumulative estimate in all three settings.The theory characterizes one-step loss differences through cross-block curvature and extends comparisons across iterations using trajectory and loss recursions.Source: §6 · p. 9

A PROOFS FOR ONE-STEP COMPARISONS

The appendix establishes the one-step comparison for acyclic block-update schedules and supplies bounds and recursions used to control trajectory differences. These arguments connect fresh-value dependencies and cross-block curvature to the comparison between a scheme and Jacobi.

A PROOFS FOR ONE-STEP COMPARISONS

  • The proof proceeds from a gradient approximation under an acyclic delay pattern to a one-step loss expansion and then the GS–JC criterion.Acyclicity permits sequential implementation that respects fresh-value dependencies.Source: A PROOFS FOR ONE-STEP COMPARISONS · p. 13, §A.1 · p. 13

A.1 GRADIENT APPROXIMATION UNDER AN ACYCLIC DELAY PATTERN

  • Acyclic delay patterns support a gradient approximation based on the displacements of already-updated blocks.Each such displacement is −ηg_j + O(η^2).Source: §A.1 · p. 13

A.2 THE ONE-STEP LOSS EXPANSION

  • A second-order Taylor expansion compares the scheme’s loss change with Jacobi’s, with the scheme’s displacement including a curvature-dependent correction.The expansion retains an O(η^3) remainder.Source: §A.2 · p. 13

A.3 THE GS–JC CRITERION AND UPDATE ORDERING

  • For a fixed common starting point and nonzero cross-curvature, the leading term determines the GS–JC loss-difference sign for sufficiently small η.If cross-curvature is zero, the difference is O(η^3); any two full GS orderings from the same point differ by O(η^3).Source: §A.3 · p. 13

B AUXILIARY BOUNDS AND TRAJECTORY DYNAMICS

B.1 AUXILIARY NORM AND HESSIAN BOUNDS

  • The mask inherits the Hessian bound, and consecutive Jacobi Hessians differ by O(η).The stated constants depend only on the listed regularity parameters and block count.Source: §B.1 · p. 14

B.2 SIZE OF THE TRAJECTORY DIFFERENCE

  • The trajectory-size argument bounds the separation of the two methods’ iterates over the iteration horizon.The proof uses a growth factor bounded by e^(ηkL), with ηK ≤ T.Source: §B.2 · p. 14

B.3 THE TRAJECTORY RECURSION

  • The parameter recursion separates inherited trajectory differences from fresh update forcing and has a uniform O(η^3) remainder.The remainder bound uses ∥∆θ_k∥ = O(η); for a quadratic loss, the third-order Taylor remainder vanishes.Source: §B.3 · pp. 14–15

C PROOF OF THE LOSS EVOLUTION RECURSION

The loss-evolution proof substitutes the parameter recursion into a Taylor expansion and controls the resulting terms using trajectory-size bounds. This yields a uniformly bounded remainder for the loss recursion.

C PROOF OF THE LOSS EVOLUTION RECURSION

  • The loss recursion combines inherited parameter differences with fresh-update contributions and bounds the remaining terms using the parameter recursion.The proof evaluates the gradient at the next iteration and substitutes the parameter recursion into the loss expansion.Source: C PROOF OF THE LOSS EVOLUTION RECURSION · p. 15
  • The proof bounds terms involving the existing parameter difference, its interaction with the fresh-update correction, and the cubic remainder.The cubic remainder is controlled using a bound on the next iterate’s parameter difference.Source: C PROOF OF THE LOSS EVOLUTION RECURSION · pp. 15–16
  • All remainder terms are uniformly O(η^3), establishing the stated loss recursion.Source: C PROOF OF THE LOSS EVOLUTION RECURSION · p. 16

D MULTI-STEP CUMULATIVE DERIVATION

Under kη ≤ T, the terminal loss comparison follows by propagating local remainders through the trajectory. The resulting signed formula has O(Kη^3) error.

D MULTI-STEP CUMULATIVE DERIVATION

E EXPERIMENTS DETAILS

The experiments detail block structures and update semantics, then derive layer-wise gradients and distinguish simultaneous from sequential update states. For ReLU networks, the loss-comparison assumptions apply locally away from activation boundaries.

E EXPERIMENTS DETAILS

  • The experiments compare layer-wise, personal/shared, and LoRA factor updates by the parameter values used to evaluate block gradients.The appendix documents idealized update equations, implementations, stochastic state, and loss-recording conventions.Source: E EXPERIMENTS DETAILS · p. 17, Table 2 · p. 17

E.1 LAYER-WISE UPDATES AND BACK-PROPAGATION

  • Back-propagation computes the reduced gradient through forward states and backward adjoints; JC evaluates all layer gradients at one common state, whereas GS incorporates preceding block updates.In the specified GS sweep, the output-layer update agrees with JC at a common starting point, while earlier-layer updates generally differ through updated subsequent layers.Source: §E.1 · pp. 18–19
  • For ReLU networks, the loss-comparison smoothness assumptions hold locally away from activation boundaries and need not hold when an update crosses one.The panel (a) implementation uses updated weights in one backward recursion but retains original forward states and output residual, so its GS-like updates need not be the mixed-state gradients.Source: §E.1 · p. 19

E.2 FEDERATED LEARNING WITH PARTIAL MODEL PERSONALIZATION

The federated setup contrasts joint local updates with personal-then-shared updates and aggregates shared parameters across participating clients. The LoRA setup compares simultaneous and alternating factor updates, which correspond to JC and GS under a fixed deterministic objective and common step size.

E.2 FEDERATED LEARNING WITH PARTIAL MODEL PERSONALIZATION

  • FedSim evaluates personal and shared gradients at the same local state, while FedAlt updates personal parameters first and evaluates the shared gradient using those updated parameters.With exact gradients of the same fixed local objective, the two-block FedAlt equations reduce to GS; multiple local steps, stochastic sampling, and server aggregation add dynamics beyond one deterministic GS sweep.Source: §E.2 · pp. 19–20
  • Only shared parameters are communicated and aggregated; under uniform client sampling with unequal shard sizes, normalized selected-client weights need not give an unbiased full-population weighted aggregate.Personal parameters remain local across communication rounds.Source: §E.2 · pp. 19–20

E.3 SIMULTANEOUS AND ALTERNATING UPDATES FOR LORA

  • For LoRA, simultaneous updates evaluate both factor gradients at the current state, while alternating updates evaluate the A gradient after updating B.The alternating rule requires a new network evaluation at the mixed state; retaining previous adjoints does not generally recover that partial derivative.Source: §E.3 · pp. 20–21
  • With a common step size and fixed deterministic objective, simultaneous and alternating LoRA updates are exactly two-block JC and GS updates in order (B, A).Cross-Hessian blocks between the factors determine the coupling term in the one-step comparison.Source: §E.3 · p. 21

Related papers

Loading 2609.33489v1…