Cache-Resident Optimization After Manifold Identification

Many sparse and low-rank optimization problems simplify partway through a run. A proximal gradient method, which alternates a gradient step with a shrinkage step that zeros small coordinates or small singular values, provably locks onto the solution's sparsity pattern or rank after finitely many iterations. From that point on it is effectively solving a much smaller smooth problem and converges geometrically. Solvers ignore this. They keep the full-size data in the same memory layout, so they keep paying for slow memory traffic on coordinates that no longer matter. Separately, parallel computing has many examples of super-linear speedup, meaning more than $N\times$ from $N$ processors. It happens when splitting a problem shrinks each processor's share until it fits in fast on-chip cache. This note proposes to connect the two. Once the solver has certifiably identified the low-dimensional structure, it repacks the active data so each node's working set drops below the cache threshold. The run then gets a mid-optimization jump in speed that comes from the algorithm's geometry rather than from adding hardware.

The difficulty is knowing when identification has happened. Repacking too early wastes work, and a support change forces a rollback. We propose two pieces to handle this. The first is an easy-to-hard schedule over the problem's difficulty: decreasing regularization strength for sparse and low-rank problems, increasing outlier ratio for robust subspace recovery. The schedule keeps the active structure small and lets the solver identify it early. The second is a sufficient-descent test on the reduced problem, used as the online signal that it is safe to advance a stage and stay compacted. In plain terms, the claim is that a curriculum keeps the optimizer inside the regime where geometry says the problem is small. A cheap descent check confirms the optimizer is there. Physically shrinking the data at that moment produces super-linear wall-clock speedup at node counts where static partitioning gives only linear speedup.

Core Claim

For partly smooth problems, which are nonsmooth objectives that behave smoothly once restricted to a lower-dimensional "active manifold," we claim the following. Identification-triggered compaction, combined with an easy-to-hard continuation schedule, reaches a fixed accuracy at least $N\times$ faster than the same solver on one node. This holds at node counts $N$ well below those where static strong scaling first becomes super-linear. The effect is predictable from the ambient size, the active-manifold size, and the per-node cache size.

A simple cost model states the prediction. Let $n$ be the ambient working-set size in bytes and $m \ll n$ the active-manifold working-set size. Let $S$ be per-node cache capacity. Let $c(s)$ be the per-iteration cost at per-node footprint $s$, which drops sharply when $s < S$. Let $K_1$ and $K_2$ be the iterations spent before and after identification. Then

$$T(N) \approx K_1\, c(n/N) + K_2\, c(m/N).$$

The super-linear regime is $m/N < S < n/N$. In that regime, the post-identification phase is cache-resident while static partitioning is still memory-bound. The curriculum's job is to make $K_1$ small and $m$ small throughout. The model is just the cache-residency picture from strong-scaling studies with the footprint made time-varying.

Prior Work and Positioning

The geometric half is supplied by Local Linear Convergence of Forward-Backward under Partial Smoothness. That paper proves finite-time identification of the active manifold under a non-degeneracy condition, followed by local linear convergence: R-linear on flat manifolds such as Lasso supports, Q-linear on curved ones such as the low-rank manifold. Its extensions to other splitting schemes, Activity Identification and Local Linear Convergence of Forward-Backward-type Methods and Convergence Rates of Forward-Douglas-Rachford Splitting Method, tell us the phenomenon is not specific to one algorithm. These works analyze iteration counts only. They say nothing about memory layout, and that gap is ours to fill.

For curved non-smooth problems, A Linearly Convergent Method for Non-Smooth Non-Convex Optimization on the Grassmannian proves linear convergence of a Riemannian subgradient method under a regularity condition with geometric step decay. Dual Principal Component Pursuit for Robust Subspace Learning applies this to robust subspace recovery, the task of finding a subspace when many data points are outliers. Both name the need for a good initialization as an open limitation. We use this setting as the second testbed, with a curriculum over outlier ratio standing in for a good initialization.

The descent certificate comes from Sufficient Descent Riemannian Conjugate Gradient Methods. That paper gives conjugate-gradient directions that satisfy a sufficient descent inequality regardless of line-search quality. We reuse the idea of a line-search-independent descent check, but apply it on the reduced problem as a switching criterion rather than as a convergence device.

The curriculum half is motivated by When Does Curriculum Learning Help? A Theoretical Perspective. It models curricula as a sequence of problems each regularized toward the previous solution. It shows benefits when each stage lands within radius $r$ of a good next-stage solution, and admits that this condition cannot be checked in advance. A Task-centric Theory for Iterative Self-Improvement with Easy-to-Hard Curricula constrains the design. Its result that easy-to-hard training wins only under moderate stage separation and feasible initialization, with failures otherwise, predicts that overly aggressive continuation schedules will cause support blow-ups and rollbacks. We test that prediction directly. Our contribution relative to both is to make the proximity condition checkable online through the descent test on a structured convex or weakly convex problem.

The systems half is motivated by strong-scaling studies in which super-linearity appears when partitions fit in cache. Domain decomposition preconditioners for Schur complement systems arising in structured nonlinear optimization problems observes this between 64 and 256 MPI ranks inside an interior-point solver. Distributed Inference with Minimal Off-Chip Traffic for Transformers on Low-Power MCUs reports 26.1× on 8 chips by keeping weights in on-chip memory. Spatially Parallel Convolutions reports 4.2× on 4 GPUs. In all of these the footprint shrinks because hardware is added and the problem is fixed. We instead shrink the footprint because the optimizer has learned which part of the problem matters. The Bochem et al. work also constrains us: very small kernels underuse compute cores, so compaction can overshoot. The cost model must include that floor.

Decentralized Riemannian Gradient Descent on the Stiefel Manifold is the closest distributed manifold-optimization work. It reports only linear speedup with static data and is a natural distributed reference.

Research Program

We would build a distributed proximal solver in MPI for three problem families: $\ell_1$-regularized least squares, nuclear-norm matrix completion, and holistic DPCP on the Grassmannian. The solver runs in two layouts. The full layout stores each node's partition of the design matrix or observed entries. The compacted layout stores only the columns of the current support, or the current rank-$r$ factors and the data they touch, packed contiguously.

The curriculum is a sequence of stages $t = 1, \dots, T$. Regularization decreases geometrically from a level where the solution is nearly empty, or, for DPCP, the outlier fraction increases. Each stage is warm-started from the previous solution, which is the biased-regularization view of Arora et al.

Switching between layouts is governed by an identification test. After the support or rank has been unchanged for a window of iterations, the solver checks whether proximal steps on the reduced problem satisfy

$$f_t(x_{k+1}) \le f_t(x_k) - c\, \|G_t(x_k)\|^2,$$

where $f_t$ is the stage-$t$ objective, $G_t$ its proximal-gradient map, and $c>0$ a fixed constant. It also checks that the full-problem optimality residual on inactive coordinates stays strictly inside the non-degeneracy margin. If both hold, the solver compacts. If a later full-residual check, run every few iterations at low cost, detects an inactive coordinate entering, the solver rolls back to the full layout for that stage.

On the analysis side, we would prove that under strict complementarity at each stage solution and a bound on stage separation, the warm start lands in the identification neighborhood of the next stage. That bound is our analogue of the $(r,\alpha)$ condition. The number of rollbacks is then bounded by the number of stages. This turns the existing local linear convergence results into a whole-path guarantee with a time cost that the model above can predict.

Baselines

The naive reference is the same proximal solver on the full layout with no curriculum and no compaction, run on 1 to 64 nodes. This measures ordinary strong scaling, and its super-linear onset, if any, marks the threshold we claim to beat.

The strongest optimization competitor is the solver with the curriculum and warm starts but no compaction. It isolates how much benefit comes purely from fewer iterations. For DPCP, the strongest existing method is holistic DPCP with geometric step decay as in Ding et al. That paper reports 1.78 seconds at ambient dimension 1000 and codimension 50, against nearly 80 seconds for recursive DPCP. Zhu et al. report geometric steps reaching error $10^{-10}$ in a few hundred iterations, while polynomial decay stalls at $10^{-2}$ to $10^{-3}$. We will reproduce these on our hardware before comparing. For distributed Lasso and matrix completion wall-clock time, there is no reported result found on Lacuna, so our own tuned full-layout run is the reference.

The key ablation is compaction without the descent certificate. It uses a fixed "compact after $k$ iterations of unchanged support" rule, which isolates whether the certificate earns its place. A second ablation is compaction without the curriculum, solving directly at the target regularization. It tests whether the curriculum is needed to identify early and keep $m$ small.

All variants share data, stopping tolerance, node counts and hardware. Each gets the same hyperparameter budget: an equal number of trials over step sizes and continuation ratios, chosen on held-out instances. We count beating the baselines as two outcomes. First, time-to-$10^{-8}$ relative suboptimality must be lower than both the curriculum-only and fixed-rule variants at every node count. Second, speedup over one node must exceed $N$ at a node count at least 4× smaller than the onset for the full-layout run.

Why not just…?

Why not just add more nodes? Static strong scaling does produce super-linear speedup once partitions fit in cache, as the Lueg et al. and Bochem et al. results show. But it needs enough nodes to shrink the ambient problem, not the active one, and communication eventually dominates. Lueg et al. found exactly this, with the lowest-iteration preconditioner losing on wall-clock time to communication. Our scaling curves will show directly whether compaction moves the onset to fewer nodes. If it does not, the claim fails.

Why not just use continuation with warm starts, which is a known trick? This is the main threat, since much of any speedup may come from fewer iterations rather than from cache residency. The curriculum-only baseline settles it. We will also read hardware counters, specifically last-level cache misses and stalled cycles per iteration, before and after compaction. The goal is to attribute the remaining gap to memory behavior rather than iteration count.

Why not just compact on a heuristic working-set rule? Fixed-window rules are simpler and may work on easy instances. The certificate's value should appear on instances with near-degenerate solutions, where Liang et al.'s strict complementarity barely holds and supports flicker. There, heuristic rules either compact too early and roll back repeatedly or wait too long. The fixed-rule ablation, run across a sweep of non-degeneracy margins, measures rollbacks and time lost. If the heuristic matches the certificate everywhere, we would report that and drop the certificate.

Why not just use polynomial step sizes or a direct solver? On the Grassmannian, Zhu et al. show that polynomial decay stalls orders of magnitude above geometric decay. Lueg et al. show sparse direct and serial incomplete-factorization solvers hitting memory and scaling walls. Neither alternative reaches the regime where compaction matters, so we include them only as sanity references.

Proposed Experiments

The first experiment is a cost-model validation. On Lasso instances whose full footprint is 4 to 64 times per-node cache, with planted supports of controlled size, we measure $c(s)$ per node and predict the super-linear window $m/N < S < n/N$. We then check whether measured speedups land in that window. The decisive check is whether the onset of super-linearity tracks the active size $m$ rather than the ambient size $n$ as we vary $m$ at fixed $n$.

The second experiment is a curriculum-separation sweep. We vary the continuation ratio between stages from gentle to a single jump. We predict a U-shape in time-to-accuracy: too many stages waste work, and too few cause support blow-ups and rollbacks. This mirrors the moderate-separation condition of Liu et al. and tests our stage-separation bound.

The third experiment covers nuclear-norm completion, using the 50×50 rank-5 setting of Liang et al. scaled up to matrices whose full data exceed cache. Here the curved active manifold should give Q-linear convergence after compaction, and we check that the rate is unchanged by repacking.

The fourth experiment uses DPCP on the random spherical model with ambient dimension 1000 and codimension 50. We compare against holistic DPCP's reported timing. An outlier-ratio curriculum is tested as a replacement for spectral initialization in the 70 to 80 percent outlier regime, where Ding et al. report near-zero error. Recovery error and wall-clock time are the metrics.

The project succeeds if compaction gives super-linear speedup at substantially fewer nodes than static scaling, and if the effect survives the curriculum-only control. It fails informatively if the counters show no memory-behavior change after identification, which would mean the active working set never actually fits in cache in practice.