6 papers
Replicability is Asymptotically Free in Multi-armed Bandits
Junpei Komiyama, Shinji Ito, Yuichi Yoshida +1
We consider a replicable stochastic multi-armed bandit algorithm that ensures, with high probability, that the algorithm's sequence of actions is not affected by the randomness inh…
Low-Sensitivity Matching via Sampling from Gibbs Distributions
Yuichi Yoshida, Zihan Zhang
In this work, we study the maximum matching problem from the perspective of sensitivity. The sensitivity of an algorithm on a graph is defined as the maximum Wasserstein di…
Pointwise Lipschitz Continuous Graph Algorithms
Quanquan C. Liu, Grigoris Velegkas, Yuichi Yoshida +1
In many real-world applications, it is undesirable to drastically change the problem solution after a small perturbation in the input, as unstable outputs can lead to costly transa…
-Approximation Algorithms for Bipartiteness Ratio
Tasuku Soma, Mingquan Ye, Yuichi Yoshida
We propose an -approximation algorithm for the bipartiteness ratio of undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where $…
Sensitivity Lower Bounds for Approximaiton Algorithms
Noah Fleming, Yuichi Yoshida
Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitiv…
From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning
Max Hopkins, Sihan Liu, Christopher Ye +1
The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2…