Cover Image

Sample-Adaptivity Tradeoff in On-Demand Sampling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Haghtalab, Nika, Montasser, Omar, Qiao, Mingda
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Truthfulness of Calibration Measures
by: Haghtalab, Nika, et al.
Published: (2024)

Leakage-Robust Bayesian Persuasion
by: Haghtalab, Nika, et al.
Published: (2024)

Platforms for Efficient and Incentive-Aware Collaboration
by: Haghtalab, Nika, et al.
Published: (2024)

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

Online Prediction with Limited Selectivity
by: Liu, Licheng, et al.
Published: (2025)

Limitations of Membership Queries in Testable Learning
by: Lange, Jane, et al.
Published: (2025)

On the Distance from Calibration in Sequential Prediction
by: Qiao, Mingda, et al.
Published: (2024)

Collaborative Learning with Different Labeling Functions
by: Deng, Yuyang, et al.
Published: (2024)

Smooth Nash Equilibria: Algorithms and Complexity
by: Daskalakis, Constantinos, et al.
Published: (2023)

Learning in Stackelberg Games with Non-myopic Agents
by: Haghtalab, Nika, et al.
Published: (2022)

DDPM Score Matching and Distribution Learning
by: Chewi, Sinho, et al.
Published: (2025)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
by: Epasto, Alessandro, et al.
Published: (2020)

Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
by: Qin, Yilong, et al.
Published: (2023)

Thompson Sampling Itself is Differentially Private
by: Ou, Tingting, et al.
Published: (2024)

Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
by: Gayen, Sutanu, et al.
Published: (2024)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
by: Draganov, Andrew, et al.
Published: (2024)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Optimal Dimension-Free Sampling for Regularized Classification
by: Alishahi, Meysam, et al.
Published: (2026)

Metalearning with Very Few Samples Per Task
by: Aliakbarpour, Maryam, et al.
Published: (2023)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Distribution Learning Meets Graph Structure Sampling
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
by: Attias, Idan, et al.
Published: (2025)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
by: He, Kaiwen, et al.
Published: (2025)

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
by: Rohatgi, Dhruv, et al.
Published: (2025)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)

Sample-Efficient Optimization over Generative Priors via Coarse Learnability
by: Awasthi, Pranjal, et al.
Published: (2025)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
by: Xu, Haoran, et al.
Published: (2026)

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
by: Shah, Poojan, et al.
Published: (2025)

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
by: Chauhan, Rohan, et al.
Published: (2025)

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
by: Cheng, Kangke, et al.
Published: (2026)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
by: Qin, Hao, et al.
Published: (2025)

On Tradeoffs in Learning-Augmented Algorithms
by: Benomar, Ziyad, et al.
Published: (2025)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
by: Mangoubi, Oren, et al.
Published: (2024)

Matrix Product Sketching via Coordinated Sampling
by: Daliri, Majid, et al.
Published: (2025)

Spike-and-Slab Posterior Sampling in High Dimensions
by: Kumar, Syamantak, et al.
Published: (2025)