Error Feedback in the Right Units for Hyperbolic Embeddings

Hyperbolic embeddings place the items of a hierarchy, such as the nouns of WordNet, inside a negatively curved space. In that space, distances grow exponentially toward the edge. General concepts sit near the center, specific ones sit near the boundary, and a 5-dimensional embedding can beat a 200-dimensional flat one. Error feedback is the standard trick that lets distributed training send heavily compressed gradients (top few coordinates, or just signs) without losing accuracy. Each worker keeps whatever compression threw away and adds it back the next round. Nobody has combined the two. The combination is not a plug-in, because error feedback silently assumes that every coordinate of every gradient is measured in the same units.

This note argues that the main way naive error feedback fails on hyperbolic embeddings is a units problem, not a curvature problem. In the Poincaré ball, the local "ruler" changes by orders of magnitude between the center and the boundary. A compressor that ranks raw coordinate gradients therefore sends almost only boundary (leaf) rows and starves the general concepts near the center. We propose to rescale gradients and residuals into the space's local orthonormal frame before compressing and buffering them. In that frame, moving a stored residual from one point to the next becomes a pure rotation, which is cheap or even negligible. We also lay out the experiments that would show whether this matters, or whether plain ambient error feedback is already good enough.

Core Claim

Use the Poincaré ball model, the open unit ball with conformal factor $\lambda_x = 2/(1-\|x\|^2)$ at point $x$. The metric is $\lambda_x^2$ times the Euclidean one. Riemannian SGD, as in Poincaré Embeddings for Learning Hierarchical Representations, computes the ordinary coordinate gradient $g$ of an embedding row. It then steps along $r = \lambda_x^{-2} g$. The length of that step, measured by the space's own metric, is $\|r\|_x = \|g\|/\lambda_x$.

Any compressor that ranks rows or coordinates by $\|g\|$ therefore over-weights each row by exactly $\lambda_x$ relative to the size of the update it will actually produce. With the usual clipping at $\|x\| \le 1-10^{-5}$, $\lambda_x$ reaches about $10^5$ at the boundary and equals 2 at the center. Error feedback guarantees that starved rows are eventually sent, as Error Feedback Fixes SignSGD and other Gradient Compression Schemes shows: it converts loss into delay. Here, though, the delay for an interior row grows roughly with the ratio of boundary to interior conformal factors. The interior rows are precisely the ones that fix the global angular layout of the hierarchy. That layout is already the fragile part of hyperbolic training: Nickel and Kiela need a reduced-learning-rate burn-in phase to find it.

The proposal, which we call frame-normalized error feedback, works on the rescaled vector $u = \lambda_x r = g/\lambda_x$. This is the Riemannian gradient written in an orthonormal frame at $x$, so its length is its true length. Each worker keeps its residual $e$ in that same frame and compresses $u + e$ with a biased compressor $C$ (keep the largest few, or send scaled signs). It sends $m = C(u+e)$ and stores $e \leftarrow u + e - m$. The server applies the step

$$x \leftarrow \exp_x\!\left(-\eta\, m/\lambda_x\right),$$

where $\exp_x$ is the Poincaré exponential map and $\eta$ the learning rate.

In this frame, parallel transport from $x$ to the next iterate $x'$ preserves the length of the residual. Transport here means the geometrically correct way to carry a vector from one point's tangent space to another's. In the Poincaré ball it is the conformal ratio $\lambda_x/\lambda_{x'}$ times a gyration, a rotation built from $x$ and $x'$. Once the conformal ratio is absorbed by the frame, only the gyration remains, and it is close to the identity for small steps. For the Lorentz (hyperboloid) model of Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry, we use the closed-form hyperboloid transport, which costs a few inner products per row, to express each tangent gradient in the orthonormal spatial frame at the origin. This is an exact change of frame for vectors. It is not the distorting map of points to the origin discussed below.

What would be new is the diagnosis (unit mismatch causes depth-dependent starvation), the fix (compress and buffer in the orthonormal frame), and the claim that full transport is a second-order refinement. One part of the research file pushes back on that last point. It treats per-step parallel transport as computationally demanding. For hyperbolic space the transport is closed-form and costs $O(N)$ per row, so we test it directly as an arm rather than assume it away.

Relation to Prior Work

The closest precursor is Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold, which proposes EF-Landing. It compresses the ambient Euclidean gradient with error feedback and keeps iterates near the orthogonal-matrix manifold with a penalty. The authors identify "geometric stagnation," where compressed updates become orthogonal to the manifold. That paper motivates this one: it shows that naive compression interacts badly with geometry. It also supplies our strongest baseline, because ambient compression is exactly what we claim is in the wrong units for hyperbolic space. The Stiefel manifold is compact and its metric is uniform, so EF-Landing never meets a metric that varies by five orders of magnitude across the space. That variation is the phenomenon we study.

The error feedback literature supplies the mechanism. Error feedback goes back to 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. Error Feedback Fixes SignSGD and other Gradient Compression Schemes proves that it matches uncompressed SGD rates for non-convex objectives. On Biased Compression for Distributed Learning shows that biased compressors retain far more gradient energy than unbiased ones at equal budget. All of these analyses take place in one fixed vector space where coordinates are commensurable. Our contribution is to identify the unit conversion that restores that assumption on a manifold whose metric varies from point to point. Primal and bidirectional variants are natural later extensions, but we hold them out of scope to keep the comparison clean. These are EF21-P and Friends for primal error feedback on iterates and DoubleSqueeze for compressing both directions.

On the hyperbolic side, Hyperbolic Graph Convolutional Neural Networks constrains the design in two ways. First, it shows that working in the tangent space at the origin distorts points far from the center, which is why it aggregates in each node's own tangent space. Second, its trainable weight matrices act in tangent spaces and are themselves Euclidean, so compressing those weights is ordinary Euclidean error feedback. We therefore deliberately target models whose parameters live on the manifold, namely shallow embedding tables. Hyperbolic federated systems such as HyperFed, FlatLand and Federated Classification in Hyperbolic Spaces via Secure Aggregation of Convex Hulls distribute hyperbolic learning but communicate at full precision. They show the deployment setting exists and leave compression untouched.

Research Program

We will build data-parallel Riemannian SGD for Poincaré and Lorentz embedding tables. Edges are sharded across $W$ workers. Each worker sends compressed updates for the rows its minibatch touched. Compression works at two levels: keep the top fraction of rows by norm, then send each surviving row as scaled signs or 4-bit values. The byte count always includes row indices. Communication for low-dimensional tables is modest per row, so honest accounting matters more than headline ratios.

The analysis has two parts. The first is a simple delay bound. It predicts how many rounds an interior row waits under ambient ranking compared with frame-normalized ranking, as a function of the conformal-factor spread in the current embedding. The second instruments training to measure the actual delay per hierarchy depth. The empirical heart of the program is a two-by-two decomposition. One factor is the units the compressor ranks and buffers in: ambient or orthonormal frame. The other is whether the residual is transported: no transport, conformal rescaling only, or full gyration or hyperboloid transport. This separates the two possible causes of failure that the research file conflates.

Baselines

The naive reference points are two. One is uncompressed distributed Riemannian SGD with the same number of workers, which sets the accuracy ceiling. On the full WordNet noun hierarchy, Poincaré Embeddings for Learning Hierarchical Representations reports reconstruction MAP 0.823 at dimension 5, against 0.168 for a 200-dimensional Euclidean embedding. Our uncompressed run must first reproduce roughly that ceiling before any compressed comparison means anything. The other is biased compression with no error feedback, which shows how much there is to fix.

The strongest competitor is ambient error feedback in the style of EF-Landing. It compresses the raw coordinate gradient $g$, keeps the residual in raw coordinates, and lets the server apply the Riemannian rescaling at update time. It is the strongest because it is simple, already works on a curved manifold per Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold, and inherits the guarantees of Error Feedback Fixes SignSGD and other Gradient Compression Schemes. No reported result was found on Lacuna for any compressed or error-feedback method on hyperbolic embeddings. The closest compressed-manifold number is EF-Landing's 50% to 90% communication reduction on distributed PCA, which is a different task and serves only as context.

Further baselines cover the remaining design choices. An unbiased compressor arm uses random-subset or stochastic-rounding compression without error feedback. An origin-tangent arm maps points to the origin's tangent space, runs Euclidean error feedback there, and maps back. A Euclidean arm trains a high-dimensional Euclidean embedding with standard error feedback at matched bytes. The ablation isolating our key ingredient is frame-normalized ranking without transport versus with full transport. The method may drop transport only if that comparison shows no meaningful difference.

Every arm gets the same edge shards, number of workers, negative sampling, burn-in schedule, and an identical learning-rate grid searched separately for each arm. Every arm gets the same per-round byte budget, indices included. Beating ambient error feedback means reaching the uncompressed MAP to within 0.01 using fewer total bytes. Equivalently, it means higher MAP at equal bytes, across three seeds, with the gap concentrated in interior depths as the starvation hypothesis predicts.

Why not just…?

Why not just compress the ambient gradient with ordinary error feedback? This is the real threat. Error feedback guarantees eventual transmission, and if the embedding's norms stay away from the boundary, $\lambda_x$ barely varies and the two methods coincide. Our experiments settle it in three ways. We sweep the boundary clip threshold, which controls the maximum $\lambda_x$. We report transmission frequency and reconstruction quality by hierarchy depth. We also include a non-hierarchical control graph where we predict a tie. If ambient error feedback matches us even with tight clipping, the units story is wrong and we will say so.

Why not just send full-precision sparse rows, since the tables are only 5 to 10 dimensions? For small tables and few workers this may well be right. Indices dominate the payload, and value compression saves at most a few times. We report total bytes and wall-clock time, not value-bit ratios. We also scale workers and synchronization frequency to find where communication actually dominates. If it never does on these benchmarks, the honest conclusion is that the method matters mainly for federated or bandwidth-limited deployments such as those in HyperFed.

Why not just use unbiased compressors, whose noise folds into ordinary Riemannian SGD analysis? On Biased Compression for Distributed Learning reports that keeping the largest coordinates retains 3x to 40x more gradient energy than random selection at the same budget. It also reports that biased compression with error feedback was 4x faster than the best unbiased method on ALBERT-large pretraining. The unbiased arm tests whether that advantage survives in hyperbolic tables.

Why not just work in the origin's tangent space, which is flat? Hyperbolic Graph Convolutional Neural Networks found that this distorts peripheral points, which are most of a hierarchy's leaves. Our frame change is an isometry of each tangent space rather than a chart of the whole manifold, and the origin-tangent arm measures the difference directly.

Why not just use a large Euclidean embedding? The 0.823 versus 0.168 MAP gap above means a Euclidean table would need far more dimensions, and therefore far more bytes, to compete. The matched-byte Euclidean arm makes that comparison explicit.

Proposed Experiments and Decisive Checks

The main benchmark is WordNet noun transitive-closure reconstruction (MAP and mean rank) at dimensions 5 and 10, with subtrees used for fast sweeps. Supporting benchmarks are the EuroVoc and ACM taxonomies, and HyperLex graded entailment measured by Spearman correlation, where the uncompressed Poincaré reference is 0.512. A grid-like synthetic graph serves as the non-hierarchical control. Each method is run in both the Poincaré and Lorentz models.

Four checks would decide the question. The first is a depth-resolved starvation plot: transmission rate and per-depth MAP for ambient versus frame-normalized ranking. It should show interior starvation scaling with the conformal spread, and it should vanish on the control graph. The second is the transport ablation. If transport adds nothing beyond frame normalization, the cheap version stands. The third is a MAP-versus-total-bytes curve against all baselines at 1 to 64 workers. The fourth counts boundary-clip events and angular-layout errors during burn-in, to test whether sign compression with mis-scaled residuals causes overshoot.

The proposal is falsified if ambient error feedback matches frame-normalized error feedback on tightly clipped WordNet runs at equal bytes. In that case the right recommendation is simply to use EF-Landing-style ambient compression.