Approximate coding computing

on YouTube ↗32m

" summary

Describes concrete schemes that trade fidelity for speed by producing an approximate matrix product in stages then exact recovery later, using MatDot-like polynomial encodings, complex-valued evaluations, random permutation of subblocks and grouping. Simulations with 40 workers multiplying 100×8000 matrices (K=8, standard threshold 15) show discrete error jumps: first useful approximation after 6 or 8 workers, improved at later arrivals. Proposes successive approximation coding with a three-group design and alternatives using OrthoMatDot bases; works in simulation but has numerical stability and wall-clock evaluation caveats.

AI-written summary · about

" chapters (12)

1. 0:00Coded computing research
2. 1:02Approximate coded computing
3. 3:30Straggler approaches
4. 6:03MatDot codes
5. 8:29Epsilon MatDot codes
6. 13:55Early recovery via polynomials
7. 16:47Layered coding design
8. 21:58Orthogonal polynomials
9. 24:49Coding schemes comparison
10. 25:32Open questions
11. 26:37Conclusion
12. 26:59Q&A

" related talks

• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 25mSimple, Efficient and Neural Algorithms for Sparse CodingAnkur Moitra · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 57mCoding for Interactive CommunicationLeonard J. Schulman · Real-Time Decision Making
• 44mStochastic Integration via Error-Correcting CodesDimitris Achlioptas · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 31mPast, Present and Future of Randomized Numerical Linear Algebra IIMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 28mRandomized Constrained Matrix DecompositionsBenjamin Erichson · Randomized Numerical Linear Algebra and Applications 2018
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)Ran Gelles · Information Theory in Complexity Theory and Combinatorics 2015