Algorithms and Data Sciences

Established: May 5, 2014

“Big Data” is currently an explosive phenomenon, triggered by proliferation of data in ever increasing volumes, rates, and variety. The Big Data revolution changes the perspective of many research areas in how they address both foundational questions and practical applications. In particular, this calls for a paradigm shift in Algorithms and the underlying mathematical techniques. While the impact of big data on the field of computing seems recent, foundations for algorithms on big data, especially based on random sampling on the fly, have been laid in the 90’s by theoretical computer scientists including those currently at MSR India. The goal for the research area of Algorithms and Data Sciences is to build on these foundational strengths and address the state of the art challenges in big data that could lead to practical impact. We see our efforts as a bridge between traditional Algorithms area, which focusses on well-structured problems and has a host of ideas and techniques to offer, and Statistics, Machine Learning and Optimization areas which have interesting and relevant models and problems.

Some research themes of our focus include

  • Massive Matrix Computation, including randomized and distributed PCA-like problems
  • Low rank approximations to Tensors
  • Streaming Algorithms
  • Property Testing
  • Clustering
  • Large Scale (distributed, stochastic) Optimization





Online Buy-at-Bulk Network Design
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi, in FOCS '15 Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Washington, DC, USA, October 17, 2015, View abstract, Download PDF



Memory Limited, Streaming PCA
Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain, in Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States., December 1, 2013, View abstract, View external link








Provable Non-convex Optimization for Machine Learning Problems

Established: April 4, 2014

In this work, we explore theoretical properties of simple non-convex optimization methods for problems that feature prominently in several important areas such as recommendation systems, compressive sensing, computer vision etc. Talks: Provable Non-convex Optimization for Machine Learning. Summer School on Non-convex Optimization, IIT Bombay, 2015. [part 1] [part 2] Iterative Hard Thresholding for Sparse/Low-rank Linear Regression. INRIA, France, 2015. [pdf version] Iterative Hard Thresholding for Robust Regression.  ITW, 2015. [pdf version] Provable Alternating Minimization methods for…