Study on optimal rates for sequential probability assignment using smoothed analysis.
problem Optimal rates for sequential probability assignment under smoothed adversaries.
method General-purpose reduction from minimax rates to transductive learning, development of an efficient algorithm using MLE oracle.
result Optimal (logarithmic) fast rates for parametric and finite VC dimension classes, sublinear regret for general classes.
Study minimax regret in sequential probability assignment with and without side information.
problem Minimax regret analysis in sequential probability assignment.
method Upper and lower bounds on minimax regret using square-root entropy.
result Lower bound matches upper bound for Donsker classes, up to log factors.
We develop a probabilistic framework for sequential random projection.
problem Challenges of sequential decision-making under uncertainty.
method Novel construction of a stopped process and method of mixtures.
result Achieved a non-asymptotic probability bound for random projection.
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.
New insights on active sequential prediction for mean estimation.
problem Active sequential prediction-powered mean estimation problem.
method Combining uncertainty-based suggestion with a constant probability, analyzing non-asymptotic bounds, and using no-regret learning.
result The optimal query probability is close to the constraint when using no-regret learning.
New bounds on minimax regret for sequential probability assignment using logarithmic loss.
problem Minimizing regret in sequential probability assignment against arbitrary experts.
method Using self-concordance property of logarithmic loss to derive tight bounds.
result Tight bounds on minimax regret for various expert classes.
New method for sequential probability assignment reduces regret using contextual Shtarkov sums.
problem Minimizing regret in sequential probability assignment with arbitrary hypothesis classes.
method Introducing contextual Shtarkov sum and contextual Normalized Maximum Likelihood (cNML) algorithm.
result The contextual Shtarkov sum characterizes minimax regret and provides a minimax optimal strategy.
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.
We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of experts. We provide upper and lower bounds for minimax regret in terms of sequential complexities of the …
Method solves complex optimization problems with high probability bounds.
problem Nonlinear equality constrained stochastic optimization problems.
method Step-search sequential quadratic programming method.
result High-probability bound on iteration complexity for first-order stationarity.
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.
DP-SPRT improves privacy in sequential tests with near-optimal error rates.
problem Privacy constraints in sequential probability ratio tests.
method A wrapper for SPRT that uses a private mechanism to determine when to stop based on predefined intervals.
result DP-SPRT achieves near-optimal error rates and privacy guarantees.
In many applications, accurate class probability estimates are required, but many types of models produce poor quality probability estimates despite achieving acceptable classification accuracy. Even though probability calibration has been a hot topic of research in recent times, the majority of this has investigated n…
The paper proposes an efficient method for estimating ATEs using adaptive experiments.
problem Estimating average treatment effects (ATEs) with minimal sample size and high accuracy.
method The paper defines and uses the efficient treatment-assignment probability to sequentially assign treatments, estimating ATEs using an Adaptive Augmented Inverse Probability Weighting (A2IPW) estimator.
result The proposed experimental design and A2IPW estimator achieve the minimized semiparametric efficiency bound and provide anytime valid confidence intervals for early stopping.
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.
A computer code can simulate a system's propagation of variation from random inputs to output measures of quality. Our aim here is to estimate a critical output tail probability or quantile without a large Monte Carlo experiment. Instead, we build a statistical surrogate for the input-output relationship with a modest …
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.
We propose a nonparametric sequential test that aims to address two practical problems pertinent to online randomized experiments: (i) how to do a hypothesis test for complex metrics; (ii) how to prevent type 1 error inflation under continuous monitoring. The proposed test does not require knowledge of the underlying…
The paper addresses estimating long-term treatment effects with monotone missing data.
problem Estimating long-term treatment effects with missing data, especially monotone missing.
method The paper introduces the sequential missingness assumption for identification and proposes three novel estimation methods: inverse probability weighting, sequential regression imputation, and SeqMSM. It also introduces a balancing-enhanced approach, BalanceNet, to improve estimation accuracy.
result The proposed methods, including BalanceNet, effectively estimate long-term treatment effects with monotone missing data.
Randomized SINDy learns dynamic data structures using probabilistic methods.
problem Learning time-dependent data structures in dynamic systems.
method Sequential machine learning with a probabilistic approach, incorporating feature augmentation and Tikhonov regularization.
result Demonstrated effectiveness in regression and binary classification using real-world data.
New method uses Fokker-Planck equation for sampling and inference.
problem Intractability of evaluating probability density in practical applications.
method Reformulates Fokker-Planck equation as a particle flow method, using velocity field.
result Turns intractable density evaluation into an advantage for variational inference, kernel mean embeddings, and sequential Monte Carlo.
Bayesian method for estimating inputs leading to specific probability outputs.
problem Estimating inputs for specific probability outputs of uncertain functions.
method Bayesian strategy using Gaussian process modeling and SUR principle.
result Surpassed performance of existing methods through numerical experiments.
New algorithms minimize MMD to approximate probability measures efficiently.
problem Approximating probability measures by representative point sets.
method Sequential greedy minimization of maximum mean discrepancy (MMD) over candidate sets, with mini-batch variants.
result Consistency of proposed algorithms and mini-batch variants established.
Study on information cascade fragility under mismatched revealing probabilities.
problem Analyzing the fragility of information cascades in decision-making processes with imperfect knowledge of revealing probabilities.
method Examined sequential decision-making models with players having private information and imitating previous decisions. Studied the effect of a mismatch between players' beliefs and actual revealing probabilities.
result Derived closed-form expressions for optimal learning rates and identified phase transitions in the behavior of asymptotic learning rates.
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.
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.
The paper proposes a new method to approximate Wasserstein-Fisher-Rao flows using Monte Carlo techniques.
problem Sampling from probability distributions and minimizing Kullback-Leibler divergence.
method Sequential Monte Carlo approximations of Wasserstein-Fisher-Rao gradient flows.
result The proposed method outperforms other Monte Carlo algorithms in certain conditions.
First, we consider the problem of hedging in complete binomial models. Using the discrete-time Föllmer-Schweizer decomposition, we demonstrate the equivalence of the backward induction and sequential regression approaches. Second, in incomplete trinomial models, we examine the extension of the sequential regression app…
The book explores universal time-series forecasting using mixture predictors.
problem Sequential probability forecasting in a general setting.
method Mixture predictors combining multiple predictors.
result Universality of mixture predictors in a general probabilistic setting.
This paper addresses missing covariates in stochastic linear bandits, providing a high-probability regret bound.
problem Effect of missing covariates on regret in stochastic linear bandit algorithms.
method Proposes an algorithm that provides a high-probability upper bound on regret in terms of covariate sampling probabilities.
result Regret degrades due to missingness by at most ζmin2, where ζmin is the minimum probability of observing covariates. 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. We build on auto-encoding sequential Monte Carlo (AESMC): a method for model and proposal learning based on maximizing the lower bound to the log marginal likelihood in a broad family of structured probabilistic models. Our approach relies on the efficiency of sequential Monte Carlo (SMC) for performing inference in st…
Algorithm identifies nearest mode in noisy data.
problem Identifying the point with the minimum k-th nearest neighbor distance in unknown multivariate probability density.
method Sequential learning algorithm using noisy oracle queries to adaptively decide which points to query.
result Upper bounds on query complexity show significant improvement over baselines.
CRPS improves GP-based sequential design for chemical space.
problem Finding molecules with specific properties in synthetic chemistry.
method Threshold-weighted CRPS as acquisition function for GP models in sequential design.
result Improved performance in molecule research with CRPS-based strategies.
Maximal Rate of Stepwise Uncertainty Reduction selects simulations to reduce uncertainty efficiently.
problem Efficiently estimating quantities of interest from multi-fidelity simulations.
method Bayesian sequential strategy that maximizes the ratio of expected uncertainty reduction to simulation cost.
result MR-SUR strategy unifies and provides principled approaches to develop new methods.
A new method estimates rare failure events in complex systems.
problem Estimating the probability of rare failure events in non-linear systems.
method Stochastic Spectral Embedding (SSE) combined with modifications for efficient rare event estimation.
result Rare failure probability decomposed into conditional probabilities for easier computation.
Study designs for estimating treatment effects in adaptive experiments.
problem Estimating treatment effects under adaptive treatment assignment.
method Propose and analyze IPW and AIPW estimators, establish CLTs under design stability.
result Central limit theorems for IPW and AIPW estimators under design stability.
This study proposes an efficient surrogate for Darcy flow inverse problems.
problem Efficiently constructing accurate surrogate models for high-dimensional complex inverse problems.
method Sequential Bayesian design strategy to acquire a locally accurate surrogate model focusing on high-probability regions.
result The proposed method accelerates inversion accuracy and computational speed.
Proposes SNML for selecting word2vec Skip-gram dimensionality.
problem Selecting optimal dimensionality for word2vec Skip-gram models.
method Information criteria (AIC, BIC, SNML) applied to SG and SG Negative Sampling models.
result SNML outperforms AIC and BIC, selecting closer optimal dimensionality.
We propose a new framework for how to use sequential Monte Carlo (SMC) algorithms for inference in probabilistic graphical models (PGM). Via a sequential decomposition of the PGM we find a sequence of auxiliary distributions defined on a monotonically increasing sequence of probability spaces. By targeting these auxili…
VCSMC improves efficiency in Bayesian phylogenetic inference.
problem Inefficient exploration of phylogenetic state space.
method Variational Combinatorial Sequential Monte Carlo (VCSMC) and nested CSMC.
result VCSMC and VNCSMC explore higher probability spaces efficiently.
Safe actions learned in finite trials, without infinite exploration.
problem Learning safe actions in unknown environments efficiently.
method Defining a handicap metric and using sequential probability ratio test for discarding unsafe actions.
result Achieves constant handicap, discarding unsafe machines with probability one in finite rounds.
Paper develops a TR-SSQP method for noisy optimization with heavy-tailed noise.
problem Optimization problems with stochastic objectives and heavy-tailed noise.
method Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method.
result Achieves high-probability first-order and second-order stationarity bounds for heavy-tailed noise.
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.
An algorithm finds the most probable best solution in uncertain parameter settings.
problem Finding the most probable best solution in uncertain parameter settings.
method Designing an efficient sequential sampling algorithm to learn the most probable best (MPB) and optimizing the computing budget allocation.
result The algorithms achieve the optimal sampling ratios as the simulation budget increases and significantly improve empirical performance.
The paper develops a method to learn cost-optimal sequential testing policies from retrospective data.
problem Learning cost-optimal sequential decision policies from retrospective data with missing test results.
method Doubly robust Q-learning framework with path-specific inverse probability weights.
result The method reduces testing cost without compromising predictive accuracy.
Unified technique for sequential estimation of convex divergences.
problem Estimating convex divergences between distributions.
method Martingale methods and maximal inequalities for reverse submartingales.
result Valid time-uniform confidence sequences for arbitrary stopping times.
Algorithm clusters items by sequentially selecting features, minimizing observations.
problem Clustering items based on bandit feedback with many features.
method Sequential Halving algorithm for feature selection.
result Accurate recovery of item partition with minimal observations.