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

People

Publications

2016

2015

2014

2013

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

2012

2010

2009

2008

2007

Projects

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…

‚Äč