16 citations · 35 across the 27 of their papers we have counts for
32 papers
Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes
Han Bao, Shinsaku Sakaue, Kazuki Watanabe
Safety verification of a Markov decision process (MDP) asks whether the probabilities of reaching several failure states jointly lie in a convex safe region under every scheduler.…
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Shinsaku Sakaue
We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from…
Sensitivity and Differential Privacy in Metric Voting with Distortion below Three
Shinsaku Sakaue, Kaito Fujii, Soh Kumabe +1
Voting rules aggregate individual preferences into collective decisions, but the rankings they receive contain only ordinal information. The metric distortion framework studies ord…
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…
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…
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…
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…
Revisiting Online Learning Approach to Inverse Linear Optimization: A FenchelYoung Loss Perspective and Gap-Dependent Regret Analysis
Shinsaku Sakaue, Han Bao, Taira Tsuchiya
This paper revisits the online learning approach to inverse linear optimization studied by Bärmann et al. (2017), where the goal is to infer an unknown linear objective function of…
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…
Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses
Han Bao, Shinsaku Sakaue, Yuki Takezawa
The gradient descent (GD) has been one of the most common optimizer in machine learning. In particular, the loss landscape of a neural network is typically sharpened during the ini…
Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
Shinsaku Sakaue, Taira Tsuchiya, Han Bao +1
In online inverse linear optimization, a learner observes time-varying sets of feasible actions and an agent's optimal actions, selected by solving linear optimization over the fea…
No-Regret M-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
Taihei Oki, Shinsaku Sakaue
M-concave functions, a.k.a. gross substitute valuation functions, play a fundamental role in many fields, including discrete mathematics and economics. In practice,…
Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss
Shinsaku Sakaue, Han Bao, Taira Tsuchiya +1
This paper studies online structured prediction with full-information feedback. For online multiclass classification, Van der Hoeven (2020) established \emph{finite} surrogate regr…
Rate Constant Matrix Contraction Method for Stiff Master Equations with Detailed Balance
Satoru Iwata, Taihei Oki, Shinsaku Sakaue
This paper considers master equations for Markovian kinetic schemes that possess the detailed balance property. Chemical kinetics, as a prime example, often yields large-scale, hig…
Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
Shinsaku Sakaue, Taihei Oki
How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question. Recently, there has been a surge of interest in reducing LP sizes using random projection…
Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case
Taihei Oki, Shinsaku Sakaue
Recent years have seen a growing interest in accelerating optimization algorithms with machine-learned predictions. Sakaue and Oki (NeurIPS 2022) have developed a general framework…
Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster -/-Convex Function Minimization
Shinsaku Sakaue, Taihei Oki
An emerging line of work has shown that machine-learned predictions are useful to warm-start algorithms for discrete optimization problems, such as bipartite matching. Previous stu…
Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation
Shinsaku Sakaue, Taihei Oki
Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a genera…
Lazy and Fast Greedy MAP Inference for Determinantal Point Process
Shinichi Hemmi, Taihei Oki, Shinsaku Sakaue +2
The maximum a posteriori (MAP) inference for determinantal point processes (DPPs) is crucial for selecting diverse items in many machine learning applications. Although DPP MAP inf…
Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search
Shinsaku Sakaue, Taihei Oki
Greedy best-first search (GBFS) and A* search (A*) are popular algorithms for path-finding on large graphs. Both use so-called heuristic functions, which estimate how close a verte…
Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
Shinsaku Sakaue, Taihei Oki
Augmenting algorithms with learned predictions is a promising approach for going beyond worst-case bounds. Dinitz, Im, Lavastida, Moseley, and Vassilvitskii~(2021) have demonstrate…
Nearly Tight Spectral Sparsification of Directed Hypergraphs by a Simple Iterative Sampling Algorithm
Kazusato Oko, Shinsaku Sakaue, Shin-ichi Tanigawa
Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirect…
Algorithmic Bayesian persuasion with combinatorial actions
Kaito Fujii, Shinsaku Sakaue
Bayesian persuasion is a model for understanding strategic information revelation: an agent with an informational advantage, called a sender, strategically discloses information by…
Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games
Shinsaku Sakaue, Kengo Nakamura
We address Stackelberg models of combinatorial congestion games (CCGs); we aim to optimize the parameters of CCGs so that the selfish behavior of non-atomic players attains desirab…