Sign Up

1111 Engineering Drive, Boulder, CO 80309

View map

Randomization methods for big-data

Abstract: In this era of big-data, we must adapt our algorithms to handle large datasets. One obvious issue is that the number of floating-point operations (flops) increases as the input size increases, but there are many less obvious issues as well, such as the increased communication cost of moving data between different levels of computer memory. Randomization is increasingly being used to alleviate some of these issues, as those familiar with random mini-batch sampling in machine learning are well aware of. This talk goes into some specific examples of using randomization to improve algorithms. We focus on special classes of structured random dimensionality reduction, including the count sketch, tensorSketch, Kronecker fast Johnson-Lindenstrauss sketch, and pre-conditioned sampling. These randomized techniques can then be applied to speeding up the classical Lloyd's algorithm for K-means and for computing tensor decompositions, for example. If time permits, we will also show extensions to optimization, including a gradient-free method that uses random finite differences and a method for solving semi-definite programs in an optimal low-memory fashion.

Bio: Stephen Becker is an associate professor of applied mathematics at the University of Colorado Boulder, with courtesy appointments in the Electrical, Computer and Energy Engineering and Computer Science departments. Previously he was a Herman Goldstine Postdoctoral fellow in Mathematical Sciences at IBM Research in Yorktown Heights, NY, and a postdoctoral fellow via the Fondation Sciences Mathématiques de Paris at Paris 6. He received his PhD in 2011 from Caltech under Emmanuel Candès, and bachelor’s degrees in math and physics from Wesleyan University. His research interests are in optimization, machine learning, signal processing, imaging, inverse problems in quantum information, PDE-constrained optimization, and randomized numerical linear algebra.

https://cuboulder.zoom.us/j/190280621

  • Mohammad Zahidul Alam
  • Niraj Agarwal

2 people are interested in this event

User Activity

No recent activity