Principal components analysis (PCA) is a widely used dimension reduction technique with an extensive range of applications. In this paper, an online distributed algorithm is proposed for recovering the principal eigenspaces. We further establish its rate of convergence and show how it relates to the number of nodes employed in the distributed computation, the effective rank of the data matrix under consideration, and the gap in the spectrum of the underlying population covariance matrix. The proposed algorithm is illustrated on low-rank approximation and $\boldsymbol{k}$-means clustering tasks. The numerical results show a substantial computational speed-up vis-a-vis standard distributed PCA algorithms, without compromising learning accuracy.

The pair-matching problem appears in many applications where one wants to discover good matches between pairs of individuals. Formally, the set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represent the good matches. The algorithm queries pairs of nodes and observes the presence/absence of edges. Its goal is to discover as many edges as possible with a fixed budget of queries. Pair-matching is a particular instance of multi-armed bandit problem in which the arms are pairs of individuals and the rewards are edges linking these pairs. This bandit problem is non-standard though, as each arm can only be played once. Given this last constraint, sublinear regret can be expected only if the graph presents some underlying structure. This paper shows that sublinear regret is achievable in the case where the graph is generated according to a Stochastic Block Model (SBM) with two communities. Optimal regret bounds are computed for this pair-matching problem. They exhibit a phase transition related to the Kesten-Stigund threshold for community detection in SBM. To avoid undesirable features of optimal solutions, the pair-matching problem is also considered in the case where each node is constrained to be sampled less than a given amount of times. We show how this constraint deteriorates optimal regret rates. The paper is concluded by a conjecture regarding the optimal regret when the number of communities is larger than $2$. Contrary to the two communities case, we believe that a statistical-computational gap would appear in this problem.

With an eye toward understanding complexity control in deep learning, we study how infinitesimal regularization or gradient descent optimization lead to margin maximizing solutions in both homogeneous and non-homogeneous models, extending previous work that focused on infinitesimal regularization only in homogeneous models. To this end we study the limit of loss minimization with a diverging norm constraint (the "constrained path"), relate it to the limit of a "margin path" and characterize the resulting solution. For non-homogeneous ensemble models, which output is a sum of homogeneous sub-models, we show that this solution discards the shallowest sub-models if they are unnecessary. For homogeneous models, we show convergence to a "lexicographic max-margin solution", and provide conditions under which max-margin solutions are also attained as the limit of unconstrained gradient descent.

We propose a novel model for temporal detection and localization which allows the training of deep neural networks using only counts of event occurrences as training labels. This powerful weakly-supervised framework alleviates the burden of the imprecise and time-consuming process of annotating event locations in temporal data. Unlike existing methods, in which localization is explicitly achieved by design, our model learns localization implicitly as a byproduct of learning to count instances. This unique feature is a direct consequence of the model's theoretical properties. We validate the effectiveness of our approach in a number of experiments (drum hit and piano onset detection in audio, digit detection in images) and demonstrate performance comparable to that of fully-supervised state-of-the-art methods, despite much weaker training requirements.

A decentralized learning mechanism, Federated Learning (FL), has attracted much attention, which enables privacy-preserving training using the rich data and computational resources of mobile clients. However, data on mobile clients is typically not independent and identically distributed (IID) owing to diverse of mobile users' interest and usage, and FL on non-IID data could degrade the model performance. This work aims to extend FL to solve the performance degradation problem resulting from non-IID data of mobile clients. We assume that a limited number (e.g., less than 1%) of clients who allow their data to be uploaded to a server, and we propose a novel learning mechanism referred to as Hybrid-FL, where the server updates the model using data gathered from the clients and merge the model with models trained by clients. In Hybrid-FL, we design a heuristic algorithms that solves the data and client selection problem to construct "good" dataset on the server under bandwidth and time limitation. The algorithm increases the amount of data gathered from clients and makes the data approximately IID for improving model performance. Evaluations consisting of network simulations and machine learning (ML) experiments show that the proposed scheme achieves a significantly higher classification accuracy than previous schemes in the non-IID case.

One of the problems with these algorithms and the features they leverage is that they are based on correlational relationships that may not be causal. As Russ states: "Because there could be a correlation that's not causal. And I think that's the distinction that machine learning is unable to make--even though "it fit the data really well," it's really good for predicting what happened in the past, it may not be good for predicting what happens in the future because those correlations may not be sustained." This echoes a theme in a recent blog post by Paul Hunermund: "All of the cutting-edge machine learning tools--you know, the ones you've heard about, like neural nets, random forests, support vector machines, and so on--remain purely correlational, and can therefore not discern whether the rooster's crow causes the sunrise, or the other way round" I've made similar analogies before myself and still think this makes a lot of sense. However, a talk at the International Conference on Learning Representations definitely made me stop and think about the kind of progress that has been made in the last decade and the direction research is headed. Abstract: "Learning algorithms often capture spurious correlations present in the training data distribution instead of addressing the task of interest.

Dynamic Mode Decomposition (DMD) yields a linear, approximate model of a system's dynamics that is built from data. We seek to reduce the order of this model by identifying a reduced set of modes that best fit the output. We adopt a model selection algorithm from statistics and machine learning known as Least Angle Regression (LARS). We modify LARS to be complex-valued and utilize LARS to select DMD modes. We refer to the resulting algorithm as Least Angle Regression for Dynamic Mode Decomposition (LARS4DMD). Sparsity-Promoting Dynamic Mode Decomposition (DMDSP), a popular mode-selection algorithm, serves as a benchmark for comparison. Numerical results from a Poiseuille flow test problem show that LARS4DMD yields reduced-order models that have comparable performance to DMDSP. LARS4DMD has the added benefit that the regularization weighting parameter required for DMDSP is not needed.

Nonnegative matrix factorization based on generalized dual divergence Karthik Devarajan Department of Biostatistics & Bioinformatics, Fox Chase Cancer Center, Temple University Health System, Philadelphia, PA karthik.devarajan@fccc.edu Keywords: nonnegative matrix factorization, Kullback-Leibler divergence, dual divergence, EM algorithm, high dimensional data, tensor Abstract A theoretical framework for nonnegative matrix factorization based on generalized dual Kullback-Leibler divergence, which includes members of the exponential family of models, is proposed. A family of algorithms is developed using this framework and its convergence proven using the Expectation-Maximization algorithm. The proposed approach generalizes some existing methods for different noise structures and contrasts with the recently proposed quasi-likelihood approach, thus providing a useful alternative for nonnegative matrix factorizations. A measure to evaluate the goodness-of-fit of the resulting factorization is described.

In this paper, we develop a theory of learning nonlinear input-output maps with fading memory by dissipative quantum systems, as a quantum counterpart of the theory of approximating such maps using classical dynamical systems. The theory identifies the properties required for a class of dissipative quantum systems to be {\em universal}, in that any input-output map with fading memory can be approximated arbitrarily closely by an element of this class. We then introduce an example class of dissipative quantum systems that is provably universal. Numerical experiments illustrate that with a small number of qubits, this class can achieve comparable performance to classical learning schemes with a large number of tunable parameters. Further numerical analysis suggests that the exponentially increasing Hilbert space presents a potential resource for dissipative quantum systems to surpass classical learning schemes for input-output maps.

This paper presents a method for solving the supervised learning problem in which the output is highly nonlinear and discontinuous. It is proposed to solve this problem in three stages: (i) cluster the pairs of input-output data points, resulting in a label for each point; (ii) classify the data, where the corresponding label is the output; and finally (iii) perform one separate regression for each class, where the training data corresponds to the subset of the original input-output pairs which have that label according to the classifier. It has not yet been proposed to combine these 3 fundamental building blocks of machine learning in this simple and powerful fashion. This can be viewed as a form of deep learning, where any of the intermediate layers can itself be deep. The utility and robustness of the methodology is illustrated on some toy problems, including one example problem arising from simulation of plasma fusion in a tokamak.