OpenRaiser/Intern-Atlas huggingface dataset:
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
Venue: arXiv cs.LG 2020
Year: 2020

We study differentially private (DP) algorithms for stochastic non-convex optimization. In this problem, the goal is to minimize the population loss over a $p$-dimensional space given $n$ i.i.d. samples drawn from a distribution. We improve upon the population gradient bound of ${\sqrt{p}}/{\sqrt{n}}$ from prior work and obtain a sharper rate of $\sqrt[4]{p}/\sqrt{n}$. We obtain this rate by providing the first analyses on a collection of private gradient-based methods, including adaptive algorithms DP RMSProp and DP Adam. Our proof technique leverages the connection between differential privacy and adaptive data analysis to bound gradient estimation error at every iterate, which circumvents the worse generalization bound from the standard uniform convergence argument. Finally, we evaluate the proposed algorithms on two popular deep learning tasks and demonstrate the empirical advantages of DP adaptive gradient methods over standard DP SGD.
When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence
Venue: arXiv cs.LG 2020
Year: 2020

Generative adversarial imitation learning (GAIL) is a popular inverse reinforcement learning approach for jointly optimizing policy and reward from expert trajectories. A primary question about GAIL is whether applying a certain policy gradient algorithm to GAIL attains a global minimizer (i.e., yields the expert policy), for which existing understanding is very limited. Such global convergence has been shown only for the linear (or linear-type) MDP and linear (or linearizable) reward. In this paper, we study GAIL under general MDP and for nonlinear reward function classes (as long as the objective function is strongly concave with respect to the reward parameter). We characterize the global convergence with a sublinear rate for a broad range of commonly used policy gradient algorithms, all of which are implemented in an alternating manner with stochastic gradient ascent for reward update, including projected policy gradient (PPG)-GAIL, Frank-Wolfe policy gradient (FWPG)-GAIL, trust region policy optimization (TRPO)-GAIL and natural policy gradient (NPG)-GAIL. This is the first systematic theoretical study of GAIL for global convergence.
Fetch-Directed Instruction Prefetching Revisited
Venue: arXiv cs.AR 2020
Year: 2020

Prior work has observed that fetch-directed prefetching (FDIP) is highly effective at covering instruction cache misses. The key to FDIP's effectiveness is having a sufficiently large BTB to accommodate the application's branch working set. In this work, we introduce several optimizations that significantly extend the reach of the BTB within the available storage budget. Our optimizations target nearly every source of storage overhead in each BTB entry; namely, the tag, target address, and size fields. We observe that while most dynamic branch instances have short offsets, a large number of branches has longer offsets or requires the use of full target addresses. Based on this insight, we break-up the BTB into multiple smaller BTBs, each storing offsets of different length. This enables a dramatic reduction in storage for target addresses. We further compress tags to 16 bits and avoid the use of the basic-block-oriented BTB advocated in prior FDIP variants. The latter optimization eliminates the need to store the basic block size in each BTB entry. Our final design, called FDIP-X, uses an ensemble of 4 BTBs and always outperforms conventional FDIP with a unified basic-block-oriented BTB for equal storage budgets.
Network connectivity under a probabilistic node failure model
Venue: arXiv cs.SI 2020
Year: 2020

Centrality metrics have been widely applied to identify the nodes in a graph whose removal is effective in decomposing the graph into smaller sub-components. The node--removal process is generally used to test network robustness against failures. Most of the available studies assume that the node removal task is always successful. Yet, we argue that this assumption is unrealistic. Indeed, the removal process should take into account also the strength of the targeted node itself, to simulate the failure scenarios in a more effective and realistic fashion. Unlike previous literature, herein a {\em probabilistic node failure model} is proposed, in which nodes may fail with a particular probability, considering two variants, namely: {\em Uniform} (in which the nodes survival-to-failure probability is fixed) and {\em Best Connected} (BC) (where the nodes survival probability is proportional to their degree). To evaluate our method, we consider five popular centrality metrics carrying out an experimental, comparative analysis to evaluate them in terms of {\em effectiveness} and {\em coverage}, on four real-world graphs. By effectiveness and coverage we mean the ability of selecting nodes whose removal decreases graph connectivity the most. Specifically, the graph spectral radius reduction works as a proxy indicator of effectiveness, and the reduction of the largest connected component (LCC) size is a parameter to assess coverage. The metric that caused the biggest drop has been then compared with the Benchmark analysis (i.e, the non-probabilistic degree centrality node removal process) to compare the two approaches. The main finding has been that significant differences emerged through this comparison with a deviation range that varies from 2\% up to 80\% regardless of the dataset used that highlight the existence of a gap between the common practice with a more realistic approach.
Exploring the Security Awareness of the Python and JavaScript Open Source Communities
Venue: arXiv cs.SE 2020
Year: 2020

Software security is undoubtedly a major concern in today's software engineering. Although the level of awareness of security issues is often high, practical experiences show that neither preventive actions nor reactions to possible issues are always addressed properly in reality. By analyzing large quantities of commits in the open-source communities, we can categorize the vulnerabilities mitigated by the developers and study their distribution, resolution time, etc. to learn and improve security management processes and practices. With the help of the Software Heritage Graph Dataset, we investigated the commits of two of the most popular script languages -- Python and JavaScript -- projects collected from public repositories and identified those that mitigate a certain vulnerability in the code (i.e. vulnerability resolution commits). On the one hand, we identified the types of vulnerabilities (in terms of CWE groups) referred to in commit messages and compared their numbers within the two communities. On the other hand, we examined the average time elapsing between the publish date of a vulnerability and the first reference to it in a commit. We found that there is a large intersection in the vulnerability types mitigated by the two communities, but most prevalent vulnerabilities are specific to language. Moreover, neither the JavaScript nor the Python community reacts very fast to appearing security vulnerabilities in general with only a couple of exceptions for certain CWE groups.
Stochastic Transceiver Optimization in Multi-Tags Symbiotic Radio Systems
Venue: arXiv cs.IT 2020
Year: 2020

Symbiotic radio (SR) is emerging as a spectrum- and energy-efficient communication paradigm for future passive Internet-of-things (IoT), where some single-antenna backscatter devices, referred to as Tags, are parasitic in an active primary transmission. The primary transceiver is designed to assist both direct-link (DL) and backscatter-link (BL) communication. In multi-tags SR systems, the transceiver designs become much more complicated due to the presence of DL and inter-Tag interference, which further poses new challenges to the availability and reliability of DL and BL transmission. To overcome these challenges, we formulate the stochastic optimization of transceiver design as the general network utility maximization problem (GUMP). The resultant problem is a stochastic multiple-ratio fractional non-convex problem, and consequently challenging to solve. By leveraging some fractional programming techniques, we tailor a surrogate function with the specific structure and subsequently develop a batch stochastic parallel decomposition (BSPD) algorithm, which is shown to converge to stationary solutions of the GNUMP. Simulation results verify the effectiveness of the proposed algorithm by numerical examples in terms of the achieved system throughput.
Deep Categorization with Semi-Supervised Self-Organizing Maps
Venue: arXiv cs.LG 2020
Year: 2020

Nowadays, with the advance of technology, there is an increasing amount of unstructured data being generated every day. However, it is a painful job to label and organize it. Labeling is an expensive, time-consuming, and difficult task. It is usually done manually, which collaborates with the incorporation of noise and errors to the data. Hence, it is of great importance to developing intelligent models that can benefit from both labeled and unlabeled data. Currently, works on unsupervised and semi-supervised learning are still being overshadowed by the successes of purely supervised learning. However, it is expected that they become far more important in the longer term. This article presents a semi-supervised model, called Batch Semi-Supervised Self-Organizing Map (Batch SS-SOM), which is an extension of a SOM incorporating some advances that came with the rise of Deep Learning, such as batch training. The results show that Batch SS-SOM is a good option for semi-supervised classification and clustering. It performs well in terms of accuracy and clustering error, even with a small number of labeled samples, as well as when presented to unsupervised data, and shows competitive results in transfer learning scenarios in traditional image classification benchmark datasets.
Kernelization of Whitney Switches
Venue: arXiv cs.DS 2020
Year: 2020

A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size O(k), and thus, is fixed-parameter tractable when parameterized by k.
Equivalence in Deep Neural Networks via Conjugate Matrix Ensembles
Venue: arXiv cs.LG 2020
Year: 2020

A numerical approach is developed for detecting the equivalence of deep learning architectures. The method is based on generating Mixed Matrix Ensembles (MMEs) out of deep neural network weight matrices and {\it conjugate circular ensemble} matching the neural architecture topology. Following this, the empirical evidence supports the {\it phenomenon} that difference between spectral densities of neural architectures and corresponding {\it conjugate circular ensemble} are vanishing with different decay rates at the long positive tail part of the spectrum i.e., cumulative Circular Spectral Difference (CSD). This finding can be used in establishing equivalences among different neural architectures via analysis of fluctuations in CSD. We investigated this phenomenon for a wide range of deep learning vision architectures and with circular ensembles originating from statistical quantum mechanics. Practical implications of the proposed method for artificial and natural neural architectures discussed such as the possibility of using the approach in Neural Architecture Search (NAS) and classification of biological neural networks.
Coconut: a scalable bottom-up approach for building data series indexes
Venue: arXiv cs.DB 2020
Year: 2020

Many modern applications produce massive amounts of data series that need to be analyzed, requiring efficient similarity search operations. However, the state-of-the-art data series indexes that are used for this purpose do not scale well for massive datasets in terms of performance, or storage costs. We pinpoint the problem to the fact that existing summarizations of data series used for indexing cannot be sorted while keeping similar data series close to each other in the sorted order. This leads to two design problems. First, traditional bulk-loading algorithms based on sorting cannot be used. Instead, index construction takes place through slow top-down insertions, which create a non-contiguous index that results in many random I/Os. Second, data series cannot be sorted and split across nodes evenly based on their median value; thus, most leaf nodes are in practice nearly empty. This further slows down query speed and amplifies storage costs. To address these problems, we present Coconut. The first innovation in Coconut is an inverted, sortable data series summarization that organizes data series based on a z-order curve, keeping similar series close to each other in the sorted order. As a result, Coconut is able to use bulk-loading techniques that rely on sorting to quickly build a contiguous index using large sequential disk I/Os. We then explore prefix-based and median-based splitting policies for bottom-up bulk-loading, showing that median-based splitting outperforms the state of the art, ensuring that all nodes are densely populated. Overall, we show analytically and empirically that Coconut dominates the state-of-the-art data series indexes in terms of construction speed, query speed, and storage costs.
Embedding Differentiable Sparsity into Deep Neural Network
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose embedding sparsity into the structure of deep neural networks, where model parameters can be exactly zero during training with the stochastic gradient descent. Thus, it can learn the sparsified structure and the weights of networks simultaneously. The proposed approach can learn structured as well as unstructured sparsity.
Advances in Asynchronous Parallel and Distributed Optimization
Venue: arXiv cs.LG 2020
Year: 2020

Motivated by large-scale optimization problems arising in the context of machine learning, there have been several advances in the study of asynchronous parallel and distributed optimization methods during the past decade. Asynchronous methods do not require all processors to maintain a consistent view of the optimization variables. Consequently, they generally can make more efficient use of computational resources than synchronous methods, and they are not sensitive to issues like stragglers (i.e., slow nodes) and unreliable communication links. Mathematical modeling of asynchronous methods involves proper accounting of information delays, which makes their analysis challenging. This article reviews recent developments in the design and analysis of asynchronous optimization methods, covering both centralized methods, where all processors update a master copy of the optimization variables, and decentralized methods, where each processor maintains a local copy of the variables. The analysis provides insights as to how the degree of asynchrony impacts convergence rates, especially in stochastic optimization methods.
Modelling the Statistics of Cyclic Activities by Trajectory Analysis on the Manifold of Positive-Semi-Definite Matrices
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, a model is presented to extract statistical summaries to characterize the repetition of a cyclic body action, for instance a gym exercise, for the purpose of checking the compliance of the observed action to a template one and highlighting the parts of the action that are not correctly executed (if any). The proposed system relies on a Riemannian metric to compute the distance between two poses in such a way that the geometry of the manifold where the pose descriptors lie is preserved; a model to detect the begin and end of each cycle; a model to temporally align the poses of different cycles so as to accurately estimate the \emph{cross-sectional} mean and variance of poses across different cycles. The proposed model is demonstrated using gym videos taken from the Internet.
Diffusion-Weighted Magnetic Resonance Brain Images Generation with Generative Adversarial Networks and Variational Autoencoders: A Comparison Study
Venue: arXiv cs.CV 2020
Year: 2020

We show that high quality, diverse and realistic-looking diffusion-weighted magnetic resonance images can be synthesized using deep generative models. Based on professional neuroradiologists' evaluations and diverse metrics with respect to quality and diversity of the generated synthetic brain images, we present two networks, the Introspective Variational Autoencoder and the Style-Based GAN, that qualify for data augmentation in the medical field, where information is saved in a dispatched and inhomogeneous way and access to it is in many aspects restricted.
Efficient Metastability Characterization for Schmitt-Triggers
Venue: arXiv cs.OH 2020
Year: 2020

Despite their attractiveness as metastability filters, Schmitt-Triggers can suffer from metastability themselves. Therefore, in the selection or construction of a suitable Schmitt-Trigger implementation, it is a necessity to accurately determine the metastable behavior. Only then one is able to compare different designs and thus guide proper optimizations, and only then one can assess the potential for residual metastable upsets. However, while the state of the art provides a lot of research and practical characterization approaches for flip-flops, comparatively little is known about Schmitt-Trigger characterization. Unlike the flip-flop with its single metastable point, the Schmitt-Trigger exhibits a whole range of metastable points depending on the input voltage. Thus the task of characterization gets much more challenging. In this paper we present different approaches to determine the metastable behavior of Schmitt-Triggers using novel methods and mechanisms. We compare their accuracy and runtime by applying them to three common circuit implementations. The achieved results are then used to reason about the metastable behavior of the chosen designs which turns out to be problematic in some cases. Overall the approaches proposed in this paper are generic and can be extended beyond the Schmitt-Trigger, i.e., to efficiently characterize metastable states in other circuits as well.
XREF: Entity Linking for Chinese News Comments with Supplementary Article Reference
Venue: arXiv cs.CL 2020
Year: 2020

Automatic identification of mentioned entities in social media posts facilitates quick digestion of trending topics and popular opinions. Nonetheless, this remains a challenging task due to limited context and diverse name variations. In this paper, we study the problem of entity linking for Chinese news comments given mentions' spans. We hypothesize that comments often refer to entities in the corresponding news article, as well as topics involving the entities. We therefore propose a novel model, XREF, that leverages attention mechanisms to (1) pinpoint relevant context within comments, and (2) detect supporting entities from the news article. To improve training, we make two contributions: (a) we propose a supervised attention loss in addition to the standard cross entropy, and (b) we develop a weakly supervised training scheme to utilize the large-scale unlabeled corpus. Two new datasets in entertainment and product domains are collected and annotated for experiments. Our proposed method outperforms previous methods on both datasets.
Small Longest Tandem Scattered Subsequences
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of identifying tandem scattered subsequences within a string. Our algorithm identifies a longest subsequence which occurs twice without overlap in a string. This algorithm is based on the Hunt-Szymanski algorithm, therefore its performance improves if the string is not self similar. This occurs naturally on strings over large alphabets. Our algorithm relies on new results for data structures that support dynamic longest increasing sub-sequences. In the process we also obtain improved algorithms for the decremental string comparison problem.
Cost Sharing Security Information with Minimal Release Delay
Venue: arXiv cs.GT 2020
Year: 2020

We study a cost sharing problem derived from bug bounty programs, where agents gain utility by the amount of time they get to enjoy the cost shared information. Once the information is provided to an agent, it cannot be retracted. The goal, instead of maximizing revenue, is to pick a time as early as possible, so that enough agents are willing to cost share the information and enjoy it for a premium time period, while other agents wait and enjoy the information for free after a certain amount of release delay. We design a series of mechanisms with the goal of minimizing the maximum delay and the total delay. Under prior-free settings, our final mechanism achieves a competitive ratio of $4$ in terms of maximum delay, against an undominated mechanism. Finally, we assume some distributions of the agents' valuations, and investigate our mechanism's performance in terms of expected delays.
Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems
Venue: arXiv cs.LG 2020
Year: 2020

We provide the first global model recovery results for the IRLS (iteratively reweighted least squares) heuristic for robust regression problems. IRLS is known to offer excellent performance, despite bad initializations and data corruption, for several parameter estimation problems. Existing analyses of IRLS frequently require careful initialization, thus offering only local convergence guarantees. We remedy this by proposing augmentations to the basic IRLS routine that not only offer guaranteed global recovery, but in practice also outperform state-of-the-art algorithms for robust regression. Our routines are more immune to hyperparameter misspecification in basic regression tasks, as well as applied tasks such as linear-armed bandit problems. Our theoretical analyses rely on a novel extension of the notions of strong convexity and smoothness to weighted strong convexity and smoothness, and establishing that sub-Gaussian designs offer bounded weighted condition numbers. These notions may be useful in analyzing other algorithms as well.