6 papers
Accelerating operator Sinkhorn iteration with overrelaxation
Tasuku Soma, André Uschmajew
We propose accelerated versions of the operator Sinkhorn iteration for operator scaling using successive overrelaxation. We analyze the local convergence rates of these accelerated…
Numerically stable variants of overrelaxation for operator Sinkhorn iteration
Henrik Eisenmann, Tasuku Soma, Xun Tang +1
We consider accelerated versions of the operator Sinkhorn iteration (OSI) for solving scaling problems for completely positive maps. Based on the interpretation of OSI as alternati…
-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 $…
Algorithmic aspects of semistability of quiver representations
Yuni Iwamasa, Taihei Oki, Tasuku Soma
We study the semistability of quiver representations from an algorithmic perspective. We present efficient algorithms for several fundamental computational problems on the semistab…
Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond
Tasuku Soma, Khashayar Gatmiry, Sharut Gupta +1
Distributionally robust optimization (DRO) can improve the robustness and fairness of learning methods. In this paper, we devise stochastic algorithms for a class of DRO problems i…
Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank
Taihei Oki, Tasuku Soma
Matrix representations are a powerful tool for designing efficient algorithms for combinatorial optimization problems such as matching, and linear matroid intersection and parity.…