This work explores the non-convex optimization in compressive learning and the performance of heuristics.
problem The challenge of learning from compressed representations in compressive learning.
method Numerical simulations of the non-convex optimization landscape and heuristic performance.
result Properties of the non-convex optimization landscape and heuristic performance are explored.
Finite mixture models are among the most popular statistical models used in different data science disciplines. Despite their broad applicability, inference under these models typically leads to computationally challenging non-convex problems. While the Expectation-Maximization (EM) algorithm is the most popular approa…
Paper proposes a method to efficiently cluster stretched mixtures.
problem Clustering stretched elliptical mixtures using standard methods like PCA and k-means fails.
method Proposes a non-convex program to transform data into a one-dimensional point cloud.
result Efficient first-order algorithm achieves near-optimal statistical precision.
Study reveals structure of local minima in GMMs, identifying key cluster centers.
problem Identifying optimal cluster centers in non-convex GMM landscapes.
method Analyzing the negative log-likelihood function of GMMs in the population limit.
result Local minima share a common structure that partially identifies true cluster centers.
GAT-GMM improves GANs' performance in learning Gaussian mixture models.
problem GANs struggle with multi-modal distributions like Gaussian mixtures.
method Proposes a minimax GAN framework using random linear generator and softmax-based quadratic discriminator.
result Gradient Descent Ascent method converges to an approximate minimax point.
Algorithm recovers multiple low-rank matrices from unlabeled data.
problem Learning mixtures of low-rank models from unlabelled data.
method Three-stage meta-algorithm that copes with non-convexity and noise.
result Near-optimal sample and computational complexities under Gaussian designs.
New method estimates chirp parameters robustly from noisy mixtures.
problem Estimating chirp parameters from noisy mixtures of higher-order polynomials.
method Modified Langevin Monte Carlo (LMC) with curvature guidance.
result CG-LMC algorithm reliably finds minimizer in low SNR regimes.
A meta-learning approach improves the performance of alternating minimization for non-convex optimization problems.
problem Optimizing non-convex problems with multiple variables using alternating minimization.
method Meta-learning based alternating minimization (MLAM) to replace handcrafted updating rules.
result The proposed MLAM method outperforms traditional AM-based methods in various non-convex optimization problems.
Mixture modeling is a general technique for making any simple model more expressive through weighted combination. This generality and simplicity in part explains the success of the Expectation Maximization (EM) algorithm, in which updates are easy to derive for a wide class of mixture models. However, the likelihood of…
Shielded LMC samples from non-convex spaces with repulsive drift.
problem Sampling from non-convex spaces with convex holes.
method Combining adaptive temperature and repulsive drift.
result Advantages over unconstrained sampling in constrained spaces.
Develops a tensor mixture model for high-dimensional data clustering.
problem Jointly modeling and clustering tensors in high dimensions.
method High-dimensional tensor mixture model with plausible dimension reduction assumptions. EHCMA algorithm for efficient estimation.
result The HECM algorithm converges geometrically to a neighborhood within statistical precision of the true parameter.
NPMLE estimator automatically chooses the right model complexity for Gaussian mixtures.
problem Learning mixture models and empirical Bayes estimation with non-convex likelihoods.
method Nonparametric maximum likelihood estimator (NPMLE) using complex-analytic techniques.
result NPMLE solution has O(logn) atoms with high probability, improving model complexity. We show that many machine learning goals, such as improved fairness metrics, can be expressed as constraints on the model's predictions, which we call rate constraints. We study the problem of training non-convex models subject to these rate constraints (or any non-convex and non-differentiable constraints). In the non…
Analysis of SGD for Gaussian mixture classification using dynamical mean-field theory.
problem Learning dynamics of SGD for a neural network classifying Gaussian mixture.
method Applying dynamical mean-field theory to track SGD dynamics in high dimensions.
result Reveals how SGD navigates the non-convex loss landscape.
A new graph embedding method using Hebbian learning for improved vector representations.
problem Creating accurate vector representations for nodes in graphs.
method Hebbian learning with non-convex Gaussian mixture model for node embeddings.
result The method outperforms state-of-the-art methods on benchmark data sets and generates relevant recommendations.
The likelihood function of a finite mixture model is a non-convex function with multiple local maxima and commonly used iterative algorithms such as EM will converge to different solutions depending on initial conditions. In this paper we ask: is it possible to assess how far we are from the global maximum of the likel…
Optimizes MMD learning for generative models with theoretical guarantees.
problem Theoretical guarantees for optimizing non-convex MMD objectives.
method Analyzes MMD optimization landscape for specific distributions.
result Gradient-based methods globally minimize MMD objective for certain distributions.
Graphical model has been widely used to investigate the complex dependence structure of high-dimensional data, and it is common to assume that observed data follow a homogeneous graphical model. However, observations usually come from different resources and have heterogeneous hidden commonality in real-world applicati…
Expectation Maximization (EM) is among the most popular algorithms for maximum likelihood estimation, but it is generally only guaranteed to find its stationary points of the log-likelihood objective. The goal of this article is to present theoretical and empirical evidence that over-parameterization can help EM avoid …
AA extracts archetypes from data for clear feature extraction.
problem Non-convex optimization problem in AA.
method Computational procedure extracting archetypes as convex combinations of data.
result AA offers interpretable representations for high-dimensional data.
We consider the problem of finding critical points of functions that are non-convex and non-smooth. Studying a fairly broad class of such problems, we analyze the behavior of three gradient-based methods (gradient descent, proximal update, and Frank-Wolfe update). For each of these methods, we establish rates of conver…
The paper optimizes model selection and parameter estimation for multi-dimensional Gaussian Mixture Models.
problem Learning and distinguishing multi-dimensional Gaussian Mixture Models with reliable model order selection and efficient estimation.
method The paper establishes an information-theoretic lower bound and proposes a thresholding-based estimation algorithm with a time complexity of O(k^2 n). It also introduces a gradient-based minimization method with PCA for high-dimensional cases.
result The proposed method matches the established lower bound in sample complexity and achieves optimal parametric convergence rate.
We assume data sampled from a mixture of d-dimensional linear subspaces with spherically symmetric distributions within each subspace and an additional outlier component with spherically symmetric distribution within the ambient space (for simplicity we may assume that all distributions are uniform on their correspondi…
Deep neural networks help recover two signals from noisy mixtures.
problem Recovering two signals from noisy subgaussian mixtures with prior structural information.
method Used deep generative neural networks (GNNs) to solve the demixing problem for Lipschitz signals.
result Proved a sample complexity bound for nearly optimal recovery error, extending previous results.
New approach to machine learning optimization using distribution space.
problem Optimization challenges in machine learning with non-convex constraints.
method Relaxation to convex optimization in distribution space, numerical algorithm based on mixture distributions.
result Approximate optimization in distribution space is consistent and effective.
Most high-dimensional estimation and prediction methods propose to minimize a cost function (empirical risk) that is written as a sum of losses associated to each data point. In this paper we focus on the case of non-convex losses, which is practically important but still poorly understood. Classical empirical process …
Paper develops a robust classifier for Gaussian mixture models under sparse adversarial perturbations.
problem Classifying data under sparse adversarial perturbations for Gaussian mixture models.
method Develops FilTrun algorithm with filtration and truncation modules.
result Characterizes optimal robust classifier and robust classification error.
In many statistical learning problems, the target functions to be optimized are highly non-convex in various model spaces and thus are difficult to analyze. In this paper, we compute \emph{Energy Landscape Maps} (ELMs) which characterize and visualize an energy function with a tree structure, in which each leaf node re…
NOTMAD estimates context-specific Bayesian networks without breaking datasets.
problem Non-convexity of acyclic graphs limits sharing information between context-specific estimators.
method NOTMAD models context-specific Bayesian networks as mixtures of archetypal DAGs, estimating structures and parameters jointly.
result NOTMAD shares information between context-specific acyclic graphs, enabling single-sample resolution.
A new method for clustering heterogeneous data using likelihood-adjusted SDP.
problem Clustering heterogeneous data with different cluster shapes and sizes.
method Iterative likelihood-adjusted semidefinite programming (iLA-SDP) method.
result iLA-SDP achieves lower mis-clustering errors compared to other methods.
New algorithm reduces communication in federated learning.
problem Communication inefficiency in distributed federated learning.
method Distributionally Robust Federated Averaging (DRFA) with snapshotting scheme.
result DRFA achieves efficient convergence in various settings.
Compact, non-convex curve flows are created.
problem Creating compact, non-convex ancient solutions for curve shortening flow.
method Constructed an ancient solution asymptotic to Yin-Yang curve.
result Compact, non-convex ancient solutions for curve shortening flow are demonstrated.
Many tasks in machine learning and signal processing can be solved by minimizing a convex function of a measure. This includes sparse spikes deconvolution or training a neural network with a single hidden layer. For these problems, we study a simple minimization method: the unknown measure is discretized into a mixture…
We propose a set of convex low rank inducing norms for a coupled matrices and tensors (hereafter coupled tensors), which shares information between matrices and tensors through common modes. More specifically, we propose a mixture of the overlapped trace norm and the latent norms with the matrix trace norm, and then, w…
Paper uses integer programming for non-convex boosting in classification.
problem Improving classification performance using non-convex optimization.
method Non-convex boosting via integer programming.
result Results comparable to or better than state-of-the-art.
First order methods can take extremely long to find global minima of non-convex functions.
problem Finding global minimizers of non-convex functions.
method Designing a family of non-convex functions and using statistical lower bounds for parameter estimation.
result First order methods can take exponential time to converge to a global minimizer.
MixMax improves model performance across different settings using convex optimization.
problem Worst-case performance in group distributionally robust optimization for non-convex and non-parametric models.
method Reparameterizing group DRO from parameter space to function space, resulting in a convex optimization problem.
result MixMax matches or outperforms standard group DRO baselines, improving XGBoost performance on specific datasets.
New algorithm improves convergence for non-convex problems with boundaries.
problem Optimizing non-convex problems with constraints.
method Reflected Gradient Langevin Dynamics with probabilistic representation.
result Promising convergence rates, faster than existing methods.
We consider a Bayesian framework for estimating a high-dimensional sparse precision matrix, in which adaptive shrinkage and sparsity are induced by a mixture of Laplace priors. Besides discussing our formulation from the Bayesian standpoint, we investigate the MAP (maximum a posteriori) estimator from a penalized likel…
Persistent sampling improves SMC efficiency by retaining and reusing particles.
problem High computational costs and particle impoverishment in SMC.
method Persistent sampling (PS) retains and reuses particles from all prior iterations, using multiple importance sampling and resampling from a mixture of historical distributions.
result PS achieves more accurate posterior approximations and lower variance in marginal likelihood estimates without additional likelihood evaluations.
We introduce a new local regret framework for non-convex models in dynamic environments.
problem Challenges in online forecasting for non-convex models with frequent updates and concept drift.
method We propose a novel local regret framework and a time-smoothed gradient update rule.
result Our approach yields more stable, robust, and computationally efficient forecasting compared to state-of-the-art methods.
This work shows neural networks can solve non-convex constraints problems.
problem Training neural networks under non-convex constraints.
method Project stochastic gradient descent with no-regret analysis of online learning.
result Overparameterized neural networks achieve near-optimal and near-feasible solutions.
In this paper, we consider the problem of learning high-dimensional tensor regression problems with low-rank structure. One of the core challenges associated with learning high-dimensional models is computation since the underlying optimization problems are often non-convex. While convex relaxations could lead to polyn…
New algorithms optimize non-smooth, non-convex objectives with improved complexity.
problem Optimizing non-smooth, non-convex stochastic objectives.
method Reduction to online learning, applying optimistic online learning techniques.
result Improved complexity for finding (δ,ε)-stationary points. SGD's uncertainty quantified in non-convex learning problems.
problem Uncertainty quantification in non-convex learning problems.
method Asymptotic normality of SGD iterates and bias characterization.
result SGD iterates are asymptotically normally distributed around the expected value of the invariant distribution.
Optimizers find approximate global minima in non-convex problems.
problem Understanding why local methods solve non-convex optimization problems.
method Formalizing the hypothesis that many local minima are approximately global minima.
result Most local minima of practical non-convex objectives are approximately global minima.
New insights into using momentum for non-convex optimization.
problem Improving training of non-convex models like deep neural networks.
method Developed a Lyapunov analysis of SGD with momentum using stochastic primal averaging.
result Precise conditions under which SGD+M outperforms SGD and optimal hyper-parameter schedules.
Here we study non-convex composite optimization: first, a finite-sum of smooth but non-convex functions, and second, a general function that admits a simple proximal mapping. Most research on stochastic methods for composite optimization assumes convexity or strong convexity of each function. In this paper, we extend t…