Proposes BMME for optimizing nonsmooth nonconvex problems with block structure.
problem Optimizing nonsmooth nonconvex problems with block structure.
method Block Alternating Bregman Majorization Minimization with Extrapolation (BMME).
result Subsequential convergence to a first-order stationary point under mild assumptions, global convergence under stronger conditions.
New algorithm for nonconvex optimization on constrained Riemannian manifolds converges quickly.
problem Optimization on constrained Riemannian manifolds.
method Block majorization-minimization (BMM) for smooth nonconvex objectives with Riemannian constraints.
result Converges to stationary points within O(ε−2) iterations. BMM algorithm improves convergence for nonconvex optimization problems.
problem Constrained nonsmooth nonconvex optimization problems.
method Block majorization-minimization with diminishing radius.
result Improved convergence rate for nonconvex optimization problems.
Paper extends SMM to weakly convex and multi-convex surrogates for non-convex optimization.
problem Non-convex optimization with weakly convex or multi-convex surrogates.
method Stochastic majorization-minimization with proximal regularization or block-minimization.
result Convergence rates for empirical and expected losses under non-i.i.d. data.
This paper revisits the classic iterative proportional scaling (IPS) from a modern optimization perspective. In contrast to the criticisms made in the literature, we show that based on a coordinate descent characterization, IPS can be slightly modified to deliver coefficient estimates, and from a majorization-minimizat…
Introduces PPMM algorithm for nonconvex robust regression problems.
problem Nonconvex tuning-free robust regression problems.
method PPMM algorithm with inner subproblems solved by SSN-PPA.
result Converges to d-stationary point with KL property.
Improved graph clustering with modularity and coarsening for attributes and communities.
problem Inaccurate community detection and computational inefficiency in graph clustering.
method Integrates coarsening and modularity maximization, using a loss function with log-determinant, smoothness, and modularity components.
result Superior clustering outcomes, proven consistent under DC-SBM, and efficient algorithm integration with GNNs and VGAEs.
Proposes a method for forecasting large-scale interval-valued time series.
problem Modeling and forecasting large-scale interval-valued time series.
method Feature extraction procedure involving auto-segmentation, clustering, and precision matrix estimation.
result The method enhances forecasting performance for large-scale interval-valued time series.
We propose an inference method to estimate sparse interactions and biases according to Boltzmann machine learning. The basis of this method is L1 regularization, which is often used in compressed sensing, a technique for reconstructing sparse input signals from undersampled outputs. L1 regularization impedes the …
Combines OT and PCA for DR, preserving clusters.
problem Analyzing high-dimensional data with global dependencies.
method Optimal transport (OT) for minimizing reconstruction error, combined with PCA.
result Effective preservation of high-dimensional clusters in embeddings.
A new method for 1-bit matrix completion that is faster and more accurate.
problem Estimating a low-rank matrix from binary observations.
method Majorization-Minimization Gauss-Newton (MMGN) method.
result MMGN outperforms existing methods in accuracy and speed.
Non-convex optimization is ubiquitous in machine learning. Majorization-Minimization (MM) is a powerful iterative procedure for optimizing non-convex functions that works by optimizing a sequence of bounds on the function. In MM, the bound at each iteration is required to \emph{touch} the objective function at the opti…
This paper considers the mean-reverting portfolio design problem arising from statistical arbitrage in the financial markets. The problem is formulated by optimizing a criterion characterizing the mean-reversion strength of the portfolio and taking into consideration the variance of the portfolio and an investment budg…
This paper introduces a robust mixing model to describe hyperspectral data resulting from the mixture of several pure spectral signatures. This new model not only generalizes the commonly used linear mixing model, but also allows for possible nonlinear effects to be easily handled, relying on mild assumptions regarding…
Nonconvex and nonsmooth optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology in the sense of scalability. A reason for this relatively low degree of popularity is the lack of a well developed system of theory an…
Majorization-minimization algorithms consist of iteratively minimizing a majorizing surrogate of an objective function. Because of its simplicity and its wide applicability, this principle has been very popular in statistics and in signal processing. In this paper, we intend to make this principle scalable. We introduc…
Unified framework for graph coarsening using node features and graph matrices.
problem Dimensionality reduction of large graphs while preserving node features.
method Optimization-based framework that unifies graph learning and dimensionality reduction.
result The learned coarsened graph is ε-similar to the original graph, where ε is a small positive number.
Unified approach for federated learning using MM optimization.
problem Scaling stochastic optimization to federated learning.
method Unified Majorize-Minimize (MM) framework for stochastic optimization, extended to federated learning.
result Unified algorithm \QSMM\ for federated learning that aggregates surrogate majorizing functions.
In this paper, we consider high-dimensional nonconvex square-root-loss regression problems and introduce a proximal majorization-minimization (PMM) algorithm for these problems. Our key idea for making the proposed PMM to be efficient is to develop a sparse semismooth Newton method to solve the corresponding subproblem…
Paper proposes an efficient algorithm for nonnegative binary matrix factorization.
problem Decomposing binary data using matrix factorization.
method Majorization-minimization algorithm with Beta prior for improved performance.
result Proposed algorithm offers excellent trade-off between performance, complexity, and interpretability.
Inexact Riemannian optimization converges to stationary points efficiently.
problem Analyzing convergence and complexity of inexact Riemannian optimization.
method Tangential Block Majorization-Minimization (tBMM) framework.
result tBMM converges to an ε-stationary point within O(ε⁻²) iterations.
One of the most fundamental concepts in statistics is the concept of sample mean. Properties of the sample mean that are well-defined in Euclidean spaces become unwieldy or even unclear in graph spaces. Open problems related to the sample mean of graphs include: non-existence, non-uniqueness, statistical inconsistency,…
New algorithm speeds up NMF with β-divergence.
problem Efficiently factorize nonnegative matrices with β-divergence. method Joint majorization-minimization with multiplicative updates.
result Significant reduction in computation time for NMF.
Majorization-minimization algorithms consist of successively minimizing a sequence of upper bounds of the objective function. These upper bounds are tight at the current estimate, and each iteration monotonically drives the objective function downhill. Such a simple principle is widely applicable and has been very popu…
Support vector machines (SVMs) are an important tool in modern data analysis. Traditionally, support vector machines have been fitted via quadratic programming, either using purpose-built or off-the-shelf algorithms. We present an alternative approach to SVM fitting via the majorization--minimization (MM) paradigm. Alg…
QMME balances cost and speed in convex optimization.
problem Slow convergence of first-order methods and high cost of second-order methods.
method Minimizing quadratic majorants with fixed curvature at each iteration.
result QMME framework achieves sequential convergence under standard assumptions.
New framework tracks communities in dynamic networks.
problem Discovering and tracking communities in evolving networks.
method Spectral framework on Grassmann manifold for subspace tracking.
result Improved dynamic community detection results across various network types.
Proposes MM-DUST for efficient generalized lasso solution paths.
problem Efficiently solve generalized lasso problems in large-scale and non-linear models.
method Majorization-minimization dual stagewise algorithm incorporating quadratic majorizers and stagewise learning.
result Established the uniform convergence of approximated solution paths.
Paper proposes a method to improve graph clustering by integrating node textual metadata with node signals in GGMs.
problem Graph learning in Gaussian Graphical Models with auxiliary node metadata.
method Laplacian-constrained Gaussian Graphical Models with majorization-minimization algorithm.
result The proposed method outperforms state-of-the-art approaches that use either signals or metadata alone.
New algorithm improves on EM for streaming data, outperforming existing methods.
problem Processing high-volume, streaming data efficiently.
method Incremental stochastic Majorization-Minimization (MM) algorithm.
result The algorithm converges to a stationary point with vanishing gradient.
CCMM efficiently solves large-scale convex clustering problems.
problem Scalability and hierarchical structure in convex clustering.
method Majorization-minimization algorithm with cluster fusions and efficient updating.
result CCMM achieves efficient solutions for large datasets.
A new framework for predictive clustering and optimization.
problem Finding clusters of data that yield low error on a supervised target.
method Generalized optimization framework using MILP and MM for scalability.
result Models can uncover different interpretable discrete cluster structures.
Tyler's M-estimator's phase transition at DS-SNR = 1 is resolved.
problem Robust Subspace Recovery
method Tyler's M-estimator
result TME converges exactly to the true subspace for DS-SNR >= 1 under a new stability condition.
Paper proposes a new method for SP with covariates using PADR and ERM.
problem Stochastic programming with covariate information.
method Empirical risk minimization (ERM) with nonconvex piecewise affine decision rules (PADR).
result The method provides theoretical consistency and computational tractability for nonconvex SP problems.
A new framework evaluates large language models efficiently and accurately.
problem Evaluation of large language models is challenging due to stochasticity and heterogeneity of benchmarks.
method Interpretable and scalable framework based on Item Response Theory (IRT) and majorization-minimization principle.
result Our method achieves superior scalability and interpretability compared to existing approaches.
Novel Bayesian framework for spatio-temporal neuroimaging data.
problem Inference on multi-task sparse hierarchical regression models with complex spatio-temporal dynamics.
method Flexible hierarchical Bayesian framework with Kronecker product covariance structure, majorization-minimization optimization, and Riemannian geometry.
result Improved performance on synthetic and real M/EEG data.
MM (majorization--minimization) algorithms are an increasingly popular tool for solving optimization problems in machine learning and statistical estimation. This article introduces the MM algorithm framework in general and via three popular example applications: Gaussian mixture regressions, multinomial logistic regre…
Paper tackles low-rank matrix recovery with column ℓ2,0-norm regularization.
problem Low-rank matrix recovery problems with column sparsity constraints.
method Developed alternating majorization-minimization (AMM) methods with extrapolation and hybrid AMM.
result Global convergence analysis and superior performance in matrix completion problems.
WDL models density curves using Wasserstein distance and flexible mixture models.
problem Modeling entire distribution and non-negativity constraints.
method Wasserstein distance, Semi-parametric Conditional Gaussian Mixture Models (SCGMM), Majorization-Minimization optimization.
result WDL better characterizes nonlinear dependence of conditional densities.
In this paper we develop a method for learning nonlinear systems with multiple outputs and inputs. We begin by modelling the errors of a nominal predictor of the system using a latent variable framework. Then using the maximum likelihood principle we derive a criterion for learning the model. The resulting optimization…
Optimal transport aggregation combines distributed MoE models efficiently.
problem Combining local MoE models trained on distributed datasets.
method Optimal transport for minimizing divergence between local and global estimators, with MM algorithm for optimization.
result Aggregated estimator achieves performance comparable to centralized training but with reduced computation time.
The paper develops an algorithm to select a subset of training data for efficient regression models.
problem Designing an efficient algorithm for selecting a subset of training data to train regression models quickly without sacrificing accuracy.
method The paper tackles this problem by formulating it as a minimization of training loss with respect to both trainable parameters and subset of training data, subject to error bounds on the validation set. They use a novel problem formulation and represent it with simplified constraints using the dual of the original training problem. They then develop SELCON, an efficient majorization-minimization algorithm for data subset selection, which admits an approximation guarantee.
result The experiments show that SELCON trades off accuracy and efficiency more effectively than the current state-of-the-art.
PIANO speeds up multinomial logistic regression solving.
problem Handling large datasets and many classes in logistic regression.
method Parallel iterative algorithm based on Majorization Minimization.
result PIANO converges to a stationary point of Multinomial and Sparse Multinomial Logistic Regression.
Paper proposes SRA algorithm for online learning robustness and adaptivity.
problem Quantifying and evaluating tradeoff between robustness and adaptivity in online learning.
method SRA algorithm using biased stochastic approximation scheme with adaptive threshold.
result SRA algorithm provides superior performance in synthetic and real datasets.
This paper presents a novel Block Iterative Bayesian Algorithm (Block-IBA) for reconstructing block-sparse signals with unknown block structures. Unlike the existing algorithms for block sparse signal recovery which assume the cluster structure of the nonzero elements of the unknown signal to be independent and identic…
This letter presents a novel Block Bayesian Hypothesis Testing Algorithm (Block-BHTA) for reconstructing block sparse signals with unknown block structures. The Block-BHTA comprises the detection and recovery of the supports, and the estimation of the amplitudes of the block sparse signal. The support detection and rec…
We examine the recovery of block sparse signals and extend the framework in two important directions; one by exploiting signals' intra-block correlation and the other by generalizing signals' block structure. We propose two families of algorithms based on the framework of block sparse Bayesian learning (BSBL). One fami…
In econometrics and finance, the vector error correction model (VECM) is an important time series model for cointegration analysis, which is used to estimate the long-run equilibrium variable relationships. The traditional analysis and estimation methodologies assume the underlying Gaussian distribution but, in practic…