Paper analyzes Nyström regularization for time series forecasting with sequential sub-sampling.
problem Learning rate analysis of Nyström regularization for τ-mixing time series. method Banach-valued Bernstein inequality and integral operator approach for τ-mixing sequences. result Almost optimal learning rates for Nyström regularization with sequential sub-sampling.
This study improves audit sampling by using sequential procedures with statistical guarantees.
problem Improving audit efficiency and reliability with statistical methods.
method Formulated as a sequential testing problem, defining null and alternative hypotheses, stopping and decision rules, and exact boundary conditions.
result Exact design yields ex ante control of decision error probabilities, and simulation-based implementation approximates this design.
New private algorithm for sequential hypothesis testing with privacy and error rate guarantees.
problem Privacy protection in sequential hypothesis testing for sensitive data.
method Renyi differential privacy, Wald's Sequential Probability Ratio Test (SPRT).
result Private algorithm with strong privacy guarantees and theoretical performance analysis.
Proposes LDIDPs for efficient sequential data generation from latent dynamical models.
problem Challenges in generating high-fidelity sequential samples from latent dynamical models.
method Utilizes implicit diffusion processes to sample from latent dynamical processes.
result Demonstrates accurate learning of dynamics and efficient generation of high-quality sequential data.
We consider the problem of inferring a latent function in a probabilistic model of data. When dependencies of the latent function are specified by a Gaussian process and the data likelihood is complex, efficient computation often involve Markov chain Monte Carlo sampling with limited applicability to large data sets. W…
A sequential classifier minimizes test samples for binary and multi-class classification.
problem Minimizing test samples for sequential classification with unknown distributions.
method Proposes a classifier for binary and multi-class problems, analyzing error probabilities and extending results.
result Significant advantage over non-sequential classifiers, achieving same exponents without rejection option.
Study optimizes sampling to avoid extreme tail risks in unknown heavy-tailed distributions.
problem Identify optimal alternative with minimal extreme tail risk from unknown heavy-tailed distributions.
method Data-driven sequential sampling policies to maximize likelihood of selecting the optimal alternative.
result Proposed methods outperform existing approaches in identifying the optimal alternative.
SPRT-TANDEM improves sequential classification accuracy with fewer samples.
problem Efficiently classifying sequential data with high accuracy and low sampling cost.
method Deep neural network-based SPRT algorithm that estimates log-likelihood ratio of two hypotheses.
result SPRT-TANDEM achieves statistically significantly better classification accuracy than other classifiers with fewer samples.
We present a novel framework for kernel learning with sequential data of any kind, such as time series, sequences of graphs, or strings. Our approach is based on signature features which can be seen as an ordered variant of sample (cross-)moments; it allows to obtain a "sequentialized" version of any static kernel. The…
Recently, it has been shown how sampling actions from the predictive distribution over the optimal action-sometimes called Thompson sampling-can be applied to solve sequential adaptive control problems, when the optimal policy is known for each possible environment. The predictive distribution can then be constructed b…
Sequential tests for two-sample and independence testing using betting strategies.
problem Testing sequential data for two-sample and independence without kernel selection issues.
method Prediction-based betting strategies that adaptively determine distribution and joint distribution.
result Prediction-based tests outperform kernel-based approaches in high-dimensional or structured data settings.
Optimal unimodal fitting for linear loss functions in a sequential, efficient manner.
problem Optimal unimodal transformation of univariate model scores under linear loss functions.
method Proposes a sequential approach to estimate the optimal rectangular fit for observed samples with each new sample.
result Sequential approach achieves optimal efficiency with logarithmic time complexity per iteration.
Efficiently selects top-m designs for various contexts using sequential sampling.
problem Optimizing selection of top-m designs across different contexts.
method Formulated as a stochastic dynamic programming problem, developed sequential sampling policy.
result Asymptotically optimal sampling ratios for efficient selection.
Algorithm optimizes quantized isotonic regression with log-linear time updates.
problem Optimizing quantized isotonic regression estimations.
method Modified PAVA algorithm for sequential optimization.
result Log-linear time updates for optimal quantized mapping.
Paper proposes a new method for sampling from complex distributions.
problem Sampling from unnormalised density functions in complex distributions.
method Combines amortised and particle-based methods with reinforcement learning.
result Improves sampling from complex distributions compared to existing methods.
Self-balancing sampler improves sampling efficiency and unpredictability.
problem Efficient and unpredictable sampling in various applications.
method Adaptive biasing of sampling probabilities to achieve faster convergence and unpredictability.
result Self-balancing sampler converges at O(n−1) rate, outperforming IID sampling. Algorithm improves multi-armed bandit performance by transferring reward samples.
problem Sequential multi-armed bandit problem with changing reward distributions.
method UCB algorithm with reward sample transfer.
result Significant improvement in cumulative regret over standard UCB.
New batched Langevin Thompson Sampling reduces communication costs for sequential decision making.
problem Efficiently learning unknown reward distributions and transition dynamics in batched settings.
method Langevin Thompson Sampling with logarithmic communication costs.
result Order-optimal regret guarantees for stochastic MABs and RL.
Estimating the largest community in a mixed population via sequential sampling.
problem Identifying the largest community in a mixed population with limited sampling.
method Sequential, random sampling of individuals across multiple boxes, optimizing sampling strategy and decision rule.
result Proposed algorithms achieve optimal error probability decay rates under fixed budget constraints.
Transforms any test into anytime-valid with sample savings.
problem Sequential data invalidates classical test guarantees.
method Predicts test outcomes to create anytime-valid stopping rules.
result Ensures Type-I error control and near-optimal power.
We develop a new method to estimate failure probabilities in complex systems.
problem Estimating failure probabilities in safety-critical autonomous systems is challenging due to the rarity of failures and large state spaces.
method We propose an adaptive importance sampling algorithm that minimizes forward Kullback-Leibler divergence and uses Markov score ascent methods.
result Our method provides more accurate failure probability estimates than existing techniques.
PDTS improves robustness in sequential decision-making.
problem Robust active task sampling for efficient and reliable decision-making.
method Characterizes robust active task sampling as a Markov decision process, proposes PDTS method.
result Significantly improves zero-shot and few-shot adaptation robustness.
Improved diffusion models using energy distillation and sequential Monte Carlo.
problem Training instability and inferior performance in energy parameterized diffusion models.
method Introduced a novel training regime for energy functions through distillation of pre-trained diffusion models, and cast the sampling procedure as a Feynman Kac model.
result Demonstrated improved performance and new sampling techniques.
New SMC sampler improves diffusion model sampling efficiency.
problem Sampling generative diffusion models efficiently.
method Constructs correlated observation paths and designs a sampler.
result Improved statistical efficiency, especially under outlier conditions.
New algorithms estimate and test collision probability with near-optimal sample complexity.
problem Estimating and testing collision probability in discrete distributions.
method Developed algorithms for (α,β)-local differential privacy and sequential testing. result Achieved nearly optimal sample complexity for estimating and testing collision probability.
EviTrack improves sequential prediction in delayed disambiguation scenarios.
problem Challenges in sequential prediction with delayed disambiguation where early observations are ambiguous.
method EviTrack operates over latent trajectories, applying evidence- and likelihood-ratio-based selection to delay commitment until supported by data.
result EviTrack outperforms sampling-based baselines in a controlled synthetic benchmark, achieving faster post-disambiguation recovery.
A key limitation of sampling algorithms for approximate inference is that it is difficult to quantify their approximation error. Widely used sampling schemes, such as sequential importance sampling with resampling and Metropolis-Hastings, produce output samples drawn from a distribution that may be far from the target …
Sequential hypothesis testing is a desirable decision making strategy in any time sensitive scenario. Compared with fixed sample-size testing, sequential testing is capable of achieving identical probability of error requirements using less samples in average. For a binary detection problem, it is well known that for k…
Boosts change-point detection power with optimal sub-sampling.
problem Power loss in sequential change-point detection from large history data.
method Optimal sub-sampling of history data before kernel-based detection procedures.
result Improved detection performance in extensive experiments.
Parallelizes active learning for Bayesian inference using Nested Sampler.
problem Expensive likelihood evaluations in complex experiments.
method Uses Nested Sampler to generate nearly-optimal batches of candidates in parallel.
result Comparable accuracy to sequential conditioning with efficient parallelization.
VISA improves inference efficiency for complex models.
problem Efficient approximate inference in computationally intensive models.
method Sequential sample-average approximations within a trust region.
result VISA achieves comparable accuracy with computational savings.
Combines SMC and diffusion-based samplers for improved sampling performance.
problem Sampling from unnormalized densities efficiently and robustly.
method Viewing SMC and diffusion-based samplers as continuous-time processes, SCLD combines their strengths.
result SCLD achieves improved performance on multiple benchmark problems with less training budget.
New bounds for SMC show its advantage over MCMC in multimodal distributions.
problem Estimating expectations under multimodal distributions with slow global mixing.
method Proves finite sample complexities for SMC with local mixing times, addressing bias through sequential resampling.
result SMC provides fully polynomial time approximation for multimodal problems.
Thompson Sampling tackles USS, a sequential selection problem without feedback.
problem Unsupervised Sequential Selection (USS) problem with fixed costs and ordered arms.
method Thompson Sampling algorithm for USS problem.
result Thompson Sampling achieves near optimal regret and better performance than existing algorithms.
Efficiently samples sequences without replacement for machine learning models.
problem Generating diverse outputs from sequential models without duplicates.
method Incremental sampling procedure for randomized programs, including neural models.
result Efficacy and flexibility of incremental sampling for large output spaces.
Optimal tests developed for sequential experiments with asymptotic properties.
problem Performing hypothesis tests after sequential experiments without prior design.
method Analyze asymptotic properties of sequential experiments; develop tests for Gaussian process observations.
result Asymptotic power function of any test can be matched by a specific test in a limit experiment.
DAIS improves AIS by resampling, avoiding gradient issues.
problem Low effective sample size in DAIS.
method DAIS with resampling step to improve efficiency.
result Resampling step avoids gradient variance issues.
New algorithms for fast online decision making using neural networks and martingale posteriors.
problem Online sequential decision making under uncertainty.
method Martingale posterior neural networks for fast online learning and decision making.
result Achieves competitive performance-speed trade-offs in non-stationary contextual bandits and Bayesian optimization.
Novel method for nonlinear data assimilation using Langevin sampling.
problem Nonlinear data assimilation challenges in Bayesian filtering.
method Score-based sequential Langevin sampling (SSLS) with dynamic models and annealing.
result Asymptotic stability and error bounds for local posterior sampling.
A universal framework for constructing confidence sets using sequential likelihood mixing.
problem Constructing reliable confidence sets for realizable likelihood functions.
method Sequential likelihood mixing, integrating Bayesian inference and regret inequalities.
result Establishes fundamental connections and provable coverage guarantees for various inference techniques.
A new MDP with Bandits approach for sequential decision making in linear-flow scenarios.
problem Sequential decision making with limited feedback in a linear-flow context.
method Formulated as an MDP with Bandits, using Thompson sampling for action selection and exact dynamic programming for allocation.
result The proposed MDP with Bandits algorithm outperforms other methods in sequential decision making.
The paper tackles sequential mode estimation with oracle queries.
problem Adaptively PAC-learning a probability distribution's mode.
method Two query models: index queries and pair queries. Sequential algorithms for mode estimation.
result Lower bounds on optimal query complexity for both models.
For a finite function class we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a G-heat equation. In the language of Peng's sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional $…
We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from com…
We consider the problem of sequential sampling from a finite number of independent statistical populations to maximize the expected infinite horizon average outcome per period, under a constraint that the expected average sampling cost does not exceed an upper bound. The outcome distributions are not known. We construc…
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.
OMLE combines optimism and MLE for efficient sequential decision making.
problem Efficiently solving sequential decision making problems, especially in partially observable settings.
method Combines optimism for exploration and maximum likelihood estimation for model learning.
result OMLE learns near-optimal policies for a wide range of sequential decision making problems.
Paper formalizes a reinforcement learning model for complex information structures.
problem Complex interdependence in sequential decision-making problems.
method Formalizes a novel reinforcement learning model with explicit information structure representation.
result Upper bound on sample complexity of learning general sequential decision-making problems.