Expectation-Maximization (EM) is a prominent approach for parameter estimation of hidden (aka latent) variable models. Given the full batch of data, EM forms an upper-bound of the negative log-likelihood of the model at each iteration and updates to the minimizer of this upper-bound. We first provide a "model level" in…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Online EM”
We study the problem of learning a latent variable model from a stream of data. Latent variable models are popular in practice because they can explain observed data in terms of unobserved concepts. These models have been traditionally studied in the offline setting. In the online setting, on the other hand, the online…
In this paper we formulate the nonnegative matrix factorisation (NMF) problem as a maximum likelihood estimation problem for hidden Markov models and propose online expectation-maximisation (EM) algorithms to estimate the NMF and the other unknown static parameters. We also propose a sequential Monte Carlo approximatio…
Paper develops an online EM algorithm for graph signal inference from streaming data.
problem Joint inference and clustering of graph signals with non-white excitation.
method Mixture model with low-rank plus sparse prior, online EM algorithm.
result Proposed online EM algorithm converges to MAP solution.
Online (also called "recursive" or "adaptive") estimation of fixed model parameters in hidden Markov models is a topic of much interest in times series modelling. In this work, we propose an online parameter estimation algorithm that combines two key ideas. The first one, which is deeply rooted in the Expectation-Maxim…
New model tackles interference in online experiments.
problem Understanding cumulative performance in interference experiments.
method Introduces Multi-Armed Bandits with Interference (MABI) model.
result Cluster randomization policy achieves optimal expected regret and high probability bound.
New methods speed up fitting for large datasets with noisy observations.
problem Fitting large datasets with Gaussian noise and known covariance.
method Two minibatch variants of extreme deconvolution, online EM algorithm, and gradient-based optimisation.
result Methods can scale to larger models and fit larger datasets faster.
The Gaussian mixture model is a classic technique for clustering and data modeling that is used in numerous applications. With the rise of big data, there is a need for parameter estimation techniques that can handle streaming data and distribute the computation over several processors. While online variants of the Exp…
As an automatic method of determining model complexity using the training data alone, Bayesian linear regression provides us a principled way to select hyperparameters. But one often needs approximation inference if distribution assumption is beyond Gaussian distribution. In this paper, we propose a Bayesian linear reg…
A new algorithm for cryo-EM data collection that balances reward and latency.
problem Optimizing data collection in cryo-EM experiments with action delays.
method Latency-aware contextual bandit framework and COAF algorithm.
result The COAF algorithm efficiently maximizes reward over time in cryo-EM experiments.
Bayesian framework estimates label shift for improved classifier performance.
problem Label shift in supervised learning leading to degraded classifier performance.
method Bayesian framework with dynamic Dirichlet priors and online EM algorithms.
result Significant improvements in classifier accuracy over state-of-the-art methods.
Paper addresses online identification and clustering for mixed linear regression models.
problem Online identification and clustering of mixed linear regression models.
method Introduces two online identification algorithms based on the EM principle, proving global convergence without i.i.d. data assumptions.
result Global convergence of the proposed algorithms for mixed linear regression models.
A new framework predicts hidden Markov model regimes online.
problem Efficiently identify hidden Markov model regimes in streaming data.
method Develops a predictive-first optimisation framework for streaming HMMs, approximating the full posterior predictive distribution.
result The method provides competitive prequential performance compared to Online EM and Sequential Monte Carlo.
The stochastic dual coordinate-ascent (S-DCA) technique is a useful alternative to the traditional stochastic gradient-descent algorithm for solving large-scale optimization problems due to its scalability to large data sets and strong theoretical guarantees. However, the available S-DCA formulation is limited to finit…
We present a family of expectation-maximization (EM) algorithms for binary and negative-binomial logistic regression, drawing a sharp connection with the variational-Bayes algorithm of Jaakkola and Jordan (2000). Indeed, our results allow a version of this variational-Bayes approach to be re-interpreted as a true EM al…
New accelerators for EM improve convergence speed in complex mixture models.
problem Improving the convergence speed of the EM algorithm for complex mixture models.
method Derive a new operator connecting global descent and local convergence, and use it to develop two acceleration strategies.
result Two new acceleration strategies (G-Accelerator and Geo-Adaptive) significantly improve EM algorithm performance.
New method for online low-rank matrix completion with improved regret.
problem Designing an efficient algorithm for online recommendation systems with low regret.
method Explore-then-commit (ETC) approach and iterative user clustering (OCTAL) for rank-1 setting.
result Nearly optimal regret bounds for online low-rank matrix completion.
We introduce a new class of reinforcement learning methods referred to as {\em episodic multi-armed bandits} (eMAB). In eMAB the learner proceeds in {\em episodes}, each composed of several {\em steps}, in which it chooses an action and observes a feedback signal. Moreover, in each step, it can take a special action, c…
Paper proposes a method to estimate consumer valuations from bundle sales data.
problem Estimating consumer valuations from bundle sales data using classical methods is challenging.
method Proposes an approach using EM algorithm and Monte Carlo simulation to estimate consumer valuations from bundle sales data.
result The approach can recover the distribution of consumers' valuations and is robust to unobserved no-purchases and clustered market segments.
New framework tackles stochastic latent subgroup heterogeneity in online decision-making.
problem Stochastic latent heterogeneity in online decision-making where individual responses vary with unobserved subgroups.
method Latent heterogeneous bandit framework using EM-greedy algorithm to learn subgroup probabilities and reward parameters.
result Achieves optimal estimation and classification guarantees, revealing a fundamental stochastic barrier in online decision-making.
Inverse reinforcement learning (IRL) is the problem of learning the preferences of an agent from the observations of its behavior on a task. While this problem has been well investigated, the related problem of {\em online} IRL---where the observations are incrementally accrued, yet the demands of the application often…
Many real world problems can now be effectively solved using supervised machine learning. A major roadblock is often the lack of an adequate quantity of labeled data for training. A possible solution is to assign the task of labeling data to a crowd, and then infer the true label using aggregation methods. A well-known…
A new KF handles outliers without MSE loss.
problem Outliers degrade Kalman filter performance.
method NUV priors, EM and AM for variance estimation.
result Outlier-insensitive KF outperforms existing methods.
This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…
Extracting latent low-dimensional structure from high-dimensional data is of paramount importance in timely inference tasks encountered with `Big Data' analytics. However, increasingly noisy, heterogeneous, and incomplete datasets as well as the need for {\em real-time} processing of streaming data pose major challenge…
The paper addresses sampling bias in risk-based active learning.
problem Sampling bias in active learning leads to poor decision-making performance.
method The paper uses a semi-supervised Gaussian mixture model with an EM algorithm to counteract sampling bias.
result The EM algorithm effectively incorporates pseudo-labels for unlabelled data, reducing sampling bias.
Bounds on Littlestone dimension for private learning and online prediction.
problem Understanding the Littlestone dimension of composed classes for private learning.
method Deriving bounds on Littlestone dimension and transforming private learners.
result Improved bounds on sample complexity for private learning.
The paper improves smoothed analysis for online problems with adaptive adversaries.
problem Online prediction, discrepancy minimization, and online optimization with adaptive adversaries.
method General technique to prove smoothed guarantees against adaptive adversaries, reducing to simpler oblivious adversaries.
result Strong smoothed guarantees for three online problems, matching or improving previous results.
Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significan…
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.
The paper tackles online learning with two types of losses and shows it's impossible without certain assumptions.
problem Online learning with primary and secondary losses where the secondary loss is bounded by a linear threshold.
method Analyzes the feasibility of achieving low regret with respect to the primary loss while keeping the secondary loss within a linear threshold.
result Achieving the goal is impossible without bounded variance assumption on the secondary loss.
Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and…
We present a novel technique for learning the mass matrices in samplers obtained from discretized dynamics that preserve some energy function. Existing adaptive samplers use Riemannian preconditioning techniques, where the mass matrices are functions of the parameters being sampled. This leads to significant complexiti…
Paper tackles online allocation problems using adversarial training.
problem Online bipartite matching, especially in AdWords.
method Constructs a framework combining game theory, adversarial training, and GANs.
result Designs robust algorithms that perform well under practical and adversarial conditions.
Global Generalized Bianchi Identities for Invariant Variational Problems on Gauge-natural Bundlesmath-ph
We derive both {\em local} and {\em global} generalized {\em Bianchi identities} for classical Lagrangian field theories on gauge-natural bundles. We show that globally defined generalized Bianchi identities can be found without the {\em a priori} introduction of a connection. The proof is based on a {\em global} decom…
Paper proposes a faster SPIDER-EM variant for large-scale nonconvex optimization.
problem High computational cost of EM algorithm in large-scale learning.
method Extension of SPIDER-EM for nonconvex finite-sum optimization problems.
result Achieves state-of-the-art complexity bounds and linear convergence under certain conditions.
We consider the geometric formulation of the Hamiltonian formalism for field theory in terms of {\em Hamiltonian connections} and {\em multisymplectic forms}. In this framework the covariant Hamilton equations for Mechanics and field theory are defined in terms of multisymplectic --forms, where is the dimens…
Efficiently trains GMMs for streaming data with SGD, addressing local optima and numerical instabilities.
problem Local optima and numerical instabilities in training GMMs for high-dimensional streaming data.
method Stochastic Gradient Descent (SGD) with adaptive annealing and exponential-free approximation.
result SGD approach trains GMMs without k-means initialization and outperforms sEM for high-dimensional data.
Anomaly Detection has several important applications. In this paper, our focus is on detecting anomalies in seller-reviewer data using tensor decomposition. While tensor-decomposition is mostly unsupervised, we formulate Bayesian semi-supervised tensor decomposition to take advantage of sparse labeled data. In addition…
The EM algorithm is one of many important tools in the field of statistics. While often used for imputing missing data, its widespread applications include other common statistical tasks, such as clustering. In clustering, the EM algorithm assumes a parametric distribution for the clusters, whose parameters are estimat…
Bayesian networks (BN) are used in a big range of applications but they have one issue concerning parameter learning. In real application, training data are always incomplete or some nodes are hidden. To deal with this problem many learning parameter algorithms are suggested foreground EM, Gibbs sampling and RBE algori…
On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecs.LG
New algorithm learns halfspaces with adversarial noise efficiently.
problem Learning halfspaces in the presence of adversarial noise.
method Polynomial-time Perceptron-like online active learning algorithm.
result Near-optimal label and sample complexity with isotropic log-concave marginal distribution.
Gradient EM converges globally for over-parameterized Gaussian mixtures.
problem Recovering ground truth Gaussian mixtures with over-parameterized models.
method Gradient EM with over-parameterization, using Hermite polynomials and tensor decomposition.
result Gradient EM globally converges to ground truth with over-parameterization.
EM algorithm converges in KL divergence for exponential families via mirror descent.
problem Lack of understanding of EM's non-asymptotic convergence properties.
method Viewing EM as a mirror descent algorithm, showing convergence rates in KL divergence.
result KL divergence rates for EM in exponential families, invariant to parametrization.
Improves EM algorithm for better local optima in mixture models.
problem EM algorithm's sensitivity to initialization and bad local optima.
method Big Learning principle applied to upgrade EM algorithm.
result BigLearn-EM delivers optimal solution with high probability.
The study characterizes Hermitian manifolds with parallel Bismut-Strominger torsion.
problem Characterizing Hermitian manifolds with specific torsion properties.
method Analyzing the curvature tensor and properties of the Bismut-Strominger connection.
result A necessary and sufficient condition for Bismut torsion parallel manifolds.
sEM uses optimal transport to improve EM algorithm for better convergence and avoiding local optima.
problem Improving the EM algorithm for better convergence and avoiding local optima.
method sEM uses entropic optimal transport to compute responsibilities in the expectation step, leading to better global convergence guarantees and avoiding local optima.
result sEM learns cell labels significantly better than other approaches, improving convergence and avoiding local optima.
Paper analyzes EM algorithm's trajectory in 2MLR, revealing cycloid behavior.
problem Understanding the convergence and trajectory of EM algorithm in 2MLR.
method Explicit closed-form expressions for EM updates, recurrence relation derivation at population level.
result EM iterations lie on a cycloid trajectory, leading to theoretical estimate of convergence exponent.