New framework maximizes perturbed samples for inverse classification with budget constraints.
problem Maximizing perturbed samples for desired classification outcomes under budget constraints.
method Gradient methods, stochastic processes, Lagrangian relaxations, Gumbel trick.
result Stochastic process-based algorithms outperform in different budget settings.
New findings on complexity limits in fixed budget bandit identification.
problem Determining the best possible error rate for fixed budget bandit identification.
method Analyzing the best non-adaptive sampling procedures and showing the existence of complexities.
result No fixed complexity for certain bandit identification tasks.
The paper improves PCS approximation for ranking and selection under limited simulation budgets.
problem Improving finite sample performance in Ranking and Selection.
method Develops a Bahadur-Rao type expansion for PCS, proposes a novel FCBA policy.
result FCBA policy achieves superior PCS performance compared to traditional methods.
New algorithm identifies best arm with optimal budget usage.
problem Identifying the arm with the highest mean reward from multiple options.
method Proposes Almost Tracking, a closed-form algorithm for anytime best arm identification.
result Proven to be rate-optimal and outperforms existing algorithms.
Proposes a new sampling method for online learning with cumulative oversampling.
problem Budgeted Influence Maximization in online learning.
method Cumulative Oversampling (CO) method for online learning.
result CO-based algorithm achieves comparable regret to UCB-based algorithms and performs similarly to Thompson Sampling.
New research shows fixed-budget best-arm identification cannot match static oracle performance.
problem Fixed-budget best-arm identification's performance limitations.
method Analysis of various adaptive and static algorithms for best-arm identification.
result For any algorithm, there exists at least one instance where the error decay rate is at most \((1 + \frac{\log(K)}{8})^{-1}\) times that of the static oracle.
Bridges uplift modeling and sequential decision-making with online budget allocation.
problem Treatment allocation under budget constraints in digital advertising.
method Budget-Constrained Causal Bandits (BCCB) integrates learning, exploration, and budget pacing.
result Data-efficiency crossover: BCCB operates effectively from the first user, 3-5x lower performance variance.
APGAI identifies good arms anytime with fixed budget.
problem Identifying a good arm with a fixed sampling budget.
method An anytime algorithm for good arm identification in stochastic bandits.
result APGAI achieves efficient detection of good arms with upper bounds on probability of error and sampling complexity.
The paper tackles budget allocation for multiple campaigns using a novel combinatorial bandit approach.
problem Maximizing cumulative returns with limited budgets across various ad lines.
method Formulated as a multi-task combinatorial bandit problem, integrates Bayesian hierarchical models, and uses Thompson sampling.
result Demonstrates robustness and adaptability in maximizing overall cumulative returns.
We analyze alternating minimization for column space recovery of a partially observed, approximately low rank matrix with a growing number of columns and a fixed budget of observations per column. In this work, we prove that if the budget is greater than the rank of the matrix, column space recovery succeeds -- as the …
A new UCB policy improves reward-cost ratio estimation in budgeted MAB.
problem Maximizing reward-cost ratio under budget constraints.
method ω-UCB policy with asymmetric confidence intervals.
result Logarithmic regret and superior performance in various settings.
Box Thirding identifies the best arm efficiently under limited samples.
problem Efficiently identifying the best arm with limited sampling.
method Iterative ternary comparison of arms, discarding the weakest and exploring the best.
result Achieves comparable performance to Successive Halving with less predefined parameters.
This paper studies the problem of nonparametric estimation of a smooth function with data distributed across multiple machines. We assume an independent sample from a white noise model is collected at each machine, and an estimator of the underlying true function needs to be constructed at a central machine. We place l…
Paper shows FB and FC are equally hard up to logarithmic factors.
problem Comparing fixed budget and fixed confidence approaches in best-arm identification.
method Proposes FC2FB, a meta algorithm converting FC to FB.
result FC sample complexity is an upper bound for FB sample complexity up to logarithmic factors.
DARTS optimizes covariate selection in trials with limited data.
problem Limited budget for high-dimensional pretreatment data.
method Dynamic Adaptive Rerandomization via Thompson Sampling (DARTS).
result DARTS efficiently concentrates budget on informative features.
DSI improves tail-risk estimation in generative models by averaging checkpoints.
problem Generative models' instability in rare adverse scenarios.
method Diachronic Sample Integration (DSI) ensembles generated samples across checkpoints.
result DSI reduces tail-estimation error compared to single-checkpoint baselines.
Adaptive Nucleus Truncation Improves Long-Form Reasoning
problem Improving long-form reasoning in language models
method Adaptive Nucleus Truncation Sampling (ANTS)
result Significant performance gains across various benchmarks
Monte Carlo algorithms simulate some prescribed number of samples, taking some random real time to complete the computations necessary. This work considers the converse: to impose a real-time budget on the computation, which results in the number of samples simulated being random. To complicate matters, the real time t…
EB-TCε identifies the best arm with ε confidence in stochastic bandits.
problem Identifying the best arm in stochastic bandits with a fixed level of confidence.
method EB-TCε is a novel sampling rule for ε-best arm identification in stochastic bandits.
result EB-TCε is the first anytime algorithm for fixed confidence or fixed budget identification.
Improved adaptive algorithms for identifying the best arm in MABs with fixed budget.
problem Identifying the best arm in stochastic Multi-Armed Bandits with a fixed sampling budget.
method Established a connection between Large Deviation Principles and adaptive algorithms, improving error probability bounds and devising new algorithms.
result The \sred algorithm outperforms existing algorithms in identifying the best arm.
Study optimal policies under budget and coverage constraints.
problem Optimal policy learning with budget and coverage constraints.
method Combination of knapsack structure, affine threshold rule, linear programming relaxation, Greedy-Lagrangian (GLC), and rank-and-cut (RC) algorithms.
result GLC closely approximates the optimal solution and achieves near-optimal performance in finite samples; RC is approximately optimal under certain conditions.
New OCBA procedures minimize PICS in robust R&S.
problem Selecting the best alternative under input uncertainty.
method Developed new asymptotically optimal OCBA procedures.
result Procedures minimize probability of incorrect selection.
Estimates model performance based on compute budget and evaluates stability over time.
problem Understanding how model performance evolves with compute budget and stability over time.
method Large-scale observational evaluations, prescriptive scaling laws, smoothed quantile regression, I-optimal sampling algorithm.
result Estimates attainable accuracies and stability of model performance over time.
This paper proposes a new AED framework for multi-metric experiments with fixed budget.
problem Statistical power challenges in testing multiple metrics simultaneously.
method Two-phase structure: adaptive exploration followed by validation. SHRVar algorithm with relative-variance-based sampling.
result Achieves provable error probability that decreases exponentially.
A/B testing refers to the task of determining the best option among two alternatives that yield random outcomes. We provide distribution-dependent lower bounds for the performance of A/B testing that improve over the results currently available both in the fixed-confidence (or delta-PAC) and fixed-budget settings. When…
Recently, crowdsourcing has emerged as an effective paradigm for human-powered large scale problem solving in various domains. However, task requester usually has a limited amount of budget, thus it is desirable to have a policy to wisely allocate the budget to achieve better quality. In this paper, we study the princi…
Study wSAA for contextual decisions, improving uncertainty quantification under computational constraints.
problem Uncertainty quantification limitations in wSAA for contextual stochastic optimization.
method Establish central limit theorems and asymptotic-normality-based confidence intervals for optimal costs.
result Over-optimizing can mitigate misspecification and preserve asymptotic normality, albeit at a slower convergence rate.
This paper compares self-reflection and budget tuning for LLMs, revealing domain-specific performance gains.
problem Improving inference-time performance of LLMs without retraining, balancing quality, cost, and latency.
method Systematic comparison of self-reflection and budget tuning across mathematical reasoning and translation tasks, evaluating various LLMs and model families.
result Substantial domain-dependent variation in self-reflection effectiveness, with up to 220% performance gains in mathematical reasoning.
SODA optimizes data augmentation allocation for deep learning models.
problem Inefficient allocation of data augmentation budget in deep neural networks.
method Online learning to dynamically allocate data augmentation budget during training.
result Optimized data augmentation can save computation time and promote greener machine learning.
The pairwise influence matrix of Dobrushin has long been used as an analytical tool to bound the rate of convergence of Gibbs sampling. In this work, we use Dobrushin influence as the basis of a practical tool to certify and efficiently improve the quality of a discrete Gibbs sampler. Our Dobrushin-optimized Gibbs samp…
Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
POCA optimizes hyperparameters with adaptive allocation for faster convergence.
problem Optimizing hyperparameters for machine learning models.
method Adaptive allocation of computational budget using Bayesian sampling.
result POCA finds strong configurations faster than its competitors.
Optimal best-arm identification in linear bandits reduces sampling budget.
problem Identifying the best arm with fixed confidence in stochastic linear bandits.
method A simple algorithm that tracks an optimal proportion of arm draws, updated as rarely as desired.
result The algorithm's sampling complexity matches known lower bounds, asymptotically almost surely and in expectation.
This paper identifies drift Lipschitz budget K as key to diffusion policy expressivity and statistical trade-offs.
problem Understanding and maximizing the expressivity of diffusion policies while managing statistical limitations.
method Identifying drift Lipschitz budget K as central, quantifying expressivity and statistical behavior, proving lower bounds, and providing practical implementation guidelines.
result Balancing expressivity and statistical complexity yields a finite-sample performance gap, with rates depending on sample size and drift type.
Optimal strategy found for identifying best arm in bandits with small gap.
problem Best arm identification in two-armed bandits with a fixed budget and small gap.
method Neyman allocation rule augmented with inverse probability weighting.
result Proposed strategy is asymptotically optimal when gap is small.
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.
Engineering problems often involve data sources of variable fidelity with different costs of obtaining an observation. In particular, one can use both a cheap low fidelity function (e.g. a computational experiment with a CFD code) and an expensive high fidelity function (e.g. a wind tunnel experiment) to generate a dat…
Proposes a new method to optimize treatment allocation with budget constraints.
problem Optimizing treatment allocation with budget constraints in marketing.
method Learning to rank for profit maximization.
result Learning to rank can maximize the area under a policy's incremental profit curve.
Synthetic tabular data synthesis models balance utility and risk.
problem Generating synthetic tabular data for regulated domains.
method Latent flow models with various learning targets, paths, and sampling methods.
result Velocity and posterior matching objectives yield higher utility, while score and noise matching achieve lower risk.
New algorithm identifies optimal subtrees in fixed-budget tree search.
problem Identifying optimal subtrees in fixed-budget Monte Carlo Tree Search.
method ε-agnostic algorithm for max-min action identification.
result Misidentification probability decays exponentially with sample size.
In this paper we propose a fast online Kernel SVM algorithm under tight budget constraints. We propose to split the input space using LVQ and train a Kernel SVM in each cluster. To allow for online training, we propose to limit the size of the support vector set of each cluster using different strategies. We show in th…
GSSBO reduces GP fitting time in Bayesian optimization.
problem High computational cost of fitting Gaussian process surrogate models in Bayesian optimization.
method Gradient-based sample selection to reduce the number of samples used in GP fitting.
result Sublinear regret bounds and significant reduction in computational cost.
ABae efficiently computes subset means with expensive predicates using stratified sampling.
problem Computing subset means with expensive predicates efficiently.
method Stratified sampling and proxy models.
result Mean squared error of O(N−1) when N is split evenly between stages. This paper analyzes OCBA algorithms' convergence rates for DEDS optimization.
problem Optimizing discrete-event dynamic systems with limited computing resources.
method Characterizes convergence rates of two OCBA algorithms under different performance measures.
result OCBA algorithms achieve optimal convergence rates under probability of correct selection and expected opportunity cost measures.
We develop a method to estimate the time to unsafe responses in LLMs.
problem Estimating the time to unsafe responses in large language models is challenging due to the rarity of unsafe outputs.
method We frame the problem as survival analysis and propose a calibration technique for constructing a lower predictive bound (LPB).
result Our method provides rigorous coverage guarantees and improves sample efficiency.
Study optimizes data collection from biased, costly sources to minimize risk.
problem Estimating population means and group-conditional means from multiple sources with varying costs and biases.
method Develops a sampling plan that maximizes effective sample size, paired with a post-stratification estimator.
result Achieves budgeted minimax optimal risk for estimating population means and group-conditional means.
New method optimizes costly functions with unknown costs and budget constraints.
problem Optimizing functions with unknown and heterogeneous evaluation costs under a budget constraint.
method Budgeted multi-step expected improvement acquisition function.
result Our method outperforms existing approaches in various synthetic and real problems.
Efficiently allocate budgets for LLM-assisted virtual screening to reduce costs.
problem Reducing the cost of evaluating alternatives in large-scale screening tasks.
method Propose a top-m greedy evaluation mechanism and the EFG-m algorithm for efficient budget allocation. result Prove that EFG-m is both sample-optimal and consistent in large-scale virtual screening.