Dynamic extensions of Stochastic block model (SBM) are of importance in several fields that generate temporal interaction data. These models, besides producing compact and interpretable network representations, can be useful in applications such as link prediction or network forecasting. In this paper we present a conditional pseudo-likelihood based extension to dynamic SBM that can be efficiently estimated by optimizing a regularized objective. Our formulation leads to a highly scalable approach that can handle very large networks, even with millions of nodes. We also extend our formalism to causal impact for networks that allows us to quantify the impact of external events on a time dependent sequence of networks. We support our work with extensive results on both synthetic and real networks.

We present online prediction methods for time series that let us explicitly handle nonstationary artifacts (e.g., trend and seasonality) present in most real time series. Specifically, we show that applying appropriate transformations to such time series before prediction can lead to improved theoretical and empirical prediction performance. Moreover, since these transformations are usually unknown, we employ the learning with experts setting to develop a fully online method (NonSTOP-NonSTationary Online Prediction) for predicting nonstationary time series. This framework allows for seasonality and/or other trends in univariate time series and cointegration in multivariate time series. Our algorithms and regret analysis subsume recent related work while significantly expanding the applicability of such methods. For all the methods, we provide sublinear regret bounds. We support all of our results with experiments on simulated and real data.

We address the issue of using mini-batches in stochastic optimization of SVMs. We show that the same quantity, the spectral norm of the data, controls the parallelization speedup obtained for both primal stochastic subgradient descent(SGD) and stochastic dual coordinate ascent (SCDA) methods and use it to derive novel variants of mini-batched SDCA. Our guarantees for both methods are expressed in terms of the original nonsmooth primal problem based on the hinge-loss.

Many terrains in outdoor robot navigation problems have paths that are distinct and continuous compared to the non-traversable regions. In image space these paths correspond to continuous segments that can be thought of as clusters embedded in image feature space. These segments very often translate directly to traversable ground plane. In this paper we build the intuition for semi-supervised methods in path identification and present a Markov random walk based approach that requires very few labeled points. The method creates a nearest neighbor graph representation of the current image frame using features deemed suitable for the task and propagates labels based on the concept of absorbing Markov chains. We extend this formalism to the task of dynamically identifying traversable and non-traversable regions in the incoming image frames. We present results on actual terrains corresponding to test courses used by the LAGR test team. The results demonstrate that with minimal initial supervision the robot can navigate to the goal. We also conduct comparisons of our path labeling technique against other machine learning techniques including nonlinear support vector machines on hand labeled data. The results demonstrate that our semi-supervised approach is proficient in the domain of path traversal in unstructured domains.

The role of a distance metric in many supervised and semi-supervised learning applications is central in the success of clustering algorithms. Since existing metrics like Euclidean do not necessarily reflect the true structure (clusters or manifolds) in the data, it becomes imperative that an appropriate metric be somehow learned from training or labeled data. Metric learning has been a relatively new topic in data mining and machine learning, though most work that deals with this topic learns a suitable linear transformation of the original data. This transformation is usually learned using training data and has been shown to improve test data classification accuracy. In this paper we present a Markov random walk based semi-supervised method for metric learning. Our method differs from the aforementioned techniques in that we use minimal labeled data and we do not assume any Mahalanobis type metric structure on the data. We create a computationally efficient nearest neighbor graph representation of the data and pose a semidefinite program that learns the random walk on the associated graph. This is used to generate a distance measure between all unlabeled points and the performance is compared against other important metrics using the k-NN classification rule.