Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [She17], optimal transport [JST19], and bipartite matching [AJJ+22]. We develop efficient near-linear time, high-accuracy solvers for regularized variants of these games. Beyond the immediate applications of such solvers for computing Sinkhorn distances, a prominent tool in machine learning, we show that these solvers can be used to obtain improved running times for maintaining a (fractional) ε-approximate maximum matching in a dynamic decremental bipartite graph against an adaptive adversary. We give a generic framework which reduces this dynamic matching problem to solving regularized graph-structured optimization problems to high accuracy. Through our reduction framework, our regularized box-simplex game solver implies a new algorithm for dynamic decremental bipartite matching in total time tildeO(m · ε-3), from an initial graph with m edges and n nodes. We further show how to use recent advances in flow optimization [CKL+22] to improve our runtime to m1 + o(1) · ε-2, thereby demonstrating the versatility of our reduction-based approach. These results improve upon the previous best runtime of tildeO(m · ε-4) [BGS20] and illustrate the utility of using regularized optimization problem solvers for designing dynamic algorithms.