Toward Optimal Semi-streaming Algorithm for (1+ε)-approximate Maximum Matching @SimonsInstituteTOC

Simons Institute | Toward Optimal Semi-streaming Algorithm for (1+ε)-approximate Maximum Matching @SimonsInstituteTOC | Uploaded 1 week ago | Updated 16 hours ago
Wen-Horng Sheu (UC Davis)
https://simons.berkeley.edu/talks/wen-horng-sheu-uc-davis-2024-08-07
Workshop on Local Algorithms (WoLA)

We design a deterministic algorithm for the (1+ε)-approximate maximum matching problem. As our main result, we show that this problem can be solved in O(ε^-6) semi-streaming passes, improving the O(ε^-19) pass-complexity obtained by the algorithm of [Fischer, Mitrović, and Uitto, STOC'22]. This significantly progresses toward resolving Open question 2 from [Assadi, SOSA'24]. By utilizing the framework proposed in [FMU'22], our algorithm yields the same round complexity speed-up for computing a (1+ε)-approximate maximum matching in Massively Parallel Computation and CONGEST models.

The data structures our algorithm maintains are phrased in the language of blossoms and represented by alternating trees. This approach essentially allows us to simplify the correctness analysis by effectively treating certain aspects as if they were operating on bipartite graphs, thus circumventing certain technical intricacies appearing in prior work.

Attractor decompositions in games and automata

Debugging genomic profiling experiments and predictive models with interpretation tools

A Theory of Multi-objective Machine Learning

$Large Scale Private Learning on Data Streams, and the BLTs Abhradeep Guha Thakurta (Google DeepMind) https://simons.berkeley.edu/talks/abhradeep-guha-thakurta-google-deepmind-2024-06-18 Extroverted Sublinear Algorithms In recent years, Differentially Private Follow the Regularized Leader (DP-FTRL) style algorithms have become increasingly popular for training large models over data streams, e.g., in training DP models for Gboard next-word prediction (https://research.google/blog/federated-learning-with-formal-differentia… and https://arxiv.org/abs/2305.18465). At the heart of these algorithms is a correlated noise addition mechanism that factorizes a square lower triangular matrix of all ones (A=BC) and adds noise BZ (with Z ~ N(0,σ^2)^{training steps x dimensions}) to the prefix sum of the gradients observed during training. Prior work required generating and storing the noise matrix in advance, which is prohibitively expensive for large-scale model training. In this talk, we introduce a new algorithmic construction called the Buffered Linear Toeplitz operator (BLT) that allows generating the noise required for DP in a streaming fashion while requiring a buffer size of approximately log^2(training steps) x dimensions. Furthermore, compared to the class of all Lower Triangular Toeplitz (LTT) factorizations (i.e., B and C being LTT), BLTs are only off by an additive constant in terms of utility under standard error metrics. The talk will draw ideas from rational function approximations and constant recurrence sequences for the construction of BLTs. The talk will also demonstrate the practicality of this work through simulation experiments. The talk is primarily based on https://arxiv.org/pdf/2404.16706, and is a joint work with Krishnamurthy (Dj) Dvijotham, Brendan McMahan, Krishna Pillutla, and Thomas Steinke.$

Space is a latent sequence: A theory of hippocampus and PFC

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set

Towards Understanding Generalization Properties of Score-Based Losses