  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)
$\epsilon$-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 $\tilde{O}(m \cdot
\epsilon^{-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 $m^{1 + o(1)} \cdot \epsilon^{-2}$, thereby demonstrating the
versatility of our reduction-based approach. These results improve upon the
previous best runtime of $\tilde{O}(m \cdot \epsilon^{-4})$ [BGS20] and
illustrate the utility of using regularized optimization problem solvers for
designing dynamic algorithms.
