Learning Inexact Alternating Minimization: Neural Networks Accelerate Convex Optimization

Neural networks approximate alternating minimization subproblems, achieving 5-30x speedups with theoretical guarantees.
For convex problems with quadratic coupling between variable blocks, this paper proposes learned inexact alternating minimization: a neural network approximates the inner subproblem solution each iteration, replacing expensive iterative solving with a single forward pass. The authors derive a worst-case optimality gap bound split into a decaying term and a network approximation error term, guiding greedy per-network training. Combined with PAC-Bayes analysis, this yields fixed-horizon, high-probability generalization bounds. Experiments on robust matrix completion and low-dose CT reconstruction show 5-13x speedups at matching accuracy, rising to 30x after end-to-end fine-tuning, outperforming other learned schemes. Code is open-sourced.
Title
Learning Inexact Alternating Minimization: Neural Networks Accelerate Convex Optimization
Meta Description
This article introduces a learned inexact alternating minimization scheme that uses neural networks to approximate subproblem solutions, derives optimality gap bounds for convex problems with quadratic coupling, and combines them with PAC-Bayes analysis to achieve 5-30x speedups in matrix completion and low-dose CT reconstruction.
Article Content
Alternating minimization is a standard tool for solving optimization problems with two coupled variable blocks, but its computational cost is dominated by the inner subproblem solvers, which often lack closed-form solutions. This paper proposes learning an inexact alternating scheme in which a neural network approximates the subproblem solution at each iteration. For convex problems with quadratic coupling between variable blocks that satisfy a quadratic growth condition, the authors derive worst-case bounds on the optimality gap that reveal the per-iteration error each network should minimize when trained greedily. Combining this bound with a PAC-Bayes argument yields fixed-horizon, high-probability bounds on the expected optimality gap over a distribution of problem instances. The authors apply the learned scheme to robust matrix completion and low-dose CT reconstruction with dictionary regularization, achieving 5x to 13x speedups over inexact first-order baselines at matching accuracy. A brief end-to-end fine-tuning stage raises the speedup to 30x and outperforms other learned schemes. The code is open-sourced on GitHub.

The Bottleneck of Alternating Minimization and Learned Schemes
Alternating minimization (AM) is a classical method for handling convex optimization problems with two coupled variable blocks, and is widely used in fields such as matrix completion and image reconstruction. At each iteration, one variable block is fixed and a subproblem is solved for the other block. However, these subproblems usually lack closed-form solutions and must be solved approximately with iterative algorithms (such as gradient descent), which constitutes the main computational overhead.
The core idea of this paper is to replace traditional subproblem solvers with neural networks, directly learning a mapping from the current iteration state to an approximate subproblem solution. This "learned inexact alternating scheme" preserves the alternating framework while replacing the inner iterations with a single network forward pass, thereby greatly reducing the cost per iteration.
Quadratic coupling refers to the presence of a cross term such as (\frac{\rho}{2}|Ax - By|^2) or (x^\top C y) between the two variable blocks in the objective, so that once one block is fixed, the subproblem for the other block is still a (usually linear-term-augmented) quadratic program. This structure is extremely common in models such as matrix completion (low-rank factorization) and dictionary learning. The special property of quadratic coupling is that the Hessian of the subproblem does not depend on the variable being solved for, so the optimality gap can be expressed explicitly in terms of the coupling operator and the subproblem residual—this is precisely the key prerequisite that enables the paper to derive worst-case bounds. By contrast, under general nonlinear coupling the condition number of the subproblem varies across iterations, making it difficult to obtain tight error propagation bounds.
The quadratic growth condition is a weaker assumption than strong convexity in optimization: near the optimum, the objective satisfies (f(x) - f^\star \ge \mu \cdot \mathrm{dist}(x, X^\star)^2), i.e., the function value controls the distance to the optimal solution set at a quadratic rate. It allows the objective to be nonconvex or flat far from the optimum, requiring only a local quadratic lower bound. This condition is widely used to analyze convergence rates of nonconvex problems; the paper uses it to convert the network approximation error at each iteration into decay of the optimality gap, thereby avoiding reliance on global strong convexity.
Theoretical Guarantees: Optimality Gap Bounds and PAC-Bayes Analysis
The effectiveness of a learned scheme requires theoretical support. For convex problems with quadratic coupling between variable blocks, under the quadratic growth condition, the authors derive a worst-case upper bound on the optimality gap. This bound decomposes cleanly into two parts: one that decays with iterations, and one related to the network approximation error at each iteration. This decomposition directly identifies the training objective for each network—greedily minimizing the approximation error at the current iteration—thereby guaranteeing overall convergence.
Furthermore, the authors combine the above deterministic bound with PAC-Bayes theory to obtain fixed-horizon, high-probability bounds on the expected optimality gap over a distribution of problem instances. This means the learned scheme is guaranteed not only on a single instance but also generalizes to unseen instance distributions. This analysis provides a rigorous statistical learning perspective for learned optimization algorithms.
PAC-Bayes is a generalization-bound framework based on posterior distributions: given a prior (P) and a data-dependent posterior (Q), it bounds the difference between expected risk and empirical risk with high probability, in the form (\mathbb{E}{Q}[\text{risk}] \le \mathbb{E}{Q}[\text{empirical risk}] + \sqrt{(\mathrm{KL}(Q|P) + \ln(1/\delta))/(2n)}). Unlike combinatorial bounds such as VC dimension, PAC-Bayes can still yield non-trivial bounds for overparameterized models such as neural networks, and the bound depends explicitly on the distribution used for training. This paper treats each learned subproblem solver as a stochastic network (with weights following a posterior distribution), uses PAC-Bayes to control its average approximation error over the instance distribution, and then composes this with the deterministic error propagation bound to obtain an end-to-end generalization bound on the optimality gap.
A fixed-horizon bound refers to a bound when the number of iterations (K) is fixed in advance and does not vary with the data. It contrasts with "anytime" bounds: the latter require a union bound over all iterations, leading to a logarithmic factor; the fixed horizon requires controlling only the sum of (K) error terms, yielding a tighter bound. The bound in this paper holds for each (K) and is uniform in probability, so it can be used directly to guide the trade-off between the number of training rounds and network capacity.
Experimental Validation: Matrix Completion and Low-Dose CT Reconstruction
The authors apply learned alternating minimization to two practical problems: robust matrix completion and low-dose CT reconstruction with dictionary regularization. At matching accuracy, the learned scheme achieves 5x to 13x speedups over inexact first-order baselines. This improvement mainly stems from the neural network avoiding repeated computation in the inner iterations.
In addition, the authors introduce a brief end-to-end fine-tuning stage that jointly optimizes all networks, further raising the speedup to 30x and surpassing other learned schemes. This shows that combining greedy per-network training with end-to-end fine-tuning can fully unlock the potential of learned alternating schemes.
Open Source and Outlook
The authors have open-sourced the code (https://github.com/paulhausner/learned-alternating-minimization) to facilitate reproduction and extension by the community. This work provides a new paradigm for accelerating alternating minimization, especially for scenarios where subproblem solving is expensive. Possible future directions include extending to nonconvex problems, more complex coupling forms, and integration with other learned optimization frameworks.
Overall, this research strikes a good balance between theoretical analysis and practical acceleration, demonstrating the great potential of learned methods in classical optimization algorithms.
One-line Summary
Neural networks approximate the subproblems of alternating minimization, achieving 5-30x speedups with theoretical guarantees.
Paragraph Summary
For convex optimization problems with quadratic coupling between variable blocks, this paper proposes learned inexact alternating minimization: a neural network directly approximates the inner subproblem solution at each iteration, replacing expensive iterative solving with a single forward pass. The authors derive a worst-case upper bound on the optimality gap, decomposing it into a term that decays with iterations and a network approximation error term, thereby indicating that each network should greedily minimize the current-iteration error; combined with a PAC-Bayes argument, they further obtain fixed-horizon, high-probability bounds on the expected gap over the instance distribution. In robust matrix completion and low-dose CT reconstruction with dictionary regularization, the method achieves 5-13x speedups over inexact first-order baselines at matching accuracy, and up to 30x after end-to-end fine-tuning, outperforming other learned schemes. The code is open-sourced.
Related articles

AI Writes Your Code—Do You Still Need to Learn Git? Five Reasons
AI coding agents handle Git operations automatically—is it still necessary to learn Git? Five reasons: team communication, reviewing agent PRs, monitoring code changes, fallback when AI goes down, and the joy of learning—plus how the focus of learning Git is shifting in the agent era.

Anthropic Reportedly Prices IPO at $83 Per Share, Valuing Company at $1.5 Trillion
Anthropic reportedly prices IPO at $83 per share, above the expected range, with a fully diluted valuation of $1.5 trillion. This article analyzes the signal significance of the pricing and its impact on the AI industry's financing environment.

Open-Source Code Hosting Platform Codeberg Suffers Outage, Sparking Debate in Developer Community
Open-source code hosting platform Codeberg.org suffered an outage, sparking Hacker News debate over nonprofit platform stability and open-source infrastructure dependency risks.