Keeping Quasi-Newton Methods Coordinate-Free in Low Precision

Some optimizers are affine-invariant: if you stretch or rotate the coordinate system the problem is written in, they take exactly the same steps, just expressed in the new coordinates. Quasi-Newton methods such as BFGS have this property on log-sum-exp losses like multinomial logistic regression, and their convergence guarantees do not depend on how badly the problem is scaled. Those guarantees assume exact arithmetic. Floating-point numbers are not coordinate-free, because every coordinate carries its own exponent and rounds independently. The thesis of this note is that, in 16-bit arithmetic, invariant optimizers quietly become coordinate-dependent, and that this happens through two specific, repairable channels. The first is the representable range: individual entries underflow, meaning they fall below the smallest representable number and become zero, even when the invariant quantity they sum to is perfectly ordinary. The second is cancellation: gradient differences near a confident optimum are computed as small differences of nearly equal numbers. Computing the curvature information in log space removes both channels while keeping 16-bit memory cost.

The mechanism is concrete. Under the reparameterization $z = A^{-1}x$, the step $s$ and gradient difference $y$ that BFGS stores transform oppositely: $s_z = A^{-1}s_x$ and $y_z = A^\top y_x$. Their inner product $s^\top y$ is therefore invariant, but its individual terms are not. With a diagonal $A$ of condition number $\kappa$, entries of $s_z$ shrink by up to $\kappa$ while entries of $y_z$ grow by up to $\kappa$, and either can leave the fp16 normal range of roughly $6\times10^{-5}$ to $6.5\times10^{4}$. When $s^\top y$ is then computed as nonpositive, standard implementations skip the update or add a damping term $\epsilon I$. That damping prefers the stored basis, so the method degrades toward scaled gradient descent, which is exactly the coordinate-dependent behaviour invariance was meant to avoid. A second, independent source of tiny numbers is model confidence. On log-sum-exp losses the gradient is $J^\top(p - e_y)$, where $J$ is the data matrix, $p$ the predicted class probabilities and $e_y$ the one-hot label. As $p_y \to 1$ the residual $1 - p_y$ and the difference $p_{k+1} - p_k$ cancel catastrophically in any short format.

Core Claim

The claim is that the low-precision "invariance gap" of a quasi-Newton method splits into a range component and a cancellation component. Rotations mostly leave both alone. Ill-conditioned diagonal scalings trigger the range component, and confidence saturation triggers the cancellation component. Both can be closed by one change: form the curvature pairs in log space. For log-sum-exp objectives the gradient difference can be written as

$$y_k = J^\top \big(p_k \odot \mathrm{expm1}(\log p_{k+1} - \log p_k)\big),$$

where $\odot$ is elementwise product and $\mathrm{expm1}(u) = e^u - 1$ is evaluated accurately for small $u$. This computes the probability change from a difference of log-probabilities, which are well-scaled, rather than from a difference of probabilities that are both near 1. The vectors $s$ and $y$ are stored as sign plus log-magnitude in 16 bits, following the logarithmic number tracking that Sheldon et al. embed in automatic differentiation. Their inner products are accumulated as a signed log-sum-exp with compensated (Kahan) summation, so the scalar $s^\top y$ never passes through per-coordinate products that underflow. Limited-memory BFGS (L-BFGS) needs only inner products and vector updates, so the change costs $O(md)$ for $m$ stored pairs in dimension $d$, with no $d \times d$ matrix.

Relation to Prior Work

Two papers supply the exact-arithmetic baseline that this work stress-tests. Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance proves scale-free linear and then superlinear rates for full-memory BFGS on self-concordant losses, including log-sum-exp, and shows that BFGS trajectories are unchanged under linear transformations where gradient descent degrades. It assumes exact arithmetic and full memory. We ask how much of that invariance survives fp16 and bf16 with limited memory, and how to restore it.

Affine-Invariant Online Optimization and the Low-rank Experts Problem motivates the focus on damping. It shows that initializing a preconditioner with $\epsilon I$ imposes an arbitrary basis, and avoids this with a pseudoinverse. We argue that low precision reintroduces this hidden $\epsilon I$ through skipped or damped updates.

LSEMINK is both our strongest competitor and a constraint. It shows that log-sum-exp Hessians vanish at high confidence, and fixes the resulting unbounded Newton steps with a shift restricted to the data row space instead of isotropic damping. That fix addresses the exact-arithmetic degeneracy, not floating-point range, and it carries no invariance proof. Our proposal targets the arithmetic failure that remains even when the degeneracy is handled.

The log-space and low-precision ideas we reuse come from three papers. A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization cancels exponentials analytically in a dual update, but keeps a Euclidean primal step. SoftDTW-CUDA-Torch moves an unstable backward recursion into log space. Low-Precision Reinforcement Learning shows that fp16 Adam crashes because $g^2$ underflows, and fixes it with hypot-based second moments and Kahan summation. That fix is local to each coordinate. Our setting is a cross-coordinate invariant scalar whose terms scale with the basis.

Preconditioned Norms characterizes when matrix optimizers are affine- or scale-invariant, again in exact arithmetic. Its MuAdam-SANIA is reported to stay robust on ill-conditioned Mushrooms data where AdamW degrades. Finally, the work on Adam's coordinate geometry (Understanding Adam Requires Better Rotation Dependent Assumptions; Adam Exploits ℓ∞-geometry) establishes that basis dependence can help as well as hurt. Our study adds a different and previously unmeasured source of basis dependence: the number format itself.

Research Program

The first deliverable is a diagnostic. We run the same optimizer on $f(x)$ and on $f(Az)$ and map the second trajectory back through $A$. The invariance gap is the normalized distance between the two iterate sequences, recorded alongside suboptimality. We sweep three families of transformations: random rotations, diagonal scalings with $\kappa$ from $10^2$ to $10^{12}$, and products of the two. Each is run in fp32, fp16 and bf16.

The decomposition predicts four things in advance:

  1. Rotations should produce gaps near rounding level in all formats, because they preserve norms and do not spread magnitudes systematically.
  2. Diagonal scalings should break fp16 once the scaled entries of $s$ and $y$ exit the fp16 normal range. The threshold in $\kappa$ can be computed from the natural spread of entries and the roughly $10^9$ ratio between the largest and smallest normal fp16 values.
  3. bf16 has an fp32-sized exponent range, so it should survive the scaling sweep but fail as confidence saturates, through cancellation in $y$.
  4. The fraction of skipped or damped updates should track the gap, which identifies hidden damping as the route by which invariance is lost.

The second deliverable is log-space L-BFGS as described above. It is tested deterministically and then with mini-batches, where invariance additionally competes with gradient noise. The analysis component is a floating-point error bound on $s^\top y$ and on the two-loop recursion of L-BFGS. The bound is stated in terms of the log-magnitude precision instead of the per-coordinate exponent range, so it is independent of diagonal $A$ by construction.

As a secondary probe we will test the Newton-Schulz orthogonalization inside MuAdam under the same diagonal-scaling sweep in bf16. Preconditioned Norms does not examine that iteration's behaviour at small singular values. This probe only reports measurements; it is not part of the core claim.

Baselines

The naive reference is L-BFGS run entirely in fp16, and separately in bf16, with standard safeguards (skip the update when $s^\top y \le \epsilon$). It shows the size of the problem. The exact reference is the same L-BFGS in fp32. It is the ceiling for invariance gap and convergence that the proposal must approach at 16-bit memory.

The strongest simple competitor is bf16 storage with fp32 accumulation of inner products plus Kahan summation. This is what mixed-precision hardware and the Low-Precision RL recipe would suggest. A second competitor is fp32 storage of only the $m$ history pairs. That is a real threat, since history is a modest fraction of memory, and we report its memory honestly.

The strongest existing method for these objectives is LSEMINK. It will be run in the same precision formats, under the same Armijo line search and the same budget of gradient and Hessian-vector evaluations. Its reported strength on CIFAR-10 multinomial regression is runtime: "roughly 30 seconds on a standard laptop" where CVX did not finish in 30 minutes. No reported result was found on Lacuna for low-precision L-BFGS or LSEMINK, nor for invariance gaps under scaling. We will therefore establish those numbers ourselves, with each method's own hyperparameters tuned on the untransformed problem using an equal grid. Tuning only on the untransformed problem is the point of an invariance test.

Adam and the hypot-based hAdam in fp16 serve as first-order references, to show what a practitioner would get without curvature information.

Two ablations isolate the ingredients. One uses log-residual formation of $y$ with ordinary 16-bit storage. The other uses log-magnitude storage with the naive $y$. The decomposition predicts that the first closes the confidence-saturation gap and the second closes the scaling gap.

The proposal beats the field if it achieves three things across the full diagonal-scaling sweep and the high-confidence regime:

  1. Its invariance gap and iterations-to-tolerance stay within a small factor of fp32 L-BFGS.
  2. It does this at 16-bit history memory.
  3. It shows clearly lower gaps than bf16 with fp32 accumulation, and than LSEMINK in the same format, in at least one of the two regimes.

Why not just…?

Why not just use fp32 or fp64? Higher precision closes the gap and is our ceiling, not a straw man. The question is whether the gap can be closed at half the history memory and with 16-bit throughput. The memory argument is concrete: SoftDTW-CUDA-Torch shows that changing representation can cut memory from about 8 GB to 161 MB where brute-force precision cannot. If fp32 history storage costs little overall and matches us, we will say so. The contribution then narrows to the diagnosis and the cancellation fix, which fp32 does not fully remove as $p_y \to 1$.

Why not just use bf16, which has fp32's exponent range? This is the most serious alternative. The decomposition predicts that bf16 survives diagonal scaling on range grounds, so for that channel bf16 may be enough. The predicted bf16 failure is cancellation in $y$ at high confidence, which no exponent range addresses. The confidence sweep, run with logit scales increasing and smoothing $\eta \to 0$ as in LSEMINK's stress tests, decides whether that failure is real and large. If bf16 with fp32 accumulation matches us there as well, the log-space machinery is unnecessary and we will report that.

Why not just use Adam or hAdam and skip curvature altogether? First-order methods sidestep $s^\top y$ entirely. However, the BFGS invariance paper shows gradient descent degrading under ill-conditioned linear transformations where BFGS does not. Preconditioned Norms reports AdamW degrading on ill-conditioned Mushrooms data. hAdam fixes Adam's underflow but keeps it tied to the stored basis. The scaling sweep measures this directly.

Why not just whiten or rescale the data once? Rescaling removes the particular $A$ we inject. It does not remove confidence saturation, which arises during training. It also requires knowing the bad scaling in advance, which the online low-rank experts work argues is generally unavailable. The confidence-regime experiments are unaffected by any preprocessing.

Proposed Experiments

The deterministic suite follows LSEMINK's settings. It uses multinomial logistic regression on MNIST and on CIFAR-10 random-feature and AlexNet features, Mushrooms from LIBSVM, and synthetic geometric programs including the nearly non-smooth large-$\eta$ cases. Each problem is crossed with the rotation, diagonal-scaling and combined sweeps, and with three precision formats.

The decisive checks are three. First, the diagonal-scaling threshold at which naive fp16 L-BFGS breaks should match the threshold predicted from the format's range, and should coincide with a rise in skipped updates. Second, the bf16 gap should appear only as confidence grows, and it should close under the log-residual ablation but not under the storage ablation. Third, rotation gaps should stay at rounding level for every method in the invariant family. If rotations alone produce large gaps, the decomposition is wrong.

The stochastic extension runs mini-batch L-BFGS on CIFAR-100 linear probes in the imbalanced setting used by the compositional entropic risk work. It tests whether log-space curvature pairs keep their advantage once gradient noise dominates rounding error. A negative result there would bound the claim to deterministic or large-batch regimes.