The Perturbed Prox-Preconditioned SPIDER algorithm for EM-based large scale learning

• URL: http://arxiv.org/abs/2105.11732v1
• Date: Tue, 25 May 2021 07:54:58 GMT
• Title: The Perturbed Prox-Preconditioned SPIDER algorithm for EM-based large scale learning
• Authors: Gersende Fort (IMT), Eric Moulines (X-DEP-MATHAPP, XPOP)
• Abstract summary: Incremental Expectation Maximization (EM) algorithms were introduced to design EM for the large scale learning framework. We propose a novel algorithm named Perturbed Prox-Preconditioned SPIDER, which builds on the Perturbed Integral EstimatoR EM (SPIDER-EM) algorithm. The 3P-SPIDER algorithm addresses many intractabilities of the E-step of EM; it also deals with non-smooth regularization and convex constraint set.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Incremental Expectation Maximization (EM) algorithms were introduced to design EM for the large scale learning framework by avoiding the full data set to be processed at each iteration. Nevertheless, these algorithms all assume that the conditional expectations of the sufficient statistics are explicit. In this paper, we propose a novel algorithm named Perturbed Prox-Preconditioned SPIDER (3P-SPIDER), which builds on the Stochastic Path Integral Differential EstimatoR EM (SPIDER-EM) algorithm. The 3P-SPIDER algorithm addresses many intractabilities of the E-step of EM; it also deals with non-smooth regularization and convex constraint set. Numerical experiments show that 3P-SPIDER outperforms other incremental EM methods and discuss the role of some design parameters.

Related papers

• Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis [30.713243690224207]
  In Markov decision processes (MDPs), quantile risk measures such as Value-at-Risk are a standard metric for modeling RL agents' preferences for certain outcomes. This paper proposes a new Q-learning algorithm for quantile optimization in MDPs with strong convergence and performance guarantees.
  arXiv  Detail & Related papers  (2024-10-31T16:53:20Z)
• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  We design algorithms for Robust Component Analysis (A) It consists in decomposing a matrix into the sum of a low Principaled matrix and a sparse Principaled matrix.
  arXiv  Detail & Related papers  (2023-07-12T03:48:26Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Non-stationary Reinforcement Learning under General Function Approximation [60.430936031067006]
  We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA. We show that SW-OPEA is provably efficient as long as the variation budget is not significantly large.
  arXiv  Detail & Related papers  (2023-06-01T16:19:37Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization [0.0]
  3P-SP-IDER is a novel algorithm designed to solve finite sum non-backward logistic equations. We show that 3P-SP-IDER extends some preconditioned and some Incremental Maximization algorithms to the case forward operator can not be computed in closed form. We also discuss the role of some design parameters of 3P-SP-IDER in some application to inference in a regression model with random effects.
  arXiv  Detail & Related papers  (2023-01-02T12:49:48Z)
• Classical and Quantum Iterative Optimization Algorithms Based on Matrix Legendre-Bregman Projections [1.5736899098702972]
  We consider Legendre-Bregman projections defined on the Hermitian matrix space and design iterative optimization algorithms based on them. We study both exact and approximate Bregman projection algorithms. In particular, our approximate iterative algorithm gives rise to the non-commutative versions of the generalized iterative scaling (GIS) algorithm for maximum entropy inference.
  arXiv  Detail & Related papers  (2022-09-28T15:59:08Z)
• Multi-objective hyperparameter optimization with performance uncertainty [62.997667081978825]
  This paper presents results on multi-objective hyperparameter optimization with uncertainty on the evaluation of Machine Learning algorithms. We combine the sampling strategy of Tree-structured Parzen Estimators (TPE) with the metamodel obtained after training a Gaussian Process Regression (GPR) with heterogeneous noise. Experimental results on three analytical test functions and three ML problems show the improvement over multi-objective TPE and GPR.
  arXiv  Detail & Related papers  (2022-09-09T14:58:43Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization [21.81837334970773]
  We propose an extension of the Path-Integrated Differential Estima to the Expectation Maximization (EM) algorithm. We show it supports the same state art bounds as SPIDER-EM-IDER; and results provide for a rate for our findings.
  arXiv  Detail & Related papers  (2020-11-24T21:20:53Z)
• Better Trees: An empirical study on hyperparameter tuning of classification decision tree induction algorithms [5.4611430411491115]
  Decision Tree (DT) induction algorithms present high predictive performance and interpretable classification models. This paper investigates the effects of hyperparameter tuning for the two DT induction algorithms most often used, CART and C4.5. Experiments were carried out with different tuning strategies to induce models and to evaluate HPs' relevance using 94 classification datasets from OpenML.
  arXiv  Detail & Related papers  (2018-12-05T19:59:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.