10 papers
Sensitivity and Differential Privacy in Metric Voting with Distortion below Three
Shinsaku Sakaue, Kaito Fujii, Soh Kumabe +1
The paper proposes randomized voting rules that achieve a metric distortion slightly below three while maintaining low worst‑case sensitivity and providing approximate differential…
Non-Stationary Online Structured Prediction with Surrogate Losses
Shinsaku Sakaue, Han Bao, Yuzhou Cao
Online structured prediction, including online classification as a special case, is the task of sequentially predicting labels from input features. In this setting, the surrogate r…
Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
Taihei Oki, Shinsaku Sakaue
We study online inverse linear optimization, also known as contextual recommendation, where a learner sequentially infers an agent's hidden objective vector from observed optimal a…
From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
Shinsaku Sakaue, Yuichi Yoshida
We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. By extending the batch-to…
Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness
Shinsaku Sakaue
Contextual recommendation is a variant of contextual linear bandits in which the learner observes an (optimal) action rather than a reward scalar. Recently, Sakaue et al. (2025) de…
Bandit and Delayed Feedback in Online Structured Prediction
Yuki Shibukawa, Taira Tsuchiya, Shinsaku Sakaue +1
Online structured prediction is a task of sequentially predicting outputs with complex structures based on inputs and past observations, encompassing online classification. Recent…