Learning inexact alternating minimization for convex problems with quadratic coupling

Paul Häusner, Jevgenija Rudzusika, Jens Sjölund, Ozan ÖktemarXiv 2026 · arXiv

This paper, recently presented at NeurIPS 2026, tackles a major bottleneck in large-scale optimization: the "inner loop" problem. By replacing traditional iterative solvers with specialized neural networks, the authors demonstrate how to achieve massive speedups in image reconstruction and matrix completion without sacrificing the mathematical rigor that researchers in optimization hold dear.

TL;DR

The authors propose a "learned inexact alternating minimization" scheme that replaces expensive inner-loop solvers with neural networks. This approach delivers up to a 30x speedup in CT reconstruction while providing first-of-their-kind PAC-Bayes generalization guarantees for learned optimization.

What Problem Does This Paper Address?

Many real-world problems—like reconstructing a medical CT scan or completing a sparse matrix—are solved using Alternating Minimization (AM). These problems typically involve two sets of variables (e.g., the image pixels and the dictionary coefficients) that are "coupled" together.

The standard way to solve this is to hold one set fixed, solve for the other, and then switch. The catch? These "subproblems" often don't have a simple solution. You usually have to run another iterative algorithm (an "inner loop") inside every single step of your main "outer loop." This is computationally brutal. While "Learning to Optimize" (L2O) has tried to replace these loops with fast neural networks, most existing methods lack strong theoretical guarantees, making them "black boxes" that might fail on new data.

Methods

The authors introduce a framework for Learning Inexact Alternating Minimization. Instead of solving subproblems to high precision with a classical algorithm, they use a sequence of small neural networks to predict the next iterate.

Key technical components include:

  • Greedy Training Strategy: Rather than training a massive "unrolled" network end-to-end (which is memory-intensive and unstable), they train networks for each iteration $k$ sequentially. Each network is trained to solve its specific subproblem given the output of the previous one.
  • Theoretical Safety Net: They derive a worst-case bound on the "optimality gap." Crucially, they show that errors made in early iterations are discounted exponentially, allowing the learned solvers to be "inexact" early on without ruining the final result.
  • PAC-Bayes Generalization: They apply PAC-Bayes theory to provide high-probability bounds on how well the learned optimizer will perform on unseen data. This bridges the gap between empirical "hacks" and provable optimization.
  • Architectures: They use lightweight convolutional neural networks (CNNs), including LISTA-style architectures for sparse subproblems, ensuring that the neural network "inference" is much faster than running 50-100 iterations of a classical solver.

Datasets

The method was evaluated on two distinct problem types:

  1. Dictionary-Regularized CT Reconstruction: Using real human abdomen data from the 2016 Low Dose CT Grand Challenge. The authors simulated low-dose 2D projections to test the algorithm's ability to reconstruct high-quality images from noisy, indirect data.
  2. Robust Matrix Completion: A synthetic benchmark involving $100 \times 100$ matrices. This task requires recovering a low-rank matrix from observations that are both sparse and corrupted by outliers.

Key Insights and Ideas

  • "Greedy" is more than a shortcut: The authors argue that greedy training isn't just a way to save memory; it's mathematically motivated by their error bounds. It ensures each network is actually learning to solve the optimization subproblem it was intended for.
  • Warm-starting the training: By initializing the weights of the network for iteration $k$ with the weights from iteration $k-1$, the authors found that the "parameter drift" remains small. This isn't just a training trick—it's a key variable that tightens their PAC-Bayes generalization bounds.
  • The Discounting Principle: A major "aha" moment in the theory is that the algorithm can tolerate significantly larger errors in the first few iterations. As shown in Figure 2, the learned scheme can start "worse" than a heavy-duty baseline but quickly catches up as the discount factor shifts.
Figure 2: Relative objective gap vs. outer iteration k (left) and cumulative runtime (right) over 20 iterations: medians with 5th–95th percentiles over test instances.

Key Results

  • Massive Speedups: In the CT reconstruction task, the greedy learned scheme achieved a 13x speedup over a FISTA baseline at the same accuracy level. Adding a final end-to-end fine-tuning stage pushed this to a 30x speedup (see Figure 1).
  • Efficiency at Scale: For robust matrix completion, the learned method outperformed classical solvers like ADMM and Proximal Gradient descent at the trained depth (8 iterations), maintaining a lower optimality gap for the same computational budget.
  • Subproblem Accuracy: Figure 3 demonstrates that the networks successfully learn to solve their respective subproblems, with the function gap decreasing consistently across outer iterations.
Figure 1: Runtime vs. final relative objective gap of learned and baseline methods: medians with 5th–95th percentiles and numbers give the inner iterations of the inexact baseline.

Limitations and Future Work

  • Convexity Constraints: The current theory relies on joint convexity and a "quadratic growth" condition. Many real-world problems are bi-convex or non-convex, where this specific theory might not yet apply.
  • Loose Bounds in High Dimensions: While the PAC-Bayes bounds are a major theoretical contribution, the authors admit they can be "vacuous" (numerically loose) for extremely high-dimensional problems like full 3D CT scans.
  • Distribution Shift: Like most learned methods, there is a risk that a model trained on one type of medical scanner might not generalize perfectly to another without retraining.

The authors suggest that future work could involve relaxing the convexity assumptions and scaling the implementation to 3D CT reconstruction, where the potential for speedup is even greater.

Summary updated

Abstract

Alternating minimization is a standard tool for optimization problems with two coupled variable blocks. Its cost is dominated by the inner subproblem solvers, which rarely have a closed-form solution. In this paper, we propose to learn an inexact alternating scheme in which neural networks approximate the subproblem solution at each iteration. For convex problems with quadratic couplings between the variable blocks that satisfy a quadratic growth condition, we derive a worst-case bound on the optimality gap that exposes the per-iteration error that each network is trained to minimize in a greedy fashion. Combining the bound with a PAC-Bayes argument, we obtain a fixed-horizon, high-probability bound on the expected optimality gap over the distribution of problem instances. We apply the learned scheme to robust matrix completion and low-dose CT reconstruction with dictionary regularization where we achieve a 5x-13x speedup over the inexact first-order baseline at matched accuracy. A brief end-to-end fine-tuning stage extends this up to 30x and outperforms other learned schemes. The code is available at https://github.com/paulhausner/learned-alternating-minimization.
BibTeX
@misc{hausner2026learning,
  author = {Paul Häusner and Jevgenija Rudzusika and Jens Sjölund and Ozan Öktem},
  title = {{Learning inexact alternating minimization for convex problems with quadratic coupling}},
  year = {2026},
  eprint = {2611.12544},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12544},
}
Figure