Cover Image

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sakaue, Shinsaku, Yoshida, Yuichi
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

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

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

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

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

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

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Average Sensitivity of Hierarchical $k$-Median Clustering
by: Li, Shijie, et al.
Published: (2025)

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

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

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

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, 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)

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

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

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

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

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)

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

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

Tolerant Testing for Unique Games
by: Yoshida, Yuichi
Published: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
by: Yoshida, Yuichi
Published: (2026)

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)

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

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

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, 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)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

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

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

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

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

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

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

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)