pwc-archive/papers-with-abstracts huggingface dataset:
CrossLight: A Cross-Layer Optimized Silicon Photonic Neural Network Accelerator
Authors: Febin Sunny, Asif Mirza, Mahdi Nikdast, Sudeep Pasricha
Date: 2021-02-13 00:00:00

Domain-specific neural network accelerators have seen growing interest in recent years due to their improved energy efficiency and inference performance compared to CPUs and GPUs. In this paper, we propose a novel cross-layer optimized neural network accelerator called CrossLight that leverages silicon photonics. CrossLight includes device-level engineering for resilience to process variations and thermal crosstalk, circuit-level tuning enhancements for inference latency reduction, and architecture-level optimization to enable higher resolution, better energy-efficiency, and improved throughput. On average, CrossLight offers 9.5x lower energy-per-bit and 15.9x higher performance-per-watt at 16-bit resolution than state-of-the-art photonic deep learning accelerators.
PerSim: Data-Efficient Offline Reinforcement Learning with Heterogeneous Agents via Personalized Simulators
Authors: Anish Agarwal, Abdullah Alomar, Varkey Alumootil, Devavrat Shah, Dennis Shen, Zhi Xu, Cindy Yang
Date: 2021-02-13 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Offline RL, reinforcement-learning, Reinforcement Learning (RL)

We consider offline reinforcement learning (RL) with heterogeneous agents under severe data scarcity, i.e., we only observe a single historical trajectory for every agent under an unknown, potentially sub-optimal policy. We find that the performance of state-of-the-art offline and model-based RL methods degrade significantly given such limited data availability, even for commonly perceived "solved" benchmark settings such as "MountainCar" and "CartPole". To address this challenge, we propose PerSim, a model-based offline RL approach which first learns a personalized simulator for each agent by collectively using the historical trajectories across all agents, prior to learning a policy. We do so by positing that the transition dynamics across agents can be represented as a latent function of latent factors associated with agents, states, and actions; subsequently, we theoretically establish that this function is well-approximated by a "low-rank" decomposition of separable agent, state, and action latent functions. This representation suggests a simple, regularized neural network architecture to effectively learn the transition dynamics per agent, even with scarce, offline data. We perform extensive experiments across several benchmark environments and RL methods. The consistent improvement of our approach, measured in terms of both state dynamics prediction and eventual reward, confirms the efficacy of our framework in leveraging limited historical data to simultaneously learn personalized policies across agents.
On the convergence of group-sparse autoencoders
Authors: Emmanouil Theodosis, Bahareh Tolooshams, Pranay Tankala, Abiy Tasissa, Demba Ba
Date: 2021-02-13 00:00:00
Tasks: Clustering

Recent approaches in the theoretical analysis of model-based deep learning architectures have studied the convergence of gradient descent in shallow ReLU networks that arise from generative models whose hidden layers are sparse. Motivated by the success of architectures that impose structured forms of sparsity, we introduce and study a group-sparse autoencoder that accounts for a variety of generative models, and utilizes a group-sparse ReLU activation function to force the non-zero units at a given layer to occur in blocks. For clustering models, inputs that result in the same group of active units belong to the same cluster. We proceed to analyze the gradient dynamics of a shallow instance of the proposed autoencoder, trained with data adhering to a group-sparse generative model. In this setting, we theoretically prove the convergence of the network parameters to a neighborhood of the generating matrix. We validate our model through numerical analysis and highlight the superior performance of networks with a group-sparse ReLU compared to networks that utilize traditional ReLUs, both in sparse coding and in parameter recovery tasks. We also provide real data experiments to corroborate the simulated results, and emphasize the clustering capabilities of structured sparsity models.
A Statistical Relational Approach to Learning Distance-based GCNs
Authors: Devendra Singh Dhami, Siwen Yan, Sriraam Natarajan
Date: 2021-02-13 00:00:00
Tasks: Density Estimation, Link Prediction, Node Classification, Relational Reasoning

We consider the problem of learning distance-based Graph Convolutional Networks (GCNs) for relational data. Specifically, we first embed the original graph into the Euclidean space $\mathbb{R}^m$ using a relational density estimation technique thereby constructing a secondary Euclidean graph. The graph vertices correspond to the target triples and edges denote the Euclidean distances between the target triples. We emphasize the importance of learning the secondary Euclidean graph and the advantages of employing a distance matrix over the typically used adjacency matrix. Our comprehensive empirical evaluation demonstrates the superiority of our approach over $12$ different GCN models, relational embedding techniques and rule learning techniques.
Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
Authors: Aritra Mitra, Rayana Jaafar, George J. Pappas, Hamed Hassani
Date: 2021-02-14 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Federated Learning

We consider a standard federated learning (FL) architecture where a group of clients periodically coordinate with a central server to train a statistical model. We develop a general algorithmic framework called FedLin to tackle some of the key challenges intrinsic to FL, namely objective heterogeneity, systems heterogeneity, and infrequent and imprecise communication. Our framework is motivated by the observation that under these challenges, various existing FL algorithms suffer from a fundamental speed-accuracy conflict: they either guarantee linear convergence but to an incorrect point, or convergence to the global minimum but at a sub-linear rate, i.e., fast convergence comes at the expense of accuracy. In contrast, when the clients' local loss functions are smooth and strongly convex, we show that FedLin guarantees linear convergence to the global minimum, despite arbitrary objective and systems heterogeneity. We then establish matching upper and lower bounds on the convergence rate of FedLin that highlight the effects of intermittent communication. Finally, we show that FedLin preserves linear convergence rates under aggressive gradient sparsification, and quantify the effect of the compression level on the convergence rate. Our work is the first to provide tight linear convergence rate guarantees, and constitutes the first comprehensive analysis of gradient sparsification in FL.
A Forward Backward Greedy approach for Sparse Multiscale Learning
Authors: Prashant Shekhar, Abani Patra
Date: 2021-02-14 00:00:00

Multiscale Models are known to be successful in uncovering and analyzing the structures in data at different resolutions. In the current work we propose a feature driven Reproducing Kernel Hilbert space (RKHS), for which the associated kernel has a weighted multiscale structure. For generating approximations in this space, we provide a practical forward-backward algorithm that is shown to greedily construct a set of basis functions having a multiscale structure, while also creating sparse representations from the given data set, making representations and predictions very efficient. We provide a detailed analysis of the algorithm including recommendations for selecting algorithmic hyper-parameters and estimating probabilistic rates of convergence at individual scales. Then we extend this analysis to multiscale setting, studying the effects of finite scale truncation and quality of solution in the inherent RKHS. In the last section, we analyze the performance of the approach on a variety of simulation and real data sets, thereby justifying the efficiency claims in terms of model quality and data reduction.
Doping: A technique for efficient compression of LSTM models using sparse structured additive matrices
Authors: Urmish Thakker, Paul N. Whatmough, ZhiGang Liu, Matthew Mattina, Jesse Beu
Date: 2021-02-14 00:00:00

Structured matrices, such as those derived from Kronecker products (KP), are effective at compressing neural networks, but can lead to unacceptable accuracy loss when applied to large models. In this paper, we propose the notion of doping -- addition of an extremely sparse matrix to a structured matrix. Doping facilitates additional degrees of freedom for a small number of parameters, allowing them to independently diverge from the fixed structure. To train LSTMs with doped structured matrices, we introduce the additional parameter matrix while slowly annealing its sparsity level. However, we find that performance degrades as we slowly sparsify the doping matrix, due to co-matrix adaptation (CMA) between the structured and the sparse matrices. We address this over dependence on the sparse matrix using a co-matrix dropout regularization (CMR) scheme. We provide empirical evidence to show that doping, CMA and CMR are concepts generally applicable to multiple structured matrices (Kronecker Product, LMF, Hybrid Matrix Decomposition). Additionally, results with doped kronecker product matrices demonstrate state-of-the-art accuracy at large compression factors (10 - 25x) across 4 natural language processing applications with minor loss in accuracy. Doped KP compression technique outperforms previous state-of-the art compression results by achieving 1.3 - 2.4x higher compression factor at a similar accuracy, while also beating strong alternatives like pruning and low-rank methods by a large margin (8% or more). Additionally, we show that doped KP can be deployed on commodity hardware using the current software stack and achieve 2.5 - 5.5x inference run-time speed-up over baseline.
Costly Features Classification using Monte Carlo Tree Search
Authors: Ziheng Chen, Jin Huang, Hongshik Ahn, Xin Ning
Date: 2021-02-14 00:00:00
Tasks: Classification, General Classification, Sensitivity

We consider the problem of costly feature classification, where we sequentially select the subset of features to make a balance between the classification error and the feature cost. In this paper, we first cast the task into a MDP problem and use Advantage Actor Critic algorithm to solve it. In order to further improve the agent's performance and make the policy explainable, we employ the Monte Carlo Tree Search to update the policy iteratively. During the procedure, we also consider its performance on the unbalanced dataset and its sensitivity to the missing value. We evaluate our model on multiple datasets and find it outperforms other methods.
Tight lower bounds for Dynamic Time Warping
Authors: Geoffrey I. Webb, Francois Petitjean
Date: 2021-02-14 00:00:00
Tasks: Computational Efficiency, Dynamic Time Warping, Time Series, Time Series Analysis

Dynamic Time Warping (DTW) is a popular similarity measure for aligning and comparing time series. Due to DTW's high computation time, lower bounds are often employed to screen poor matches. Many alternative lower bounds have been proposed, providing a range of different trade-offs between tightness and computational efficiency. LB Keogh provides a useful trade-off in many applications. Two recent lower bounds, LB Improved and LB Enhanced, are substantially tighter than LB Keogh. All three have the same worst case computational complexity - linear with respect to series length and constant with respect to window size. We present four new DTW lower bounds in the same complexity class. LB Petitjean is substantially tighter than LB Improved, with only modest additional computational overhead. LB Webb is more efficient than LB Improved, while often providing a tighter bound. LB Webb is always tighter than LB Keogh. The parameter free LB Webb is usually tighter than LB Enhanced. A parameterized variant, LB Webb Enhanced, is always tighter than LB Enhanced. A further variant, LB Webb*, is useful for some constrained distance functions. In extensive experiments, LB Webb proves to be very effective for nearest neighbor search.
Exploiting Shared Representations for Personalized Federated Learning
Authors: Liam Collins, Hamed Hassani, Aryan Mokhtari, Sanjay Shakkottai
Date: 2021-02-14 00:00:00
Tasks: Federated Learning, Meta-Learning, Multi-Task Learning, Personalized Federated Learning, Representation Learning

Deep neural networks have shown the ability to extract universal feature representations from data such as images and text that have been useful for a variety of learning tasks. However, the fruits of representation learning have yet to be fully-realized in federated settings. Although data in federated settings is often non-i.i.d. across clients, the success of centralized deep learning suggests that data often shares a global feature representation, while the statistical heterogeneity across clients or tasks is concentrated in the labels. Based on this intuition, we propose a novel federated learning framework and algorithm for learning a shared data representation across clients and unique local heads for each client. Our algorithm harnesses the distributed computational power across clients to perform many local-updates with respect to the low-dimensional local parameters for every update of the representation. We prove that this method obtains linear convergence to the ground-truth representation with near-optimal sample complexity in a linear setting, demonstrating that it can efficiently reduce the problem dimension for each client. This result is of interest beyond federated learning to a broad class of problems in which we aim to learn a shared low-dimensional representation among data distributions, for example in meta-learning and multi-task learning. Further, extensive experimental results show the empirical improvement of our method over alternative personalized federated learning approaches in federated environments with heterogeneous data.
CATE: Computation-aware Neural Architecture Encoding with Transformers
Authors: Shen Yan, Kaiqiang Song, Fei Liu, Mi Zhang
Date: 2021-02-14 00:00:00
Tasks: AutoML, Neural Architecture Search, Representation Learning, Unsupervised Pre-training

Recent works (White et al., 2020a; Yan et al., 2020) demonstrate the importance of architecture encodings in Neural Architecture Search (NAS). These encodings encode either structure or computation information of the neural architectures. Compared to structure-aware encodings, computation-aware encodings map architectures with similar accuracies to the same region, which improves the downstream architecture search performance (Zhang et al., 2019; White et al., 2020a). In this work, we introduce a Computation-Aware Transformer-based Encoding method called CATE. Different from existing computation-aware encodings based on fixed transformation (e.g. path encoding), CATE employs a pairwise pre-training scheme to learn computation-aware encodings using Transformers with cross-attention. Such learned encodings contain dense and contextualized computation information of neural architectures. We compare CATE with eleven encodings under three major encoding-dependent NAS subroutines in both small and large search spaces. Our experiments show that CATE is beneficial to the downstream search, especially in the large search space. Moreover, the outside search space experiment demonstrates its superior generalization ability beyond the search space on which it was trained. Our code is available at: https://github.com/MSU-MLSys-Lab/CATE.
Machine Learning Methods for the Design and Operation of Liquid Rocket Engines -- Research Activities at the DLR Institute of Space Propulsion
Authors: Günther Waxenegger-Wilfing, Kai Dresia, Jan Deeken, Michael Oschwald
Date: 2021-02-14 00:00:00
Tasks: BIG-bench Machine Learning

The last years have witnessed an enormous interest in the use of artificial intelligence methods, especially machine learning algorithms. This also has a major impact on aerospace engineering in general, and the design and operation of liquid rocket engines in particular, and research in this area is growing rapidly. The paper describes current machine learning applications at the DLR Institute of Space Propulsion. Not only applications in the field of modeling are presented, but also convincing results that prove the capabilities of machine learning methods for control and condition monitoring are described in detail. Furthermore, the advantages and disadvantages of the presented methods as well as current and future research directions are discussed.
A New Algorithm for Hidden Markov Models Learning Problem
Authors: Taha Mansouri, Mohamadreza Sadeghimoghadam, Iman Ghasemian Sahebi
Date: 2021-02-14 00:00:00

This research focuses on the algorithms and approaches for learning Hidden Markov Models (HMMs) and compares HMM learning methods and algorithms. HMM is a statistical Markov model in which the system being modeled is assumed to be a Markov process. One of the essential characteristics of HMMs is their learning capabilities. Learning algorithms are introduced to overcome this inconvenience. One of the main problems of the newly proposed algorithms is their validation. This research aims by using the theoretical and experimental analysis to 1) compare HMMs learning algorithms proposed in the literature, 2) provide a validation tool for new HMM learning algorithms, and 3) present a new algorithm called Asexual Reproduction Optimization (ARO) with one of its extensions - Modified ARO (MARO) - as a novel HMM learning algorithm to use the validation tool proposed. According to the literature findings, it seems that populationbased algorithms perform better among HMMs learning approaches than other algorithms. Also, the testing was done in nine benchmark datasets. The results show that MARO outperforms different algorithms in objective functions in terms of accuracy and robustness.
A Spectral Algorithm for Learning Hidden Markov Models
Authors: Daniel Hsu, Sham M. Kakade, Tong Zhang
Date: 2008-11-26 00:00:00
Tasks: Time Series, Time Series Analysis

Hidden Markov Models (HMMs) are one of the most fundamental and widely used statistical tools for modeling discrete time series. In general, learning HMMs from data is computationally hard (under cryptographic assumptions), and practitioners typically resort to search heuristics which suffer from the usual local optima issues. We prove that under a natural separation condition (bounds on the smallest singular value of the HMM parameters), there is an efficient and provably correct algorithm for learning HMMs. The sample complexity of the algorithm does not explicitly depend on the number of distinct (discrete) observations---it implicitly depends on this quantity through spectral properties of the underlying HMM. This makes the algorithm particularly applicable to settings with a large number of observations, such as those in natural language processing where the space of observation is sometimes the words in a language. The algorithm is also simple, employing only a singular value decomposition and matrix multiplications.
A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization
Authors: Canh T. Dinh, Tung T. Vu, Nguyen H. Tran, Minh N. Dao, Hongyu Zhang
Date: 2021-02-14 00:00:00
Tasks: Federated Learning, Few-Shot Learning, Multi-Task Learning, Personalized Federated Learning

Non-Independent and Identically Distributed (non- IID) data distribution among clients is considered as the key factor that degrades the performance of federated learning (FL). Several approaches to handle non-IID data such as personalized FL and federated multi-task learning (FMTL) are of great interest to research communities. In this work, first, we formulate the FMTL problem using Laplacian regularization to explicitly leverage the relationships among the models of clients for multi-task learning. Then, we introduce a new view of the FMTL problem, which in the first time shows that the formulated FMTL problem can be used for conventional FL and personalized FL. We also propose two algorithms FedU and dFedU to solve the formulated FMTL problem in communication-centralized and decentralized schemes, respectively. Theoretically, we prove that the convergence rates of both algorithms achieve linear speedup for strongly convex and sublinear speedup of order 1/2 for nonconvex objectives. Experimentally, we show that our algorithms outperform the algorithm FedAvg, FedProx, SCAFFOLD, and AFL in FL settings, MOCHA in FMTL settings, as well as pFedMe and Per-FedAvg in personalized FL settings.
Distributed Second Order Methods with Fast Rates and Compressed Communication
Authors: Rustem Islamov, Xun Qian, Peter Richtárik
Date: 2021-02-14 00:00:00
Tasks: Distributed Optimization, Second-order methods

We develop several new communication-efficient second-order methods for distributed optimization. Our first method, NEWTON-STAR, is a variant of Newton's method from which it inherits its fast local quadratic rate. However, unlike Newton's method, NEWTON-STAR enjoys the same per iteration communication cost as gradient descent. While this method is impractical as it relies on the use of certain unknown parameters characterizing the Hessian of the objective function at the optimum, it serves as the starting point which enables us design practical variants thereof with strong theoretical guarantees. In particular, we design a stochastic sparsification strategy for learning the unknown parameters in an iterative fashion in a communication efficient manner. Applying this strategy to NEWTON-STAR leads to our next method, NEWTON-LEARN, for which we prove local linear and superlinear rates independent of the condition number. When applicable, this method can have dramatically superior convergence behavior when compared to state-of-the-art methods. Finally, we develop a globalization strategy using cubic regularization which leads to our next method, CUBIC-NEWTON-LEARN, for which we prove global sublinear and linear convergence rates, and a fast superlinear rate. Our results are supported with experimental results on real datasets, and show several orders of magnitude improvement on baseline and state-of-the-art methods in terms of communication complexity.
Adversarial Attack on Network Embeddings via Supervised Network Poisoning
Authors: Viresh Gupta, Tanmoy Chakraborty
Date: 2021-02-14 00:00:00
Tasks: Adversarial Attack, Link Prediction, Network Embedding, Node Classification, Representation Learning

Learning low-level node embeddings using techniques from network representation learning is useful for solving downstream tasks such as node classification and link prediction. An important consideration in such applications is the robustness of the embedding algorithms against adversarial attacks, which can be examined by performing perturbation on the original network. An efficient perturbation technique can degrade the performance of network embeddings on downstream tasks. In this paper, we study network embedding algorithms from an adversarial point of view and observe the effect of poisoning the network on downstream tasks. We propose VIKING, a supervised network poisoning strategy that outperforms the state-of-the-art poisoning methods by upto 18% on the original network structure. We also extend VIKING to a semi-supervised attack setting and show that it is comparable to its supervised counterpart.