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
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
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.
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.
Figure 3: Network approximation error of both subproblems across iterations k ; dots are test instances and black bars medians.
Method
Training time ↓
Inference steps ↓
Inference time ↓
Test objective ↓
Fully-amortized
17h28m
1
0.35 s
45.547±1.996
Semi-amortized
34h11m
10
0.51 s
24.425±0.508
Greedy (ours)
11h21m
10
0.53 s
25.824±0.362
+ fine tuning
+5h55m
10
0.54 s
23.840±0.468
Greedy (ours)
16h27m
20
1.05 s
24.043±0.328
Table 1: Comparison of different learning based approaches to solve Eq. 15 showing the mean objective and standard deviation across 210 test instances.
Figure 4: Relative objective gap for robust matrix completion against the outer iteration k with equal computational budget per iteration. The learned curve is the mean over 5 training seeds. The dashed vertical line marks the trained depth k=8 .
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Greedy
Greedy + FT
Semi-amortized
Fully-amortized
Outer iterations ( K )
20
10
10
1
Total parameters
3369100
1684550
1684550
2213957
Training epochs
Section D.4
greedy epochs + 10
50
50
Optimizer
AdamW
AdamW
AdamW
AdamW
Batch size
4 ( x ) / 8 ( z )
2
2
2
LR Scheduler
cosine
cosine
cosine
cosine
Appendix
Table 2: Details about the training settings for the different learned methods
Asset
Type
License
Reference
Low Dose CT Grand Challenge
Dataset
CC BY-NC 4.0 /
[ Moen et al., 2021 ]
NIH Controlled Data Access Policy
ODL
Software
MPL-2.0
[ Adler et al., 2017 ]
ASTRA Toolbox
Software
GPL-3.0
[ Van Aarle et al., 2015 , Van Aarle et al., 2016 ]
PyTorch
Software
BSD-3-Clause
[ Paszke et al., 2019 ]
Appendix
Table 3: Third-party assets used in this work.
Figure 5: Numerical verification of the assumption of the quadratic growth in a neighborhood of the optimal set as stated in 1 .
Figure 6: Relative parameter drift of the learned model across outer iterations k . We can see a decrease of the relative drift across the training epochs even though the training steps remain constant for later iterations.
Figure 7: Per-iteration training loss of the x - and z -networks under greedy training with warm-starting, normalized to the loss at the start of each outer iteration. Panel headers list the epoch budget used for each network at iteration k .
Figure 8: Comparison of three training strategies for the learned alternating scheme at K=10 outer iterations: greedy training, greedy training with end-to-end fine-tuning, and the semi-amortized variant. Both panels show the relative objective gap (F~K−F∗)/F∗ on a log scale, against the outer iteration k on the left and against cumulative runtime on the right. The shaded bands cover the 5 th– 95 th percentile range over the test instances.
Figure 9: Pareto-front comparison of the learned warm start with the inexact and learned methods. Both iterative methods are run for 20 outer iterations with different number of inner iterations. The inner solver can be stopped early if the subproblem has converged. Markers show the median over test instances and bands the 5th–95th percentiles and numbers give the inner-iteration budget.
variance ς
KL
risk term
complexity
RHS
trivial
RHS/trivial
0.001
1.9×109
2.2×10−3
608
608
0.83
733
0.0032
1.9×108
0.080
192
192
0.83
232
0.01
1.9×107
1.57
214
216
2.92
74
0.032
1.9×106
4.11
139
143
5.99
24
0.1
1.9×105
6.45
109
116
14.9
7.8
0.32
1.9×104
38.7
237
276
102
2.7
Appendix
Table 4: Evaluation of Eq. 81 for CT reconstruction ( K=20 , N=2000 , ρ=0.243 ) over the prior standard deviation ς . The risk term is ∑kρK−kEQ[Δ^k] , and the trivial bound grows with ς because the plug-in estimate M^ does.
k
Learned (ours)
FISTA (equal SVDs)
FISTA (time to match)
1 (trained)
0.112±0.002 s
0.116 s
0.335 s (3 SVDs)
4 (trained)
0.439±0.003 s
0.442 s
2.141 s (20 SVDs)
8 (trained)
0.873±0.003 s
0.878 s
4.355 s (40 SVDs)
16 (extrapolated)
1.746±0.009 s
1.764 s
5.114 s (48 SVDs)
32 (extrapolated)
3.495±0.012 s
3.460 s
6.935 s (64 SVDs)
Appendix
Table 5: Wall-clock time in seconds for the 128 test instances of robust matrix completion. Equal SVDs: FISTA at the same outer iteration k . Time to match: FISTA with the smallest number of SVDs (in parentheses) that reaches the objective of the learned scheme at k .
Outer iterations k
Learned (ours)
ADMM ( ρ=0.2 )
Prox-grad ( α=2.6 )
FISTA ( α=1/L )
1 (trained)
(3.46±0.01)×10−1
7.6×10−1
4.1×100
5.0×10−1
4 (trained)
(1.67±0.01)×10−2
7.5×10−2
1.3×10−1
2.5×10−1
8 (trained)
(6.59±0.11)×10−4
9.9×10−3
1.4×10−2
1.2×10−1
16 (extrapolated)
(3.66±0.53)×10−5
7.3×10−4
1.4×10−4
2.7×10−2
32 (extrapolated)
(4.38±0.64)×10−5
1.4×10−5
2.3×10−5
6.6×10−4
Appendix
Table 6: Relative optimality gap (F−F⋆)/F⋆ for robust matrix completion problem at equal SVD budget k (one SVD per outer iteration for all four methods). Learned results are the mean ± standard deviation over 5 independent training runs.
Figure 10: Learned parameters for robust matrix completion solver. Left: learned step size αk for each of the 5 seeds (markers) and their mean (line). Right: learned threshold (τk)i for the i -th singular value relative to the classical threshold αkλ1 at the same step size, averaged over the seeds. We show the first 20 indices only. The thresholds of smaller singular values receive no gradient during training, since these singular values lie below the threshold, and, therefore, remain at their initial value.
Symbol
Meaning
Value
K
trained depth
8
N
training sample size
2048
β
confidence level
0.05
C
log((2J+1)/β)+logG with J=40 , G=18000
17.2
μ
common quadratic growth constant ( estimated )
0.564
ρ
contraction rate at the selected α=0.02
0.66
Appendix
Table 7: Quantities entering Eq. 81 for robust matrix completion at the selected (α,ς) . Model trained on a fixed pool of N=2048 instances with drift penalty λD=10−4 . The constants μ and M^ are plug-in estimates, not certified constants.
N
λD
D
KL
RHS
trivial
LHS
gap at k=8
2048
0
53.6
2524
0.341
0.375
1.5×10−2
6.2×10−4
2048
10−4
20.2
951
0.218
0.375
1.7×10−2
4.3×10−4
2048
3×10−4
8.5
418
0.135
0.335
1.3×10−2
1.0×10−3
2048
10−3
3.5
174
0.095
0.335
1.4×10−2
3.1×10−3
128
10−4
19.4
915
0.954
0.446
1.6×10−2
4.3×10−4
Appendix
Table 8: Effect of the drift penalty λD and the sample size N on the bound for robust matrix completion. RHS is the right-hand side of Eq. 81 at the selected (α,ς) , and LHS is its left-hand side estimated on held-out instances. The last column is the relative optimality gap of the trained model at k=8 , averaged per instance. All rows use the common constant μ=0.564 and ρ=0.66 .
Given a matrix M∈Rm×n, the low rank matrix completion problem asks us to find a rank-k approximation of M as UV⊤ for U∈Rm×k and V∈Rn×k by only observing a few entries specified by a set of entries Ω⊆[m]×[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 M has incoherent rows and columns, then alternating minimization provably recovers the matrix M by observing a nearly linear in n 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), 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) time.
Yuzhou Gu, Zhao Song, Junze Yin +1
Institute of Advanced Study. · Adobe Research. · Boston University +1
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×n, a non-negative weight matrix W∈R≥0n×n, a parameter k, the goal is to output two matrices X,Y∈Rn×k such that ∥W∘(M−XY⊤)∥F is minimized, where ∘ 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 to ∥W∥0k where ∥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/ε)) includes the initialization. In exchange, our guarantee needs the weight matrix to be within spectral distance γn of the all-ones matrix for a γ that is polynomially small in n.
Zhao Song, Mingquan Ye, Junze Yin +1
Simons Institute for the Theory of Computing, UC Berkeley · University of Illinois, Chicago · Rice University +1
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.
Junan Lin, Paul J. Goulart, Luca Furieri
Department of Engineering Science, University of Oxford, OX1 3PJ Oxford, UK