Cover Image

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Attias, Idan, Hanneke, Steve, Ramaswami, Arvind
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

Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
by: Attias, Idan, et al.
Published: (2026)

Transductive and Learning-Augmented Online Regression
by: Raman, Vinod, et al.
Published: (2025)

Private List Learnability vs. Online List Learnability
by: Hanneke, Steve, et al.
Published: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
by: Ghuge, Rohan, et al.
Published: (2025)

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
by: Fioravanti, Simone, et al.
Published: (2024)

Sample Compression Scheme Reductions
by: Attias, Idan, et al.
Published: (2024)

Adversarial Resilience in Sequential Prediction via Abstention
by: Goel, Surbhi, et al.
Published: (2023)

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

Mistake-Bounded Language Generation
by: Kleinberg, Jon, et al.
Published: (2026)

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
by: Hanneke, Steve, et al.
Published: (2026)

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Learning on the Edge: Online Learning with Stochastic Feedback Graphs
by: Esposito, Emmanuel, et al.
Published: (2022)

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
by: Balcan, Maria-Florina, et al.
Published: (2022)

Parsimonious Learning-Augmented Online Metric Matching
by: Shin, Yongho, et al.
Published: (2026)

Learning-Augmented Online Scheduling with Parsimonious Preemption
by: Blue, Mugen, et al.
Published: (2026)

Learning-Augmented Algorithms for $k$-median via Online Learning
by: Hebbar, Anish, et al.
Published: (2026)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

Online Classification with Predictions
by: Raman, Vinod, et al.
Published: (2024)

Is Transductive Learning Equivalent to PAC Learning?
by: Dughmi, Shaddin, et al.
Published: (2024)

Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
by: Lechowicz, Adam, et al.
Published: (2023)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

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

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)

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

Learning-augmented Online Algorithm for Two-level Ski-rental Problem
by: Zhang, Keyuan, et al.
Published: (2024)

Fixed Point Computation: Beating Brute Force with Smoothed Analysis
by: Attias, Idan, et al.
Published: (2025)

Online Two-Stage Submodular Maximization
by: Nikolaou, Iasonas, et al.
Published: (2025)

Online Weighted Paging with Unknown Weights
by: Levy, Orin, et al.
Published: (2024)

Online Algorithms with Limited Data Retention
by: Immorlica, Nicole, et al.
Published: (2024)

Online Algorithms with Uncertainty-Quantified Predictions
by: Sun, Bo, et al.
Published: (2023)

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

Path-Reporting Distance Oracles with Linear Size
by: Neiman, Ofer, et al.
Published: (2024)

On the Learning Curves of Revenue Maximization
by: Hanneke, Steve, et al.
Published: (2026)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Improving Online Algorithms via ML Predictions
by: Kumar, Ravi, et al.
Published: (2024)

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

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

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

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