DEPENDENT ROUNDING SPEEDUPS AND APPLICATIONS

Abstract

Dependent rounding is a rounding method on bipartite graphs with several good theoret-ical properties, including negative correlation and total degree preservation. However, a naive implementation of the dependent rounding algorithm runs in at least cubic time with respect to the number of vertices present, which is untenable for larger graphs. To alleviate this problem, we introduce several speedup methods, including reformulations and parallelism. These methods can be used to reduce the runtime of dependent rounding by several orders of magnitude, making it feasible to use repeatedly on large graphs. We also present potential applications of dependent rounding enabled by these speedups. These applications are largely modifications to machine learning algorithms, such as SignSGD, that include dependent rounding in order to improve a rounding method or make a sampling method more consistent. We hope that dependent round- ing can serve as a new method to improve machine learning techniques both theoretically and empirically.