This paper presents a Bayesian optimization method with exponential convergence without the need of auxiliary optimization and without the delta-cover sampling. Most Bayesian optimization methods require auxiliary optimization: an additional non-convex global optimization problem, which can be time-consuming and hard t…
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,695 papers · 148 categories
Trend · papers per month
48 results for “Exponential Sample Requirement”
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcs.DS
Polynomial-time algorithm estimates mean with bounded covariance using differential privacy.
problem Estimating mean of a d-variate distribution with differential privacy constraints.
method Sum of Squares (SoS) exponential mechanism for polynomial-time differentially private estimation.
result First polynomial-time algorithm with samples for mean estimation under pure differential privacy.
Quantum algorithm speeds up learning from big data exponentially.
problem Scalable learning from big data with optimized random features.
method Quantum algorithm for sampling optimized random features.
result Exponential speedup in runtime compared to classical algorithms.
New offline RL study shows exponential sample requirement for accurate policy evaluation.
problem Understanding statistical limits of offline RL with linear function approximation.
method Analyzes necessary representational and distributional conditions for sample-efficient offline reinforcement learning.
result Even with realizability and good feature coverage, offline RL requires exponential samples for accurate policy evaluation.
Improved sample complexity for identifying best policies in risk-sensitive reinforcement learning.
problem Identifying approximately optimal policies in risk-sensitive reinforcement learning with exponential horizon dependence.
method Forward-model based algorithm with KL-based exploration bonuses adapted for entropic criterion, leveraging smoothness properties of exponential utility and a new stopping rule.
result Achieved sample complexity matching the lower bound, closing the gap between upper and lower bounds.
The Critical Horizon: Inspection Design Principles for Multi-Stage Operations and Deep Reasoningstat.ML
New insights into how to inspect and learn from multi-stage processes and AI reasoning.
problem Understanding how to attribute outcomes to early stages in multi-stage operations and AI reasoning.
method Information-theoretic analysis and mathematical proofs of four key results.
result Uniform checkpoint spacing is minimax-optimal for inspection design under homogeneous signal attenuation.
New study shows exponential sample growth for ReQU neural networks.
problem Computing neural network approximations from samples is challenging.
method Information-based complexity tools.
result Functions can be approximated by ReQU neural networks at arbitrary rates but require exponentially growing samples.
The paper addresses hypothesis selection with local differential privacy, requiring more samples than non-private methods.
problem Hypothesis selection under local differential privacy constraints.
method Develops algorithms for hypothesis selection with local differential privacy, achieving near-optimal sample and round complexities.
result Non-interactive algorithms for -wise simple hypothesis testing require samples and rounds of interaction.
Efficient method for learning continuous exponential families beyond Gaussian.
problem Learning continuous exponential families with unbounded support.
method Interaction Screening approach for scalable learning of continuous graphical models.
result Our estimator maintains similar accuracy and sample complexity scalings compared to alternative approaches, while improving run-time.
We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for RL with a generic model class and analyze their statistical properties. Our algorithms have sample …
Multi-sample, importance-weighted variational autoencoders (IWAE) give tighter bounds and more accurate uncertainty estimates than variational autoencoders (VAE) trained with a standard single-sample objective. However, IWAEs scale poorly: as the latent dimensionality grows, they require exponentially many samples to r…
SteinGen generates diverse graph samples from a single example.
problem Generating graphs with characteristic structures and diversity from a single example.
method Combines Stein's method and MCMC with Glauber dynamics and re-estimation of the Stein operator.
result High distributional similarity to the original data, combined with high sample diversity.
Learning ReLU networks to high uniform accuracy requires exponentially many samples.
problem Achieving high uniform accuracy on ReLU networks for security-critical applications.
method Quantified the number of training samples needed for any algorithm to guarantee uniform accuracy.
result The minimal number of training samples scales exponentially with network depth and input dimension.
Study shows exponential sample complexity for stabilizing certain linear systems.
problem Statistical hardness of learning to stabilize linear time-invariant systems.
method Analysis of sample complexity and co-stabilizability using robust control ideas.
result Sample complexity increases exponentially with system dimension.
New algorithm for efficiently identifying the best arm in stochastic bandits.
problem Best arm identification in stochastic multi-armed bandits with fixed confidence.
method Sequential probability ratio tests for arm selection.
result Asymptotically optimal sample complexity and guaranteed PAC performance.
New algorithm explores optimally using same primitives as Thompson Sampling.
problem Optimal exploration of unknown parameter vectors with noisy measurements.
method Algorithm leveraging sampling and argmax oracles.
result Achieves exponential convergence rate, optimal among all allocations.
Paper proposes SLINK clustering for nonparametric data sequences with improved consistency.
problem Nonparametric clustering of data sequences from unknown distributions.
method Exponentially consistent nonparametric SLINK clustering algorithm.
result SLINK clustering achieves exponential consistency under less strict conditions.
Parallelized Bayesian quadrature improves sample efficiency and inference.
problem Efficient Bayesian inference and model evidence calculation.
method Batch Bayesian quadrature with kernel recombination for parallel sampling.
result Empirically, outperforms state-of-the-art methods in various datasets.
A new method for exponentially weighted moving models using approximations.
problem Efficiently updating moving averages for time series data.
method Approximates EWMM using a fixed window and quadratic term, solving non-growing problems.
result Approximation produces estimates similar to exact EWMM.
New algorithm reduces feature count and accelerates error convergence.
problem Exponential error convergence in data classification with optimized random features.
method Optimized random features accelerated by quantum machine learning.
result Achieves exponential error convergence under low-noise condition.
Improved score-based models generate high-quality images up to 256x256.
problem Training score-based models for high-resolution images is unstable and limited.
method Theoretical analysis, exponential moving average of model weights.
result Score-based models can generate high-fidelity images up to 256x256.
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.
Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditsstat.ML
New Thompson sampling algorithm reduces regret for exponential family bandits.
problem Minimizing regret in multi-armed bandit problems with exponential family rewards.
method Proposes ExpTS and ExpTS algorithms using novel sampling distributions.
result Minimizes both finite-time and asymptotic regret for exponential family rewards.
This paper explores robust recovery of a superposition of distinct complex exponential functions from a few random Gaussian projections. We assume that the signal of interest is of dimensional and . This framework covers a large class of signals arising from real applications in biology, automation,…
This paper enhances privacy in statistical model checking of cyber-physical systems.
problem Privacy concerns in consumer-level applications due to statistical model checking.
method Proposes expected differential privacy and a new exponential mechanism for sequential algorithms.
result Demonstrates a novel mechanism to preserve privacy in statistical model checking.
NatPN provides fast, accurate uncertainty estimation for exponential family distributions.
problem Uncertainty in machine learning models.
method NatPN uses Normalizing Flows to fit a single density in a latent space, updating predictions based on likelihood.
result NatPN delivers competitive performance in classification, regression, and count prediction tasks.
In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active…
Paper proposes a method to improve MCMC sampling for energy-based models.
problem MCMC sampling of energy-based models is often not mixing in high-dimensional data.
method Proposes using a flow-based model as a backbone to correct the energy-based model, enabling mixing in latent space.
result MCMC sampling of the corrected EBM in the latent space mixes well and traverses modes in the data space.
A Tractable Pseudo-Metric on Non-Parametric Exponential Statistical Manifolds via SPD Geometrymath.ST
A tractable pseudo-metric for non-parametric distributions via SPD geometry.
problem Computing distances between non-parametric probability distributions is intractable.
method Two-stage framework: projection onto parametric family, embedding into SPD matrices.
result Closed-form pseudo-metric for two-sample hypothesis testing.
New algorithms achieve decision calibration without sample complexity dependent on feature dimension.
problem Achieving decision calibration for nonlinear loss functions with polynomial sample complexity.
method Developed smooth relaxation of decision calibration, enabling dimension-free algorithms.
result Efficient algorithms post-process predictors to satisfy decision calibration without worsening accuracy.
New algorithm for reward-free RL with linear function approximation, reducing sample complexity.
problem Efficiently learning optimal policies without prior reward information in complex environments.
method Developed an algorithm for reward-free RL in linear Markov decision processes, proving sample complexity bounds.
result Polynomial sample complexity in feature dimension and planning horizon, independent of states and actions.
Correspondence found between exponential families and affine Grassmannians.
problem Understanding the relationship between exponential families and geometric structures.
method Established a one-to-one correspondence between exponential families and affine Grassmannians.
result Found a correspondence between minimal exponential families and affine Grassmannians.
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.
The paper studies randomized approximations of Tukey's depth for log-concave isotropic data.
problem The challenge of approximating Tukey's depth in high dimensions.
method The study examines randomized algorithms for approximating Tukey's depth for log-concave isotropic data.
result Randomized algorithms correctly approximate maximal depth and close to zero depths but not intermediate depths.
New sampling method on Lie groups converges quickly.
problem Sampling on non-Euclidean Lie groups.
method Kinetic Langevin dynamics with noise added.
result Exponential convergence rate proved under distance.
We consider the problem of learning the underlying graph of an unknown Ising model on p spins from a collection of i.i.d. samples generated from the model. We suggest a new estimator that is computationally efficient and requires a number of samples that is near-optimal with respect to previously established informatio…
Efficient algorithms improve learning of large-margin halfspaces.
problem Learning large-margin halfspaces efficiently and reproducibly.
method Design of efficient, dimension-independent, polynomial-time algorithms; SGD-based approach; DP-to-Replicability reduction.
result Improved sample complexity compared to previous algorithms, with optimal sample complexity for one algorithm.
Flow Matching on Lie Groupsmath.DG
Generative model learns from simpler distributions on Lie groups.
problem Learning from complex Lie group data.
method Substituting exponential curves for line segments on Lie groups.
result Simple, intrinsic, and fast implementation for generative modelling.
Enhanced feedback model improves sample-efficiency in POMDPs.
problem Exponential hardness of learning in POMDPs.
method Multiple observations in hindsight feedback model.
result Sample-efficient learning possible for new subclasses of POMDPs.
Massively parallel RWS improves inference in complex models.
problem Exponential sample requirement for effective importance weighting.
method Draws samples of all latent variables and individually reasons through all combinations.
result Significant improvements over standard RWS.
This paper operationalizes the Exponential Mechanism using Normalizing Flows for private optimization.
problem Improving privacy in machine learning while maintaining accuracy and efficiency.
method Using Normalizing Flows to approximate sampling from the Exponential Mechanism for private optimization.
result ExpM+NF provides more privacy than non-private SGD but not as much as DPSGD.
The paper characterizes probability and entropy of exponentially growing sample spaces.
problem Characterizing probability and entropy of exponentially growing sample spaces.
method Analytical and applied to real-world data (US$ broad money supply).
result Information entropy is related to the rate of sample space expansion.
The study provides error bounds for the generalized Lasso with sub-exponential data.
problem Analyzing the generalized Lasso under sub-exponential data distributions.
method Non-asymptotic analysis using generic chaining-based proof strategy.
result Error bounds for the generalized Lasso can be controlled by two complexity parameters.
Moment polytope of toric exponential families is a projection of a simplex.
problem Understanding the geometry of exponential families in finite sample spaces.
method Toric torification and projection of higher-dimensional simplices.
result Moment polytope is a projection of a higher-dimensional simplex.
Paper defines ε-Safe Decision Regions for exponential family distributions and approximates them for unbalanced data.
problem Need probabilistic guarantees for reliable predictions in machine learning.
method Formalizes ε-Safe Decision Regions, proves their form for exponential family distributions, and develops Multi Cost SVM for unbalanced data.
result Formal definition and analytical determination of ε-Safe Decision Regions for exponential family distributions.
Though deep reinforcement learning has led to breakthroughs in many difficult domains, these successes have required an ever-increasing number of samples. As state-of-the-art reinforcement learning (RL) systems require an exponentially increasing number of samples, their development is restricted to a continually shrin…
New algorithm speeds up learning of graphical models.
problem Learning graphical models with sparse structure efficiently.
method Vertex-greedy score-based algorithm for learning DAGs.
result Polynomial runtime for learning DAG models.
This paper introduces ASCAI, a novel adaptive sampling methodology that can learn how to effectively compress Deep Neural Networks (DNNs) for accelerated inference on resource-constrained platforms. Modern DNN compression techniques comprise various hyperparameters that require per-layer customization to ensure high ac…