Hyperparameter (HP) tuning in deep learning is an expensive process, prohibitively so for neural networks (NNs) with billions of parameters.We show that, in the recently discovered Maximal Update Parametrization ($\mu$P), many optimal HPs remain stable even as model size changes. This leads to a new HP tuning paradigm we call *$\mu$Transfer*: parametrize the target model in $\mu$P, tune the HP indirectly on a smaller model, and *zero-shot transfer* them to the full-sized model, i.e., without directly tuning the latter at all.We verify $\mu$Transfer on Transformer and ResNet. For example, 1) by transferring pretraining HPs from a model of 13M parameters, we outperform published numbers of BERT-large (350M parameters), with a total tuning cost equivalent to pretraining BERT-large once; 2) by transferring from 40M parameters, we outperform published numbers of the 6.7B GPT-3 model, with tuning cost only 7% of total pretraining cost. A Pytorch implementation of our technique can be found at github.com/microsoft/mup. See arxiv.org for the full, up-to-date version of this work.

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted m-edge and n-node graphs require Ω(min{nω, mn}) time (for 2 ≤ ω < 2.373). In this paper, we drastically improve these runtimes as follows: • Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in Õ(m) time computes an Õ(1)-multiplicative approximation of the girth as well as an Õ(1)-multiplicative roundtrip spanner with Õ(n) edges with high probability (w.h.p). • Nearly Tight Additive Approximations: For unweighted graphs and any a ∊ (0, 1) we give an algorithm that in Õ(mn1–a) time computes an O(na)-additive approximation of the girth, w.h.p. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial boolean matrix multiplication. We also show that if the girth is O(na), then the same guarantee can be achieved via a deterministic algorithm. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than Ω(mn) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.

In the communication problem UR (universal relation) [25], Alice and Bob respectively receive x, y ∈ {0, 1}nwith the promise that x ≠ y. The last player to receive a message must output an index i such that xi≠ yi. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly Θ(min{n, log(1/δ) log2(n/log(1/δ) )}) for failure probability δ. Our lower bound holds even if promised support(y) ⊂ support(x). As a corollary, we obtain optimal lower bounds for ℓp-sampling in strict turnstile streams for 0 ≤ pnat all points in the stream. We give two different proofs of our main result. The first proof demonstrates that any algorithm A solving sampling problems in turnstile streams in low memory can be used to encode subsets of [n] of certain sizes into a number of bits below the information theoretic minimum. Our encoder makes adaptive queries to A throughout its execution, but done carefully so as to not violate correctness. This is accomplished by injecting random noise into the encoder's interactions with A, which is loosely motivated by techniques in differential privacy. Our correctness analysis involves understanding the ability of A to correctly answer adaptive queries which have positive but bounded mutual information with A's internal randomness, and may be of independent interest in the newly emerging area of adaptive data analysis with a theoretical computer science lens. Our second proof is via a novel randomized reduction from Augmented Indexing [30] which needs to interact with A adaptively. To handle the adaptivity we identify certain likely interaction patterns and union bound over them to guarantee correct interaction on all of them. To guarantee correctness, it is important that the interaction hides some of its randomness from A in the reduction.

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition, which is a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple observation shows that every graph $G$ on $n$ vertices with $m$ edges can be decomposed in $O(mn)$ time into cycles of length at most $2 \log n,$ and at most $2n$ extra edges. We give an $(m^{1+o(1)})$-time algorithm for constructing a short cycle decomposition, with cycles of length $n^{o(1)},$ and $n^{1+o(1)}$ extra edges. Both the existential and algorithmic variants of this decomposition enable us to make the following progress on several open problems in randomized graph algorithms: (1) We present an algorithm that runs in time $m^{1+o(1)}\varepsilon^{-1.5}$ and returns $(1\pm\varepsilon)$-approximations to effective resistances of all edges, improving over the previous best runtime of $\widetilde{{O}}(\min\{m\varepsilon^{-2}, n^{2} \varepsilon^{-1}\})$. This routine in turn gives an algorithm for approximating the determinant of a graph Laplacian up to a factor of $(1\pm \varepsilon)$ in $m^{1 + o(1)} + n^{\nicefrac{15}{8}+o(1)}\varepsilon^{-\nicefrac{7}{4}}$ time. (2) We show the existence of graphical spectral sketches with about $n\varepsilon^{-1}$ edges, and also give efficient algorithms to construct them. A graphical spectral sketch is a distribution over sparse graphs $H$ such that for a fixed vector ${\mathit{x}}$, we have ${{x}}^{\top} {L}_H {{x}} = (1\pm\varepsilon) {{x}}^{\top} {L}_G {{x}}$ and ${{x}}^{\top} {L}^{+}_H {{x}} = (1\pm\varepsilon) {{x}}^{\top} {L}^{+}_G {{x}}$ with high probability, where ${L}$ is the graph Laplacian and ${L}^{+}$ is its pseudoinverse. This implies the existence of resistance sparsifiers with about $n \varepsilon^{-1}$ edges that preserve the effective resistance between every pair of vertices up to $(1\pm\varepsilon)$. (3) By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of Eulerian directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for constructing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvement in each of these algorithms.

We develop new methods based on graph motifs for graph clustering, allowing more efficient detection of communities within networks. We focus on triangles within graphs, but our techniques extend to other clique motifs as well. Our intuition, which has been suggested but not formalized similarly in previous works, is that triangles are a better signature of community than edges. We therefore generalize the notion of conductance for a graph to triangle conductance, where the edges are weighted according to the number of triangles containing the edge. This methodology allows us to develop variations of several existing clustering techniques, including spectral clustering, that minimize triangles split by the cluster instead of edges cut by the cluster. We provide theoretical results in a planted partition model to demonstrate the potential for triangle conductance in clustering problems. We then show experimentally the effectiveness of our methods to multiple applications in machine learning and graph mining.

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time | V ( H )| o (| V ( G )|) . We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of | V ( H )| o (| V ( H )|) -time algorithm deciding if graph G is a subgraph of H . For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

Finding a small spectral approximation for a tall $n \times d$ matrix $A$ is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows are sampled from those of $A$. Row sampling improves interpretability, saves space when $A$ is sparse, and preserves row structure, which is especially important, for example, when $A$ represents a graph. However, correctly sampling rows from $A$ can be costly when the matrix is large and cannot be stored and processed in memory. Hence, a number of recent publications focus on row sampling in the streaming setting, using little more space than what is required to store the outputted approximation [KL13, KLM+14]. Inspired by a growing body of work on online algorithms for machine learning and data analysis, we extend this work to a more restrictive online setting: we read rows of $A$ one by one and immediately decide whether each row should be kept in the spectral approximation or discarded, without ever retracting these decisions. We present an extremely simple algorithm that approximates $A$ up to multiplicative error $ε$ and additive error $δ$ using $O(d \log d \log(ε||A||_2/δ)/ε^2)$ online samples, with memory overhead proportional to the cost of storing the spectral approximation. We also present an algorithm that uses $O(d^2$) memory but only requires $O(d\log(ε||A||_2/δ)/ε^2)$ samples, which we show is optimal. Our methods are clean and intuitive, allow for lower memory usage than prior work, and expose new theoretical properties of leverage score based matrix approximation.

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time |V (H)|o(|V (G)|). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |V (H)|o(|V (H)|)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

In this paper we provide faster algorithms for solving the geometric median problem: given n points in d compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite a long history of research the previous fastest running times for computing a (1+є)-approximate geometric median were O(d· n4/3є−8/3) by Chin et. al, Õ(dexpє−4logє−1) by Badoiu et. al, O(nd+poly(d,є−1)) by Feldman and Langberg, and the polynomial running time of O((nd)O(1)log1/є) by Parrilo and Sturmfels and Xue and Ye.

We introduce the notion of balance for directed graphs: a weighted directed graph is α-balanced if for every cut S ⊆ V, the total weight of edges going from S to V∖ S is within factor α of the total weight of edges going from V∖ S to S. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with α = 1) and residual graphs of (1+є)-approximate undirected maximum flows (with α=O(1/є)).

Extracting dense subgraphs from large graphs is a key primitive in a variety of graph mining applications, ranging from mining social networks and the Web graph to bioinformatics [41]. In this paper we focus on a family of poly-time solvable formulations, known as the k-clique densest subgraph problem (k-Clique-DSP) [57]. When k=2, the problem becomes the well-known densest subgraph problem (DSP) [22, 31, 33, 39]. Our main contribution is a sampling scheme that gives densest subgraph sparsifier, yielding a randomized algorithm that produces high-quality approximations while providing significant speedups and improved space complexity. We also extend this family of formulations to bipartite graphs by introducing the (p,q)-biclique densest subgraph problem ((p,q)-Biclique-DSP), and devise an exact algorithm that can treat both clique and biclique densities in a unified way.

We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with m non-zero entries to a relative error of ε in O(m log1/2 n logc n log(1/ε)) time. Our approach follows the recursive preconditioning framework, which aims to reduce graphs to trees using iterative methods. We improve two key components of this framework: random sampling and tree embeddings. Both of these components are used in a variety of other algorithms, and our approach also extends to the dual problem of computing electrical flows.