Experiments › Diagnostics

Experiment: Gradient projection comparison

Source: exp_gradient_interference.sx · Euclidean PCGrad, cosine-scaled projection and Riemannian PCGrad on random conflicting pairs

What is compared

Three PCGrad-type projections are applied to pairs of conflicting gradients (\( g_i \cdot g_j < 0 \)). The cosine-scaled operator is

\[ g_i' = g_i - \alpha \cdot |\cos(g_i, g_j)| \cdot \frac{g_i \cdot g_j}{\|g_j\|^2} g_j , \]

which grades the correction by the cosine similarity. Each such projection preserves first-order descent of each objective: \( g_i' \cdot g_i > 0 \) whenever \( g_i \neq 0 \). That is the property being exercised here. The projections also have explicit limitations that the pair-counting experiment below does not probe: the projected dynamics admit non-unique limit points, stall in one dimension (where any two conflicting gradients are antiparallel and the projection removes one of them), and exhibit period-two orbits at moderate step sizes. Those cases are constructed in the Unified Adaptation Theorem record.

Method

Setup: Three projection methods run on 500 randomly generated gradient conflict pairs in 4D parameter space.

Parameters:

  • Gradient pairs: 500
  • Parameter dimension: 4
  • Conflict criterion: \( g_i \cdot g_j < 0 \)
  • Non-conflict after projection: \( g_i' \cdot g_j \ge 0 \)

Procedure: Generate pairs of gradient vectors with negative dot product. Apply each projection and record whether the projected gradient still has a negative dot product with the opposing gradient.

Results

MethodPairs with \( g_i' \cdot g_j \ge 0 \)Conflicting pairsRate
Euclidean PCGrad500500500/500
Cosine-Scaled Projection500500500/500
Riemannian PCGrad325489325/489 (66.5%)

Note: under the Riemannian metric 489 of the 500 pairs are in conflict (11 pairs are not), and 325 of those 489 have non-negative dot product after projection.

Analysis

On this pairwise, single-step test the Euclidean and cosine-scaled operators both remove the negative dot product on every pair, by construction of the operators:

  • Euclidean PCGrad removes the full component of \( g_i \) along \( g_j \), which is a large correction on nearly-aligned gradients.
  • Cosine-scaled projection grades the correction by \( |\cos(g_i, g_j)| \), applying a small correction when gradients are nearly orthogonal and the full correction only when they are directly opposed, and keeps more of the original gradient.
  • Riemannian PCGrad leaves 164 of 489 pairs with a negative dot product, because the projection direction under the curved metric does not coincide with the Euclidean conflict hyperplane used as the test.

A single-step pair count says nothing about where the iterated dynamics go. With the cosine-scaled operator: limit points are not unique (different starting points reach different balanced points); in one dimension two conflicting gradients are antiparallel and the projection removes one of them, so the iteration stalls; and at moderate step sizes the alternating corrections produce period-two orbits. These are explicit examples, not edge cases of the counting test.

Summary

On 500 random 4D pairs, Euclidean PCGrad and cosine-scaled projection remove the negative dot product on 500/500; Riemannian PCGrad on 325/489. The projections preserve first-order descent of each objective; their iterated dynamics admit non-unique limits, one-dimensional stalls and period-two orbits at moderate step size.

Reproducibility

../simplex/build/sxc exp_gradient_interference.sx -o build/exp_gradient_interference.ll
clang -O2 build/exp_gradient_interference.ll ../simplex/runtime/standalone_runtime.c \
  -o build/exp_gradient_interference -lm -lssl -lcrypto -L$(brew --prefix openssl)/lib
./build/exp_gradient_interference

Related