math.OCNov 9, 2026

Learning inexact alternating minimization for convex problems with quadratic coupling

Authors: Paul Häusner, Jevgenija Rudzusika, Jens Sjölund, Ozan Öktem

Organizations: Department of Information Technology, Uppsala University, Sweden · Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden

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.

Figures & tables

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Feb 21, 2023

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

Given a matrix M∈Rm×nM\in \mathbb{R}^{m\times n}, the low rank matrix completion problem asks us to find a rank-kk approximation of MM as UV⊤UV^\top for U∈Rm×kU\in \mathbb{R}^{m\times k} and V∈Rn×kV\in \mathbb{R}^{n\times k} by only observing a few entries specified by a set of entries Ω⊆[m]×[n]Ω\subseteq [m]\times [n]. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if MM has incoherent rows and columns, then alternating minimization provably recovers the matrix MM by observing a nearly linear in nn number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time O~(∣Ω∣k)\widetilde O(|Ω| k), which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require O~(∣Ω∣k2)\widetilde O(|Ω| k^2) time.
Jun 7, 2023

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M∈Rn×nM \in \mathbb{R}^{n \times n}, a non-negative weight matrix W∈R≥0n×nW \in \mathbb{R}_{\geq 0}^{n \times n}, a parameter kk, the goal is to output two matrices X,Y∈Rn×kX,Y\in \mathbb{R}^{n \times k} such that ∥W∘(M−XY⊤)∥F\| W \circ (M - X Y^\top) \|_F is minimized, where ∘\circ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the cost of each iteration of [LLR16] from ∥W∥0k2\|W\|_0k^2 to ∥W∥0k\|W\|_0 k where ∥W∥0\|W\|_0 denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization. We also replace the random initialization of [LLR16], whose claimed guarantee fails, by subspace iteration from a Gaussian start, so our total running time of O~((∥W∥0k+nk3)log⁡(1/ε))\widetilde O((\|W\|_0 k+nk^3)\log(1/ε)) includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance γnγn of the all-ones matrix for a γγ that is polynomially small in nn.
Apr 29, 2026

Learning Over-Relaxation Policies for ADMM with Convergence Guarantees

The Alternating Direction Method of Multipliers (ADMM) is a widely used method for structured convex optimization, and its practical performance depends strongly on the choice of penalty and relaxation parameters. Motivated by settings such as Model Predictive Control (MPC), where one repeatedly solves related optimization problems with fixed structure and changing parameter values, we propose learning online updates of the relaxation parameter to improve average performance on problem classes of interest, while guaranteeing that asymptotic convergence is not compromised for the worst-case realization of such problems. This choice is computationally attractive in the Operator Splitting Quadratic Program (OSQP)-like architectures, since adapting relaxation does not trigger the matrix refactorizations associated with penalty updates. We establish convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions, and show on benchmark quadratic programs that the resulting learned policies improve both iteration count and wall-clock time on average over baseline OSQP.