OpenRaiser/Intern-Atlas huggingface dataset:
Hoplite: Efficient and Fault-Tolerant Collective Communication for Task-Based Distributed Systems
Venue: arXiv cs.DC 2021
Year: 2021

Task-based distributed frameworks (e.g., Ray, Dask, Hydro) have become increasingly popular for distributed applications that contain asynchronous and dynamic workloads, including asynchronous gradient descent, reinforcement learning, and model serving. As more data-intensive applications move to run on top of task-based systems, collective communication efficiency has become an important problem. Unfortunately, traditional collective communication libraries (e.g., MPI, Horovod, NCCL) are an ill fit, because they require the communication schedule to be known before runtime and they do not provide fault tolerance. We design and implement Hoplite, an efficient and fault-tolerant collective communication layer for task-based distributed systems. Our key technique is to compute data transfer schedules on the fly and execute the schedules efficiently through fine-grained pipelining. At the same time, when a task fails, the data transfer schedule adapts quickly to allow other tasks to keep making progress. We apply Hoplite to a popular task-based distributed framework, Ray. We show that Hoplite speeds up asynchronous stochastic gradient descent, reinforcement learning, and serving an ensemble of machine learning models that are difficult to execute efficiently with traditional collective communication by up to 7.8x, 3.9x, and 3.3x, respectively.
Maxmin Q-learning: Controlling the Estimation Bias of Q-learning
Venue: arXiv cs.LG 2021
Year: 2021

Q-learning suffers from overestimation bias, because it approximates the maximum action value using the maximum estimated action value. Algorithms have been proposed to reduce overestimation bias, but we lack an understanding of how bias interacts with performance, and the extent to which existing algorithms mitigate bias. In this paper, we 1) highlight that the effect of overestimation bias on learning efficiency is environment-dependent; 2) propose a generalization of Q-learning, called \emph{Maxmin Q-learning}, which provides a parameter to flexibly control bias; 3) show theoretically that there exists a parameter choice for Maxmin Q-learning that leads to unbiased estimation with a lower approximation variance than Q-learning; and 4) prove the convergence of our algorithm in the tabular case, as well as convergence of several previous Q-learning variants, using a novel Generalized Q-learning framework. We empirically verify that our algorithm better controls estimation bias in toy environments, and that it achieves superior performance on several benchmark problems.
Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data
Venue: arXiv cs.LG 2021
Year: 2021

In many applications, one works with neural network models trained by someone else. For such pretrained models, one may not have access to training data or test data. Moreover, one may not know details about the model, e.g., the specifics of the training data, the loss function, the hyperparameter values, etc. Given one or many pretrained models, it is a challenge to say anything about the expected performance or quality of the models. Here, we address this challenge by providing a detailed meta-analysis of hundreds of publicly-available pretrained models. We examine norm based capacity control metrics as well as power law based metrics from the recently-developed Theory of Heavy-Tailed Self Regularization. We find that norm based metrics correlate well with reported test accuracies for well-trained models, but that they often cannot distinguish well-trained versus poorly-trained models. We also find that power law based metrics can do much better -- quantitatively better at discriminating among series of well-trained models with a given architecture; and qualitatively better at discriminating well-trained versus poorly-trained models. These methods can be used to identify when a pretrained neural network has problems that cannot be detected simply by examining training/test accuracies.
Learning Individually Fair Classifier with Path-Specific Causal-Effect Constraint
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning is used to make decisions for individuals in various fields, which require us to achieve good prediction accuracy while ensuring fairness with respect to sensitive features (e.g., race and gender). This problem, however, remains difficult in complex real-world scenarios. To quantify unfairness under such situations, existing methods utilize {\it path-specific causal effects}. However, none of them can ensure fairness for each individual without making impractical functional assumptions on the data. In this paper, we propose a far more practical framework for learning an individually fair classifier. To avoid restrictive functional assumptions, we define the {\it probability of individual unfairness} (PIU) and solve an optimization problem where PIU's upper bound, which can be estimated from data, is controlled to be close to zero. We elucidate why our method can guarantee fairness for each individual. Experimental results show that our method can learn an individually fair classifier at a slight cost of accuracy.
Relational Message Passing for Knowledge Graph Completion
Venue: arXiv cs.LG 2021
Year: 2021

Knowledge graph completion aims to predict missing relations between entities in a knowledge graph. In this work, we propose a relational message passing method for knowledge graph completion. Different from existing embedding-based methods, relational message passing only considers edge features (i.e., relation types) without entity IDs in the knowledge graph, and passes relational messages among edges iteratively to aggregate neighborhood information. Specifically, two kinds of neighborhood topology are modeled for a given entity pair under the relational message passing framework: (1) Relational context, which captures the relation types of edges adjacent to the given entity pair; (2) Relational paths, which characterize the relative position between the given two entities in the knowledge graph. The two message passing modules are combined together for relation prediction. Experimental results on knowledge graph benchmarks as well as our newly proposed dataset show that, our method PathCon outperforms state-of-the-art knowledge graph completion methods by a large margin. PathCon is also shown applicable to inductive settings where entities are not seen in training stage, and it is able to provide interpretable explanations for the predicted results. The code and all datasets are available at https://github.com/hwwang55/PathCon.
Equivalence of Dataflow Graphs via Rewrite Rules Using a Graph-to-Sequence Neural Model
Venue: arXiv cs.LG 2021
Year: 2021

In this work we target the problem of provably computing the equivalence between two programs represented as dataflow graphs. To this end, we formalize the problem of equivalence between two programs as finding a set of semantics-preserving rewrite rules from one into the other, such that after the rewrite the two programs are structurally identical, and therefore trivially equivalent. We then develop the first graph-to-sequence neural network system for program equivalence, trained to produce such rewrite sequences from a carefully crafted automatic example generation algorithm. We extensively evaluate our system on a rich multi-type linear algebra expression language, using arbitrary combinations of 100+ graph-rewriting axioms of equivalence. Our system outputs via inference a correct rewrite sequence for 96% of the 10,000 program pairs isolated for testing, using 30-term programs. And in all cases, the validity of the sequence produced and therefore the provable assertion of program equivalence is computable, in negligible time.
When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems
Venue: arXiv cs.LO 2021
Year: 2021

We produce a class of $ω$-categorical structures with finite signature by applying a model-theoretic construction -- a refinement of the Hrushosvki-encoding -- to $ω$-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate $ω$-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and $ω$-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of $ω$-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.
Weighted Additive Spanners
Venue: arXiv cs.DM 2021
Year: 2021

A \emph{spanner} of a graph $G$ is a subgraph $H$ that approximately preserves shortest path distances in $G$. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured \emph{multiplicatively}. In this work, we investigate whether one can similarly extend constructions of spanners with purely \emph{additive} error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic $+2$ and $+4$ unweighted spanners (both all-pairs and pairwise) to $+2W$ and $+4W$ weighted spanners, where $W$ is the maximum edge weight. Specifically, we show that a weighted graph $G$ contains all-pairs (pairwise) $+2W$ and $+4W$ weighted spanners of size $O(n^{3/2})$ and $\widetilde{O}(n^{7/5})$ ($O(np^{1/3})$ and $O(np^{2/7})$) respectively. For a technical reason, the $+6$ unweighted spanner becomes a $+8W$ weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that $G$ contains all-pairs (pairwise) $+8W$ weighted spanners of size $O(n^{4/3})$ ($O(np^{1/4})$).
Density of Binary Disc Packings: The 9 Compact Packings
Venue: arXiv cs.DM 2021
Year: 2021

A disc packing in the plane is compact if its contact graph is a triangulation. There are $9$ values of $r$ such that a compact packing by discs of radii $1$ and $r$ exists. We prove, for each of these $9$ values, that the maximal density over all the packings by discs of radii $1$ and $r$ is reached for a compact packing (we give it as well as its density).
On the Fine-Grained Complexity of Parity Problems
Venue: arXiv cs.DS 2021
Year: 2021

We consider the parity variants of basic problems studied in fine-grained complexity. We show that finding the exact solution is just as hard as finding its parity (i.e. if the solution is even or odd) for a large number of classical problems, including All-Pairs Shortest Paths (APSP), Diameter, Radius, Median, Second Shortest Path, Maximum Consecutive Subsums, Min-Plus Convolution, and $0/1$-Knapsack. A direct reduction from a problem to its parity version is often difficult to design. Instead, we revisit the existing hardness reductions and tailor them in a problem-specific way to the parity version. Nearly all reductions from APSP in the literature proceed via the (subcubic-equivalent but simpler) Negative Weight Triangle (NWT) problem. Our new modified reductions also start from NWT or a non-standard parity variant of it. We are not able to establish a subcubic-equivalence with the more natural parity counting variant of NWT, where we ask if the number of negative triangles is even or odd. Perhaps surprisingly, we justify this by designing a reduction from the seemingly-harder Zero Weight Triangle problem, showing that parity is (conditionally) strictly harder than decision for NWT.
Mind Your Weight(s): A Large-scale Study on Insufficient Machine Learning Model Protection in Mobile Apps
Venue: arXiv cs.CR 2021
Year: 2021

On-device machine learning (ML) is quickly gaining popularity among mobile apps. It allows offline model inference while preserving user privacy. However, ML models, considered as core intellectual properties of model owners, are now stored on billions of untrusted devices and subject to potential thefts. Leaked models can cause both severe financial loss and security consequences. This paper presents the first empirical study of ML model protection on mobile devices. Our study aims to answer three open questions with quantitative evidence: How widely is model protection used in apps? How robust are existing model protection techniques? What impacts can (stolen) models incur? To that end, we built a simple app analysis pipeline and analyzed 46,753 popular apps collected from the US and Chinese app markets. We identified 1,468 ML apps spanning all popular app categories. We found that, alarmingly, 41% of ML apps do not protect their models at all, which can be trivially stolen from app packages. Even for those apps that use model protection or encryption, we were able to extract the models from 66% of them via unsophisticated dynamic analysis techniques. The extracted models are mostly commercial products and used for face recognition, liveness detection, ID/bank card recognition, and malware detection. We quantitatively estimated the potential financial and security impact of a leaked model, which can amount to millions of dollars for different stakeholders. Our study reveals that on-device models are currently at high risk of being leaked; attackers are highly motivated to steal such models. Drawn from our large-scale study, we report our insights into this emerging security problem and discuss the technical challenges, hoping to inspire future research on robust and practical model protection for mobile devices.
Fundamental Limits of Wireless Caching Under Mixed Cacheable and Uncacheable Traffic
Venue: arXiv cs.IT 2021
Year: 2021

We consider cache-aided wireless communication scenarios where each user requests both a file from an a-priori generated cacheable library (referred to as 'content'), and an uncacheable 'non-content' message generated at the start of the wireless transmission session. This scenario is easily found in real-world wireless networks, where the two types of traffic coexist and share limited radio resources. We focus on single-transmitter, single-antenna wireless networks with cache-aided receivers, where the wireless channel is modelled by a degraded Gaussian broadcast channel (GBC). For this setting, we study the delay-rate trade-off, which characterizes the content delivery time and non-content communication rates that can be achieved simultaneously. We propose a scheme based on the separation principle, which isolates the coded caching and multicasting problem from the physical layer transmission problem. We show that this separation-based scheme is sufficient for achieving an information-theoretically order optimal performance, up to a multiplicative factor of 2.01 for the content delivery time, when working in the generalized degrees of freedom (GDoF) limit. We further show that the achievable performance is near-optimal after relaxing the GDoF limit, up to an additional additive factor of 2 bits per dimension for the non-content rates. A key insight emerging from our scheme is that in some scenarios considerable amounts of non-content traffic can be communicated while maintaining the minimum content delivery time, achieved in the absence of non-content messages; compliments of 'topological holes' arising from asymmetries in wireless channel gains.
Learning by Semantic Similarity Makes Abstractive Summarization Better
Venue: arXiv cs.CL 2021
Year: 2021

By harnessing pre-trained language models, summarization models had rapid progress recently. However, the models are mainly assessed by automatic evaluation metrics such as ROUGE. Although ROUGE is known for having a positive correlation with human evaluation scores, it has been criticized for its vulnerability and the gap between actual qualities. In this paper, we compare the generated summaries from recent LM, BART, and the reference summaries from a benchmark dataset, CNN/DM, using a crowd-sourced human evaluation metric. Interestingly, model-generated summaries receive higher scores relative to reference summaries. Stemming from our experimental results, we first argue the intrinsic characteristics of the CNN/DM dataset, the progress of pre-trained language models, and their ability to generalize on the training data. Finally, we share our insights into the model-generated summaries and presents our thought on learning methods for abstractive summarization.
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
Venue: arXiv cs.DS 2021
Year: 2021

We study dynamic graph algorithms in the Massively Parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can efficiently handle large batches of edge insertions and deletions. We show algorithms that require fewer rounds to update a solution to problems such as Minimum Spanning Forest, 2-Edge Connected Components, and Maximal Matching than would be required by their static counterparts to compute it from scratch. They work in the most restrictive memory regime, in which local memory per machine is strongly sublinear in the number of graph vertices. Improving on the size of the batch they can handle efficiently would improve on the round complexity of known static algorithms on sparse graphs. Our algorithms can process batches of updates of size $Θ(S)$, for Minimum Spanning Forest and 2-Edge Connected Components, and $Θ(S^{1-\varepsilon})$, for Maximal Matching, in $O(1)$ rounds, where $S$ is the local memory of a single machine.
A Novel Framework for Selection of GANs for an Application
Venue: arXiv cs.LG 2021
Year: 2021

Generative Adversarial Network (GAN) is a current focal point of research. The body of knowledge is fragmented, leading to a trial-error method while selecting an appropriate GAN for a given scenario. We provide a comprehensive summary of the evolution of GANs starting from its inception addressing issues like mode collapse, vanishing gradient, unstable training and non-convergence. We also provide a comparison of various GANs from the application point of view, its behaviour and implementation details. We propose a novel framework to identify candidate GANs for a specific use case based on architecture, loss, regularization and divergence. We also discuss application of the framework using an example, and we demonstrate a significant reduction in search space. This efficient way to determine potential GANs lowers unit economics of AI development for organizations.
A Neural Lip-Sync Framework for Synthesizing Photorealistic Virtual News Anchors
Venue: arXiv cs.CV 2021
Year: 2021

Lip sync has emerged as a promising technique for generating mouth movements from audio signals. However, synthesizing a high-resolution and photorealistic virtual news anchor is still challenging. Lack of natural appearance, visual consistency, and processing efficiency are the main problems with existing methods. This paper presents a novel lip-sync framework specially designed for producing high-fidelity virtual news anchors. A pair of Temporal Convolutional Networks are used to learn the cross-modal sequential mapping from audio signals to mouth movements, followed by a neural rendering network that translates the synthetic facial map into a high-resolution and photorealistic appearance. This fully trainable framework provides end-to-end processing that outperforms traditional graphics-based methods in many low-delay applications. Experiments also show the framework has advantages over modern neural-based methods in both visual appearance and efficiency.
Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
Venue: arXiv cs.DS 2021
Year: 2021

We show the existence of an exact mimicking network of $k^{O(\log k)}$ edges for minimum multicuts over a set of terminals in an undirected graph, where $k$ is the total capacity of the terminals, as well as a method for computing a mimicking network of quasipolynomial size in polynomial time. As a consequence of the latter, several problems are shown to have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, and Edge Multicut parameterized by the solution and the number of cut requests. The result combines the matroid-based irrelevant edge approach used in the kernel for $s$-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for $s$-Multiway Cut for constant value of $s$ (Kratsch and Wahlström, FOCS 2012).
Geometric Interpretation of Running Nyström-Based Kernel Machines and Error Analysis
Venue: arXiv cs.LG 2021
Year: 2021

Recently, Nyström method has proved its prominence empirically and theoretically in speeding up the training of kernel machines while retaining satisfactory performances and accuracy. So far, there are several different approaches proposed to exploit Nyström method in scaling up kernel machines. However, there is no comparative study over these approaches, and they were individually analyzed for specific types of kernel machines. Therefore, it remains a question that the philosophy of which approach is more promising when it extends to other kernel machines. In this work, motivated by the column inclusion property of Gram matrices, we develop a new approach with a clear geometric interpretation for running Nyström-based kernel machines. We show that the other two well-studied approaches can be equivalently transformed to be our proposed one. Consequently, analysis established for the proposed approach also works for these two. Particularly, our proposed approach makes it possible to develop approximation errors in a general setting. Besides, our analysis also manifests the relations among the aforementioned two approaches and another naive one. First, the analytical forms of the corresponding approximate solutions are only at odds with one term. Second, the naive approach can be implemented efficiently by sharing the same training procedure with others. These analytical results lead to the conjecture that the naive approach can provide more accurate approximate solutions than the other two sophisticated approaches. Since our analysis also offers ways for computing the accuracy of these approximate solutions, we run experiments with classification tasks to confirm our conjecture.