Organizer(s):

Petros Drineas, Purdue University

Michael Mahoney, University of California, Berkeley

Aleksander Mądry, Massachusetts Institute of Technology

David P. Woodruff, Carnegie Mellon University

Description

Many tasks in machine learning, statistics, scientific computing, and optimization ultimately boil down to numerical linear algebra. Randomized numerical linear algebra (RandNLA) exploits randomness to improve matrix algorithms for fundamental problems like matrix multiplication and least-squares using techniques such as random sampling and random projection. RandNLA has received a great deal of interdisciplinary interest in recent years, with contributions coming from numerical linear algebra, theoretical computer science, scientific computing, statistics, optimization, data analysis, and machine learning, as well as application areas such as genetics, physics, astronomy, and internet modeling. RandNLA is of great interest from a theoretical perspective, but it has the potential to be a transformative new tool for machine learning, statistics, and data analysis. The workshop aims to:

(1) Present connections between RandNLA and TCS. The workshop will highlight worst-case theoretical aspects of matrix randomized algorithms, including models of data access, pass efficiency, lower bounds, and connections to other algorithms for large-scale machine learning and data analysis, input-sparsity time embeddings, and geometric data analysis methods.

(2) Elucidate the interplay between RandNLA, sketching, data streams, and communication-constrained implementations. Besides input-sparsity time algorithms and terabyte-scale algorithms, a number of algorithms in RandNLA draw inspiration from techniques in the data stream literature, particularly those based on oblivious sketching. For instance, Cauchy embeddings and subsampling data structures—originally studied in the context of estimating norms in a data stream—now give the fastest known algorithms for robust regression. TensorSketch, a variant of the CountSketch data structure for finding heavy hitters in a stream, has machine learning applications such as kernel classification and the tensor power method.

(3) Present connections between RandNLA and more traditional approaches to problems in applied mathematics, statistics, and optimization. The workshop will emphasize connections with (convex) optimization, but also consider signal processing, sparsity-based algorithms, and matrix reconstruction.  Recent developments in RandNLA with connections to statistics and optimization include both using RandNLA techniques to solve traditional statistics and optimization problems, e.g., ridge regression, Newton methods, etc., as well as characterizing implicit statistics and optimization perspectives on existing RandNLA algorithms.

This workshop aims to build on ideas and collaborations developed during the 2018 Simons Institute program on Foundations of Data Science as well as the broader DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization.

Program

Monday, September 16, 2019

Tuesday, September 17, 2019

Wednesday, September 18, 2019

Call For Participation

Attendance at the workshop is open to all interested participants (subject to space limitations), but please register if you would like to attend this workshop.

Full video playlist

Important information about parking: If you are not affiliated with Rutgers and will need parking during the event, you will receive a link to register your vehicle for parking after you register for the event. Please register your vehicle using this link to avoid ticketing.

If you need to register for parking but don't have access to your registration confirmation email, the link is below for your convenience.

https://rudots.nupark.com/events/Events/Register/54e7dfa3-b4c4-4b26-bb9f-efe27bec60f4

Presented in association with the Special Focus on Bridging Continuous and Discrete Optimization.

Please click here to get information for travel and accomodations information for this event.

Registration for this event is closed.