Search

AbstractRecent theoretical studies have shown that heavy-tails can emerge in stochastic optimization due to ‘multiplicative noise’, even under surprisingly simple settings, such as linear regression with Gaussian data. While these studies have uncovered several interesting phenomena, they consider conventional stochastic optimization problems, which exclude decentralized settings that naturally arise in modern machine learning applications. In this paper, we study the emergence of heavy-tails in decentralized stochastic gradient descent (DE-SGD), and investigate the effect of decentralization on the tail behavior. We first show that, when the loss function at each computational node is twice continuously differentiable and strongly convex outside a compact region, the law of the DE-SGD iterates converges to a distribution with polynomially decaying (heavy) tails. To have a more explicit control on the tail exponent, we then consider the case where the loss at each node is a quadratic function, and show that the tail-index can be estimated as a function of the step-size, batch-size, and the topological properties of the network of the computational nodes. Then, we provide theoretical and empirical results showing that DE-SGD has heavier tails than centralized SGD. We also compare DE-SGD to disconnected SGD where nodes distribute the data but do not communicate. Our theory uncovers an interesting interplay between the tails and the network structure: we identify two regimes of parameters (stepsize and network size), where DE-SGD can have lighter or heavier tails than disconnected SGD depending on the regime. Finally, to support our theoretical results, we provide numerical experiments conducted on linear regression and neural networks that suggest the heavier tails is correlated with better generalization in the decentralized setting. [ABSTRACT FROM AUTHOR]

Non-negative matrix factorization has been shown to be powerful for modelling audio signals. Many useful applications based on NMF, including musical source separation and polyphonic transcription, have been presented in the field of music information retrieval. The multiplicative update rules for making inference on the NMF model are quite simple and practical; however, they do not scale up well with the increasing size of the dictionary matrices. In this study, we develop efficient approaches based on randomized matrix decompositions and exemplar selection that can easily handle very large dictionary matrices that can be encountered in real applications. We apply our methods on the transcription of polyphonic piano music. The results show that by only retainingof a large dictionary matrix, we still get high performance in terms of objective measures. [ABSTRACT FROM AUTHOR]

In this paper we present two probabilistic models for real-time acoustic event detection: the Hidden Markov Model and the Change Point Model. We construct the generative models in such a way that each time slice of the audio spectra is generated from a 'spectral template' which is multiplied by a volume factor. From this point of view, we treat the event detection problem as a template matching problem where the aim is to infer the active template and its volume while the audio data are observed. The novel contribution in this paper is a Change Point Model for real-time template matching using a conditional Poisson observation model. For this model, we develop an exact inference algorithm and an effective approximation schema. We evaluate the models on online monophonic pitch tracking of two low pitched instruments where we focus on the trade-off between the latency and accuracy of the system. The evaluation results suggest favourable features such as quick detection, graceful degradation and an acceptable level of accuracy when compared with a state-of-the-art monophonic pitch tracking algorithm (YIN). We believe that these models provide a flexible and powerful modelling framework for real-time event and pitch detection. [ABSTRACT FROM AUTHOR]

We study distributed stochastic gradient (D-SG) method and its accelerated variant (DASG) for solving decentralized strongly convex stochastic optimization problems where the objective function is distributed over several computational units, lying on a fixed but arbitrary connected communication graph, subject to local communication constraints where noisy estimates of the gradients are available. We develop a framework which allows to choose the stepsize and the momentum parameters of these algorithms in a way to optimize performance by systematically trading off the bias, variance and dependence to network effects. When gradients do not contain noise, we also prove that D-ASG can achieve acceleration, in the sense that it requires O(p ≤ log(1=")) gradient evaluations and O(p ≤ log(1=")) communications to converge to the same fixed point with the non-accelerated variant where ≤ is the condition number and" is the target accuracy. For quadratic functions, we also provide finer performance bounds that are tight with respect to bias and variance terms. Finally, we study a multistage version of D-ASG with parameters carefully varied over stages to ensure exact convergence to the optimal solution. It achieves optimal and accelerated O(k= p ≤) linear decay in the bias term as well as optimal O(-2=k) in the variance term. We illustrate through numerical experiments that our approach results in accelerated practical algorithms that are robust to gradient noise and that can outperform existing methods. [ABSTRACT FROM AUTHOR]