Algorithm samples from Bingham distribution efficiently.
problem Sampling from the Bingham distribution on a sphere.
method Rejection sampling with polynomial approximation.
result Exact samples from Bingham distribution in polynomial time.
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 “Polynomial Samples”
New bounds for learning polynomial surrogates with guarantees.
problem Learning polynomial surrogates for bounded binary functions with error guarantees.
method Characterized minimax sample complexity for two classes of polynomials under subgaussian noise.
result Sample complexity rates differ from noiseless case, scaling as for degree polynomials and for sparse polynomials.
SURF simplifies distribution estimation with simple, robust, and fast algorithms.
problem Efficient and accurate distribution estimation in statistics and machine learning.
method Piecewise polynomial approximation using empirical probability interpolation and divide-and-conquer merging.
result Surpassing state-of-the-art algorithms in efficiency and accuracy, SURF estimates distributions robustly and quickly.
Polynomial-time methods count and sample DAGs from equivalence classes.
problem Counting and sampling DAGs from Markov equivalence classes.
method Polynomial-time algorithms for DAGs.
result Counting and sampling can be done in polynomial time.
The study reveals the efficiency of sampling from tilted distributions.
problem Sampling from a tilted distribution of an unknown underlying distribution.
method Self-normalized importance sampling to characterize accuracy.
result Polynomial vs super-polynomial sample complexity for bounded vs unbounded distributions.
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradoxstat.ML
Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.
problem Finding optimal solutions in combinatorial semi-bandits with suboptimal sampling.
method Proposes Thompson Sampling with polynomial regret for linear combinatorial semi-bandits.
result Demonstrates 'mismatched sampling paradox' where knowing distributions can lead to worse performance.
Paper analyzes sample complexity of polynomial neural networks.
problem Understanding the sample complexity of polynomial neural networks.
method Extends previous literature to polynomial neural networks and analyzes sample complexity.
result Obtains novel results on sample complexity of polynomial neural networks.
New bounds for score matching in polynomial exponential families.
problem Understanding the sample complexity of score matching for polynomial exponential families.
method Non-asymptotic sample complexity analysis for score matching.
result First finite sample bounds for score matching in polynomial exponential families.
Polynomial-time DP algorithm for learning Gaussians with matching sample complexity.
problem Learning Gaussian distributions while maintaining privacy.
method General framework for reducing DP estimation to non-private, polynomial-time algorithm for Gaussian learning.
result Matching sample complexity to information-theoretic upper bound for Gaussian learning.
Efficiently samples arbitrary compact bodies with polynomial complexity.
problem Uniform sampling from arbitrary compact bodies efficiently.
method Warm start algorithm under isoperimetry and volume growth condition.
result Substantial generalization of known results for convex and star-shaped bodies.
Polynomial-time methods count and sample DAGs from Markov classes.
problem Counting and sampling Markov equivalent DAGs.
method Polynomial-time algorithms for DAGs from Markov classes.
result Long-standing open problem solved, making practical infeasible strategies feasible.
We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a polynomial-time algorithm for standard ICA with sample complexity nearly linear in the dimension, thereby improving substantially on previous b…
Three-layer neural networks learn hierarchical polynomial functions efficiently.
problem Learning hierarchical polynomial functions with three-layer neural networks.
method Layerwise gradient descent on square loss, focusing on feature learning.
result Achieves optimal sample complexity for learning hierarchical polynomials.
We study dual volume sampling, a method for selecting k columns from an n x m short and wide matrix (n <= k <= m) such that the probability of selection is proportional to the volume spanned by the rows of the induced submatrix. This method was proposed by Avron and Boutsidis (2013), who showed it to be a promising met…
Robustly estimates multivariate polynomials in noisy data.
problem Estimating multivariate polynomials in noisy data with outliers.
method Generalizes robust multivariate polynomial regression to n-variate setting.
result Achieves optimal sample complexity and approximation error.
We study computational and sample complexity of parameter and structure learning in graphical models. Our main result shows that the class of factor graphs with bounded factor size and bounded connectivity can be learned in polynomial time and polynomial number of samples, assuming that the data is generated by a netwo…
The paper analyzes tensor recovery from symmetric rank-one measurements using information theory.
problem Recovering tensors with low symmetric rank from symmetric rank-one measurements.
method Covering numbers argument, Carbery-Wright inequality, orthogonal polynomials, Fano's inequality.
result Near-optimal sample complexity bounds for log-concave distributions.
New framework allows reinforcement learning with polynomial sample complexity.
problem Generalization in reinforcement learning with function approximation.
method Introduces Bilinear Classes, a structural framework for RL.
result Polynomial sample complexity for Bilinear Classes, matching best known bounds.
We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in polynomial time. The notion of tractability extends the basic case of planar zero-field Ising models…
New method uses higher-order Langevin dynamics for efficient parallel sampling.
problem Efficient parallel sampling from high-dimensional log-concave distributions.
method Combines higher-order Langevin dynamics with blockwise Lagrange polynomial interpolation.
result Reduces the number of parallel points required for a target accuracy.
Algorithm learns polynomials in Gaussian inputs with reduced sample complexity.
problem Learning polynomials of few relevant dimensions in high-dimensional data.
method Filtered PCA for warm start, geodesic SGD for accuracy.
result Sample complexity roughly , runtime .
Polynomial convergence proved for SGM, improving over previous methods.
problem Learning probability distributions from data and generating samples efficiently.
method Proved polynomial convergence for SGM using accurate score estimates.
result First polynomial convergence guarantees for SGM, independent of dimensionality.
We study the Gibbs sampling algorithm for continuous determinantal point processes. We show that, given a warm start, the Gibbs sampler generates a random sample from a continuous -DPP defined on a -dimensional domain by only taking number of steps. As an application, we design an algorithm to ge…
We consider the problem of low canonical polyadic (CP) rank tensor completion. A completion is a tensor whose entries agree with the observed entries and its rank matches the given CP rank. We analyze the manifold structure corresponding to the tensors with the given rank and define a set of polynomials based on the sa…
Abstract reviews algorithms for multi-index models, focusing on polynomial-time methods and their limitations.
problem Estimating the index space in multi-index models efficiently and accurately.
method Polynomial-time algorithms in Gaussian space, nonparametric gradient estimation, and neural network fitting.
result A gap exists between computationally efficient methods and information-theoretical minimum.
Polynomial-time algorithm learns causal graphs without parametric assumptions.
problem Learning causal graphs from data without assuming linearity or parametric forms.
method Model-free polynomial-time algorithm with finite-sample guarantees.
result Algorithm achieves linear cost in dimension and samples compared to optimal.
The paper tackles uniform sampling from neural networks efficiently.
problem Uniform sampling from neural network labelings given a sample.
method Polynomial-time algorithm for general neural networks, random walk for single neuron.
result Uniform sampling with high probability for general neural networks, exact uniform sampling for single neuron.
Optimizes algorithms for non-concave bandit problems.
problem Optimizing algorithms for non-concave bandit problems.
method Unified zeroth-order optimization paradigm.
result Minimax-optimal algorithms in the dimension for low-rank generalized linear bandit problems.
Paper reduces sample complexity for bilinear systems identification to nearly constant.
problem Identifying discrete-time bilinear systems under bounded disturbances.
method Uses trajectory-dependent regressors and polynomial mean-square state growth analysis.
result Proves sample complexity of for estimation error .
Efficient algorithm for sampling from arbitrary compact bodies.
problem Sampling from arbitrary compact bodies efficiently.
method Warm start algorithm with polynomial complexity.
result Substantial generalization of known results for convex and star-shaped bodies.
Tensor PCA problem analyzed with statistical query lower bounds.
problem Estimating the expected value of a rank-1 tensor from Gaussian samples.
method Sharp analysis of optimal sample complexity in the Statistical Query model.
result SQ algorithms with polynomial query complexity fail in the conjectured hard phase and have sub-optimal sample complexity.
Study analyzes learnability of RKHS under L∞ norm for kernel methods.
problem Understand performance of kernel methods and random feature models.
method Relate L∞ learnability to kernel spectrum decay and establish sample complexity bounds.
result Conditions for efficient L∞ learning of RKHS identified.
Polynomial-time algorithm for near-optimal community detection in graphs.
problem Node-private community estimation in stochastic block models.
method Explicit Lipschitz surrogate and accept-reject algorithm for sampling community labels.
result Achieves minimax rates for exact recovery with polynomial-time runtime and logarithmic privacy parameter.
New algorithm learns halfspaces with noise using Forster decomposition.
problem Learning halfspaces in noisy data.
method Forster decomposition and efficient mixture of distributions.
result First polynomial-time algorithm with strongly polynomial sample complexity.
The colored Jones polynomial is a series of one variable Laurent polynomials J(K,n) associated with a knot K in 3-space. We will show that for an alternating knot K the absolute values of the first and the last three leading coefficients of J(K,n) are independent of n when n is sufficiently large. Computation of sample…
Algorithm distinguishes Gaussian mixtures from pure Gaussians in quasi-polynomial time.
problem Distinguishing mixtures of Gaussian components from pure Gaussians, especially when components are well-separated.
method Sum-of-Squares method, quasi-polynomial time algorithm, bipartitioning sample to separate components.
result Algorithm can reliably distinguish between mixtures and pure Gaussians in quasi-polynomial time.
FNOs learn solution operators of dissipative equations efficiently via spectral methods.
problem Learning and approximation of solution operators for dissipative equations.
method Introducing spectral methods and deriving FNO approximation bounds and sample complexity guarantees.
result Polynomial sample complexity guarantees for FNOs learning solution operators of dissipative equations.
Polynomial-time algorithm for clustering mixtures with separation Δ=Ω(√(log k)).
problem Clustering mixtures of mean-separated Gaussians in high dimensions.
method Polynomial-time algorithm using implicit moment estimation.
result Achieves almost optimal clustering guarantee with separation Δ=Ω(√(log k)).
Neural networks can memorize and learn complex functions with minimal parameters.
problem Learning and memorizing complex functions with neural networks using minimal parameters.
method SGD on depth two neural networks with near optimal network size and parameters.
result SGD on depth two network can memorize and learn polynomials with bounded weights and certain kernel spaces.
A new method for assessing Bayesian sampling quality, PSD, is proposed and shown to be more powerful and efficient.
problem Scalability and convergence assessment of Bayesian sampling algorithms, especially for high-dimensional problems.
method Polynomial Stein Discrepancy (PSD) for measuring discrepancy between samples and posterior distributions.
result PSD detects differences in the first r moments for Gaussian targets and is more powerful and efficient than competitors.
Invariant polynomials improve machine learning performance.
problem Improving machine learning algorithms using invariant polynomials.
method Developed and implemented Lorentz- and permutation-invariant polynomial generators in neural networks.
result Reduction in loss on training and validation data with Hironaka decompositions.
Polynomial-time algorithm for list-decodable linear regression with batches.
problem Efficiently decoding linear regression with a fraction of adversarial data.
method Polynomial time algorithm using batches of i.i.d. samples.
result Returns a list of size O(1/α^2) with one item close to true parameter.
Efficiently learns polytrees with known skeleton in polynomial time and sample complexity.
problem Learning polytrees with known skeleton structure.
method Proposes an efficient algorithm for learning -polytrees in polynomial time and sample complexity when the skeleton is known.
result Establishes finite-sample guarantees for efficient learning of -polytrees.
We study proper losses for discrete generative models without knowing the target distribution.
problem Evaluating generative models in the discrete setting without direct access to the target distribution.
method Define and construct black-box proper losses using statistical estimation theory.
result Black-box proper losses must be of polynomial form and involve more samples than the polynomial degree.
New algorithm samples from Ising models efficiently, even with outliers.
problem Sampling from Ising models with general interaction matrices.
method Combines MCMC and variational inference techniques.
result First polynomial time sampling algorithms for low-rank Ising models.
New knot polynomials derived from Nichols algebras and braided Hopf algebras.
problem Developing new knot invariants from algebraic structures.
method Constructing knot invariants from solutions to the Yang--Baxter equation over generalized Yetter--Drinfel'd modules.
result Reproduces known knot polynomials and discovers new multivariable invariants.
Improves RLHF sample efficiency by scaling reward complexity polynomially.
problem Exponential sample complexity in RLHF algorithms for skewed preferences.
method SE-POPO, an online RLHF algorithm that achieves polynomial sample complexity.
result SE-POPO outperforms existing algorithms in sample efficiency.
New findings on depth vs. width in neural networks, showing depth can improve learnability.
problem Understanding the role of depth in neural networks, especially when width is unbounded.
method Analyzing sample complexity for learnability in norm-controlled depth-2 and depth-3 ReLU networks.
result Depth can improve learnability of functions that are otherwise unlearnable with depth-2 networks.