PaperlayerView exact revision on arXiv

Source-linked AI summary

Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization

Jingyuan Xia, Shengxi Li, Jun-Jie Huang, Imad Jaimoukha, Deniz Gunduz

arXiv:2009.04899v7cs.LGmath.OCstat.ML

TL;DR

Non-convex alternating minimization can be trapped in spurious local minima, while learning-based approaches are constrained by data needs and explainability. MLAM learns adaptive updates using global-loss information while retaining the iterative algorithmic structure. The paper reports results on matrix completion and GMM, including better mean negative log-likelihood than EM on 50 GMM tests.

Abstract

from arXiv · show

In this paper, we propose a novel solution for non-convex problems of multiple variables, especially for those typically solved by an alternating minimization (AM) strategy that splits the original optimization problem into a set of sub-problems corresponding to each variable, and then iteratively optimize each sub-problem using a fixed updating rule. However, due to the intrinsic non-convexity of the original optimization problem, the optimization can usually be trapped into spurious local minimum even when each sub-problem can be optimally solved at each iteration. Meanwhile, learning-based approaches, such as deep unfolding algorithms, are highly limited by the lack of labelled data and restricted explainability. To tackle these issues, we propose a meta-learning based alternating minimization (MLAM) method, which aims to minimize a partial of the global losses over iterations instead of carrying minimization on each sub-problem, and it tends to learn an adaptive strategy to replace the handcrafted counterpart resulting in advance on superior performance. Meanwhile, the proposed MLAM still maintains the original algorithmic principle, which contributes to a better interpretability. We evaluate the proposed method on two representative problems, namely, bi-linear inverse problem: matrix completion, and non-linear problem: Gaussian mixture models. The experimental results validate that our proposed approach outperforms AM-based methods in standard settings, and is able to achieve effective optimization in challenging cases while other comparing methods would typically fail.

I. INTRODUCTION

The paper argues that fixed, greedy alternating updates can miss global optima in non-convex problems, while learning-based approaches face limits in data availability and explainability. It proposes MLAM, which adapts update rules through meta-learning while retaining the iterative algorithmic structure, and evaluates it on matrix completion and Gaussian mixture models.

I. INTRODUCTION

  • Fixed, greedy sub-problem updates can fail to reach a global optimum in non-convex problems, even when each sub-problem is solved optimally.The paper identifies a lack of adaptiveness and global-loss information as central shortcomings of AM.Source: §I · p. 1
  • MLAM uses upper-level learning across problems and ground-level learning across sub-problems to adapt optimization rules while preserving the inner-and-outer iterative structure.The learned rule uses global-loss information rather than exhaustively minimizing each sub-problem locally.Source: §I · p. 2
  • MLAM is presented as an unsupervised, less-greedy adaptive strategy that can learn a non-monotonic algorithm for non-convex optimization.The approach retains the original model-based iterative algorithmic principles rather than replacing iterative operations with black-box networks.Source: §I · p. 2
  • The paper evaluates MLAM on matrix completion and Gaussian mixture models, reporting effective optimization on challenging problems where traditional approaches may fail.The authors frame these simulations as evidence of performance on difficult non-convex problems.Source: §I · p. 2

II. RELEVANT PRIOR WORK

The section frames multi-variable non-convex optimization and contrasts model-based alternating minimization with learning-based approaches. It motivates a method that retains optimization structure while addressing greedy local updates, data needs, and limited explainability.

II. RELEVANT PRIOR WORK

  • The general problem formulation treats observations as a mapping from two variables through a non-convex objective.The variables may be related linearly or nonlinearly.Source: §II · p. 2

A. Model-based Solutions

  • AM sequentially solves variable-specific sub-problems while holding other variables fixed, but its local, greedy updates need not optimize the global loss or reach a global optimum.The update rule is typically frozen across iterations.Source: A. Model-based Solutions · pp. 2–3

B. Learning-based Solutions

  • End-to-end deep learning methods typically use over-parameterized networks trained on large labeled datasets, which may be insufficient or unavailable for realistic non-convex tasks such as GMM.The section also identifies weak explainability as a shortcoming of these methods.Source: B. Learning-based Solutions · p. 3
  • Deep unfolding maps iterative algorithms to trainable network layers, but commonly uses a fixed number of layers and requires paired labels; cited approaches either replace solvers with networks or learn step-size parameters without surpassing a model-based counterpart.The section concludes that interpretability and performance remain limited for ill-posed non-convex problems, especially when labeled data are scarce.Source: B. Learning-based Solutions · p. 3

III. META-LEARNING BASED ALTERNATING MINIMIZATION (MLAM) APPROACH

MLAM uses two levels of meta-learning to adapt optimization rules for multi-variable non-convex problems. Its ground-level updates retain alternating inner and outer loops but use global-loss information to learn less-greedy update strategies.

III. META-LEARNING BASED ALTERNATING MINIMIZATION (MLAM) APPROACH

  • MLAM combines the optimization-based algorithmic principle with learning, aiming to surpass AM through meta-learning for highly non-convex, ill-posed problems.The method has upper- and ground-level meta-learning, each with inner and outer procedures.Source: §III · pp. 3–4, A. Overall Structure of the MLAM… · p. 4

A. Overall Structure of the MLAM Approach

  • Upper-level meta-learning learns across overall problems, while ground-level meta-learning optimizes the sequence of sub-problems within each problem.The upper-level updates MetaNet parameters across problems; the ground-level process solves each problem through alternating sub-problem updates.Source: A. Overall Structure of the MLAM… · p. 4, Figure 1 · p. 4

1) Upper-level Meta-learning:

  • Each overall problem is treated as a task, and the upper level learns general update rules across tasks rather than a solver for one task.Replacing frozen update functions with meta-networks lets inner-loop variable updates draw guidance from global-loss information at the outer level.Source: 1) Upper-level Meta-learning · p. 4

2) Ground-level Meta-learning:

  • At ground level, alternating outer-loop sub-problems contain iterative gradient-based inner loops; MetaNet parameters stay frozen inside and are updated outside with respect to global loss.The learned strategy uses experience across sub-problems to produce adaptive, less-greedy updates intended to improve solving the current task.Source: 2) Ground-level Meta-learning · pp. 4–5

B. MLAM with LSTM-based MetaNet

The LSTM-based MLAM uses recurrent MetaNets to generate variable updates and accumulated global losses to update their parameters. The inner-loop parameters are frozen, while outer-loop updates use losses accumulated over a chosen interval.

B. MLAM with LSTM-based MetaNet

  • The LSTM’s recurrent state carries information across iterations, and its cell-state update combines retained state with a candidate state.The paper describes the LSTM as able to memorize and forget sequential information.Source: B. MLAM with LSTM-based MetaNet · p. 5
  • LSTM MetaNets generate update functions for variables X and W from local-loss gradients and sequential cell-state knowledge, with outputs integrating step size and direction.The LSTM is used as the variable update function at ground level.Source: B. MLAM with LSTM-based MetaNet · p. 5
  • At inner loops, MetaNet parameters are frozen; at outer loops, accumulated global losses guide parameter updates through backpropagation.The accumulated losses connect variable-update functions with global-loss information and support adaptation across sub-problems.Source: B. MLAM with LSTM-based MetaNet · pp. 5–6
  • The update interval controls how often MetaNet parameters are updated: very short intervals such as tout = 1 can cause severe fluctuation, while accumulation can relieve outlier effects.The authors also state that accumulated global losses provide more mutual knowledge than one global-loss value.Source: B. MLAM with LSTM-based MetaNet · p. 6

F 21 end

MLAM learns adaptive optimization rules from partial global-loss trajectories while retaining an interpretable inner-and-outer iterative structure. The method uses hierarchical LSTMs and can learn non-monotonic trajectories.

F 21 end

  • MLAM updates its MetaNet to minimize partial global-loss trajectories, allowing the learned solution to increase loss early before decreasing toward better global optima.This replaces minimization of each subproblem at every step.Source: F 21 end · p. 6
  • Each outer loop begins from random initialization, runs inner updates for X and W, then updates their meta-parameters using accumulated global losses until the outer-loop limit T.The inner-loop iteration counts I and J are set to t_in in this paper, though the method can use different counts for different problems.Source: F 21 end · p. 6
  • Unlike deep unfolding, MLAM replaces each variable-update function with a meta-network and learns an optimization strategy across iterations, rather than mapping the whole procedure to a black-box operator.The paper also states that MLAM is feasible for unsupervised learning, whereas deep unfolding methods are mostly supervised.Source: F 21 end · pp. 6–7
  • The hierarchical model uses LSTMs for inner-loop optimization and updates their parameters across outer loops using accumulated global losses.It preserves the original algorithmic structure while replacing handcrafted update rules with meta-learned ones.Source: F 21 end · pp. 6–7

IV. APPLICATIONS IN TYPICAL PROBLEMS

The paper applies MLAM to matrix completion and Gaussian mixture models as representative bilinear inverse and nonlinear problems. These problems are considered settings where model-based methods are less effective and learning-based methods typically lack sufficient labelled data.

IV. APPLICATIONS IN TYPICAL PROBLEMS

  • The applications include matrix completion as a bilinear inverse problem and Gaussian mixture models as a nonlinear problem.Source: §IV · p. 7
  • The paper motivates these applications by noting that model-based methods are less effective and learning-based methods typically lack sufficient labelled data for the problems.Source: §IV · p. 7
  • Matrix completion and Gaussian mixture models serve as two representative problems for applying the proposed MLAM approach.Source: §IV · p. 7

A. Bi-linear Inverse Problem: Matrix Completion

The matrix-completion application addresses an ill-posed bilinear inverse problem whose performance can depend on initialization, gradient settings, sparsity, and restrictive assumptions. MLAM applies two LSTMs to update the factor matrices and uses global-loss information to adapt updates, including at local optima.

A. Bi-linear Inverse Problem: Matrix Completion

  • Matrix-completion performance is not universally satisfactory: it depends on initialization, gradient-descent settings, and matrix sparsity, while some methods rely on stringent assumptions uncommon in practice.Source: A. Bi-linear Inverse Problem: Matrix… · p. 7
  • The problem is ill-posed, and strong non-convexity and constraints limit traditional model-based methods as well as deep-learning and unfolding techniques.Source: A. Bi-linear Inverse Problem: Matrix… · p. 7
  • The paper tests more challenging cases—high-rank, unknown-rank, and mixed-rank completion—where existing model-based and learning-based approaches fail.Source: A. Bi-linear Inverse Problem: Matrix… · p. 7
  • Matrix completion is formulated as a low-rank matrix recovery problem, representing the matrix as UV^T; the rank parameter is typically known, and unknown rank makes the problem much harder.The paper states that existing methods would be unworkable when rank is not provided, and says MLAM is evaluated in that setting.Source: A. Bi-linear Inverse Problem: Matrix… · p. 7
  • The overall objective is non-convex in U and V, though fixing either variable yields a convex subproblem; MLAM uses separate LSTMs to update U and V and adjusts them from accumulated global losses.ALS and SGD are also described as iterative subproblem-minimization methods.Source: A. Bi-linear Inverse Problem: Matrix… · pp. 7–8
  • MLAM can still update variables at local optima, where gradient-based AM updates can become stuck, because its updates depend on learned parameters informed by partial global-loss trajectories.The paper also attributes smoother optimization to guidance from the global-loss landscape.Source: A. Bi-linear Inverse Problem: Matrix… · p. 8

B. Non-linear Problem: Gaussian Mixture Model

Gaussian mixture models present a nonlinear optimization problem with coupled parameters and many local optima, making global convergence difficult for model-based methods and labelled data intractable for learning-based approaches. MLAM directly optimizes the negative log-likelihood with meta-learned updates; in the illustrated example it escapes a local optimum where EM stops and reaches the global optimum.

B. Non-linear Problem: Gaussian Mixture Model

  • GMM optimization is nonlinear and can have many local optima; its subproblems typically lack closed-form solutions, making global convergence difficult and labelled data intractable for learning-based methods.Source: B. Non-linear Problem: Gaussian… · p. 8
  • MLAM applies a learning-based gradient-descent algorithm directly to the original GMM likelihood problem without extra constraints, with covariance assumed given in this setting.Source: B. Non-linear Problem: Gaussian… · p. 9
  • The GMM objective is split into subproblems for the mixing proportions π and means µ, which are updated by two LSTM MetaNets.The method backpropagates accumulated global losses across outer-loop iterations.Source: B. Non-linear Problem: Gaussian… · p. 9
  • The EM algorithm optimizes a lower bound through an AM-style maximization step, whereas MLAM directly optimizes the log-likelihood using updates informed by global-scope knowledge.Source: B. Non-linear Problem: Gaussian… · p. 9
  • In the illustrated three-cluster GMM, EM stops at a local optimum, while MLAM escapes it and converges to the global optimum.MLAM’s trajectory is non-monotonic: it initially moves down the loss geometry before heading toward the global optimum.Source: B. Non-linear Problem: Gaussian… · p. 9, Figure 3 · p. 9
  • MLAM’s non-monotonic flexibility can cause trajectory fluctuations and require more iterations when the optimization geometry is smooth and benign.Source: B. Non-linear Problem: Gaussian… · p. 9

V. EXPERIMENTS

The experiments assess MLAM on matrix completion and Gaussian mixture model problems. The method uses trained LSTM MetaNets and evaluates with fixed parameters on testing datasets.

V. EXPERIMENTS

  • The simulations evaluate MLAM on matrix completion and GMM problems.They are used to validate the method’s effectiveness and efficiency.Source: §V · p. 9
  • Each MetaNet uses a two-layer LSTM with 500 hidden units per layer, trained on accumulated losses using truncated BPTT and Adam at a 10^-3 learning rate.The LSTM parameters are randomly initialized and updated throughout training; ω_ts is set to 1.Source: §V · p. 9
  • For testing, the MLAM parameters are fixed and performance is evaluated on testing datasets.The ground-truth matrices are not specified here; this passage describes the evaluation procedure only.Source: §V · p. 9

A. Numerical Results on Matrix Completion

The matrix-completion experiments use synthetic problems at two matrix sizes, compare model-based and learning-based methods, and evaluate average reconstruction error on held-out tasks.

A. Numerical Results on Matrix Completion

  • Synthetic matrix-completion tasks use 10×10 and 100×100 matrices with randomly generated rank-p ground truth and randomly masked entries.The nonzero fraction of entries is the observation rate.Source: A. Numerical Results on Matrix… · p. 9
  • The comparisons include ALS and SGD as AM-based methods, and DMF and UMF as learning-based methods, with parameters tuned for best performance.Source: A. Numerical Results on Matrix… · p. 10
  • Each simulation uses 200 problems, split evenly between LSTM training and testing, with 100 alternating steps and average RMSE over the 100 test problems.Ground-truth matrices are withheld during training and testing and used only for post-optimization evaluation.Source: A. Numerical Results on Matrix… · p. 10

1) Parameter setting:

On matrix completion, MLAM outperforms the compared methods in low-rank tests and remains effective in high-rank and full-rank settings. Its parameter sweep shows a performance–efficiency trade-off, and its runtime is higher but differs from the alternatives by only seconds.

1) Parameter setting:

  • For rank-5 tasks, increasing tin improves performance substantially up to 10, while larger tin brings little gain; tout has less RMSE impact, with tout ≥10 improving stability.The sweep tested 400 combinations with tin and tout each ranging from 1 to 20 at 20% observation; the authors use tin = 10 and tout = 10 by default.Source: 1) Parameter setting · p. 10, Figure 4 · p. 10
  • Small tin may limit inner-loop ground-level meta-learning, while small tout may make outer-loop meta-learning less stable.The authors infer these possible effects from the roles of the inner and outer update steps.Source: 1) Parameter setting · p. 10

2) Standard matrix completion:

  • MLAM significantly outperforms all four existing methods on rank-5 matrix completion, especially at higher observation rates; at 20% observation, its RMSE is < 0.1.The table reports average RMSE across observation rates of 20%, 40%, 60%, and 80%.Source: 1) Parameter setting · p. 10, Table I · p. 11
  • At 20% observation, MLAM has the best RMSE performance with relatively small variance; ALS fluctuates severely, while SGD and DMF have larger variance.UMF has small variance but significantly worse accuracy than MLAM.Source: 2) Standard matrix completion · p. 10, Figure 5 · p. 11
  • As matrix rank increases, ALS is no longer workable above rank 10, while SGD, DMF, and UMF fail after rank 40; MLAM’s RMSE decreases as rank increases.The authors report that MLAM handles high- and full-rank completion without extra constraints, where standard methods typically fail.Source: 2) Standard matrix completion · p. 11
  • MLAM has higher execution time than the compared methods, with the difference within seconds; higher accuracy comes with greater time consumption.The authors describe demonstrating MLAM’s performance on multi-variable non-convex optimization as the paper’s proof-of-concept goal.Source: 2) Standard matrix completion · p. 11

3) Blind matrix completion:

Blind matrix completion tests show MLAM can handle rank uncertainty and mixed-rank samples, while GMM evaluations report better outcomes than EM across several challenging settings. The GMM tests include limited observations, anisotropic clusters, and higher dimensions.

3) Blind matrix completion:

  • MLAM tolerates large rank mismatch in blind completion: at p = 80 or 100 it remains acceptable, while other methods’ RMSEs exceed 100% when p ≥ 40.The method is described as not requiring accurate rank information for successful completion.Source: 3) Blind matrix completion · p. 11, Table III · p. 11
  • With ranks mixed from 10 to 100, p = 10 performs best across samples, especially low-rank cases; other p choices remain comparable on high-rank samples.The tests use rank values uniformly distributed between 10 and 100.Source: 3) Blind matrix completion · p. 11, Table V · p. 13

B. Numerical Results on Gaussian Mixture Model

  • In 50 random-initialization tests using 500 data points, MLAM outperformed EM in most cases, with mean negative log-likelihoods of 7.52 versus 7.75, and better clustering in one selected result.Source: B. Numerical Results on Gaussian… · p. 12
  • On 10,000-point flower-shaped data with eight anisotropic clusters, MLAM consistently achieves nearly optimal clustering while EM is highly biased under random initialization.The passage notes that such anisotropic clusters create extensive local optima.Source: B. Numerical Results on Gaussian… · p. 12, Figure 8 · p. 13
  • For GMMs with 500 observations and dimensions 4–64, MLAM outperforms EM in all tested sets, and its performance is unaffected by dimension variation.The paper concludes that MLAM finds good solutions for nonlinear problems without closed-form landscapes where EM fails.Source: B. Numerical Results on Gaussian… · p. 13, Table VI · p. 13

VI. CONCLUSION

The conclusion presents MLAM as a bi-level meta-learning approach that learns optimization strategies while retaining alternating minimization’s algorithmic structure. The authors report faster convergence and better performance than AM-based methods, and identify broader applications and theoretical analysis as future work.

VI. CONCLUSION

  • MLAM uses LSTM-based meta-learners to connect variable updates with global loss: frozen inner-loop networks update variables, while outer loops minimize accumulated global losses.The conclusion frames this as a less greedy learning-based approach to non-convex optimization.Source: §VI · p. 13
  • The authors report faster convergence and better performance than existing alternating-minimization-based methods.They describe the paper as proof of concept that a less greedy, learning-based solution could surpass traditional model-based and learning-based methods.Source: §VI · p. 13
  • Future work includes applying MLAM to more challenging practical problems, extending its theoretical analysis, and investigating online use without pre-training.Examples include dictionary learning in compressive sensing, blind image super-resolution, and MIMO beamforming.Source: §VI · p. 13
Loading 2009.04899v7…