Cover Image

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Rohatgi, Dhruv, Block, Adam, Huang, Audrey, Krishnamurthy, Akshay, Foster, Dylan J.
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

On Learning Parities with Dependent Noise
by: Golowich, Noah, et al.
Published: (2024)

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

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
by: Moitra, Ankur, et al.
Published: (2026)

Steering diffusion models with quadratic rewards: a fine-grained analysis
by: Moitra, Ankur, et al.
Published: (2026)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

Improved Time-Space Tradeoffs for 3SUM-Indexing
by: Dinur, Itai, et al.
Published: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
by: Woodruff, David P., et al.
Published: (2024)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
by: Amir, Amihood, et al.
Published: (2026)

On Computing Pairwise Statistics with Local Differential Privacy
by: Ghazi, Badih, et al.
Published: (2024)

Bin Packing under Random-Order: Breaking the Barrier of 3/2
by: Hebbar, Anish, et al.
Published: (2024)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
by: Chatziafratis, Vaggos, et al.
Published: (2023)

Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation
by: Jain, Palak, et al.
Published: (2024)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

New Statistical and Computational Results for Learning Junta Distributions
by: Beretta, Lorenzo
Published: (2025)

Directed Token Sliding
by: Banerjee, Niranka, et al.
Published: (2024)

Sample-Adaptivity Tradeoff in On-Demand Sampling
by: Haghtalab, Nika, et al.
Published: (2025)

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

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

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Learning Juntas under Markov Random Fields
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Revisiting Token Sliding on Chordal Graphs
by: Adak, Rajat, et al.
Published: (2025)

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
by: Diakonikolas, Ilias, et al.
Published: (2025)

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

On Sketching Trimmed Statistics
by: Lin, Honghao, et al.
Published: (2025)

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

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

Compression Barriers for Autoregressive Transformers
by: Haris, Themistoklis, et al.
Published: (2025)

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
by: Bousquet, Nicolas, et al.
Published: (2025)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

Last Truck Scheduling for Middle-mile Next-day Delivery Coverage
by: Benidis, Konstantinos, et al.
Published: (2023)

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

Improved Approximations for Flexible Network Design
by: Hyatt-Denesik, Dylan, et al.
Published: (2024)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

A Separator for Minor-Free Graphs Beyond the Flow Barrier
by: Le, Hung
Published: (2026)