Search

We describe the design of our federated task processing system. Originally, the system was created to support two specific federated tasks: evaluation and tuning of on-device ML systems, primarily for the purpose of personalizing these systems. In recent years, support for an additional federated task has been added: federated learning (FL) of deep neural networks. To our knowledge, only one other system has been described in literature that supports FL at scale. We include comparisons to that system to help discuss design decisions and attached trade-offs. Finally, we describe two specific large scale personalization use cases in detail to showcase the applicability of federated tuning to on-device personalization and to highlight application specific solutions., Comment: 11 pages, 1 figure

In large-scale statistical learning, data collection and model fitting are moving increasingly toward peripheral devices---phones, watches, fitness trackers---away from centralized data collection. Concomitant with this rise in decentralized data are increasing challenges of maintaining privacy while allowing enough information to fit accurate, useful statistical models. This motivates local notions of privacy---most significantly, local differential privacy, which provides strong protections against sensitive data disclosures---where data is obfuscated before a statistician or learner can even observe it, providing strong protections to individuals' data. Yet local privacy as traditionally employed may prove too stringent for practical use, especially in modern high-dimensional statistical and machine learning problems. Consequently, we revisit the types of disclosures and adversaries against which we provide protections, considering adversaries with limited prior information and ensuring that with high probability, ensuring they cannot reconstruct an individual's data within useful tolerances. By reconceptualizing these protections, we allow more useful data release---large privacy parameters in local differential privacy---and we design new (minimax) optimal locally differentially private mechanisms for statistical learning problems for \emph{all} privacy levels. We thus present practicable approaches to large-scale locally private model training that were previously impossible, showing theoretically and empirically that we can fit large-scale image classification and language models with little degradation in utility.

Modern Graphics Processing Units (GPUs) are well provisioned to support the concurrent execution of thousands of threads. Unfortunately, different bottlenecks during execution and heterogeneous application requirements create imbalances in utilization of resources in the cores. For example, when a GPU is bottlenecked by the available off-chip memory bandwidth, its computational resources are often overwhelmingly idle, waiting for data from memory to arrive. This work describes the Core-Assisted Bottleneck Acceleration (CABA) framework that employs idle on-chip resources to alleviate different bottlenecks in GPU execution. CABA provides flexible mechanisms to automatically generate "assist warps" that execute on GPU cores to perform specific tasks that can improve GPU performance and efficiency. CABA enables the use of idle computational units and pipelines to alleviate the memory bandwidth bottleneck, e.g., by using assist warps to perform data compression to transfer less data from memory. Conversely, the same framework can be employed to handle cases where the GPU is bottlenecked by the available computational units, in which case the memory pipelines are idle and can be used by CABA to speed up computation, e.g., by performing memoization using assist warps. We provide a comprehensive design and evaluation of CABA to perform effective and flexible data compression in the GPU memory hierarchy to alleviate the memory bandwidth bottleneck. Our extensive evaluations show that CABA, when used to implement data compression, provides an average performance improvement of 41.7% (as high as 2.6X) across a variety of memory-bandwidth-sensitive GPGPU applications.

Computational molecular modeling and visualization has seen significant progress in recent years with sev- eral molecular modeling and visualization software systems in use today. Nevertheless the molecular biology community lacks techniques and tools for the rigorous analysis, quantification and visualization of the associated errors in molecular structure and its associated properties. This paper attempts at filling this vacuum with the introduction of a systematic statistical framework where each source of structural uncertainty is modeled as a ran- dom variable (RV) with a known distribution, and properties of the molecules are defined as dependent RVs. The framework consists of a theoretical basis, and an empirical implementation where the uncertainty quantification (UQ) analysis is achieved by using Chernoff-like bounds. The framework enables additionally the propagation of input structural data uncertainties, which in the molecular protein world are described as B-factors, saved with almost all X-ray models deposited in the Protein Data Bank (PDB). Our statistical framework is also able and has been applied to quantify and visualize the uncertainties in molecular properties, namely solvation interfaces and solvation free energy estimates. For each of these quantities of interest (QOI) of the molecular models we provide several novel and intuitive visualizations of the input, intermediate, and final propagated uncertainties. These methods should enable the end user achieve a more quantitative and visual evaluation of various molecular PDB models for structural and property correctness, or the lack thereof., Comment: 19 figures, 30 pages

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields. This lies at the heart of many tools in higher order Fourier analysis. In this work, we extend this result to all prime fields (of size possibly growing with $n$). We also provide a generalization to nonprime fields in the large characteristic case. However, we state all our applications in the prime field setting for the sake of simplicity of presentation. Using the above generalization to large fields as a starting point, we are also able to settle the list decoding radius of fixed degree Reed-Muller codes over growing fields. The case of fixed size fields was solved by Bhowmick and Lovett [STOC 2015], which resolved a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008]. Here, we show that the list decoding radius is equal the minimum distance of the code for all fixed degrees, even when the field size is possibly growing with $n$. Additionally, we effectively resolve the weight distribution problem for Reed-Muller codes of fixed degree over all fields, first raised in 1977 in the classic textbook by MacWilliams and Sloane [Research Problem 15.1 in Theory of Error Correcting Codes].

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas. * For any fixed finite field $\mathbb{K}$, we show that the list decoding radius of the generalized Reed Muller code over $\mathbb{K}$ equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when $|\mathbb{K}|-1$ divides the order of the code [GKZ08]. * For any fixed finite field $\mathbb{K}$, we give a polynomial time algorithm to decide whether a given polynomial $P: \mathbb{K}^n \to \mathbb{K}$ can be decomposed as a particular composition of lesser degree polynomials. This had been previously established over prime fields [Bha14, BHT15]. * For any fixed finite field $\mathbb{K}$, we prove that all locally characterized affine-invariant properties of functions $f: \mathbb{K}^n \to \mathbb{K}$ are testable with one-sided error. The same result was known when $\mathbb{K}$ is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field $\mathbb{F}$, an affine-invariant property of functions $f: \mathbb{K}^n \to \mathbb{F}$, where $\mathbb{K}$ is a growing field extension over $\mathbb{F}$, is testable if it is locally characterized by constraints of bounded weight.

We discuss the problem of constructing a small subset of a finite field containing primitive elements of the field. Given a finite field, $\mathbb{F}_{q^n}$, small $q$ and large $n$, we show that the set of all low degree polynomials contains the expected number of primitive elements. The main theorem we prove is a bound for character sums over short intervals in function fields. Our result is unconditional and slightly better than what is known (conditionally under GRH) in the integer case and might be of independent interest.

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.

Deterministically generating near-uniform point samplings of the motion groups like SO(3), SE(3) and their n-wise products SO(3)^n, SE(3)^n is fundamental to numerous applications in computational and data sciences. The natural measure of sampling quality is discrepancy. In this work, our main goal is construct low discrepancy deterministic samplings in product spaces of the motion groups. To this end, we develop a novel strategy (using a two-step discrepancy construction) that leads to an almost exponential improvement in size (from the trivial direct product). To the best of our knowledge, this is the first nontrivial construction for SO(3)^n, SE(3)^n and the hypertorus T^n. We also construct new low discrepancy samplings of S^2 and SO(3). The central component in our construction for SO(3) is an explicit construction of N points in S^2 with discrepancy \tilde{\O}(1/\sqrt{N}) with respect to convex sets, matching the bound achieved for the special case of spherical caps in \cite{ABD_12}. We also generalize the discrepancy of Cartesian product sets \cite{Chazelle04thediscrepancy} to the discrepancy of local Cartesian product sets. The tools we develop should be useful in generating low discrepancy samplings of other complicated geometric spaces.

We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both $\mathbb{Z}_p$ and $\mathbb{Z}_p^n$, for large prime $p$, although our results over $\mathbb{Z}_p^n$ require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over $\mathbb{Z}_p^n$ require the list-decodability condition. We further explore special cases of additive sources. We improve previous constructions of line sources (affine sources of dimension 1), requiring a field of size linear in $n$, rather than $\Omega(n^2)$ by Gabizon and Raz. This beats the non-explicit bound of $\Theta(n \log n)$ obtained by the probabilistic method. We then generalize this result to APs and GAPs.

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a finite field $\mathbb{F}$. The Reed-Muller code $\mathrm{RM}_{\mathbb{F}}(n,d)$ is defined by $n$-variate degree-$d$ polynomials over $\mathbb{F}$. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field $\mathbb{F}=\mathbb{F}_p$, constant degree $d$ and large $n$. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by $\delta(d)$ the normalized minimal distance of $\mathrm{RM}_{\mathbb{F}}(n,d)$, then the number of codewords in any ball of radius $\delta(d)-\varepsilon$ is bounded by $c=c(p,d,\varepsilon)$ independent of $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of $\mathbb{F}=\mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of $d=2$. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For $e \leq d$, we show that the number of codewords of $\mathrm{RM}_{\mathbb{F}}(n,d)$ in a ball of radius $\delta(e) - \varepsilon$ is bounded by $\exp(c \cdot n^{d-e})$, where $c=c(p,d,\varepsilon)$ is independent of $n$. The dependence on $n$ is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] who proved similar bounds over $\mathbb{F}_2$. The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the Schwartz-Zippel lemma to compositions of polynomials., Comment: fixed a bug in the proof of claim 5.6 (now lemma 5.5)

A Matching Vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,...,u_t)$ and $V=(v_1,...,v_t)$ where $u_i,v_j \in \mathbb{Z}_m^n$ with the following inner product pattern: for any $i$, $< u_i,v_i>=0$, and for any $i \ne j$, $< u_i,v_j> \ne 0$. A MV family is called $q$-restricted if inner products $< u_i,v_j>$ take at most $q$ different values. Our interest in MV families stems from their recent application in the construction of sub-exponential locally decodable codes (LDCs). There, $q$-restricted MV families are used to construct LDCs with $q$ queries, and there is special interest in the regime where $q$ is constant. When $m$ is a prime it is known that such constructions yield codes with exponential block length. However, for composite $m$ the behaviour is dramatically different. A recent work by Efremenko [STOC 2009] (based on an approach initiated by Yekhanin [JACM 2008]) gives the first sub-exponential LDC with constant queries. It is based on a construction of a MV family of super-polynomial size by Grolmusz [Combinatorica 2000] modulo composite $m$. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When $q$ is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus $m$ is constant (as it is in the construction of Efremenko) we prove a super-polynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman-Ruzsa conjecture over $\mathbb{Z}_m$., Comment: Fixed typos and small bugs

With the growing focus on semantic searches and interpretations, an increasing number of standardized vocabularies and ontologies are being designed and used to describe data. We investigate the querying of objects described by a tree-structured ontology. Specifically, we consider the case of finding the top-k best pairs of objects that have been annotated with terms from such an ontology when the object descriptions are available only at runtime. We consider three distance measures. The first one defines the object distance as the minimum pairwise distance between the sets of terms describing them, and the second one defines the distance as the average pairwise term distance. The third and most useful distance measure, earth mover's distance, finds the best way of matching the terms and computes the distance corresponding to this best matching. We develop lower bounds that can be aggregated progressively and utilize them to speed up the search for top-k object pairs when the earth mover's distance is used. For the minimum pairwise distance, we devise an algorithm that runs in O(D + Tk log k) time, where D is the total information size and T is the total number of terms in the ontology. We also develop a novel best-first search strategy for the average pairwise distance that utilizes lower bounds generated in an ordered manner. Experiments on real and synthetic datasets demonstrate the practicality and scalability of our algorithms., Comment: 17 pages, 13 figures