Buchumschlag

Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Montasser, Omar, Shetty, Abhishek, Zhivotovskiy, Nikita
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Derandomizing Multi-Distribution Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2024)

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
von: Chen, Fan, et al.
Veröffentlicht: (2026)

Refined Risk Bounds for Unbounded Losses via Transductive Priors
von: Qian, Jian, et al.
Veröffentlicht: (2024)

Lower Bounds for Greedy Teaching Set Constructions
von: Compton, Spencer, et al.
Veröffentlicht: (2025)

Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
von: Huang, Zhiming, et al.
Veröffentlicht: (2026)

Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective
von: Block, Adam, et al.
Veröffentlicht: (2025)

Worst-Case Regret Bounds for Exploration via Randomized Value Functions
von: Russo, Daniel
Veröffentlicht: (2019)

Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
von: Supantha, Subhamon, et al.
Veröffentlicht: (2025)

Strategic Classification under Unknown Personalized Manipulation
von: Shao, Han, et al.
Veröffentlicht: (2023)

Partition Function Estimation under Bounded f-Divergence
von: Block, Adam, et al.
Veröffentlicht: (2026)

Efficient Logistic Regression with Mixture of Sigmoids
von: Di Gennaro, Federico, et al.
Veröffentlicht: (2026)

CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision
von: Altabaa, Awni, et al.
Veröffentlicht: (2025)

Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization
von: Montasser, Omar, et al.
Veröffentlicht: (2024)

Explainable Clustering Beyond Worst-Case Guarantees
von: Fleissner, Maximilian, et al.
Veröffentlicht: (2024)

Consistency and Inconsistency in $K$-Means Clustering
von: Blanchard, Moïse, et al.
Veröffentlicht: (2025)

Contextual Decision-Making with Knapsacks Beyond the Worst Case
von: Chen, Zhaohua, et al.
Veröffentlicht: (2022)

Distribution Learning with Valid Outputs Beyond the Worst-Case
von: Rittler, Nick, et al.
Veröffentlicht: (2024)

Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise
von: Hanashiro, Rafael, et al.
Veröffentlicht: (2026)

Gradient-Variation Regret Bounds for Unconstrained Online Learning
von: Zhao, Yuheng, et al.
Veröffentlicht: (2026)

Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret
von: Zhong, Han, et al.
Veröffentlicht: (2023)

Sample-Adaptivity Tradeoff in On-Demand Sampling
von: Haghtalab, Nika, et al.
Veröffentlicht: (2025)

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
von: Blanchard, Moïse, et al.
Veröffentlicht: (2026)

Revisiting Agnostic PAC Learning
von: Hanneke, Steve, et al.
Veröffentlicht: (2024)

Memorization With Neural Nets: Going Beyond the Worst Case
von: Dirksen, Sjoerd, et al.
Veröffentlicht: (2023)

Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
von: Li, Mingyi, et al.
Veröffentlicht: (2026)

Improved Kernel Alignment Regret Bound for Online Kernel Learning
von: Li, Junfan, et al.
Veröffentlicht: (2022)

Online-to-PAC Conversions: Generalization Bounds via Regret Analysis
von: Lugosi, Gábor, et al.
Veröffentlicht: (2023)

Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds
von: Tuci, Mario, et al.
Veröffentlicht: (2025)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
von: Silwal, Sandeep, et al.
Veröffentlicht: (2025)

Worst-case Error Bounds for Online Learning of Smooth Functions
von: Xie, Weian
Veröffentlicht: (2025)

Dimension-free Private Mean Estimation for Anisotropic Distributions
von: Dagan, Yuval, et al.
Veröffentlicht: (2024)

Online Prediction of Stochastic Sequences with High Probability Regret Bounds
von: Frey, Matthias, et al.
Veröffentlicht: (2026)

Regret Bounds for Robust Online Decision Making
von: Appel, Alexander, et al.
Veröffentlicht: (2025)

Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes
von: Moon, Sang Bin, et al.
Veröffentlicht: (2024)

$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
von: Vaze, Rahul, et al.
Veröffentlicht: (2025)

Majority-of-Three: The Simplest Optimal Learner?
von: Aden-Ali, Ishaq, et al.
Veröffentlicht: (2024)

(Im)possibility of Automated Hallucination Detection in Large Language Models
von: Karbasi, Amin, et al.
Veröffentlicht: (2025)

Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
von: Compton, Spencer, et al.
Veröffentlicht: (2026)

Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints
von: Bechavod, Yahav, et al.
Veröffentlicht: (2025)

Improved Regret Bounds for Online Fair Division with Bandit Learning
von: Schiffer, Benjamin, et al.
Veröffentlicht: (2025)