Technical Summary: SILAGE

Problem Statement

The paper addresses nonconvex empirical risk minimization (ERM) on massive datasets that exhibit a nested double finite-sum structure. The objective function is formulated as:
$$\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x), \quad \text{where} \quad f_i(x) := \frac{1}{m} \sum_{j=1}^m f_{i,j}(x)$$
Here, $N = nm$ represents the total number of samples, partitioned into $n$ blocks (or silos) of size $m$. This structure arises naturally in centralized settings such as pooled data lakes (e.g., healthcare records from multiple hospitals), out-of-core learning where data exceeds memory, or deliberate stratification via clustering.

Existing variance-reduced (VR) methods face a critical trade-off in this regime:

1. Recursive estimators (e.g., PAGE, SARAH): Achieve optimal oracle complexities but require periodic global full-gradient refreshes over all $nm$ samples. These refreshes are computationally expensive and create scaling bottlenecks.
2. Memory-based estimators (e.g., SILVER, SAGA): Avoid global refreshes but require storing a control variate for every individual sample, resulting in an impractical $\mathcal{O}(nm)$ memory footprint for massive datasets.

The goal is to design an algorithm that eliminates periodic global refreshes while maintaining a memory footprint proportional only to the number of blocks ($\mathcal{O}(n)$), rather than the total number of samples.

Methodology: SILAGE

The authors propose SILAGE (SIngle Loop Average Gradient Estimator), a single-loop variance-reduced algorithm tailored for the nested structure. SILAGE combines two variance-reduction philosophies:

• SILVER-style memory structure: Maintains one control variate (gradient estimator) per block ($n$ entries total), rather than per sample.
• PAGE-style recursive tracking: Updates these estimators recursively using stochastic gradients.

The algorithm operates differently depending on the relationship between the number of blocks ($n$) and block size ($m$):

1. The $m \ge n$ Regime (Algorithm 1)

In this regime, the block size is larger than or equal to the number of blocks.

• Mechanism: A single global coin flip determines the iteration type. With probability $p$, a single block $i_t$ is selected uniformly at random and its full local gradient $\nabla f_{i_t}(x_{t+1})$ is computed (an "anchor reset"). With probability $1-p$, no block is reset; instead, all $n$ blocks are updated recursively using a single sampled component gradient from each block.
• Coupling: The probability $p$ is set to $n/m$. This ensures that the marginal probability of any specific block being refreshed is $1/m$, matching the refresh rate of standard PAGE on a flat dataset, while guaranteeing that at most one block is refreshed per iteration.
• Cost: The per-iteration cost is $\mathcal{O}(m)$ (dominated by the single local full gradient or the $n$ component gradients).

2. The $n > m$ Regime (Algorithm 2)

In this regime, the number of blocks exceeds the block size.

• Mechanism: Computing a full gradient for even one block is expensive relative to the total budget if many blocks need updating. SILAGE selects one anchor block $i_t$ for a full reset and a small active subset $\Omega_t$ of size $b_{grp}-1$ for recursive updates.
• Shared Drift: For the remaining $n - b_{grp}$ un-sampled blocks, the algorithm does not compute fresh gradients. Instead, it applies a shared drift $d_t$, computed as the average of the stochastic differences from the active subset, to update their estimators.
• Implementation Efficiency: To avoid the $\mathcal{O}(n)$ cost of explicitly updating all $n$ estimators with the drift, the authors propose an implementation-efficient form (Algorithm 3) using a shared accumulator $q_t$, reducing the bookkeeping cost to $\mathcal{O}(b_{grp})$.

Key Contributions

1. Memory Efficiency via Nested Structure

SILAGE requires only $\mathcal{O}(n)$ memory (storing one $d$-dimensional vector per block plus a few auxiliary vectors). This is a substantial reduction compared to flattened methods like SILVER, which require $\mathcal{O}(nm)$ memory.

2. Elimination of Periodic Global Refreshes

Unlike PAGE and its variants, SILAGE never performs a global full-gradient pass over all $nm$ components. It only evaluates at most one local group gradient $\nabla f_i$ per iteration (at an $\mathcal{O}(m)$ cost). Initialization can be arbitrary (e.g., zero), avoiding the need for an initial global gradient computation.

3. Exploitation of Nested Similarity

The convergence analysis introduces a novel two-level dependency on data geometry, avoiding pessimistic worst-case Lipschitz constants ($L_{\max}$):

• Across-group similarity ($\delta_1$): Measures the deviation of group gradients from the global gradient.
• Within-group similarity ($\delta_2$): Measures the deviation of sample gradients from their local group averages.
  The convergence rates explicitly adapt to these constants. In the $m \ge n$ regime, the rate depends primarily on $\delta_2$. In the $n > m$ regime, both $\delta_1$ and $\delta_2$ influence the complexity, but the algorithm decouples them based on the operational regime.

4. Unification of Existing Methods

SILAGE unifies existing approaches as limiting cases:

• When $n=1$ (single block), SILAGE reduces to PAGE.
• When $m=1$ (single sample per block), SILAGE reduces to SILVER.

Results and Convergence

The paper provides tight nonconvex convergence guarantees for finding an $\epsilon$-approximate stationary point ($\mathbb{E}[\|\nabla f(\tilde{x})\|^2] \le \epsilon$).

• Regime $m \ge n$:
  The gradient complexity is $\mathcal{O}\left(nm + \frac{(nL + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$ (assuming exact initialization). Crucially, the leading term depends on $\delta_2$ (within-group variance) rather than the global flat similarity or $L_{\max}$.
• Regime $n > m$:
  The complexity is $\mathcal{O}\left(nm + \frac{(mL + m\sqrt{n-m}\delta_1 + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$.
  Here, the algorithm balances the cost of across-group heterogeneity ($\delta_1$) and within-group heterogeneity ($\delta_2$).

Compared to baselines:

• Vs. ZeroSARAH: SILAGE replaces the worst-case $L_{\max}$ with structured $L, \delta_1, \delta_2$, offering significant improvements in heterogeneous regimes.
• Vs. SILVER: SILAGE achieves similar or better gradient complexity while reducing memory from $\mathcal{O}(nm)$ to $\mathcal{O}(n)$.
• Vs. D-PAGE: While D-PAGE offers competitive complexity, it requires periodic global refreshes. SILAGE removes these refreshes entirely, trading a slight increase in memory (from $\mathcal{O}(1)$ to $\mathcal{O}(n)$) for the elimination of the most expensive operation in centralized large-scale training.

Significance and Claims

The authors claim that SILAGE addresses a fundamental scaling bottleneck in centralized large-scale optimization. By actively exploiting the nested double-sum structure, SILAGE achieves a "best of both worlds" scenario:

1. It avoids the computational bottleneck of periodic global full-gradient refreshes required by recursive estimators.
2. It avoids the memory bottleneck of storing control variates for every sample required by memory-based estimators.

The paper emphasizes that the theoretical rates are structurally tighter than existing bounds because they rely on nested similarity constants ($\delta_1, \delta_2$) which can be significantly smaller than flattened similarity constants or worst-case smoothness parameters, particularly in regimes with redundant blocks or homogeneous silos. Experimental results on synthetic nonconvex logistic regression tasks confirm that SILAGE's performance tracks these theoretical predictions, converging faster than baselines when the nested similarity structure is favorable.