Cover Image

Near-optimal Swap Regret Minimization for Convex Losses

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hu, Lunjia, Schneider, Jon, Wu, Yifan
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

Calibration Error for Decision Making
by: Hu, Lunjia, et al.
Published: (2024)

A Perfectly Truthful Calibration Measure
by: Hartline, Jason, et al.
Published: (2025)

Truthful Calibration Errors for Multi-Class Prediction
by: Lu, Yuxuan, et al.
Published: (2025)

High-Dimensional Calibration from Swap Regret
by: Fishelson, Maxwell, et al.
Published: (2025)

Testing Calibration in Nearly-Linear Time
by: Hu, Lunjia, et al.
Published: (2024)

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
by: Hu, Lunjia, et al.
Published: (2026)

Simultaneous Swap Regret Minimization via KL-Calibration
by: Luo, Haipeng, et al.
Published: (2025)

Omnipredicting Single-Index Models with Multi-Index Models
by: Hu, Lunjia, et al.
Published: (2024)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
by: Ye, Zichun, et al.
Published: (2025)

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

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

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

Near-optimal Active Regression of Single-Index Models
by: Li, Yi, et al.
Published: (2025)

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

On Computationally Efficient Multi-Class Calibration
by: Gopalan, Parikshit, et al.
Published: (2024)

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

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
by: Davoodi, Mansoor, et al.
Published: (2025)

Learning and Testing Convex Functions
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

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

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
by: He, Yuchen, et al.
Published: (2024)

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)

Chasing Convex Functions with Long-term Constraints
by: Lechowicz, Adam, et al.
Published: (2024)

Smooth Calibration and Decision Making
by: Hartline, Jason, et al.
Published: (2025)

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
by: Ye, Zichun, et al.
Published: (2025)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
by: Asi, Hilal, et al.
Published: (2024)

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

The Space Complexity of Approximating Logistic Loss
by: Dexter, Gregory, et al.
Published: (2024)

Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy
by: Wu, Ruihan, et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost
by: Vaze, Rahul, et al.
Published: (2024)

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

Optimal Scalarizations for Sublinear Hypervolume Regret
by: Zhang, Qiuyi
Published: (2023)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
by: Gu, Yuzhou, et al.
Published: (2023)

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2025)

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

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
by: Gu, Yuzhou, et al.
Published: (2024)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)