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.
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.
We study how to efficiently estimate average treatment effects (ATEs) using adaptive experiments. In adaptive experiments, experimenters sequentially assign treatments to experimental units while updating treatment assignment probabilities based on past data. We start by defining the efficient treatment-assignment prob…
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 …
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.
In this paper, we present a novel sequential paradigm for classification in crowdsourcing systems. Considering that workers are unreliable and they perform the tests with errors, we study the construction of decision trees so as to minimize the probability of mis-classification. By exploiting the connection between pro…
Algorithm solves job acceptance problem with random arrivals and values.
problem Decision-making under random job arrivals and values with limited acceptance.
method Proposes Non-Parametric Sequential Allocation (NPSA) algorithm.
result Expected reward converges to optimality as sample size increases.
This research note combines two methods that have recently improved the state of the art in language modeling: Transformers and dynamic evaluation. Transformers use stacked layers of self-attention that allow them to capture long range dependencies in sequential data. Dynamic evaluation fits models to the recent sequen…
The paper develops methods to estimate optimal treatment sequences under policy constraints.
problem Estimating the best sequence of treatments over multiple stages for individuals.
method Empirical welfare maximization approach, solving treatment assignment sequentially or simultaneously.
result Established convergence rates and upper bounds for estimation methods.
New causal versions of MaxEnt and PIR avoid paradoxical probability updates.
problem Paradoxical probability updates in causal MaxEnt and PIR.
method Separate constraints into cause-specific and mechanism-specific restrictions.
result Causal MaxEnt avoids paradoxical updates and aligns with Information Geometric Causal Inference.
Study on predicting sequences with Gaussian constraints, linking to intrinsic volumes and metric complexity.
problem Predicting sequences almost as well as the best Gaussian distribution with mean in a given subset.
method Expressed minimax regret in terms of intrinsic volumes, established comparison inequality for Wills functional, characterized global covering numbers and local Gaussian widths.
result Sharp estimates on the log-Laplace transform of intrinsic volume sequence for a general nonconvex set.
This study optimizes covariate density and propensity score for efficient ATE estimation.
problem Efficiently estimating average treatment effects (ATEs) with minimal variance.
method Adaptive experiment optimizing both covariate density and propensity score.
result Proposed method minimizes the semiparametric efficiency bound for ATE estimation.
New method constructs confidence sets for GLMs via game theory.
problem Developing reliable confidence intervals for GLM parameters.
method Reduction to sequential prediction games with low regret.
result Online-to-confidence-set conversions provide new types of intervals.
Proposes DSW for unbiased ITE estimation with dynamic confounders.
problem Estimating ITE from dynamic observational data with time-varying confounders.
method Deep Sequential Weighting (DSW) infers hidden confounders using current treatment assignments and historical information.
result DSW generates unbiased and accurate treatment effects.
Method learns optimal treatment sequences from observational data.
problem Optimal dynamic treatment regimes for public policies and medical interventions.
method Doubly robust classification-based approach via backward induction.
result Achieves optimal convergence rate of n^(-1/2) for welfare regret.
New method improves treatment effect estimation in adaptive experiments with noncompliance.
problem Estimating average treatment effect in adaptive experiments with binary instrumental variable.
method AMRIV estimator that balances outcome noise and compliance variability.
result AMRIV achieves semiparametric efficiency bound and is robust to noncompliance.
Wasserstein gradient boosting predicts probability distributions for supervised learning.
problem Distribution-valued supervised learning where outputs are probability distributions.
method Fits a new weak learner to Wasserstein gradients of loss functionals of probability distributions.
result Superior performance in probabilistic prediction compared to existing methods.
New method estimates treatment effects over time with unobserved confounders.
problem Estimating treatment effects from observational data with unobserved confounders.
method Sequential Deconfounder using Gaussian process latent variable model.
result Unbiased estimates of individualized treatment responses over time.
New method for PU learning with instance-dependent propensity scores.
problem Learning from positive and unlabeled data with instance-dependent labeling.
method Empirical risk minimization of joint risk function, alternating optimization of posterior probability and propensity score.
result The method achieves comparable or better performance than state-of-the-art methods.
Efficient inference method for adaptive experiments with tighter confidence sequences.
problem Efficient inference of Average Treatment Effect in a changing policy sequential experiment.
method Semiparametric efficient inference using Adaptive Augmented Inverse-Probability Weighted estimator and asymptotic confidence sequences.
result Derives tighter confidence sequences for adaptive experiments under data-dependent stopping times.
In treatment allocation problems the individuals to be treated often arrive sequentially. We study a problem in which the policy maker is not only interested in the expected cumulative welfare but is also concerned about the uncertainty/risk of the treatment outcomes. At the outset, the total number of treatment assign…
Eigenoptions improve credit assignment in reinforcement learning.
problem Improving credit assignment in reinforcement learning models.
method Investigated eigenoptions for credit assignment in model-free RL, comparing pre-specified and online discovery methods.
result Pre-specified eigenoptions aid exploration and credit assignment, while online discovery can hinder learning.
New method for estimating counterfactual means in adaptive experiments.
problem Inference for counterfactual means in sequentially designed experiments with adaptive treatment policies.
method Latent factor model and nearest neighbors method for estimation.
result Asymptotically valid confidence intervals for counterfactual means established.
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.
Since manually labeling training data is slow and expensive, recent industrial and scientific research efforts have turned to weaker or noisier forms of supervision sources. However, existing weak supervision approaches fail to model multi-resolution sources for sequential data, like video, that can assign labels to in…
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.
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.
Optimizes balanced treatment assignment for experiments.
problem Balancing treatment groups in experiments for optimal results.
method Optimization of a two-sample test, using minimum spanning tree test.
result Optimal assignment algorithm with polynomial time complexity.
New bandit algorithm for non-i.i.d. noise, improving standard rates.
problem Linear stochastic bandit with non-i.i.d. observation noise.
method Developed new confidence sequences and an algorithm based on optimism in uncertainty.
result Regret bounds for the new algorithm, showing recovery of standard rates up to a factor of the mixing time.
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.
Many wireless networks, including 5G NR (New Radio) and future beyond 5G cellular systems, are expected to operate on multiple frequency bands. This paper considers the band assignment (BA) problem in dual-band systems, where the basestation (BS) chooses one of the two available frequency bands (centimeter-wave and mil…
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…
We present a recurrent neural network memory that uses sparse coding to create a combinatoric encoding of sequential inputs. Using several examples, we show that the network can associate distant causes and effects in a discrete stochastic process, predict partially-observable higher-order sequences, and enable a DQN a…
Proposes rounding method for precise treatment effect estimation under budget constraints.
problem Resource-constrained experimental design for precise treatment effect estimation.
method Dependent randomized rounding procedure to convert assignment probabilities into binary treatment decisions.
result Improved estimator precision through variance reduction and efficient inference.
We model and correct bias in sequential evaluation, improving ranking accuracy.
problem Sequential evaluation bias in online, irrevocable scoring.
method Modeling the rating process, posing as statistical inference, proposing an online algorithm.
result Near-linear time, online algorithm with guarantees in ranking metrics, information theoretically optimal.
The paper develops a method for self-normalized inference in adaptive experiments.
problem Adaptive experiments require a fixed horizon for ATE estimation, but propensities can change.
method The method uses self-normalized martingale limit theory to estimate ATE.
result The Studentized statistic is asymptotically N(0,1) at the prespecified horizon.
New SMC algorithm reduces memory usage for online clustering.
problem Uncertainty in online clustering with complex distributions.
method Decomposes clustering into independent subproblems using SMC.
result Accurately and efficiently solves clustering problems.
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.
SLHF uses sequential game theory to optimize preferences from human feedback.
problem Optimizing preferences from human feedback in sequential settings.
method SLHF frames the problem as a sequential-move game between Leader and Follower, decomposing the optimization into refinement and adversarial optimization.
result SLHF achieves strong alignment across diverse preference datasets and scales to large models.
Generative model for joint discrete distributions using randomized assignment flows.
problem Efficiently representing and sampling from complex joint distributions of discrete variables.
method Randomized assignment flows on the statistical submanifold of factorizing distributions.
result Our model can efficiently represent and sample from any target distribution and assess likelihood of unseen data points.
A new algorithm learns model regimes and parameters efficiently.
problem Learning high-dimensional parameters with discontinuous jumps.
method Differentiable interacting multiple model particle filter with gradient descent.
result Superior numerical performance compared to previous methods.