Learning inexact alternating minimization

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. 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. To show convergence of the learned scheme on unseen problem instances, we combine the bound with a PAC-Bayes argument that controls the expected optimality gap with high probability. We apply the learned scheme to low-dose CT reconstruction with dictionary regularization, demonstrating a $13\times$ speedup over the inexact first-order baseline at matched accuracy. A brief end-to-end fine-tuning stage extends this to $30\times$ and outperforms other learned schemes.