Learned Sparse Preconditioners for Fixed-Latency Unfolded Solvers

Many control and signal-processing systems must solve an optimization problem within a hard deadline, such as a robot's next trajectory or a radio's next beamformer. A common approach is deep unfolding: take a fixed number of iterations of a classical algorithm, treat each iteration as a neural network layer, and learn the step sizes offline so that the fixed-depth pass returns a good answer quickly. This works well when the problems are well scaled. It breaks when they are ill-conditioned, meaning curvature is steep in some directions and flat in others. The layers then make slow progress along the flat directions, and either accuracy collapses or the network needs very many layers. The textbook fix is to precondition, that is, rescale the problem by an approximate inverse of its curvature. But computing an inverse inside every layer defeats the purpose of unfolding.

We propose to learn where the preconditioner is allowed to have nonzero entries, and to compute the entries in those positions from each new problem instance. The sparsity pattern is found once, from scratch, jointly with the unfolded solver. We use Frank-Wolfe sparse training, which produces a model that can be truncated to any sparsity level without retraining. The result is a preconditioner that adapts to each instance and costs one sparse matrix-vector product per layer. Because its nonzero count directly sets per-layer latency, a single training run yields a whole latency-versus-accuracy curve for different hardware budgets.

Core Claim

In fixed-depth unfolded solvers, the learned per-layer scalars (step sizes, penalty parameters) act as a diagonal preconditioner shared by every instance. That is why they fail on instances whose conditioning differs from training. For problem families with a consistent variable indexing, a fixed learned support $S$ for the preconditioner, with values computed per instance, can recover most of the conditioning benefit of exact preconditioning at cost linear in $|S|$. Concretely, each unfolded layer performs

$$x_{k+1} = x_k - \alpha_k \, M_S(G)\, r_k ,$$

where $G$ is the instance's curvature or system matrix, $r_k$ is the layer's residual or gradient, $\alpha_k$ is a learned step, and $M_S(G)$ is a matrix whose nonzeros are restricted to the learned index set $S$. Each entry of $M_S(G)$ is produced by a small shared function of the entries of $G$ near that position. The quantity we aim to shrink is the effective condition number $\kappa(M_S(G)\,G)$, the ratio of largest to smallest curvature after rescaling. The per-layer cost is $O(|S|)$, plus the cost of applying $G$.

The claim is specific enough to fail. If diagonal equilibration already achieves most of the reduction in $\kappa$, the learned off-diagonal support is not worth having.

Why this intersection, and what is already done

The four literatures each hold one piece of this. None holds the combination.

On conditioning, A Lower Bound for the Optimization of Finite Sums proves that dependence on the condition number is unavoidable for first-order black-box methods. This motivates us: fixed-depth unfolded layers are first-order methods, so without preconditioning their required depth must grow with $\kappa$. Preconditioning Matters supplies the method template. Its ScaledGD rescales low-rank factor gradients by small inverse Gram matrices and removes $\kappa$ from the iteration count. Fast Spectrally Sparse Signal Reconstruction via Jacobi-Preconditioned Gradient Descent does the same for Hankel recovery with a cheap Jacobi preconditioner. It still needs roughly 3 seconds at signal length 49,999, far from real time. Both are iterative solvers whose preconditioners are derived analytically for one problem class. We instead learn a sparse preconditioner inside a fixed-depth solver.

On unfolding, Deep FlexQP unfolds ADMM (alternating direction method of multipliers) for the quadratic subproblems of sequential quadratic programming. It adds an elastic relaxation that keeps subproblems feasible and uses an LSTM to adapt the ADMM penalty parameters layer by layer. Its authors state that it lacks preconditioning and slows on poorly scaled problems. This is the gap we target, and it is our primary competitor. Its LSTM adapts only a few scalars per instance, which our ablations isolate.

Deep Unfolding for MIMO Signal Detection shows the other symptom: its detector needs 100 layers to approach maximum-likelihood error rates in hard settings. That paper also constrains our domain choice. In its 8x4 antenna setting, the matrix one would invert is 4x4, so exact preconditioning is nearly free and our latency argument would not apply. We therefore deliberately pick problems where exact inversion is genuinely expensive.

On initialization, Provable accelerated gradient method for nonconvex low rank optimization shows that the region of good starting points shrinks as $\kappa$ grows. We turn that finding into a measurable prediction for fixed-depth solvers: preconditioning should widen the range of warm starts from which $K$ layers reach tolerance.

On sparse training, Learning Pruning-Friendly Networks via Frank-Wolfe supplies the training method. It trains weights inside a sparsity-constrained region with the stochastic Frank-Wolfe algorithm. This yields smooth magnitude distributions that can be pruned to any target sparsity without retraining, reporting 92.00% CIFAR-10 accuracy at 95% sparsity. It also shows that standard initializations fail under Frank-Wolfe dynamics and introduces a learned initialization, SFW-Init. That paper sparsifies image classifiers. We reuse its "any sparsity from one run" property for a different reason: preconditioner nonzeros are latency, so any-sparsity means any-latency.

Research Program

The testbed is sequential quadratic programming for trajectory optimization and safety filtering. Here each quadratic subproblem keeps the same variable layout (state and input at each time step) while its matrix values change with the linearization point. A fixed support is meaningful in this setting because entry $(i,j)$ always refers to the same pair of variables.

The unfolded solver is ADMM with the inner linear solve replaced by $K$ inexpensive preconditioned residual steps, so no factorization happens at run time. Candidate preconditioner positions are all index pairs within two hops in the sparsity graph of the subproblem's system matrix. Each candidate $c$ gets a scalar weight $w_c$. The entry value is $w_c$ times the output of a tiny shared network. That network reads the local matrix entries and the diagonal scalings computed by the standard iterative diagonal rescaling that OSQP uses.

The weights $w$ and the solver's step parameters are trained end-to-end on the residual after $K$ layers. The weights $w$ are constrained to a $K$-sparse polytope, the set of weight vectors that are convex combinations of vectors with at most a fixed number of nonzeros, and updated by stochastic Frank-Wolfe. After training, keeping the top-$s$ weights by magnitude gives a solver at nonzero budget $s$ with no further training.

We will analyze three things. The first is the effective condition number $\kappa(M_S G)$ as a function of the budget $|S|$. The second is how the learned support relates to problem structure, for example whether it recovers couplings between time steps induced by obstacle constraints. The third is the sensitivity of the sparse training itself to initialization. For that, we compare SFW-Init against standard initializations across seeds, measuring the overlap of learned supports and the spread in final accuracy.

Baselines

The naive reference is the unpreconditioned unfolded ADMM solver with learned per-layer scalars at the same depth $K$. It shows what unfolding alone achieves as $\kappa$ grows.

The strongest existing method is Deep FlexQP. It is the closest system on exactly this benchmark suite and already adapts to each instance through its LSTM. It reports being 4 to 16 times faster than OSQP inside the sequential solver loop, scaling to 10,000 variables, cutting safety-filter violations by over 70%, and raising task completion by 43%. We found no reported result on Lacuna for its iteration count or residual as a function of condition number, so we will reimplement it. It will receive the same training instances, the same number of gradient steps, and the same hyperparameter search budget as our method.

We also run OSQP to convergence, which includes its own diagonal rescaling and exact factorization, as the accuracy ceiling and wall-clock reference. On the time-staged control problems we add a structured factorization based on the Riccati recursion (the standard backward recursion for linear-quadratic control), because it is the classical fast solver for this structure.

Three ablations isolate the key ingredient. The first uses diagonal rescaling only, with no learned off-diagonal entries. The second uses a fixed support equal to the system matrix's own sparsity pattern at the same nonzero budget, which isolates whether learning the support matters. The third trains densely, then applies magnitude pruning and retraining separately at each budget, which isolates the from-scratch Frank-Wolfe training.

Beating Deep FlexQP means a higher task-completion rate at equal or lower measured wall-clock latency on the Dubins and quadrotor tasks, and a residual after $K$ layers that stays flat, rather than growing, across the high-$\kappa$ end of our sweep.

Why not just…?

Why not just use diagonal equilibration inside the unfolded solver? This is the most serious threat. Diagonal rescaling costs $O(n)$ and is exactly what OSQP already does. The analogous Jacobi preconditioner in the JHGD paper was enough to remove $\kappa$ dependence in its setting. Diagonal scaling cannot correct curvature that comes from coupling between variables, such as linearized obstacle constraints linking distant time steps. We do not know how common such coupling is in the benchmark instances. The diagonal-only ablation settles it. If diagonal scaling comes within 10% of our fixed-depth residual at the highest $\kappa$ we test, we will report that learned off-diagonal support is unnecessary for these problems.

Why not just factorize exactly, or use a Riccati solver? For purely time-staged control problems, a Riccati recursion is cheap and exact. We expect it to beat us on single-threaded CPUs when constraints do not couple distant stages. Our case rests on two regimes. The first is couplings across stages, which break the banded structure. The second is parallel embedded hardware, where the recursion's sequential dependence over the horizon limits latency while sparse matrix-vector products parallelize. We will report both regimes, including where we lose.

Why not just train densely, prune, and retrain? The Frank-Wolfe pruning paper shows that pruned SGD-trained networks collapse without retraining. With retraining, they may match us at any single budget. The honest advantage is cost: one run gives every budget. We will compare total training compute needed to produce solvers at five budgets, alongside accuracy at each budget.

Why not just add layers? Extra layers cost latency linearly. The DPST detector's 100-layer requirement shows how quickly that grows. We will plot accuracy against measured latency, not against depth, so depth and sparsity budgets compete on the same axis.

Proposed Experiments

The first experiment is a controlled condition-number sweep on synthetic time-staged quadratic programs. We generate the programs with $\kappa$ set from $10^1$ to $10^6$ by scaling cost weights and dynamics, and add cross-stage constraint couplings of varying density. We train at moderate $\kappa$ and test across the full range, including values beyond training. We measure the residual after $K$ layers and the effective $\kappa(M_S G)$. The prediction is a flat residual curve for our method and a growing one for the naive and Deep FlexQP baselines.

The second experiment is on the Deep FlexQP suite, where Dubins and quadrotor sequential solves and safety filtering are the primary tasks. We report task completion, safety violations, and wall-clock latency on a desktop CPU and an embedded GPU. The dense tasks (SVM, LASSO, portfolio) serve as a stress test where we expect little benefit from a sparse preconditioner.

The third experiment is the initialization check. At fixed $K$, we perturb each quadratic subproblem's warm start by increasing relative radii. We record the largest radius from which the solver reaches tolerance, as a function of $\kappa$. Preconditioning should keep this radius from shrinking, the fixed-depth analogue of the basin shrinkage in Li and Lin.

The decisive outcome combines three conditions. Learned support must beat the fixed-support ablation at equal nonzeros. Our method must beat diagonal rescaling at high $\kappa$ on the coupled instances. A single Frank-Wolfe run must trace a latency-accuracy curve at least as good as per-budget pruning and retraining. If the first two fail, the idea reduces to rescaling Deep FlexQP, and we will say so.