Shinsaku Sakaue
  • Bio
  • Experience
  • Papers
  • Misc
  • Recent & Upcoming Talks
    • Example Talk
  • All Papers
    • From average sensitivity to small-loss regret bounds under random-order model
    • Simple projection-free algorithm for contextual recommendation with logarithmic regret and robustness
    • Tight regret bound for online inverse linear optimization via multiscale matrix weights
    • Submodular many-to-one matching under matroid constraints
    • Sensitivity and differential privacy in metric voting with distortion below three
    • A sampling-based relaxation approach to contextual inverse optimization
    • Finite and corruption-robust regret bounds in online inverse linear optimization under M-convex action sets
    • Non-stationary online structured prediction with surrogate losses
    • Any-stepsize gradient descent for separable data under Fenchel–Young losses
    • Bandit and delayed feedback in online structured prediction
    • Online inverse linear optimization: Efficient logarithmic-regret algorithm, robustness to suboptimality, and lower bound
    • Rate constant matrix contraction method for stiff master equations with detailed balance
    • Learning to generate projections for reducing dimensionality of heterogeneous linear programming problems
    • Inverse optimization with prediction market: A characterization of scoring rules for elciting system states
    • Revisiting online learning approach to inverse linear optimization: A Fenchel–Young loss perspective and gap-dependent regret analysis
    • Generalization bound and learning methods for data-driven projections in linear programming
    • No-regret $\mathrm{M}^\natural$-concave function maximization: Stochastic bandit algorithms and NP-hardness of adversarial full-information setting
    • Online structured prediction with Fenchel–Young losses and improved surrogate regret for online multiclass classification with logistic loss
    • Faster discrete convex function minimization with predictions: The $\mathrm{M}$-convex case
    • Rethinking warm-starts with predictions: Learning predictions close to sets of optimal solutions for faster $\mathrm{L}$-/$\mathrm{L}^\natural$-convex function minimization
    • Nearly tight spectral sparsification of directed hypergraphs
    • Making individually fair predictions with causal pathways
    • Improved generalization bound and learning of sparsity patterns for data-driven low-rank approximation
    • Exact and scalable network reliability evaluation for probabilistic correlated failures
    • Discrete-convex-analysis-based framework for warm-starting algorithms with predictions
    • Lazy and fast greedy MAP inference for determinantal point process
    • Sample complexity of learning heuristic functions for greedy-best-first and A* search
    • Sparse regularized optimal transport with deformed $q$-entropy
    • Algorithmic Bayesian persuasion with combinatorial actions
    • Selecting molecules with diverse structures and properties by maximizing submodular functions of descriptors learned with graph neural networks
    • Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games
    • Differentiable greedy algorithm for monotone submodular maximization: Guarantees, gradient estimators, and applications
    • Learning individually fair classifier with path-specific causal-effect constraint
    • Guarantees of stochastic greedy algorithms for non-monotone submodular maximization with cardinality constraints
    • On maximization of weakly modular functions: Guarantees of multi-stage algorithms, tractability, and hardness
    • Practical Frank–Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games
    • Best-first search algorithm for non-convex sparse minimization
    • Beyond adaptive submodularity: Approximation guarantees of greedy policy with adaptive submodularity ratio
    • Greedy and IHT algorithms for non-convex optimization with monotone costs of non-zeros
    • Provable fast greedy compressive summarization with any monotone submodular function
    • Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams
    • Accelerated best-first search with upper-bound computation for submodular function maximization
    • Submodular function maximization over graphs via zero-suppressed binary decision diagrams
    • Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems
    • On maximizing a monotone $k$-submodular function subject to a matroid constraint
    • Using multiparameter eigenvalues for solving quadratic programming with quadratic equality constraints
    • Solving generalized CDT problems via two-parameter eigenvalues
  • Misc
    • Optimal Dynamic Regret via Multiple Learning Rates
  • Projects
  • Blog
    • 🎉 Easily create your own simple yet highly customizable blog
    • 🧠 Sharpen your thinking with a second brain
    • 📈 Communicate your results effectively with the best data visualizations
    • 👩🏼‍🏫 Teach academic courses
    • ✅ Manage your projects
  • Blog
    • 🎉 Easily create your own simple yet highly customizable blog
  • Projects
    • Pandas
    • PyTorch
    • scikit-learn
  • Experience
  • Teaching
    • Learn JavaScript
    • Learn Python
  • Publications
    • An example preprint / working paper
    • An example journal article
    • An example conference paper

From average sensitivity to small-loss regret bounds under random-order model

Sep 25, 2026·
Shinsaku Sakaue
,
Yuichi Yoshida
· 0 min read
PAPER
Type
Conference paper
Publication
Advances in Neural Information Processing Systems (NeurIPS), Oral, to appear
Last updated on Sep 25, 2026
Simple projection-free algorithm for contextual recommendation with logarithmic regret and robustness Sep 25, 2026 →

© 2026 Me. This work is licensed under CC BY NC ND 4.0

Published with Hugo Blox Builder — the free, open source website builder that empowers creators.