Taira Tsuchiya

Japanese version is here．

News

• May 3, 2025: Happy to share that two papers were accepted to COLT 2025! One paper studies the learning dynamics in two-player zero-sum and multi-player general-sum games where players' actions or observations may be corrupted (preprint), and the other one investigates instance-dependent regret upper and lower bounds in two-player zero-sum games (preprint).
• Jan 22, 2025: Our paper "Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel–Young Loss Perspective and Gap-Dependent Regret Analysis," was accepted to AISTATS 2025! The preprint is available here.
• Sep 26, 2024: Two papers were accepted to NeurIPS 2024! One paper develops a general adaptive learning rate framework for online learning with a minimax regret of $\Theta(T^{2/3})$. As an application of this framework, we consier partial monitoring, graph bandits, and bandits with paid observations, and establish improved or new best-of-both-worlds regret upper bounds. The preprint and slide are available. The second paper investigates fast rates in online convex optimization over curved feasible sets. We show that if the feasible set is enclosed by a certain sphere or is uniformly convex, algorithms adaptive to the curvature of losses can achieve fast rates. Here are the preprint and slide.
• May 2, 2024: Papers on best-of-both-worlds algorithms were accepted: one for linear contextual bandits at AISTATS 2024 (paper) and the other for partial monitoring at ICML 2024 (paper)!
• Sep 22, 2023: Our paper "Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds," was accepted to NeurIPS 2023! The preprint is available here. The paper introduces the stability-penalty-adaptive (SPA) learning rate for FTRL, establishing a regret bound jointly depending on (empirical) stability and penalty. By leveraging the new adaptive learning rate framework, we present the first best-of-both-worlds (BOBW) algorithm with a sparsity-dependent bound in bandits. Furthermore, this adaptive learning rate allows us to prove the BOBW guarantee and an empirical game-dependent bound simultaneously in partial monitoring. The camera-ready version is available here.
• Jan 20, 2023: Our paper on an adaptive combinatorial semi-bandit algorithm was accepted to AISTATS 2023!
  
• Dec 22, 2022: Two papers on the best-of-both-worlds algorithm were accepted to ALT 2023 - one for partial monitoring and the other for follow-the-perturbated-leader!
  

Publications

Preprints

1. Yuki Shibukawa, Taira Tsuchiya, Shinsaku Sakaue, and Kenji Yamanishi,
   "Bandit and Delayed Feedback in Online Structured Prediction,"
   arXiv:2502.18709, 2025.
   [arXiv]
   
2. Shinji Ito, Haipeng Luo, Taira Tsuchiya, and Yue Wu, (alphabetical order)
   "Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback,"
   arXiv:2502.17625, 2025. → accepted to COLT 2025
   [arXiv]
   
3. Shinsaku Sakaue, Taira Tsuchiya, Han Bao, and Taihei Oki,
   "Online Inverse Linear Optimization: Improved Regret Bound, Robustness to Suboptimality, and Toward Tight Regret Analysis,"
   arXiv:2501.14349, 2025.
   [arXiv]
   
4. Taira Tsuchiya, Shinji Ito, and Haipeng Luo,
   "Corrupted Learning Dynamics in Games,"
   arXiv:2412.07120, 2024. → accepted to COLT 2025
   [arXiv]
   
5. Kaito Ito and Taira Tsuchiya,
   "Online Control of Linear Systems with Unbounded and Degenerate Noise,"
   arXiv:2402.10252, 2024.
   [arXiv]
   

Conference Proceedings (peer-reviewed)

1. Shinsaku Sakaue, Han Bao, and Taira Tsuchiya,
   "Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel–Young Loss Perspective and Gap-Dependent Regret Analysis,"
   In Proceedings of 28th International Conference on Artificial Intelligence and Statistics (AISTATS 2025), pp.46–54, 2025.
   [paper] [arXiv]
   
2. Taira Tsuchiya and Shinji Ito,
   "A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds,"
   In Advances in Neural Information Processing Systems 37 (NeurIPS 2024), pp.8477–8514, 2024.
   [paper] [arXiv] [slide] [poster]
   
3. Taira Tsuchiya and Shinji Ito,
   "Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets,"
   In Advances in Neural Information Processing Systems 37 (NeurIPS 2024), pp.101671–101695, 2024.
   [paper] [arXiv] [slide] [poster]
   
4. Shinji Ito, Taira Tsuchiya, and Junya Honda,
   "Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds,"
   In Proceedings of Thirty Seventh Conference on Learning Theory (COLT 2024), pp.2522–2563, 2024.
   [paper] [arXiv]
   
5. Shinsaku Sakaue, Han Bao, Taira Tsuchiya, and Taihei Oki,
   "Online Structured Prediction with Fenchel–Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss,"
   In Proceedings of Thirty Seventh Conference on Learning Theory (COLT 2024), pp.4458–4486, 2024.
   [paper] [arXiv]
   
6. Taira Tsuchiya, Shinji Ito, and Junya Honda,
   "Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring,"
   In Proceedings of 41st International Conference on Machine Learning (ICML 2024), pp.48768–48790, 2024.
   [paper] [arXiv]
   
7. Yuko Kuroki, Alberto Rumi, Taira Tsuchiya, Fabio Vitale, and Nicolò Cesa-Bianchi,
   "Best-of-Both-Worlds Algorithms for Linear Contextual Bandits,"
   In Proceedings of 27th International Conference on Artificial Intelligence and Statistics (AISTATS 2024), pp.1216–1224, 2024.
   [paper] [arXiv]
   
8. Taira Tsuchiya, Shinji Ito, and Junya Honda,
   "Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds,"
   In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), pp.47406–47437, 2023.
   [paper] [arXiv] [slide] [slide (short)] [poster]
   
9. Taira Tsuchiya, Shinji Ito, and Junya Honda,
   "Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits,"
   In Proceedings of 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023), pp.8117–8144, 2023.
   [paper] [poster]
   
10. Junya Honda, Shinji Ito, and Taira Tsuchiya,
    "Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for Bandit Problems,"
    In Proceedings of The 34th International Conference on Algorithmic Learning Theory (ALT 2023), pp.726–754, 2023.
    [paper]
    
11. Taira Tsuchiya, Shinji Ito, and Junya Honda,
    "Best-of-Both-Worlds Algorithms for Partial Monitoring,"
    In Proceedings of The 34th International Conference on Algorithmic Learning Theory (ALT 2023), pp.1484–1515, 2023.
    [paper] [arXiv] [slide]
    
12. Shinji Ito, Taira Tsuchiya, and Junya Honda,
    "Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs,"
    In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), pp.28631–28643, 2022.
    [paper] [arXiv]
    
13. Junpei Komiyama, Taira Tsuchiya, and Junya Honda,
    "Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification,"
    In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), pp.10393–10404, 2022.
    [paper] [arXiv]
    
14. Shinji Ito, Taira Tsuchiya, and Junya Honda,
    "Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds,"
    In Proceedings of Thirty Fifth Conference on Learning Theory (COLT 2022), pp.1421–1422, 2022.
    [paper (extended abstract)] [full paper on arXiv] [slide]
    
15. Taira Tsuchiya, Junya Honda, and Masashi Sugiyama,
    "Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring,"
    In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), pp.8861–8871, 2020.
    [paper] [full paper (pdf)] [arXiv] [poster]
    
16. Taira Tsuchiya, Naohiro Tawara, Tetsuji Ogawa, and Tetsunori Kobayashi,
    "Speaker Invariant Feature Extraction for Zero-Resource Languages with Adversarial Learning,"
    In Proceedings of 2018 IEEE International Conference on Acoustic, Speech, and Signal Processing (ICASSP 2018), pp.2381–2385, 2018.
    [paper] [preprint]
    

Journal Papers (peer-reviewed)

1. Taira Tsuchiya, Nontawat Charoenphakdee, Issei Sato, and Masashi Sugiyama,
   "Semi-Supervised Ordinal Regression Based on Empirical Risk Minimization,"
   Neural Computation, 33(12):3361–3412, 2021.
   [arXiv] [paper]
   

Others (invited talks / domestic conferences / domestic proceedings / workshops)

1. Taira Tsuchiya,
   "Advances in Best of Both Worlds Algorithms,"
   Presented at Workshop on the Mathematics of Online Prediction 2025 (in japanese), Feb. 23–24, 2025.
   
2. Kaito Ito and Taira Tsuchiya,
   "Regret Analysis of Online Optimal Control for Linear Systems with Unbounded Noise,"
   Presented at 27th Information-Based Induction Sciences Workshop (IBIS 2024), Nov. 4–7, 2024.
   
3. Taira Tsuchiya,
   "Best of Both Worlds Algorithms in Online Decision Making Problems,"
   Presented at Machine Learning Summer School 2024, March 4–15, 2024.
   
4. Taira Tsuchiya, Shinji Ito, Junya Honda,
   "Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds,"
   Presented at 26th Information-Based Induction Sciences Workshop (IBIS 2023), Oct. 29– Nov. 1, 2023.
   Finalist of outstanding student presentation award [link]
5. Taira Tsuchiya,
   "Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits,"
   Presented at FIT2023, Sept. 6–8, 2023.
   invited talk
6. Taira Tsuchiya, Shinji Ito, Junya Honda,
   "Best-of-Both-Worlds Algorithms for Partial Monitoring,"
   Presented at JSAI SIG-FPAI, Aug. 29–30, 2023.
   JSAI Incentive Award [link]
7. Junya Honda, Shinji Ito, and Taira Tsuchiya,
   "On the Optimality of Follow-The-Perturbated-Leader Policy for Stochastic and Adversarial Settings"
   In Proceedings of Information-Based Induction Sciences and Machine Learning Workshop, vol.122, no.325, pp.30–37, Dec 2022.
   
8. Taira Tsuchiya,
   "Best-of-Both-Worlds Algorithms for Partial Monitoring,"
   Mathematical and Information Science Research Workshop, Dec. 15, 2022.
   
9. Taira Tsuchiya, Shinji Ito, and Junya Honda,
   "Advances in Best-of-Both-Worlds Algorithms for Bandits: Structural Bandits and Variance-Dependent Regret Bounds,"
   Presented at 25th Information-Based Induction Sciences Workshop (IBIS 2022), Nov. 20–23, 2022.
   Best student presentation award [link]
10. Junpei Komiyama, Taira Tsuchiya, and Junya Honda,
    "Minimax Optimal Algorithm for Fixed-Budget Best Arm Identification,"
    Presented at 25th Information-Based Induction Sciences Workshop (IBIS 2022), Nov. 20–23, 2022.
    
11. Taira Tsuchiya,
    "Towards Practical Algorithms for Online Decision-Making,"
    Seminar talk at INRIA Lille Scool group, July 8, 2022.
    [slide]
12. Junta Fujinaga, Taira Tsuchiya, and Junya Honda,
    "On DC Relaxation of Information-directed Sampling in Combinatorial Multi-armed Bandit Problem,"
    In Proceedings of Information-Based Induction Sciences and Machine Learning Workshop, vol.122, no.90, pp.129–136, June 2022.
    
13. Taira Tsuchiya,
    "Thompson Sampling for Partial Monitoring,"
    Toshiba Symposium 2020, Dec. 22, 2020.
    
14. Taira Tsuchiya, Junya Honda, and Masashi Sugiyama,
    "Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring,"
    Presented at 23rd Information-Based Induction Sciences Workshop (IBIS 2020), Nov. 23–26, 2020.
    Outstanding presentation award [link]
15. Taira Tsuchiya, Nontawat Charoenphakdee, Issei Sato, and Masashi Sugiyama,
    "Semi-Supervised Ordinal Regression Based on Empirical Risk Minimization,"
    Presented at 22nd Information-Based Induction Sciences Workshop (IBIS 2019), Nov. 20–23, 2019.
    
16. Taira Tsuchiya, Tomoharu Iwata, and Tetsuji Ogawa,
    "Transformed Multiple Matrix Factorization: Towards Utilizing Heterogeneous Auxiliary Information,"
    In Proceedings of Information-Based Induction Sciences and Machine Learning Workshop, vol.117, no.475, pp.41–48, March 2018.
    
17. Naohiro Tawara, Taira Tsuchiya, Tetsuji Ogawa, and Tetsunori Kobayashi,
    "Speaker Feature Extraction using Adversarial Training,"
    In Proceedings of 2018 Spring Meeting of Acoustic Society of Japan (ASJ 2018), pp.141–144, March 2018.
    
18. Taira Tsuchiya, Naohiro Tawara, Tetsuji Ogawa, and Tetsunori Kobayashi,
    "Adversarial Multi-Task Learning for Extracting Speaker Invariant Feature for Zero-Resource Languages,"
    In Proceedings of 2018 Spring Meeting of Acoustic Society of Japan (ASJ 2018), pp.9–12, March 2018.
    

Grants

1. KAKENHI Grant-in-Aid for Research Activity Start-up, JSPS [link] (July 2024 – Mar. 2026)
2. ACT-X (Frontier of mathematics and information science, acceleration phase), JST [link] (Apr. 2024 – Mar. 2025)
3. ACT-X (Frontier of mathematics and information science), JST [link] (Oct. 2021 – Mar. 2024)
4. JSPS Research Fellowship for Young Scientists (DC1), JSPS [link]
5. AIP Challenge Program, JST (Aug. 2019 – Mar. 2020)

Awards

1. Ohbu Award, RIKEN, 2025 [link]
2. (IEICE TC-IBISML Research Award, IBISML, 2023)
3. JSAI Incentive Award, The Japanese Society of Artificial Intelligence, 2023 [link]
4. Finalist of Outstanding Student Presentation Award (Top 5 of approx. 100 student presentations), IBIS2023, 2023 [link]
5. Best Student Presentation Award (1st place out of approx. 100 student presentations), IBIS2022, 2022 [link]
6. Outstanding Presentation Award (Top 5 of 118 all presentations), IBIS2020, 2020 [link]
7. Travel Award, NeurIPS 2020
8. UTokyo Toyota-Dwango AI Scholarship (Apr. 2020 – Mar. 2021)
9. UTokyo Toyota-Dwango AI Scholarship (Apr. 2019 – Mar. 2020)
10. JEES-Softbank AI Scholarship (Apr. 2019 – Mar. 2020)
11. Department Award, Waseda University, 2018

Work Experiences

1. Oct. 2023 – Present: Assistant Professor, The University of Tokyo
2. Apr. 2024 – Present: Visiting Scientist, RIKEN Center for Advanced Intelligence Project
3. Apr. 2021 – Sep. 2023: Research Fellowship for Young Scientists (DC1), JSPS
4. Feb. 2019 – Sep. 2023: RIKEN Center for Advanced Intelligence Project
(Feb. 2019 – Dec. 2020, Apr. 2021 – Mar. 2022 research part-timer; Oct. 2020 – Dec. 2020 JRA; Apr. 2022 – Sep. 2023 trainee)

Education

1. Sep. 2023: Ph.D. in Department of Systems Science, Kyoto University (supervisor: Prof. Junya Honda)
   (with Department of Computer Science, The University of Tokyo for the first half of year)
2. Sep. 2020: M.S. in Department of Complexity Science, The University of Tokyo
3. Mar. 2018: B.E. in Department of Computer Science and Engineering, Waseda University

Teaching

1. Apr. 2025 – Present: Exercise course "Probabilistic Method" at Department of Mathematical Engineering and Information Physics, The University of Tokyo
2. April. 2024 – Present: Student experiment "Virtual Net Venture" at Department of Mathematical Engineering and Information Physics, The University of Tokyo
3. Sep. 2023 – Present: Multi-instructor lecture at Department of Mathematical Engineering and Information Physics, The University of Tokyo
   (2023, 2024: "Online Convex Optimization and Bandits")
4. Sep. 2023 – Present: Short exercise course "Statistical Method" at Department of Mathematical Engineering and Information Physics, The University of Tokyo

Contact

• mail: tsuchiya [at] mist.i.u-tokyo.ac.jp