Adaptive Sampling

Ask about this topic

Overview

Adaptive sampling studies how to choose which examples, measurements, or computational steps to spend a limited budget on. Common approaches use uncertainty, prediction error, information gain, or difficulty to guide active learning, Bayesian experimental design, bandit allocation, and adaptive numerical solvers; learned policies, including reinforcement learning, are also used. Applications range from scientific experiments and sensor acquisition to diffusion-model sampling and test-time reasoning with language models. A central challenge is ensuring that the signals used to prioritize samples reliably improve the final task without sacrificing coverage, introducing bias, or costing more to compute than they save.

Latest papers

CardsList

202 papers37 papers in the last four weeks, up 106% on the four weeks before. 0.2% of all new papers.

Jun 1, 2026

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

Shapley values are a principled attribution measure widely used in interpretable machine learning, but their exact computation scales exponentially with the number of players, motivating a wide range of approximation methods based on value function evaluations of sampled coalitions. This raises the question of whether approximation accuracy can be improved by adaptively selecting coalitions for evaluation based on previous evaluations. This is particularly relevant in settings where the value function is costly and the number of evaluations is severely limited, such as retraining-based feature importance, data valuation, and hyperparameter importance. For this purpose, we propose ShaplEIG, a Bayesian experimental design approach that approximates the expensive value function using a Gaussian process surrogate and adaptively selects coalitions based on their expected information gain about the Shapley values. By the linearity of the Shapley values in the value function, we show that the expected information gain is available in closed form. Furthermore, we propose an efficient computation scheme that reduces the complexity from exponential to polynomial in the number of players via elementary symmetric polynomials. In extensive experiments across diverse costly applications, our method consistently improves sample efficiency in the low-budget regime over state-of-the-art baselines.

David Rundel, Fabian Fumagalli, Maximilian Muschalik +2

Department of Statistics, LMU Munich, Munich, Germany · Munich Center for Machine Learning, Munich, Germany · Institute for Informatics, LMU Munich, Munich, Germany +2

Shapley Value AttributionAdaptive SamplingBayesian Experimental Design
AskPDF
Jun 1, 2026

Query-Limited Community Recovery in Stochastic Block Models

We study exact community recovery in the two-community stochastic block model on nn vertices under limited and noisy access to network data. The learner may query a noisy neighborhood oracle that reveals each true neighbor of a queried vertex independently with fixed probability and never returns non-neighbors, subject to a finite query budget. We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph. For oracle-only access, balanced uniform querying gives a sharp non-adaptive benchmark: when each vertex is queried the same integer number of times, the observations reduce to an SBM with attenuated edge probabilities and the Abbe-Bandeira-Hall exact-recovery threshold applies. We show that this benchmark is not adaptively optimal: a two-stage adaptive strategy succeeds with n+o(n)n+o(n) queries in a regime where balanced uniform querying requires mnm n queries for some m>1m>1. With an additional subsampled graph, we prove a sublinear-query adaptivity gap: balanced data-independent uniform querying with a sublinear budget does not improve over the subsampled graph alone, whereas adaptive querying can target a small set of uncertain vertices and achieve exact recovery. Thus adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery.

Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen +1

1Microsoft Research, India · 2Indraprastha Institute of Information Technology, India · University of Liverpool, United Kingdom +1

Active LearningAdaptive SamplingStochastic Block ModelGraph Clustering
AskPDF
Jun 1, 2026

Improvise, Adapt, Overcome: An On-The-Fly Multifidelity Algorithm for Efficient Machine Learning

Machine learning has accelerated quantum chemistry but is hindered by the prohibitive cost of generating high fidelity training data. Multifidelity machine learning (MFML) mitigates this overhead by systematically combining abundant low fidelity data with sparse high fidelity data. In spite of its success, standard MFML schemes rely on pre-defined scaling factors to determine sparse data ratio across fidelities, often generating redundant multifidelity data resulting in a loss of efficiency. Here, we introduce an adaptive on-the-fly multifidelity framework for machine learning that autonomously determines training dataset composition. By dynamically querying training samples at each fidelity, the algorithm saturates model accuracy at lower fidelities before moving up to more expensive reference calculations. We benchmark the novel adaptive-MFML across diverse chemical properties including the computational chemistry gold standard coupled cluster energies, and the more chemically challenging excitation energies. In our numerical experiments we show that our adaptive algorithm reduces data generation costs by up to a factor of 30 compared to single fidelity methods and improves upon standard MFML by up to a factor of 5. The mitigation of data redundancy establishes a high-accuracy low-cost pathway for sustainable cost-aware machine learning in quantum chemistry.

Vivin Vinod, Peter Zaspel

School of Mathematics and Natural Sciences, University of Wuppertal, Germany.

Quantum ChemistryMultifidelity ModelingAdaptive SamplingMolecular Property PredictionData-Efficient LearningComputational Quantum Chemistry
AskPDF
Jun 1, 2026

Learning Implicit Bias in Generative Spaces for Accelerating Protein Dynamics Emulation

Generative emulators of protein dynamics produce plausible trajectories at a fraction of the cost of molecular dynamics, but they inherit their training distribution and tend to revisit known states rather than reach rare ones under long-horizon extrapolation. Inspired by classical enhanced sampling, we introduce an implicit, history-dependent bias in the generative space of a pretrained emulator. Specifically, a history-aware score estimator augments the frozen emulator with a distance-weighted bias that steers reverse-time sampling away from previously generated structures, regularized by an environment-support term. To preserve structural validity at long horizons, a score-based refinement step re-projects drifted samples onto the data manifold using the frozen emulator. Our experiments demonstrate that the method (i) raises diversity by 35%35\% on DynamicPDB-80; (ii) on 1212 zero-shot Fast-Folding proteins, the learned bias alone reaches the unbiased emulator's coverage up to ∼15×{\sim}15\times faster, and pairing it with refinement reaches the coverage up to ∼37×{\sim}37\times faster while covering ∼3×{\sim}3\times as many low-energy states. Code will be released soon.

Kaihui Cheng, Zhiqiang Cai, Wenkai Xiang +4

Fudan University · Shanghai Academy of AI for Science · Shanghai Innovation Institute

Diffusion Model SamplingAdaptive SamplingScore-Based Generative ModelingMolecular Dynamics Simulation
AskPDF
Jun 1, 2026

Self-Regulating Annealing in Heavy-Tailed Diffusion Models

Diffusion models have emerged as a leading framework for deep generative modeling. While the standard Gaussian formulation is theoretically convenient, its suitability for heavy-tailed datasets remains unclear. To address this, heavy-tailed diffusion models (HTDMs) extend the standard formulation by replacing the Gaussian distribution with a Student's t-distribution, thereby improving tail fidelity on heavy-tailed datasets. Although stochastic differential equation (SDE)-based sampling is possible in HTDMs, it has not been fully explored. In this paper, we propose an SDE-based sampler for HTDMs that explicitly incorporates a state-dependent diffusion coefficient. This state dependence naturally induces a self-regulating annealing mechanism by adaptively modulating the effective noise scale. We theoretically explore this mechanism and experimentally verify its necessity for reproducing samples from a heavy-tailed distribution.

Keito Wakatsuki, Hideaki Shimazaki

Graduate School of Informatics Kyoto University, Kyoto, Japan

Stochastic Differential EquationsDiffusion SamplingHeavy-Tailed NoiseGenerative ModelingAdaptive SamplingHeavy-Tailed Distributions+1
AskPDF
May 30, 2026

Meta-Black-Box Optimization with Ensemble Surrogate Modeling for Robustness-Accuracy Trade-off within SAEA

Surrogate-assisted evolutionary algorithms (SAEAs) have been widely used for expensive black-box optimization problems. However, their reliance on rigid and manually designed components limits their flexibility and generalization across tasks. Meta-black-box optimization (MetaBBO) provides a promising paradigm for adaptively configuring algorithmic components. Nevertheless, existing MetaBBO methods usually control only a single component, and few studies have investigated the unified control of multi-component optimizers such as SAEAs. Moreover, the robustness-accuracy trade-off in surrogate modeling, which is crucial for stable early-stage exploration and accurate late-stage exploitation, has rarely been explicitly considered. To address these issues, we propose AdaE-SAEA, an adaptive ensemble surrogate-assisted evolutionary algorithm for expensive multi-objective optimization. AdaE-SAEA embeds SAEA as the low-level optimizer within the MetaBBO framework and jointly controls the infill criterion and ensemble-based surrogate modeling. Specifically, bagging and boosting are designed as surrogate modeling modules to adaptively balance robustness and accuracy across different search phases, while the meta-policy simultaneously selects the infill criterion to enable adaptive sampling decisions. The meta-policy is trained through reinforcement learning with parallel sampling and centralized training, improving both training efficiency and transferability. Experiments on synthetic and real-world problems demonstrate that AdaE-SAEA outperforms state-of-the-art baselines and MetaBBO-based methods. We further verify the effectiveness of TabPFN as the base surrogate model for ensemble learning. To the best of our knowledge, this is the first work to unify the control of surrogate modeling and infill criteria in SAEAs while explicitly addressing the robustness--accuracy trade-off.

Xiao Jin, Yongxiong Wang, Haobo Liu +2

School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, 200093, Shanghai, China · Xinxiang University, 453003, Xinxiang, China · College of System Engineering, National University of Defense Technology, 410073, Changsha, China

Surrogate ModelingSurrogate-Assisted OptimizationLearning to OptimizeAdaptive SamplingMulti-Objective Optimization
AskPDF
May 29, 2026

PEEK: Picking Essential frames via Efficient Knowledge distillation

Video-language models can process only a limited number of frames, making frame selection a key bottleneck for efficient video captioning. Most captioning pipelines still rely on uniform sampling, which is computationally cheap but agnostic to visual content. Adaptive frame sampling has recently emerged as a promising approach for selecting the most informative frames from a video; however, existing methods remain computationally expensive. We introduce PEEK, an efficient dynamic frame sampling method that distills caption-conditioned frame relevance rankings from a stronger teacher model into a lightweight temporal model that operates only on visual content. We find that, overall, on ActivityNet Captions and MSR-VTT, our method outperforms state-of-the-art methods across all evaluated downstream vision language models, especially when only one or two frames are selected for captioning, obtaining the best CIDEr for most frame budgets. On ActivityNet Captions, PEEK is particularly strong, winning 14 out of 16 configurations. Zero-shot evaluation on MSR-VTT shows that our model transfers best at low frame budgets, while results at four and eight frames are more mixed as temporal coverage and visual diversity become increasingly competitive. Compared with recent adaptive baselines, PEEK is both more accurate in the low-budget regime and more efficient: it adds only 5.2%5.2\% to the captioning time, compared with 65.4%65.4\% for CSTA and 211.9%211.9\% for MaxInfo. We release our code and pre-trained checkpoint at https://github.com/momentslab/peek.

Killian Steunou, Anas Filali Razzouki, Khalil Guetari +2

Télécom SudParis — SAMOVAR Institut Polytechnique de Paris Palaiseau, France · Moments Lab 69 Avenue Pierre Grenier Boulogne-Billancourt, France

Efficient VLM InferenceVideo CaptioningAdaptive SamplingAdaptive Video Frame Sampling
AskPDF
May 29, 2026

Adaptive data selection improves wearable prediction under low baseline performance

Adaptive sensing strategies that selectively sample data are increasingly used in wearable health systems to improve prediction performance under limited data budgets, yet their benefits across individuals remain poorly understood. Here, we evaluate adaptive selection of time windows for model training under fixed measurement budgets across multiple sensing modalities, including heart rate, activity, and ecological momentary assessment (EMA), in a longitudinal wearable dataset. We quantify performance gains relative to random sampling using both area under the receiver operating characteristic curve (AUROC) and F1 score. Adaptive strategies yield substantial improvements in AUROC for participants with low baseline performance (with gains up to 0.7), while offering limited or negative gains for participants with strong baselines. Across modalities, adaptive gain is strongly inversely correlated with baseline performance (Pearson r = -0.67; Spearman p = -0.62). At the participant level, most individuals benefit in AUROC (60-80% across modalities), although improvements in F1 are smaller and less consistent. These findings show that adaptive sensing is not uniformly beneficial, but instead provides the greatest value in underperforming settings. Our results support selective deployment strategies that tailor adaptive sensing based on baseline performance to improve efficiency in wearable health monitoring.

Ali Kargarandehkordi

Data SelectionTraining Data SelectionAdaptive SamplingWearable Health Monitoring
AskPDF
May 28, 2026

Reasoning with Sampling: Cutting at Decision Points

Frontier reasoning models are produced by post-training base language models with reinforcement learning. Recent work has challenged this by showing that sampling from a sharpened version of the base model's distribution, a so-called power distribution, elicits comparable reasoning without additional training, curated datasets, or verifiers. However, making this method practical requires efficiently sampling from the power distribution. A sampler needs to "mix" to the power distribution, which necessitates moving between modes of the target distribution; intuitively, e.g., trying different reasoning strategies. The samplers proposed in prior works repeatedly select a "cut" position in the current reasoning trace uniformly at random and resample the suffix from that position onward. However, reasoning traces typically contain a few consequential decisions (e.g., the choice of proof strategy or algorithm), and we observe that a uniformly chosen cut tends to rewrite local details rather than revisit decision points. We introduce an algorithm (Entropy-Cut Metropolis-Hastings) that uses the base model's next-token entropy as a proxy to identify key decision points and resample from those positions. We empirically verify that entropy jumps are a useful proxy for decision points and, in a stylized model of reasoning, prove that our method's mixing time scales with the number of decisions in a trace rather than with the number of tokens, which can be much larger. Across MATH500, HumanEval, GPQA Diamond, and AIME26, our method consistently improves over baselines and RL-trained models, including best-of-N at the same token budget.

Felix Zhou, Anay Mehrotra, Quanquan C. Liu

Yale University · Stanford University

Markov Chain Monte CarloEfficient Language Model ReasoningAdaptive SamplingLLM Reasoning
AskPDF
May 26, 2026

VR-DAgger: Immersive VR for Dexterous Data Collection and Uncertainty-Guided On-Policy Correction

Learning from demonstrations is effective for robotic manipulation, but collecting sufficient task-specific data remains a major bottleneck. Under distribution shift, small errors compound, performance degrades, and expert time is often spent on redundant, low-value corrections instead of the few critical failure cases. We present VR-DAgger, a human-in-the-loop framework centered on an immersive VR application for dexterous teleoperation, demonstration collection, and selective policy correction. The VR client provides intuitive hand control with synchronized scene visualization, while a backend workstation runs simulation and learning, enabling autonomous rollouts without continuous operator oversight. We use Monte Carlo (MC) dropout to score uncertainty during Isaac Lab rollouts of a diffusion policy and select informative failure segments for correction. These segments are replayed in VR as clips, where the operator selectively labels and corrects the policy's behavior, concentrating supervision where uncertainty is highest without full-rollout monitoring or a separate intervention classifier. We evaluate on three dexterous manipulation tasks (Pan pick-and-place, Drawer opening, Valve turning) with a 10-DoF XHand under standard and challenging initial configurations. Active labeling consistently improves over behavioral cloning across all tasks, with gains of up to 23 percentage points. Compared to unguided human-in-the-loop inspection, VR-DAgger reduces per-sample collection time by approximately 40% by focusing review on selected segments rather than full rollouts.

René Zurbrügg, Tifanny Portela, Arjun Bhardwaj +3

The Authors are with the Robotics Systems Lab ETH Zürich.

Robotic Data CollectionRobot TeleoperationRobotic ManipulationAdaptive SamplingRobot Imitation LearningDataset Aggregation
AskPDF
May 26, 2026

Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning

Sampling multiple responses improves language model reasoning, but uniform compute allocation is inefficient because easy questions are over-sampled while hard questions remain under-explored. We propose Uncertainty-Aware Budget Allocation (UAB), a concave integer optimization framework that reallocates a fixed sampling budget using uncertainty estimated from the initial samples themselves. In Phase-1, every question receives a small fixed number of generations. Their answer disagreement, measured by vote entropy, provides a difficulty signal while these generations contribute to the final vote. In Phase-2, the remaining budget is allocated by a marginal-greedy algorithm that optimally solves a concave coverage-maximization surrogate, concentrating samples on questions whose initial answers disagree. Across five open-weight models (1.5B--27B parameters) and five reasoning benchmarks of varying difficulty, UAB improves average accuracy by +2.3%+2.3\% over uniform allocation, and achieves gains of up to +5.5%+5.5\% on individual benchmarks, with the largest gains in low-resource settings. Moreover, UAB meets the target budget exactly and requires no auxiliary model or additional LLM calls. Code is publicly available at https://github.com/manhitv/UAB.

Manh Nguyen, Sunil Gupta, Hung Le

Applied Artificial Intelligence Initiative Deakin University, Australia

Efficient Language Model ReasoningAdaptive SamplingUncertainty SamplingInference-Time Compute AllocationLLM Reasoning
AskPDF
May 26, 2026

DynFrame: Adaptive Reasoning-Driven Multimodal Framework with Dynamic Frame Augmentation for Complex Video Understanding

Recent video multimodal large language models (MLLMs) increasingly couple step-by-step reasoning with on-demand visual evidence retrieval, allowing models to revisit relevant video segments during inference. However, two structural gaps remain in existing thinking-with-video systems. (i) Sampling density is not a learnable decision: existing methods may let the model decide where to look, but the per-window frame rate is largely fixed. As a result, fine-grained evidence is often recovered through repeated retrieval calls, which increases inference context length and training difficulty. (ii) Retrieval and answer generation are usually optimized with a single trajectory-level advantage, so the "where to look" tokens and the "how to answer" tokens receive the same credit even when one is correct and the other is not. To address these gaps, we present DynFrame, a framework that emits the temporal window and the sampling density as native tokens within a single autoregressive pass. This learnable span-density retrieval enables acquiring multi-granularity evidence with a single retrieval step. Based on the above tokenized retrieval interface, we further introduce Segment-Decoupled GRPO (SD-GRPO), which splits each rollout at the retrieval boundary and assigns role-specific token-level advantages, separately crediting the sampling decision and the answer. Trained on the curated DM-CoT-74k and DM-RL-45k, DynFrame-4B is competitive with strong 7B-8B baselines across six benchmarks (NExT-GQA, Charades-STA, ActivityNet-MR, Video-MME, MLVU, LVBench), and DynFrame-8B sets new state-of-the-art on most metrics. Code is available at https://github.com/zhangguanghao523/DynFrame.

Peng Zhang, Guanghao Zhang, Wanggui He +10

Zhejiang University · Alibaba Group

Multimodal Large Language ModelsVideo ReasoningAdaptive SamplingMultimodal Foundation ModelsAdaptive Video Frame SamplingRL for VLMs+2
AskPDF
May 25, 2026

Retrying vs Resampling in AI Control

AI coding scaffolds like Claude Code and Codex use retrying: blocking actions flagged as risky and continuing the trajectory. We study retrying from an AI control perspective, which treats the model as potentially adversarial. We find that while retrying reduces honest suspicion scores, the untrusted model can exploit monitor rationale to construct sneakier attacks, negating safety gains. We also study resampling: drawing multiple samples from the same context, which does not leak exploitable information. We disentangle design choices that previous work on resampling had bundled together. In BashArena, with Claude Opus 4.6 as the untrusted model and MiMo-V2-Flash as the trusted monitor, drawing five samples per step and auditing on the maximum suspicion score raises safety from 61% to 71% at a 0.3% audit budget, at no cost to usefulness. Selectively resampling only the steps that look suspicious on the first draw recovers 6.2 percentage points of the gain while drawing only 10% as many extra samples. Two of our findings in this setting contradict earlier work on resampling. The first is that auditing based on the maximum across resampled suspicion scores outperforms using the minimum, which is the opposite of what Ctrl-Z found. The second is that executing the least suspicious sample, which is the central mechanism in earlier defer-to-resample protocols, gives only a small empirical safety gain in our setting (+3.9 pp, with the confidence interval overlapping zero).

James Lucassen, Adam Kaufman

Redwood Research

AI Agent SafetyAI Agent MonitoringAI ControlAdaptive SamplingAI Safety Evaluation
AskPDF
May 24, 2026

Active Learning for Stochastic Contextual Linear Bandits

A key goal in stochastic contextual linear bandits is to efficiently learn a near-optimal policy. Prior algorithms for this problem learn a policy by strategically sampling actions but naively (passively) sampling contexts from the underlying context distribution. However, in many practical scenarios -- including online content recommendation, survey research, and clinical trials -- practitioners can actively sample or recruit contexts based on prior knowledge of the context distribution. Despite this potential for active learning, the role of strategic context sampling in stochastic contextual linear bandits is underexplored. We propose an algorithm that learns a near-optimal policy by strategically sampling rewards of context-action pairs. We prove instance-dependent theoretical guarantees demonstrating that our active context sampling strategy can improve over the minimax rate by up to a factor of d\sqrt{d}, where dd is the linear dimension. We show empirically that our algorithm reduces the number of samples needed to learn a near-optimal policy, in tasks such as warfarin dose prediction and joke recommendation.

Emma Brunskill, Ishani Karmarkar, Zhaoqi Li

Stanford University

Active LearningAdaptive SamplingContextual BanditsPolicy LearningLinear Contextual Bandits
AskPDF
May 22, 2026

Flow-Based Generative Modeling for Optimizing Sampling Policies in Compressed Sensing Applications

Numerous modern applications in signal processing and medical imaging necessitate acquiring high-dimensional signals under tight resource constraints. Traditional sampling theory suggests that accurate signal reconstruction requires a number of measurements proportional to the signal's ambient dimension, a requirement often too expensive or impractical. Compressed sensing challenges this notion by demonstrating that sparse signals can be recovered with fewer measurements, provided the measurement operator meets certain conditions. This proof-of-concept study presents a task-aware flow-based generative framework -- a reformulation of the conventional Flow Matching training paradigm with a flow model trained to optimize subsampling in compressed sensing applications. We establish the fundamental feasibility of the proposed framework of learning subsampling masks that substantially enhance the performance of compressed sensing for image classification, image reconstruction, and MRI acceleration. For the image reconstruction task, our method demonstrated state-of-the-art performance, achieving Peak Signal-to-Noise Ratio of 25.17 dB at the subsampling rate of 5% on the CelebA dataset and 29.24 dB when reconstructing 8×8\times accelerated MRI measurements (fastMRI dataset) with the minimal computational overhead. These results highlight the effectiveness of task-conditioning within generative flow models and reveal a promising direction for representation learning strategies. Overall, the proposed framework offers a unified, flexible approach to designing data- and task-driven sensing schemes that can be potentially adapted to a broad range of inverse problems.

Roman Pavelkin, Luis A. Zavala-Mondragon, Christiaan G. A. Viviers +1

Eindhoven University of Technology, Eindhoven

Flow MatchingImage ReconstructionAccelerated MRI ReconstructionAdaptive SamplingCompressed SensingFlow-Based Generative Modeling
AskPDF
May 22, 2026

Instance-Optimal Estimation with Multiple LLM Judges on a Budget

Evaluating large language models increasingly relies on LLM-as-a-judge protocols, but such evaluations remain costly: different judges have different prices and reliabilities, and the difficulty of each prompt-response pair can vary substantially. This raises a basic allocation question: under a fixed budget, how should one distribute evaluation queries across heterogeneous judges and instances to obtain the most accurate score estimates? We formalize this question as budgeted heteroskedastic multi-judge estimation. Given KK prompt-response pairs, JJ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an ℓp\ell_p-error. Our first contribution is to analyze the inverse-variance weighted estimator (IVWE) and to derive the oracle allocation that minimizes its error rate. Since this allocation depends on the unknown variances, we then address the practical unknown-variance setting by proposing EST-IVWE, an adaptive algorithm that constructs and leverages optimistically biased variance estimates to stabilize the empirical allocation. We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget. Our second and central theoretical contribution is a matching local minimax lower bound, which establishes the instance-optimality of the proposed algorithms. A key technical insight is that Fano-type high-probability arguments are too coarse for this problem: their packing construction loses the local variance structure that governs the optimal allocation. We instead use an Assouad-type in-expectation argument, based on local perturbations, which preserves this structure and yields the sharp allocation-dependent lower bound. Finally, we numerically validate the superiority of our approach over naïve uniform allocation on synthetic and HelpSteer2 datasets.

Junghyun Lee, Sanghwa Kim, Yassir Jedra +2

KAIST AI · ICL EEE · KTH EECS

Parameter EstimationLLM EvaluationLLM-as-a-JudgeMinimax EstimationAdaptive Sampling
AskPDF
May 21, 2026

Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations

Kernel methods are typically formulated under the assumption of exact, noise-free access to the Gram matrix. However, in emerging settings such as quantum machine learning, each kernel entry must be inferred from noisy observations, and its accuracy depends on how a limited measurement budget is allocated. Despite this, existing approaches overwhelmingly rely on uniform allocation, which equalizes estimator variance but ignores the highly non-uniform dependence of kernelized classifiers on the Gram matrix. In this work, we introduce an adaptive measurement-allocation strategy for learning kernelized Support Vector Machines (SVMs) from noisy Bernoulli observations. Our approach combines two complementary principles: (i) geometric sensitivity, capturing how perturbations of individual kernel entries affect the classifier margin, and (ii) active-set instability, quantifying the probability of discrete changes in support-vector membership induced by measurement noise. These signals define a task-aware allocation scheme that concentrates measurements on the most decision-critical regions of the kernel matrix. We provide a theoretical analysis showing that the benefit of adaptive allocation is governed by the heterogeneity of the induced kernel importance structure, leading to distinct regimes in which adaptive or uniform strategies are preferable. Empirical evaluations on synthetic datasets demonstrate that adaptive allocation significantly improves support-vector recovery, margin estimation, and decision-function accuracy under fixed measurement budgets. A dual-coefficient stability criterion further enables early stopping, achieving near-optimal performance while using only a fraction of the measurement cost. Additional experiments on quantum kernels derived from real-world data reveal a regime-dependent behavior aligned with known phenomena such as kernel concentration. Together...

Artur Miroszewski

Φ-lab, European Space Agency (ESA/ESRIN), Frascati, Italy

Adaptive SamplingSupport Vector MachinesKernel Methods
AskPDF
May 20, 2026

MetaDNS: Enhancing Exploration in Discrete Neural Samplers via Well-Tempered Metadynamics

Sampling from discrete distributions with multiple modes and energy barriers is fundamental to machine learning and computational physics. Recent discrete neural samplers like MDNS suffer from mode collapse and fail to sample high-energy barrier regions between modes, which is critical for free energy estimation and understanding phase transitions. We propose Metadynamics Discrete Neural Sampler (MetaDNS), a general framework integrating well-tempered metadynamics into discrete diffusion or autoregressive samplers. By maintaining an adaptive, history-dependent bias potential along selected low-dimensional coordinates, MetaDNS forces exploration of previously inaccessible regions, enabling free energy reconstruction infeasible with standard neural samplers due to a lack of high-energy samples. On challenging low-temperature benchmarks including Ising, Potts, and the copper-gold binary alloy, MetaDNS reproduces the thermodynamic distribution. Compared to MCMC-based metadynamics, MetaDNS also achieves comparable exploration requiring fewer bias deposition steps.

Xiaochen Du, Juno Nam, Jaemoo Choi +7

Massachusetts Institute of Technology · Georgia Institute of Technology

Free Energy CalculationAdaptive Sampling
AskPDF
May 20, 2026

Closed Loop Dynamic Driving Data Mixture for Real-Synthetic Co-Training

Data scaling is fundamental to modern deep learning, and grows increasingly critical as autonomous driving shifts to end-to-end learning. Real-world driving data is expensive to annotate and scene-biased, making real-synthetic co-training with near-infinite synthetic data a promising direction. However, naively incorporating all available synthetic data is inefficient and leads to distribution shifts, and optimizing data mixture under practical training budgets remains a critical yet under-explored problem. In this sense, we claim that the mixture of training data requires clear guidance in terms of scene types and quantities. Particularly in this work, we conceptualize the data mixture approximately as a dynamic optimization process that iteratively adjusts the training data mixture to maximize model performance, guided by closed-loop evaluation feedback, and propose AutoScale, a fully automated closed-loop data engine unifying scene representation, data mixture optimization and retrieval, as well as model training and evaluation. Specifically, we propose Graph Regularized AutoEncoder (Graph-RAE) for driving scene representations, introduce Cluster-aware Gradient Ascent (Cluster-GA) for cluster-wise importance estimation and reweighting, and perform cluster-guided vector retrieval to select high-value samples. Experiments on NavSim demonstrate that AutoScale outperforms vanilla co-training and cross-domain baselines, achieving better performance with fewer synthetic samples under constrained budgets.

Hongzhi Ruan, Pei Liu, Weiliang Ma +5

Li Auto · HKUST (GZ) · HKUST

Autonomous Driving DatasetsSynthetic Data AugmentationEnd-to-End Autonomous DrivingAdaptive SamplingData Mixture Optimization
AskPDF
May 20, 2026

SURF: Steering the Scalarization Weight to Uniformly Traverse the Pareto Front

Scalarization is widely used in multi-objective optimization owing to its simplicity and scalability. In many applications, the goal is to generate solutions that represent diverse user preferences, ideally with uniform coverage of the Pareto front (PF). However, uniformly sampling scalarization weights usually induces non-uniform coverage of the PF. We explain this mismatch through the geometry of the scalarization path. As the weight varies, the corresponding solutions traverse the PF at a generally nonuniform speed. Integrating this speed gives cumulative arc length. After normalization by the total length, it defines a cumulative distribution function (CDF) on weights whose inverse selects points at equal arc-length intervals. Building on this insight, we propose SURF (Sampling Uniformly along the Pareto Front). For structured problems, including bi-objective bandits, we derive analytical expressions for this CDF map and the resulting PF-aware weight sampling rule. For general problems, SURF alternates between CDF reconstruction and weight sampling. Theoretically, we show that under provable conditions for bi-objective LS, SURF's CDF reconstruction error converges linearly to an O(N−2)O(N^{-2}) discretization floor. Empirically, experiments on bandits, multi-objective-gymnasium, and multi-objective LLM alignment demonstrate that SURF efficiently achieves more uniform PF coverage than baselines.

Liuyuan Jiang, Chentong Huang, Lisha Chen

Department of Electrical and Computer Engineering University of Rochester, Rochester, NY 14627

Adaptive SamplingMulti-Objective OptimizationPareto Optimization
AskPDF
May 19, 2026

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector pp. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known pp, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order n/T ∥p∥1/2\sqrt{n/T \, \lVert p \rVert_{1/2}}, whereas active sampling with allocation qj∝pj2/3q_j \propto p_j^{2/3} achieves the tight rate n/T ∥p∥2/3\sqrt{n/T} \, \lVert p \rVert_{2/3}. The resulting improvement can be as large as Θ(k1/4)Θ(k^{1/4}), where kk is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When pp is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-pp active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

College of Management of Technology, EPFL · Department of Computer Science, TU Munich

Multi-Armed BanditsBest-Arm IdentificationAdaptive SamplingRegret MinimizationContextual Bandits
AskPDF
May 19, 2026

APS: Bias-Controlled Adaptive Prototype Simulation for Population-Scale LLM Agents

LLM-agent simulation offers a flexible computational tool for studying population response trajectories that depend on scenario events, memory, demographics, and evolving social context. However, full multi-round simulation scales linearly with both population size and horizon, requiring every agent to query the LLM at every round. We propose Adaptive Prototype Simulation (APS), a framework that reframes scalable LLM-based simulation as a recurrent oracle-allocation problem. APS retains the designated LLM as the online transition oracle while querying adaptive core prototypes, selected singleton-tail agents, and shadow-audit agents. Prototype responses induce local response surfaces for nearby agents, reducing online LLM calls without replacing the underlying transition model. To control approximation bias, shadow-audit residual correction estimates propagation residuals for aggregate correction and future budget allocation, while tail-protected singleton routing directly queries selected isolated, heterogeneous, or high-curvature regions that are vulnerable to smoothing. Theoretically, we treat APS as an estimator for full-scale high-precision individual social simulation and decompose its errors into prototype-coverage error, shadow-audit residual-correction error, local-propagation bias, and temporal context mismatch. Under the reported protocols, APS gives lower reference-aligned distributional discrepancy than scale-oriented and same-budget baselines while reducing online LLM calls, with ablations and compact robustness checks diagnosing the main bias-control mechanisms. In a 10M-agent, multi-round public-opinion simulation, APS achieves a 381.1-fold reduction over full simulation, with reference-aligned final-round JSD of 0.094 against the corresponding full-LLM reference.

Quan Zheng, Yan Gao, Shaobin He +6

1Beijing Normal University · 2Zhongguancun Academy, Beijing, China · 3Zhongguancun Institute of Artificial Intelligence

Human Behavior SimulationAdaptive SamplingLLM AgentsLarge Language Model-Based Social Simulation
AskPDF
May 18, 2026

SIREM: Speech-Informed MRI Reconstruction with Learned Sampling

Real-time magnetic resonance imaging (rtMRI) of speech production enables non-invasive visualization of dynamic vocal-tract motion and is valuable for speech science and clinical assessment. However, rtMRI is fundamentally constrained by trade-offs among spatial resolution, temporal resolution, and acquisition speed, often leading to undersampled k-space measurements and degraded reconstructions. We propose SIREM, a speech-informed MRI reconstruction framework that uses synchronized speech as a cross-modal prior. The central idea is that vocal-tract configurations during speech are correlated with the produced acoustics, making part of the image content predictable from audio. SIREM models each frame as a fusion of an audio-driven component and an MRI-driven component through a spatial weighting map. The audio branch predicts articulator-related structure from speech, while the MRI branch reconstructs complementary content from measured k-space data. We further introduce a learnable soft weighting profile over spiral arms, enabling a differentiable study of how k-space arm usage interacts with speech-informed fusion. This yields a unified multimodal formulation that combines audio-driven prediction, MRI reconstruction, and sampling adaptation. We evaluate SIREM on the USC speech rtMRI benchmark against standard baselines, including gridding, wavelet-based compressed sensing, and total variation. SIREM introduces a speech-informed reconstruction paradigm that operates in a substantially higher-throughput regime than iterative methods while preserving anatomically plausible vocal-tract structure. These results establish an initial benchmark for multimodal speech-informed rtMRI reconstruction and highlight the potential of synchronized speech as an auxiliary prior for fast reconstruction. The source code is available at https://github.com/mdhasanai/SIREM

Md Hasan, Nyvenn Castro, Daiqi Liu +6

1Pattern Recognition Lab, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany · Institute of Radiology, University Hospital Erlangen, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany · 3Institut für Informationsverarbeitung, Leibniz Universität Hannover, Hannover, Germany +1

Accelerated MRI ReconstructionMagnetic Resonance ImagingAdaptive Sampling
AskPDF
May 18, 2026

Curriculum Group Policy Optimization: Adaptive Sampling for Unleashing the Potential of Text-to-Image Generation

Text-to-Image (T2I) generation has achieved remarkable progress in recent years. Meanwhile, reinforcement learning methods, particularly those based on Group Relative Policy Optimization (GRPO), have attracted widespread attention and been successfully applied to T2I tasks. However, the uniform sampling strategy commonly used during training often ignores the match between sample difficulty and the model's current learning capability, leading to low training efficiency. We argue that improving training efficiency requires continuously prioritizing prompts that match the model's evolving capability and remain actively learnable. To this end, we propose Curriculum Group Policy Optimization (CGPO), an adaptive curriculum training framework. During training, each prompt produces a group of images scored by a reward model. We use the variance of group rewards as an online proxy for prompt inconsistency. A higher variance suggests that the model has partially captured the prompt requirements but has not yet achieved stable mastery. Such prompts are more likely to provide useful learning signals, so we increase their sampling probabilities accordingly. Additionally, to address data imbalance in multi-category datasets, we design a category calibration method based on proportional fairness optimization, which balances training difficulty across categories. Experiments on GenEval, T2I-CompBench++, and DPG Bench demonstrate that our framework effectively improves generation performance.

Baoteng Li, Xianghao Zang, Xinran Wang +8

School of Artificial Intelligence, Beijing University of Posts and Telecommunications1 · Beijing Key Laboratory of Multimodal Data Intelligent Perception and Governance3 · Institute of Artificial Intelligence (TeleAI), China Telecom2

Group Relative Policy OptimizationCurriculum RLRL for Image GenerationAdaptive Sampling
AskPDF
May 15, 2026

Entropy Across the Bridge: Conditional-Marginal Discretization for Flow and Schrödinger Samplers

For a fixed flow-based generative model under a small inference budget, sample quality can depend strongly on where the sampler spends its few function evaluations. Flow matching and Schrödinger bridges define probability paths, yet their inference grids are usually heuristic or inherited from one-endpoint diffusion. We derive a conditional-marginal entropy-rate objective for bridge-aware discretization, separating endpoint-conditioned bridge geometry from marginal flow evolution, and use it to build a training-free entropic inference-time scheduler from first principles. For Gaussian Brownian bridges this rate is closed-form and U-shaped, motivating boundary-heavy nonuniform grids. On trained two-dimensional bridge/flow models, the estimated profile recovers the predicted shape and improves 10-step ODE-Heun MMD over linear by 18.1%, with a paired 22.7% SDE-Heun improvement in the same low-NFE sweep. On EDM/CIFAR-10, the entropic time-discretization gives the best tested five-step FID (186.3 \pm 4.0 versus 200.5 \pm 2.9 for linear and 238.0 \pm 5.3 for cosine). On AlphaFlow protein generation, entropic conditional-marginal (cond-marg) scheduling shows advantage in low-NFE regimes on both CAMEO22 and ATLAS benchmarks. These results support entropy-rate scheduling as a practical low-budget allocation signal for high-dimensional bridge and flow samplers.

Bruno Trentini, Dejan Stancevic, Michael M. Bronstein +2

NVIDIA Corporation, Santa Clara, CA, USA · University of Oxford, Dept. of Computer Science, Oxford, UK · Donders Institute for Brain, Cognition, and Behaviour, Radboud University, Nijmegen, NL +1

Flow MatchingSchrödinger BridgesFew-Step Diffusion SamplingAdaptive SamplingFlow-Based Generative ModelingDiffusion Model Inference Acceleration
AskPDF
May 15, 2026

On the Power of Adaptivity for ε\varepsilon-Best Arm Identification in Linear Bandits

We study the minimax sample complexity of ε\varepsilon-best arm identification in linear bandits. Given a compact action set X\mathcal{X} that spans Rd\mathbb{R}^d and an unknown reward vector θ∈Rdθ\in\mathbb{R}^d, the goal is to output an arm x^∈X\widehat{x}\in\mathcal{X} such that ⟨x^,θ⟩≥max⁡x∈X⟨x,θ⟩−ε\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon with probability at least 1−δ1-δ, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right), where w(X)w(\mathcal{X}) is a Gaussian width term dependent on X\mathcal{X}, and we prove a matching lower bound Ω ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right) for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the ℓ2\ell_2 ball, mm-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set X\mathcal{X} for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ2\ell_2-norm estimation subroutine: we design an adaptive algorithm that uses O ⁣(dlog⁡(1/δ)ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right) samples from the unit ℓ2\ell_2 ball in Rd\mathbb{R}^d and outputs an estimate r^\widehat r satisfying ∣r^−∥θ∥2∣≤ε|\widehat r-\|θ\|_2|\le \varepsilon with probability at least 1−δ1-δ, where θθ is the unknown reward vector.

Arnab Maiti, Yunbei Xu, Kevin Jamieson

University of Washington · National University of Singapore

Multi-Armed BanditsBest-Arm IdentificationAdaptive Sampling
AskPDF
May 13, 2026

The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy evaluation of the function. The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision ηη and confidence level 1−δ1-δ, while using as few samples as possible. We propose an adaptive algorithm that first detects intervals likely to contain change points and then refines their locations to precision ηη. We establish non-asymptotic upper bounds on its sample budget, together with corresponding lower bounds. Prior work shows that jump magnitudes alone determine the asymptotic sample complexity as δ→0δ\to 0. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general δδ and ηη, the complexity is jointly governed by the jumps and the relative positions of the change points.

Maximilian Graf, Victor Thuot

INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France

Sample ComplexityAdaptive SamplingChange-Point Detection
AskPDF
May 13, 2026

Kernel-based guarantees for nonlinear parametric models in Bayesian optimization

Modern Bayesian optimization and adaptive sampling methods increasingly rely on nonlinear parametric models, yet theoretical guarantees for such models under adaptive data collection remain limited. Existing analyses largely focus on Gaussian processes, kernel machines, linear models, or linearized neural approximations, leaving a gap between theory and the nonlinear models used in practice. We develop a kernel based framework for analyzing regularized nonlinear parametric models trained on adaptively collected data. Our approach uses kernels over the parameter space to induce reproducing kernel Hilbert space structures over the corresponding model class, yielding confidence bounds for models trained with broad classes of regularized convex losses. We show how these bounds can support convergence guarantees for nonlinear acquisition and surrogate models, including randomized regularized policies that select points by maximizing a trained random model. These results provide a unified route to analyzing nonlinear parametric models in Bayesian optimization and related adaptive optimization settings.

Rafael Oliveira

The Commonwealth Scientific and Industrial Research Organisation (CSIRO) Sydney, Australia

Bayesian OptimizationAdaptive SamplingKernel MethodsStatistical Learning Theory
AskPDF
May 12, 2026

NOVA: Fundamental Limits of Knowledge Discovery Through AI

Can AI systems discover genuinely new knowledge through iterative self improvement, and if so, at what cost? We introduce the NOVA framework, which models the common ``generate, verify, accumulate, retrain'' loop as an adaptive sampling process over a knowledge space. We identify sufficient conditions under which accumulated genuine knowledge eventually covers a finite domain, and show how their violations produce distinct failure modes: contamination, forgetting, exploration failure, and acceptance failure. We then analyze imperfect verification and identify a contamination trap: as easy-to-find knowledge is exhausted, the model mass assigned to new valid artifacts shrinks, so even small false-positive rates can cause invalid artifacts to enter the knowledge base faster than genuine discoveries. We clarify that Good--Turing estimation is a local batch-diversity diagnostic, not an estimator of the historically undiscovered valid mass that governs long-term discovery. Under a separate tail-equivalence assumption relating the model's effective discovery distribution to a Zipf law with exponent α>1α>1, we prove that the cumulative generation cost required to obtain DD distinct genuine discoveries satisfies Rcum(D)=Θ(cgenDα)R_{\mathrm{cum}}(D)=Θ(c_{\mathrm{gen}}D^α), where cgenc_{\mathrm{gen}} is the per-candidate generation cost. This scaling law quantifies asymptotic diminishing returns as the discovery frontier advances. Finally, we formalize human amplification through guidance, generation, and verification, explaining why expert input is most valuable near autonomous exploration barriers.

Salman Avestimehr, Ken Duffy, Muriel Médard

University of Southern California · Northeastern University · Massachusetts Institute of Technology

Adaptive SamplingAutonomous Scientific DiscoveryLanguage Model Self-Improvement
AskPDF
May 12, 2026

Learning U-Statistics with Active Inference

UU-statistics play a central role in statistical inference. In many modern applications, however, acquiring the labels required for UU-statistics is costly. Motivated by recent advances in active inference, we develop an active inference framework for UU-statistics that selectively queries informative labels to improve estimation efficiency under a fixed labeling budget, while preserving valid statistical inference. Our approach is built on the augmented inverse probability weighting UU-statistic, which is designed to incorporate the sampling rule and machine learning predictions. We characterize the optimal sampling rule that minimizes its variance and design practical sampling strategies. We further extend the framework to UU-statistic-based empirical risk minimization. Experiments on real datasets demonstrate substantial gains in estimation efficiency over baseline methods, while maintaining target coverage.

Xiaoning Wang, Yuyang Huo, Liuhua Peng +1

School of Statistics and Data Sciences, LPMC, KLM-DASR and LEBPS, Nankai University, Tianjin, China · School of Mathematics and Statistics, The University of Melbourne, Melbourne, Australia

Active InferenceU-StatisticsActive LearningAdaptive SamplingStatistical Learning TheoryEmpirical Risk Minimization
AskPDF