Sketching and Projecting

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=c10tC86rQYs


Duration: 52:38
285 views
7

Deanna Needell (University of California, Los Angeles)
https://simons.berkeley.edu/talks/deanna-needell-university-california-los-angeles-2023-10-10
Sketching and Algorithm Design

We discuss recent work on sketching and projecting methods for linear systems as well as sketching in linear discriminant analysis. Both frameworks utilize stochastic gradient approaches, with the goal of obtaining solutions similar or exactly to the un-sketched problems, with significantly less computational burden. We present convergence guarantees for the sketched predictions on data within a fixed number of iterations. These guarantees account for both the modeling assumptions on the data and algorithmic randomness from the sketching procedure. We also include numerical results comparing the approaches.



Other Videos By Simons Institute for the Theory of Computing


2023-10-12Tight Bounds for Volumetric Spanners in All Norms
2023-10-12A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching
2023-10-11Sketching Algorithms for Max-DICUT and other CSPs
2023-10-11Error Correction for Streaming Messages
2023-10-11Streaming Lower Bounds for the Needle Problems
2023-10-11Streaming Euclidean k-median and k-means with o(log n) Space
2023-10-11Capacity Analysis of Vector Symbolic Architectures
2023-10-11Improved Frequency Estimation Algorithms with and without Predictions
2023-10-11Testing Positive Semidefiniteness and Eigenvalue Approximation
2023-10-11Sketching Techniques for Kernel Density Estimation or for Optimal Transport Computations
2023-10-11Sketching and Projecting
2023-10-10Lightning Talks
2023-10-10Memory-Regret Tradeoff for Online Learning
2023-10-09Memory-Regret Tradeoff for Online Learning
2023-10-09Sketching Techniques for Kernel Density Estimation
2023-10-09Sketching for Proving Generalization of Support Vector Machines
2023-10-09Fast Attention Requires Bounded Entries
2023-10-09Randomized Embeddings and Neural Networks
2023-10-09Sublinear Time Eigenvalue Approximation via Random Sampling
2023-10-09Nikhil Srivastava and Venkatesan Guruswami | Polylogues
2023-10-06Machine-Checked Proofs and the Rise of Formal Methods in Mathematics | Theoretically Speaking


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Sketching and Algorithm Design
Deanna Needell