CS Paper Radar

Learning inexact alternating minimization for convex problems with quadratic coupling

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

cs.LG math.OC ·submitted 2026-11-09 15:13 UTC · v1
top venuecode/data

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.

Comment
Accepted at NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

CG-GLORE: A Conjugate Gradient-Based Global-Local Regularization Network for Sparse-View CT Reconstruction

cs.CV cs.AI ·2026-08-15 ·Tran Xuan Hieu Le, Doanh C. Bui, Vu Trung Duong Le, Hoai Luan Pham, Khang Nguyen +3 more
published similarity 0.66
Abstract · Accepted for presentation at BMVC2026

Sparse-view computed tomography (CT) reduces radiation dose by acquiring fewer projection views, but the resulting inverse problem is highly ill-posed and often produces severe streak artifacts. Existing deep reconstruction methods have achieved promising performance, yet many rely on first-order updates or large regularization networks, which can be less effective in ill-conditioned settings. We propose \textbf{CG-GLORE}, a compact deep unrolling framework inspired by second-order optimization for sparse-view CT reconstruction. Each unrolled stage uses a CG-solved linear system based on a structured Hessian surrogate: it retains the physics-induced curvature of the data-fidelity term while using an identity approximation for the learned regularization term. Thus, the method is second-order-inspired rather than an exact Newton method for the full learned objective. To model image priors, we design a Global-Local Regularization Network (GLORE), which combines convolutional local feature extraction with a Long-Range Dependency Representation module based on sparse patchification and Nyström attention. This design captures anatomical details and non-local dependencies while maintaining practical complexity. Experiments on AAPM and DeepLesion under multiple sparse-view and noise settings show that CG-GLORE achieves strong quantitative performance, stable convergence, lower noise power, and improved visual fidelity compared with representative reconstruction methods.

0.27

Learning SOCP Solver Dynamics with Graph Neural Networks

cs.LG math.OC ·2026-10-19 ·Adam Ghalem, Lou Salaün, Davide Rinaldi, Fragkiskos D. Malliaros
similarity 0.64
Abstract · Learning on Graphs (LoG) Conference, 2026

Second-order cone programs (SOCPs) are a fundamental class of convex optimization problems widely applied across engineering domains. Classical interior-point methods are robust and accurate, but their iterative nature can be costly in real-time or repeated-solve settings. This has motivated learning-based solvers that approximate optimizer solutions with neural networks. Recent work has increasingly studied graph neural networks (GNNs) for linear, quadratic, and second-order cone optimization, leveraging their ability to model sparse relational structure among variables, constraints, and objective functions. Most existing GNN-based solvers compress the optimization process into a single forward pass, predicting the optimizer directly without using the intermediate trajectory produced by classical solvers. We introduce SOCPNet, a recursive GNN framework that uses solver trajectories to learn an iterative SOCP solution procedure. A shared GNN model is applied repeatedly, refining the current iterate at each step and enabling inference for a variable number of iterations. Rather than predicting the solution in a single pass, SOCPNet learns from intermediate iterates to progressively refine its estimates using a trajectory-regularized training procedure. We evaluate SOCPNet on multiple datasets spanning standard SOCP problem classes and show that it consistently reduces the final solution error relative to a SOCP-GNN baseline. Finally, we demonstrate how trained SOCPNet models can be used in a hybrid optimization pipeline by warm-starting a classical interior-point solver, reducing solver iterations without loss of accuracy.

0.11

Accelerating Variational Cone-Beam CT Reconstruction with Learned Warm Starts

eess.IV cs.AIcs.CV ·2026-11-13 ·Héloïse Dudoignon, Clément Delmas, Laurent Facq, Clair Poignard, Baudouin Denis de Senneville
similarity 0.62
Abstract · Submitted to IEEE ISBI 2027

Variational reconstruction provides a rigorous framework for cone-beam computed tomography (CBCT) by combining an explicit acquisition model with image priors. However, iterative optimization remains computationally demanding, particularly under severe noise and sparse-view conditions. Although learning-based methods achieve high reconstruction quality, they often replace the original variational formulation with learned optimization schemes or nonlinear equilibrium models. We propose a neural network-guided warm-start framework that accelerates variational reconstruction while preserving its original formulation. Projection data are first reconstructed using the Feldkamp-Davis-Kress (FDK) algorithm, and the resulting image is refined by an image-domain neural network. The network output is used solely to initialize the subsequent model-based optimization, leaving the forward model, data-fidelity term, regularization, and optimization scheme unchanged. A pre-regularization step further improves compatibility with the variational priors. Experiments on pelvic CT images from the SynthRAD2025 challenge show a more than threefold reduction in reconstruction time while maintaining comparable image quality.

0.21

Learning Variable Metrics for Convergent Proximal Splitting Algorithms

eess.IV ·2026-10-15 ·Yodai Suzuki, Shunsuke Ono
similarity 0.62
Abstract

We propose learned variable metric (LVM), a framework that learns metrics of proximal splitting algorithms adapted to each problem instance, coordinate, and iteration with a convergence guarantee. Proximal splitting algorithms can solve a wide variety of convex optimization problems but often require many iterations to converge. Choosing a suitable metric is an effective remedy, and variable metric theory naturally extends convergence guarantees to metrics that vary over the iterations. Learning is a promising way to design such adaptive metrics beyond the reach of manual design, but a naive implementation leads to (i) an expensive evaluation of a network at every iteration and (ii) difficulty in satisfying the conditions that the theory imposes on the whole infinite sequence of metrics. To resolve these difficulties, we first train a neural network to generate a few representative metrics once per problem instance, and then obtain the metric of every iteration by combining them with basis functions of the normalized iteration index. We present LVM for the proximal gradient method with a quadratic term and the primal-dual hybrid gradient method, and prove their convergence under a mild spectral condition, which is ensured by a rescaling of the representative metrics. In experiments on deblurring and inpainting, LVM reduces the number of iterations to reach a target accuracy in most tested settings compared with several baselines, and the computation time at high accuracies.

0.16

Convex-SKM-Net: Low-Latency Block Halfspace Corrections for Neural Convex Constraint Satisfaction

cs.LG cs.AImath.OC ·2026-10-28 ·Haoyu Zhu, Xiaochen Zhang, Qingchun Hou
benchmarktheory similarity 0.62
Abstract

Fast inference and strict constraint satisfaction are essential for learning-based decision-making. Existing methods often rely on constraint-specific projections or feasible-set parameterizations, while iterative repair can be costly. We introduce Convex-SKM-Net, a convex constraint-satisfaction layer that forms linearization halfspaces from residual and (sub)gradient oracles without constraint-specific inequality projectors. It applies fixed-depth dual projected-gradient descent (dual PGD) to minimum-displacement block problems using GPU-friendly matrix operations. We jointly learn the predictor and a positive-definite mobility, adapting the correction geometry to improve objective quality. We prove convergence of the outer iterates at fixed dual depth and linear convergence in distance under Slater's condition and bounded subgradients. All our test outputs on three second-order-cone model-predictive control (SOC-MPC) horizons and six power-system convex relaxations satisfy a $10^{-3}$ feasibility tolerance. Comparisons with the latest constraint-satisfaction methods show inference speedups of up to $144.3\times$ on SOC-MPC and $7.7\times$ on a convex quadratically constrained quadratic programming (QCQP) benchmark with joint training. On QCQP, the mean objective gap is $0.012\%$, with full test feasibility at $10^{-4}$. Learning mobility reduces the five-seed affine-task mean gap by $22.4\%$ and improves gaps in matched power-system comparisons.

0.10

Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

cs.LG math.OC ·2026-08-13 ·Liping Tao, Chee Wei Tan
similarity 0.61
Abstract

Laplacian-regularized minimization is fundamental in signal processing and machine learning, but explicit construction of the dense graph Laplacian pseudoinverse can be computationally expensive. To address this issue, we consider the setting where the graph Laplacian is given and propose a Difference-of-Convex Regularizer (DCR) graph learning framework that learns a reusable approximation of the pseudoinverse action through regularized Maximum Likelihood Estimation (MLE) and shrinkage-regularized Convex--Concave Procedure (CCCP) iterations. For Laplacian-Regularized Nonnegative Least Squares (LR-NNLS), dual and Karush-Kuhn-Tucker (KKT) analysis motivates separating graph-dependent pseudoinverse learning from instance-specific optimization. The learned pseudoinverse is embedded into a differentiable primal optimization procedure as a graph-aware preconditioner for nonnegative reconstruction and can be reused across LR-NNLS instances sharing the same graph. We establish stability and fixed-point existence guarantees for the proposed pseudoinverse-learning iteration. Experiments across different graph topologies and scales demonstrate near-reference accuracy, competitive time-to-moderate-accuracy behavior, and effective cross-instance reuse across independently generated problem instances sharing the same graph.

0.04

Taming Neural Fields with a Frequency-Lipschitz Curriculum for Sparse-View CT Reconstruction

cs.CV cs.LG ·2026-11-11 ·Songtao Hu, Jingrui Wu, Hong Ding, Fanhao Zhu, Yunhao Liu +1 more
similarity 0.61
Abstract

Sparse-view computed tomography (SVCT) reduces radiation dose by acquiring fewer projection views, but the resulting under-determined inverse problem requires careful regularization to prevent reconstruction algorithms from fitting streak artifacts and hallucinated structures. Existing implicit neural representation (INR) methods rely on implicit spectral bias or iterative external denoising, yet they provide limited control over when high-frequency capacity is exposed during optimization. To address this limitation, we propose FLIC (Frequency-Lipschitz INR Curriculum), a capacity-controlled self-prior INR framework that makes the network's representational capacity explicit and schedulable. The core of our method is a joint frequency-Lipschitz curriculum that couples random Fourier feature encoding with spectrally normalized MLP decoding under non-uniform Lipschitz budgets, guiding reconstruction along a coarse-to-fine trajectory from stable global anatomy to fine details. The terminal capacity is automatically calibrated from FBP gradient statistics, enabling scan-adaptive regularization without per-scan manual tuning of the terminal Lipschitz budget. We further introduce a prior-guided adaptive ray sampling strategy that concentrates integration samples near high-gradient anatomical boundaries, improving forward-model fidelity. The entire framework operates in a single training stage without iterative denoising, enabling efficient per-image reconstruction. Extensive experiments on four public CT datasets under noise-free and low-dose settings show that our method achieves state-of-the-art unsupervised reconstruction quality with consistent performance across diverse anatomical structures.

0.13

Riemannian Difference-of-Convex Optimization for K-Means Clustering

cs.LG math.OC ·2026-09-28 ·Meng Xu, Bo Jiang, Hanfu Zhang, Ya-Feng Liu, Anthony Man-Cho So
similarity 0.61
Abstract · 5 pages

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an $ε$-Riemannian critical point within $O(ε^{-3})$ iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

0.13