Unified framework for tractable inference scenarios in machine learning models.
problem Complex inference scenarios in machine learning models.
method Characterization of tractable modular operations over circuits and derivation of a unified framework.
result Unified framework for reasoning about tractable models.
PNCs balance tractability and expressiveness in probabilistic modeling.
problem Balancing tractability and expressiveness in probabilistic models.
method Introduce probabilistic neural circuits (PNCs) as a mix of Bayesian networks and neural networks.
result PNCs are powerful function approximators.
Unified tractability conditions for various compositional inference queries.
problem Analyzing tractability of probabilistic and causal inference queries.
method Algebraic perspective on circuits, focusing on semiring operators.
result Unified sufficient conditions for tractable composition of operators.
Hybrid model combines continuous and tractable probabilistic models.
problem Intractable probabilistic inference in continuous latent-space models.
method Continuous mixtures of tractable probabilistic models with finite integration points.
result Hybrid models achieve state-of-the-art performance in density estimation.
New tractable density models from squaring neural networks.
problem Flexible models for probability distributions in machine learning.
method Squared Neural Family (SNEFY) models formed by squaring neural network outputs and normalizing.
result SNEFYs are fully tractable with closed form normalizing constants in many cases.
Sum-Product-Quotient Networks boost generative model power by incorporating conditional distributions.
problem Limited expressivity of Sum-Product Networks (SPNs).
method Integrates conditional distributions using quotient nodes and provides tractability conditions.
result Proves SPQNs can compute some distributions more efficiently than SPNs, reducing size requirements.
We consider the problem of transforming samples from one continuous source distribution into samples from another target distribution. We demonstrate with optimal transport theory that when the source distribution can be easily sampled from and the target distribution is log-concave, this can be tractably solved with c…
New algorithm for HOMFLY-PT polynomial reduces computation time.
problem Computing HOMFLY-PT polynomial is #P-hard.
method Fixed-parameter tractability in treewidth.
result HOMFLY-PT polynomial can be computed efficiently using sub-exponential time algorithm.
A new algorithm approximates optimal stopping problems with semi-tractable complexity.
problem Approximating the value of optimal stopping problems in discrete and continuous time.
method Weighted Stochastic Mesh (WSM) Algorithm for discrete and continuous time optimal stopping problems.
result WSM leads to semi-tractable complexity in discrete cases, with complexity bounded by ε − 4 log d + 2 ( 1 / ε ) \varepsilon^{-4}\log^{d+2}(1/\varepsilon) ε − 4 log d + 2 ( 1/ ε ) . Tensorial Mixture Models combine tractable structure with rich distribution representation.
problem Lack of tractable marginalization in generative models.
method Derived from tensor analysis, TMMs use simple convolutional networks and leverage theoretical analyses.
result Tensorial Mixture Models deliver state-of-the-art accuracies in classification tasks with missing data.
New algorithms for efficient inference and sampling in complex Ising models.
problem Efficiently computing partition functions and sampling configurations for complex Ising models.
method Equivalent linear transition to perfect matching counting and sampling on an expanded dual graph.
result Polynomial-time inference and sampling algorithms for K 33 K_{33} K 33 -free topologies. Fixed-parameter tractability of private synthetic data generation
problem Generating synthetic data under differential privacy
method Linear programming and subsampled private multiplicative weights method
result Optimal error rates across all regimes
Probabilistic models learned as density estimators can be exploited in representation learning beside being toolboxes used to answer inference queries only. However, how to extract useful representations highly depends on the particular model involved. We argue that tractable inference, i.e. inference that can be compu…
TRUST improves structure learning with tractable uncertainty.
problem Capturing uncertainty in structure learning for causal DAGs.
method Probabilistic circuits for posterior inference.
result Probabilistic circuits enhance structure learning quality and uncertainty.
Despite widespread interest and practical use, the theoretical properties of random forests are still not well understood. In this paper we contribute to this understanding in two ways. We present a new theoretically tractable variant of random regression forests and prove that our algorithm is consistent. We also prov…
Normalizing Flows model tractable distributions for efficient sampling and evaluation.
problem Creating efficient generative models for sampling and density evaluation.
method Construct and use Normalizing Flows to learn distributions.
result Comprehensive review of current Normalizing Flow methods and future directions.
Paper introduces md-vtrees for efficient probabilistic and causal inference.
problem Efficient inference in complex probabilistic models.
method Introduces md-vtrees to generalize tractability conditions for advanced inference queries.
result Derives first polytime algorithms for causal inference queries.
Normalizing flows can now estimate densities on unknown manifolds.
problem Normalizing flows struggle with data on unknown low-dimensional manifolds.
method Conformal Embedding Flows, which combine standard flows with trainable conformal embeddings.
result Tractable density estimation on manifold-supported data is possible.
Ensemble sampling extends Thompson sampling's applicability to complex models.
problem Limited applicability of Thompson sampling to complex models.
method Develops ensemble sampling to approximate Thompson sampling for complex models.
result Ensemble sampling expands the viability of Thompson sampling to more applications.
A new process generalizes geometric Brownian motion with asymmetry.
problem Creating a positive process with asymmetry parameter.
method Introducing asymmetry parameter α to describe volatility at new lows.
result Preserves GBM properties while expressing volatility as weighted mean.
New model generates data on constrained sets without losing tractability.
problem Generating data on constrained sets without losing tractability.
method Mirror Diffusion Models (MDM) learn diffusion processes in a dual space constructed from a mirror map.
result MDM generates data on convex constrained sets without losing tractability.
New bandit algorithm works without realizability assumption.
problem Contextual bandit problems without realizability assumption.
method Computes a constrained regression problem in every epoch, ensuring similar regret guarantees as realizability-based algorithms.
result Ensures similar regret guarantees as realizability-based algorithms, up to a misspecification term.
New method models Poisson intensity using RKHS for high-dimensional data.
problem Tractable nonparametric modeling of inhomogeneous Poisson intensity functions.
method Reproducing Kernel Hilbert Space (RKHS) formulation for intensity functions.
result Optimization of penalized likelihood can be cast as a tractable finite-dimensional problem.
New copulas model multiple risk factors with tractable properties.
problem Modeling stochastic dependence in multiple risk factors.
method Introduce and study a new class of MRF copulas.
result MRF copulas are non-exchangeable and exhibit various tail dependences.
Bayesian model captures spatial correlations in data.
problem Modeling spatial correlations in high-dimensional data.
method Structured Bayesian Gaussian process latent variable model with parameterized spatial kernel and structure-exploiting algebra.
result Inference is tractable with computational complexity similar to traditional Bayesian GP-LVM.
Develops a computationally tractable differentially private mean estimator called the balloon mean.
problem Robust mean estimation in the presence of outliers and heavy-tailed distributions.
method Iterative clipping procedure over Mahalanobis balls.
result Balloon mean is robust to outliers and outperforms existing estimators in contaminated settings.
Develops a computationally tractable high-dimensional differential privacy estimator.
problem Differential privacy in high dimensions is computationally intractable.
method Combines high-dimensional robust statistics with differential privacy techniques.
result A computationally tractable algorithm with dimension-independent privacy loss.
Two new methods for variational inference without tractable densities.
problem Challenges in variational inference due to computationally intractable probability density functions.
method Introduces wild variational inference methods that do not require tractable density functions.
result Significant improvement in stochastic gradient Langevin dynamics (SGLD) step size adjustment.
New algorithm speeds up knot polynomial calculations.
problem Computing Reshetikhin--Turaev knot polynomials efficiently.
method Fixed-parameter tractable computation via tensor networks.
result Knot polynomial computations are fixed-parameter tractable.
Inference in popular nonparametric Bayesian models typically relies on sampling or other approximations. This paper presents a general methodology for constructing novel tractable nonparametric Bayesian methods by applying the kernel trick to inference in a parametric Bayesian model. For example, Gaussian process regre…
Study shows tractable generalization in RL is impossible but possible with Strong Proximity.
problem RL agents struggle to generalize to new environments.
method Introduced Weak and Strong Proximity conditions to capture similarity between environments.
result Proved Strong Proximity is sufficient for efficient generalization.
We develop a model for the dynamic evolution of default-free and defaultable interest rates in a LIBOR framework. Utilizing the class of affine processes, this model produces positive LIBOR rates and spreads, while the dynamics are analytically tractable under defaultable forward measures. This leads to explicit formul…
TRAK traces model predictions to training data efficiently.
problem Inefficiency in data attribution methods for large-scale models.
method TRAK: a new data attribution method that is both effective and computationally tractable.
result TRAK matches the performance of methods requiring thousands of models with just a handful.
A central problem in machine learning involves modeling complex data-sets using highly flexible families of probability distributions in which learning, sampling, inference, and evaluation are still analytically or computationally tractable. Here, we develop an approach that simultaneously achieves both flexibility and…
Graph Structured Prediction Energy Networks model correlations for joint inference.
problem Joint inference over multiple variables with high-order correlations.
method Energy Networks for modeling explicit local and implicit higher-order correlations.
result Tractable inference with explicit modeling of correlations.
In this paper we present decomposable priors, a family of priors over structure and parameters of tree belief nets for which Bayesian learning with complete observations is tractable, in the sense that the posterior is also decomposable and can be completely determined analytically in polynomial time. This follows from…
Infinite-dimensional polynomial diffusions preserve tractability of finite-dimensional counterparts.
problem Modeling and analyzing infinite-dimensional probability measure-valued diffusions.
method Introduced polynomial diffusions, transferred properties from finite to infinite dimensions, and proved well-posedness of martingale problems.
result Tractability of finite-dimensional polynomial processes is preserved in the infinite-dimensional setting.
In this paper we develop a tractable structural model with analytical default probabilities depending on some dynamics parameters, and we show how to calibrate the model using a chosen number of Credit Default Swap (CDS) market quotes. We essentially show how to use structural models with a calibration capability that …
Researchers compare lower bounds and tractability in reinforcement learning.
problem Intractability of reinforcement learning with misspecified representations.
method Comparison of lower bounds and eluder dimension approach.
result Reconciliation of interpretations between different lines of work.
We develop computationally efficient Riemannian manifolds for graph embeddings.
problem Challenging to maintain computational tractability in non-Euclidean graph embeddings.
method Explore computationally efficient matrix manifolds for graph embeddings.
result Consistent improvements over Euclidean geometry and outperforming hyperbolic and elliptical embeddings.
We discuss the class of "Quadratic Normal Volatility" models, which have drawn much attention in the financial industry due to their analytic tractability and flexibility. We characterize these models as the ones that can be obtained from stopped Brownian motion by a simple transformation and a change of measure that o…
AST provides a method to validate safe autonomy without unsafe simplifications.
problem Validation of safe autonomy in complex systems.
method Adaptive Stress Testing (AST) approach.
result AST can find failures without unsafe simplifications.
This article discuss a class of tractable model in the form of polynomial type.
A new CIR# model preserves volatility and tractability for short-term interest rates.
problem Inadequacy of CIR model for negative short rates and skewed distributions.
method Developed CIR# model to fit term structure of short interest rates.
result Preserves volatility and analytical tractability of original CIR model.
New algorithm achieves optimal regret in average reward MDPs without prior bias information.
problem Achieving optimal regret in average reward MDPs with computational efficiency and without prior bias information.
method Projective Mitigated Extended Value Iteration (PMEVI) to compute bias-constrained optimal policies efficiently.
result First tractable algorithm with minimax optimal regret of O ~ ( s p ( h ∗ ) S A T ) \widetilde{\mathrm{O}}(\sqrt{\mathrm{sp}(h^*) S A T}) O ( sp ( h ∗ ) S A T ) . The analytical tractability of affine (short rate) models, such as the Vasicek and the Cox-Ingersoll-Ross models, has made them a popular choice for modelling the dynamics of interest rates. However, in order to account properly for the dynamics of real data, these models need to exhibit time-dependent or even stochast…
Paper tackles expected predictions computation for arbitrary generative models.
problem Hard to compute expected predictions for arbitrary generative models.
method Identifies tractable generative and discriminative models for expected predictions.
result Tractable computation of high-order moments and expectations for classification.
To enumerate 3-manifold triangulations with a given property, one typically begins with a set of potential face pairing graphs (also known as dual 1-skeletons), and then attempts to flesh each graph out into full triangulations using an exponential-time enumeration. However, asymptotically most graphs do not result in …