« search calendars

« DIMACS Workshop on Randomized Numerical Linear Algebra, Statistics, and Optimization

DIMACS Workshop on Randomized Numerical Linear Algebra, Statistics, and Optimization

September 16, 2019 - September 18, 2019

Location:

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

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

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.

 

Monday, September 16, 2019

8:30 AM - 9:00 AM

Registration and Breakfast

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

9:00 AM - 9:40 AM

Sparse Metric Repair

Anna Gilbert, University of Michigan

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

9:40 AM - 10:20 AM

Sample Efficient Toeplitz Covariance Estimation

Cameron Musco, University of Massachusetts, Amherst

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

10:20 AM - 10:50 AM

Break

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

10:50 AM - 11:30 AM

Multicriteria Dimensionality Reduction

Santosh Vempala, Georgia Institute of Technology

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

11:30 AM - 12:10 PM

Adaptive Sketching for the Low-rank Tensor Approximation Problem

Alex Gittens, Rensselaer Polytechnic Institute (RPI)

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

12:10 PM - 2:00 PM

Lunch

Venue

DIMACS Lounge

Rutgers University

CoRE Building, Room 401

Rutgers University

96 Frelinghuysen Road

Piscataway, NJ 08854

2:00 PM - 2:40 PM

Graph Algorithms and Batched Processing

Richard Peng, Georgia Institute of Technology

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

2:40 PM - 3:20 PM

Variance Reduction for Gradient Compression

Peter Richtarik, King Abdullah University of Science and Technology (KAUST)

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

3:20 PM - 3:50 PM

Break

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

3:50 PM - 4:30 PM

Contour Integral Methods for Linear and Nonlinear Eigenvalue Problems: Learning from Sketches of the Resolvent

Mark Embree, Virginia Tech

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

4:30 PM - 5:10 PM

A Geometric Analysis of Model and Algorithm-Induced Uncertainties for Randomized Least Squares Regression

Ilse Ipsen, North Carolina State University

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

5:30 PM - 6:30 PM

Dinner

Venue

DIMACS Lounge

Rutgers University

CoRE Building, Room 401

Rutgers University

96 Frelinghuysen Road

Piscataway, NJ 08854

 

Tuesday, September 17, 2019

8:30 AM - 9:00 AM

Registration and Breakfast

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

9:00 AM - 9:40 AM

Asymptotic Analysis of Sampling Estimators for Randomized Numerical Linear Algebra Algorithms

Ping Ma, University of Georgia

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

9:40 AM - 10:20 AM

Newton-MR: Newton’s Method Without Smoothness or Convexity

Fred Roosta, University of Queensland

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

10:20 AM - 10:50 AM

Break

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

10:50 AM - 11:30 AM

Leverage scores, Christoffel functions, and applications of RandNLA beyond NLA

Christopher Musco, New York University (NYU)

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

11:30 AM - 12:10 PM

Pragmatic Ridge Spectral Sparsification for Large-Scale Graph Learning

Ioannis Koutis, New Jersey Institute of Technology

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

12:10 PM - 2:00 PM

Lunch

Venue

DIMACS Lounge

Rutgers University

CoRE Building, Room 401

Rutgers University

96 Frelinghuysen Road

Piscataway, NJ 08854

2:00 PM - 2:40 PM

Latent Simplex Learning in input-sparsity-efficient time

Ravi Kannan, Microsoft Research

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

2:40 PM - 3:20 PM

Ridge Regression and Deterministic Ridge Leverage Score Sampling

Shannon McCurdy, Ancestry

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

3:20 PM - 3:50 PM

Break

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

3:50 PM - 4:30 PM

Exact Sampling of Determinantal Point Processes with Sublinear Time Preprocessing

Michal Derezinski, University of California, Berkeley

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

4:30 PM - 5:10 PM

Error Estimation for Randomized Numerical Linear Algebra: Bootstrap Methods

Miles Lopes, University of California, Davis

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

5:10 PM - 5:50 PM

Tight Bounds for L1 Oblivious Subspace Embeddings

David P. Woodruff, Carnegie Mellon University

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

 

Wednesday, September 18, 2019

8:30 AM - 9:00 AM

Registration and Breakfast

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

9:00 AM - 9:40 AM

A Numerical Analysis Approach to Convex Optimization

Rasmus Kyng, ETH Zurich

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

9:40 AM - 10:20 AM

Matrix Sketching for Secure Federated Learning

Shusen Wang, Stevens Institute of Technology

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

10:20 AM - 10:50 AM

Break

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

10:50 AM - 11:30 AM

RandNLA and its Applications in Second-order Optimization and Deep Learning

Zhewei Yao, University of California, Berkeley

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

11:30 AM - 12:10 PM

A Random Matrix Viewpoint of Learning with Gradient Descent

Zhenyu Liao, University of Paris - Saclay

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

12:10 PM - 2:00 PM

Lunch

Venue

DIMACS Lounge

Rutgers University

CoRE Building, Room 401

Rutgers University

96 Frelinghuysen Road

Piscataway, NJ 08854

2:00 PM - 2:40 PM

Advanced Techniques for Low-rank Matrix Approximations

Ming Gu, University of California, Berkeley

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

2:40 PM - 3:20 PM

Statistical Estimations from Locality Sensitive Hashing (LSH): Adaptive Sampling at the cost of random sampling

Anshumali Shrivastava, Rice University

Venue

Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

 

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.

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

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