Actor-critic algorithms for fiber sampling problems

• URL: http://arxiv.org/abs/2405.13950v1
• Date: Wed, 22 May 2024 19:33:58 GMT
• Title: Actor-critic algorithms for fiber sampling problems
• Authors: Ivan Gvozdanović, Sonja Petrović,
• Abstract summary: We propose an actor-critic algorithm for a family of complex problems arising in statistics and discrete optimization. We translate the problem into a Markov decision process and devise an actor-critic reinforcement learning (RL) algorithm to learn a set of good moves that can be used for sampling. We prove that the actor-critic algorithm converges to an approximately optimal sampling policy.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We propose an actor-critic algorithm for a family of complex problems arising in algebraic statistics and discrete optimization. The core task is to produce a sample from a finite subset of the non-negative integer lattice defined by a high-dimensional polytope. We translate the problem into a Markov decision process and devise an actor-critic reinforcement learning (RL) algorithm to learn a set of good moves that can be used for sampling. We prove that the actor-critic algorithm converges to an approximately optimal sampling policy. To tackle complexity issues that typically arise in these sampling problems, and to allow the RL to function at scale, our solution strategy takes three steps: decomposing the starting point of the sample, using RL on each induced subproblem, and reconstructing to obtain a sample in the original polytope. In this setup, the proof of convergence applies to each subproblem in the decomposition. We test the method in two regimes. In statistical applications, a high-dimensional polytope arises as the support set for the reference distribution in a model/data fit test for a broad family of statistical models for categorical data. We demonstrate how RL can be used for model fit testing problems for data sets for which traditional MCMC samplers converge too slowly due to problem size and sparsity structure. To test the robustness of the algorithm and explore its generalization properties, we apply it to synthetically generated data of various sizes and sparsity levels.

Related papers

• Symmetry Nonnegative Matrix Factorization Algorithm Based on Self-paced Learning [10.6600050775306]
  A symmetric nonnegative matrix factorization algorithm was proposed to improve the clustering performance of the model. A weight variable that could measure the degree of difficulty to all samples was assigned in this method. The experimental results showed the effectiveness of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-10-20T06:33:02Z)
• Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models [6.54203362045253]
  We study the problem of learning directed acyclic graphs from continuous observational data. We develop a mixed-integer programming framework for learning medium-sized problems. Our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity.
  arXiv  Detail & Related papers  (2024-04-19T02:42:13Z)
• Sparse Variational Student-t Processes [8.46450148172407]
  Student-t Processes are used to model heavy-tailed distributions and datasets with outliers. We propose a sparse representation framework to allow Student-t Processes to be more flexible for real-world datasets. We evaluate two proposed approaches on various synthetic and real-world datasets from UCI and Kaggle.
  arXiv  Detail & Related papers  (2023-12-09T12:55:20Z)
• Faster Adaptive Federated Learning [84.38913517122619]
  Federated learning has attracted increasing attention with the emergence of distributed data. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on momentum-based variance reduced technique in cross-silo FL.
  arXiv  Detail & Related papers  (2022-12-02T05:07:50Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Expectation propagation on the diluted Bayesian classifier [0.0]
  We introduce a statistical mechanics inspired strategy that addresses the problem of sparse feature selection in the context of binary classification. A computational scheme known as expectation propagation (EP) is used to train a continuous-weights perceptron learning a classification rule. EP is a robust and competitive algorithm in terms of variable selection properties, estimation accuracy and computational complexity.
  arXiv  Detail & Related papers  (2020-09-20T23:59:44Z)
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning [27.775096437736973]
  We show that the independent sampling scheme tends to improve performance of the commonly-used uniform sampling scheme. Our new analysis also derives a speed for the sampling than best one available so far.
  arXiv  Detail & Related papers  (2020-09-14T16:41:32Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  We propose an easy-to-use and general-purpose approach for fast posterior sampling. We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
  arXiv  Detail & Related papers  (2020-02-21T14:03:16Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.