Cover Image

Mistake-Bounded Language Generation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kleinberg, Jon, Peale, Charlotte, Reingold, Omer
Format:	Preprint
Published:	2026
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

Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
by: Kleinberg, Jon, et al.
Published: (2025)

On Language Generation in the Limit with Bounded Memory
by: Kleinberg, Jon, et al.
Published: (2026)

Language Generation in the Limit
by: Kleinberg, Jon, et al.
Published: (2024)

Near-Optimal Algorithms for Omniprediction
by: Okoroafor, Princewill, et al.
Published: (2025)

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

Breaking the $T^{2/3}$ Barrier for Sequential Calibration
by: Dagan, Yuval, et al.
Published: (2024)

Improving Pinwheel Density Bounds for Small Minimums
by: Mishra, Ahan, et al.
Published: (2025)

Better Bounds for the Distributed Experts Problem
by: Woodruff, David P., et al.
Published: (2026)

Representative Language Generation
by: Peale, Charlotte, et al.
Published: (2025)

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

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, et al.
Published: (2026)

Improved Bounds for Online Facility Location with Predictions
by: Fotakis, Dimitris, et al.
Published: (2021)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

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

Language Generation in the Limit: Noise, Loss, and Feedback
by: Bai, Yannan, et al.
Published: (2025)

Near-optimal Swap Regret Minimization for Convex Losses
by: Hu, Lunjia, et al.
Published: (2026)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

A Note On Deterministic Submodular Maximization With Bounded Curvature
by: Li, Wenxin
Published: (2024)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
by: Rapoport, Emma, et al.
Published: (2025)

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

Towards Optimal Differentially Private Regret Bounds in Linear MDPs
by: Sahu, Sharan
Published: (2025)

A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
by: Gu, Xiang, et al.
Published: (2026)

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

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

Learning-Augmented Hierarchical Clustering
by: Braverman, Vladimir, et al.
Published: (2025)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
by: Diakonikolas, Ilias, et al.
Published: (2025)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
by: Karpov, Nikolai, et al.
Published: (2025)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
by: Oki, Taihei, et al.
Published: (2026)

Improved Margin Generalization Bounds for Voting Classifiers
by: Høgsgaard, Mikael Møller, et al.
Published: (2025)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
by: Assadi, Sepehr, et al.
Published: (2023)

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

Water-Filling is Universally Minimax Optimal
by: Banerjee, Siddhartha, et al.
Published: (2026)

Testable Learning of General Halfspaces under Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2026)

Generalized Top-k Mallows Model for Ranked Choices
by: Haddadan, Shahrzad, et al.
Published: (2025)

A Faster Generalized Two-Stage Approximate Top-K
by: Samaga, Yashas, et al.
Published: (2025)

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)