Beyond Diagonal Preconditioning in Deep Learning Optimization

23 concepts22 papers1 proposal

When training a deep neural network, the choice of optimizer can make or break a model's success. For years, the undisputed king of optimization has been Adam and its coordinate-wise adaptive variants. These algorithms scale the learning rate for each parameter independently based on historical gradient magnitudes.

To keep memory usage low, standard adaptive optimizers rely on a diagonal approximation of the gradient covariance or Hessian matrix. As noted by Liu et al., this design choice introduces a fundamental blind spot: it assumes that the gradients of different model parameters are entirely independent.

In reality, neural network parameters are highly coupled. Changing a weight in one layer alters the optimal update direction for weights in adjacent layers. By treating parameters as independent scalars, diagonal optimizers neglect these rich inter-parameter correlations, leading to inefficient navigation of high-dimensional, non-convex loss landscapes.

The Cost of the Independence Assumption

Why does ignoring parameter correlation matter? When an optimizer assumes coordinate-wise independence, it struggles with non-separable optimization problems—landscapes where the geometry is not aligned with the coordinate axes.

Diagonal Preconditioning (Adam):
Tracks only variance per parameter: [σ₁², σ₂², ..., σ_d²]
Implicitly assumes: Covariance(w_i, w_j) = 0

Full/Structured Preconditioning:
Tracks interactions: [ Covariance(w_i, w_j) ]
Captures: How changing w_i affects the gradient of w_j

As early as the work on vSGD-fd by Schaul et al., researchers recognized that diagonal approximations fail when parameters exhibit high correlations. In narrow, poorly conditioned valleys, coordinate-wise updates tend to oscillate wildly across the canyon walls rather than progressing smoothly down the valley floor—a challenge referred to as the "Valley Dilemma" by the authors of HVAdam.

This independence assumption also skews our theoretical understanding of optimization. Analytical derivations of optimizer stability often assume that gradients across different parameters are uncorrelated to keep math tractable. However, Zhang et al. demonstrated that ignoring off-diagonal covariance leads to incomplete models of optimizer variance and step stability. Similarly, modeling optimization dynamics via simplified Markov chains often breaks down because it fails to capture joint parameter dynamics during actual training (Zekri et al.).

Beyond theoretical inefficiencies, diagonal preconditioning can introduce structural pathologies into models. For instance, He et al. discovered that adapting learning rates independently for each parameter inadvertently drives specific features toward extreme values during Transformer training. This phenomenon creates "activation outliers" that severely hinder post-training 8-bit quantization.

In a comprehensive deconstruction of modern adaptive optimizers, Zhao et al. demonstrated that algorithms like Adam, Lion, and Adafactor exhibit remarkably similar peak performance limits precisely because they all share the same diagonal preconditioning bottleneck. They argue that the next major leap in optimization efficiency will require moving toward non-diagonal methods that directly model inter-parameter dependencies.

Bridging the Gap with Block-Diagonal Matrices

If a full $d \times d$ covariance matrix requires $O(d^2)$ memory and $O(d^3)$ computation—rendering it impossible for models with billions of parameters—how do we capture correlations efficiently? One natural compromise is to model local correlations using block-diagonal structures.

Instead of assuming every single weight is independent, block-diagonal methods group parameters that share a structural relationship (such as weights within the same layer, neuron, or convolutional filter) into dense blocks, while assuming independence between different blocks.

Full Matrix (Intractable)      Diagonal (Adam)          Block-Diagonal
      [ X X X X ]               [ X . . . ]               [ X X . . ]
      [ X X X X ]               [ . X . . ]               [ X X . . ]
      [ X X X X ]               [ . . X . ]               [ . . X X ]
      [ X X X X ]               [ . . . X ]               [ . . X X ]

Several frameworks leverage this compromise:

  • AdaBlock: Yun et al. proposed utilizing a flexible block-diagonal matrix adaptation scheme to capture local curvature and parameter interactions, improving both convergence speed and generalization over standard Adam.
  • Mini-Block Fisher (MBF): Bahamou et al. designed a second-order method that targets correlations within specific structural units, such as a single convolutional filter or a specific neuron's inputs, allowing the optimizer to navigate complex loss surfaces without heavy computational tolls.
  • AdaBK: From a theoretical perspective, Yong et al. proved that constraining full-matrix preconditioning to structured blocks minimizes regret bounds over time, providing rigorous guarantees for the practical success of block-structured updates.

Exploiting Tensor Structure: The Shampoo Paradigm

While block-diagonal methods isolate parameters into distinct chunks, an alternative paradigm exploits the intrinsic tensor geometry of neural network weights.

Consider a standard weight matrix $W \in \mathbb{R}^{m \times n}$. A full second-order preconditioner treating this layer as a flat vector would be a massive $mn \times mn$ matrix. The breakthrough algorithm Shampoo, introduced by Gupta et al., resolves this by factoring the preconditioner into two much smaller matrices: an $m \times m$ matrix capturing correlations between the rows, and an $n \times n$ matrix capturing correlations between the columns.

Weight Matrix W (m × n)
   ├── Row Preconditioner L (m × m)    --> Captures correlations between outputs
   └── Column Preconditioner R (n × n) --> Captures correlations between inputs

Factored Preconditioner ≈ L ⊗ R (Kronecker Product)

By utilizing this Kronecker product structure, Shampoo captures essential structural relationships within weight tensors while maintaining a runtime per step competitive with first-order methods. This tensor-structured approach has inspired a wave of modern optimization research:

  • KL-Shampoo: Lin et al. reframed the mathematical foundations of Shampoo and SOAP. By replacing the traditional Frobenius norm minimization with Kullback–Leibler (KL) divergence minimization, they eliminated the need for heuristic "Adam grafting" and significantly reduced memory overhead during large-scale language model pre-training.
  • CASPR: Duvvuri et al. extended this concept by combining axis preconditioners through a Kronecker-sum approximation, yielding tighter theoretical convergence guarantees and stronger generalization performance.
  • COSMOS: To scale non-diagonal preconditioning to massive Large Language Models (LLMs), Le et al. introduced a hybrid approach. COSMOS splits the gradient matrix into a "leading" subspace handled by the high-precision, non-diagonal SOAP algorithm, and a "residual" space managed by a memory-efficient coordinate-wise optimizer, capturing critical parameter interdependencies without exhausting hardware memory.

Matrix-Free and Sketched Alternatives

Can we capture full-matrix parameter correlations without explicitly storing blocks or Kronecker factors? Two prominent strategies have emerged to bypass explicit matrix storage entirely.

The first is matrix sketching. Feinberg et al. developed Sketchy, a framework that applies a deterministic matrix sketching technique called Frequent Directions to the gradient history. Sketchy compresses the tracking of gradient correlations from a quadratic memory footprint down to a sub-linear one, making second-order optimization viable for massive deep learning architectures.

The second strategy is matrix-free preconditioning. Cutkosky et al. developed an online learning framework that completely avoids storing or manipulating a covariance matrix. By framing optimization through a recursive "coin-betting" architecture, their algorithm adaptively senses the optimal update directions and accounts for inter-feature correlations while maintaining the strict $O(d)$ time and space complexity of simple diagonal methods.

Summary

The assumption that neural network parameters drift independently through the loss landscape is a convenient fiction—one born out of computational necessity during the early days of deep learning. As the field moves toward massive architectures where training efficiency and quantization stability are paramount, modeling inter-parameter correlations is no longer a luxury. Whether through block-diagonal grouping, Kronecker tensor factorization, or matrix sketching, capturing the structural dependencies of weights represents the frontier of deep learning optimization.

Key Foundational Work

Shampoo: Preconditioned Stochastic Tensor Optimization (2018) — contributed 1 concept elements to this direction.
Adaptive learning rates and parallelization for stochastic, sparse, non-smooth gradients (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parameter_independence_assumption_624028e0,
  title = {parameter independence assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameter-independence-assumption/rdr_624028e0ad284f5e888ba95d8d9992e1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_parameter_independence_assumption_624028e0_v1,
  title = {parameter independence assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameter-independence-assumption/rdr_624028e0ad284f5e888ba95d8d9992e1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake