Implementation notes - Implementation notes - 5.3 English - 68552

The implementation uses theta to select the algorithmic path:

• theta = 0 uses the exact method.

• theta > 0 uses the Barnes-Hut approximation.

The early exaggeration factor is applied for the first \(\min(250,\) max_iter \()\) iterations, then set to 1 for the remaining iterations.

The embedding is updated with gradient descent using momentum and per-coordinate adaptive gains. Each coordinate maintains a velocity \(v_i\) that accumulates gradient information across iterations. At each iteration the velocity and embedding are updated as

where \(\eta\) is the learning rate, \(g_i^{(t)}\) is an adaptive per-coordinate gain, and \(\alpha\) is the momentum coefficient. Momentum carries forward a fraction of the previous update, which smooths the trajectory and helps avoid poor local optima. \(\alpha\) starts at 0.5 and switches to 0.8 at iteration 250. When early exaggeration ends, gains and momentum are reset to their initial values.

Convergence checks are performed every 50 iterations and at the final iteration. The algorithm can terminate early when either:

• the gain-weighted gradient norm falls below min grad norm; or

• there is no KL-divergence improvement for n_iter_without_progress iterations after the early exaggeration phase.

Setting min grad norm to 0 disables the gradient norm criterion. Setting n_iter_without_progress to 0 disables stagnation detection.

In the Barnes-Hut approximation, \(k = \min(n - 1,\; \lfloor 3 \times \text{perplexity} + 1 \rfloor)\) nearest neighbors are used to compute the sparse affinity matrix.

Per-row conditional probabilities are calibrated by binary search. In numerically degenerate cases (for example, underflow during calibration), the corresponding row falls back to a uniform distribution over its neighbors.