Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
2013-10-21..2013-10-24
Berkeley, United States
Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24 ) ·
[Managing Parallelism 2025, Real-Time Decision Making 2018, Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Information Theory, Learning and Big Data (Simons Institute, 2015), Real-Time Decision Making, Randomized Numerical Linear Algebra and Applications 2018]
who it's for
machine learning engineers, distributed systems engineers, graph algorithm engineers, numerical linear algebra engineers, data scientists, high performance computing developers, privacy and security engineers
topics
MapReduce algorithmics; parallel graph computations; graph-parallel inference systems; cost models for locality; extreme multiclass prediction; parallel active learning; distributed machine learning systems; streaming triangle counting; single-machine billion-edge graphs; communication-optimal Strassen multiplication; randomized matrix algorithms (LSRN); tall-and-skinny QR in MapReduce
| title | author | length |
|---|---|---|
| MapReduce Algorithmics | Sergei Vassilvitskii | 53m |
MapReduce/Hadoop and related systems follow a BSP (Bulk Synchronous Parallel) model so algorithms must balance rounds and max per‑round work; with terabyte+… | ||
| Large Scale Response Prediction to Serve Ads on LinkedIn | Deepak Agarwal | 27m |
LinkedIn describes a production system that predicts ad click probability by combining a cold-start logistic regression trained on billions of observations and… | ||
| Three Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm... | Aydin Buluç | 30m |
A linear-algebra-first framework implements graph primitives (sparse matrix‑matrix, matrix‑vector, elementwise ops) using Combinatorial BLAS, exposing them to… | ||
| Scalable Graph-Parallel Inference Algorithms and Systems | Joseph E. Gonzalez | 30m |
New parallel algorithms combine an asynchronous splash primitive with prioritization, coloring and locking to make loopy belief propagation and Gibbs sampling… | ||
| Cost Models for Locality and Parallelism | Harsha Vardhan Simhadri | 28m |
Defines a program‑centric cost model that counts transfers on nested parallel DAGs and shows how to map it to a tree of caches using a parallel depth‑first… | ||
| Extreme Multiclass | John Langford | 29m |
Shows that multiclass prediction can run in O(log K) time while remaining statistically sound by reducing multiclass to binary partitions, using a ramp-loss… | ||
| Parallel Active Learning | Alekh Agarwal | 28m |
A parallel active learning pipeline combines a local active sifter that scans stored examples and subsamples informative points with a global passive updater… | ||
| MLbase: A Distributed Machine Learning System | Tim Kraska | 26m |
A declarative system called MLBase aims to let users request a classifier and get models back without coding algorithms, using MQL for queries and an MLI… | ||
| Sampling Algorithms to Count Frequent Patterns in Graphs | Ali Pinar | 27m |
Develops and proves wedge-sampling estimators that need ~38k independent samples for 1% error and 99% confidence, implements a streaming version using an edge… | ||
| Big Data on Smallish Machines | Guy Blelloch | 50m |
Argues that many “big” graphs actually fit on single shared‑memory servers: 6.6 billion edges fits on a $20k, 64‑core, 2 TB server and simple graph compression… | ||
| Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication | Grey Ballard | 28m |
Proposes CAPS, a parallel Strassen implementation that provably matches communication lower bounds by interleaving breadth- and depth-first recursion and using… | ||
| Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments | Michael Mahoney | 29m |
Randomized matrix methods run in parallel and distributed settings by random-projection preconditioning and importance sampling, producing practical solvers. A… | ||
| Tall-and-skinny QR Factorizations in MapReduce | David Gleich | 29m |
Runs 8,192 nonlinear heat-transfer simulations produce about 4.5 TB and get stitched into a 5 billion x 64 matrix (~2.2 TB) whose SVD yields reduced-order… | ||
| From Sparse Matrices to Graphs and Back Again | John Gilbert | 32m |
Argument claims sparse matrix and graph work are reciprocal: decades of graph methods optimize sparse Cholesky via nested dissection and chordal completion… | ||
| On the O(1/k) Convergence of the Asynchronous Distributed Alternating Direction Method of Mult... | Ermin Wei | 26m |
Proves an asynchronous distributed ADMM that converges to the optimal solution almost surely and achieves O(1/k) in expectation under convex (not smooth) Fi… | ||
| Distributed Learning, Communication Complexity, and Privacy | Nina Balcan | 33m |
Analyzes communication needed for distributed supervised learning and gives concrete protocols and bounds: a distributed AdaBoost yields D log(1/epsilon)… | ||
| Parallel Coordinate Descent Methods for Big Data Optimization | Peter Richtarik | 55m |
Presents a concrete parallel coordinate-descent framework built around an ESO (expected separable over-approximation) that produces algorithm parameters beta… | ||
| An Algebraic View of the New Randomized Kaczmarz Linear Solver | Sivan Toledo | 34m |
Claims a solver that turns an n-by-n Laplacian into a larger m-by-m square system so randomized Kaczmarz (Kaczmar/Casmaj) runs provably fast by choosing a… | ||
| Randomized Asynchronous Linear Solvers | Haim Avron | 26m |
Proposes a randomized Gauss‑Seidel solver for large sparse symmetric positive definite systems that runs fully asynchronously on shared memory with atomic… | ||
| Parallelization by Approximation | Kanat Tangwongsan | 30m |
Shows how greedy set cover becomes parallel by geometric bucketing plus a near-maximal independent-set routine that uses random priorities, yielding… | ||
| Highly Scalable Branch-and-Bound for Maximum Monomial Agreement | Cynthia Phillips | 29m |
Presents an exact solver for Maximum Monomial Agreement inside LPBoost using a custom branch-and-bound with equivalence-class upper bounds, strong multiway… | ||
| Provably Efficient Algorithms for Training Deep Networks | Shai Shalev-Shwartz | 33m |
Shows that extreme overspecification removes no local non-global minima: if hidden neurons ≥ number of examples and mild rank conditions hold, every local… | ||
| Peeling Algorithms | Michael Mitzenmacher | 34m |
Survey of peeling algorithms links Karp‑Sipser and pure literal ideas to practical tools like invertible Bloom lookup tables that store key/value XOR sums and… | ||
| Parallelism in Linear and Mixed Integer Programming | Ed Rothberg | 58m |
LP is mostly a solved problem in practice but the interior‑point (Barrier) solver gains from matrix‑matrix kernels while Simplex relies on cheap sparse LU… | ||
| Using Data-Oblivious Algorithms for Private Cloud Storage Access | Michael Goodrich | 30m |
Framework converts arbitrary RAM accesses into oblivious cloud storage with concrete costs: O(log^2 n) overhead with constant client registers, O(log n) with… | ||
| Communication Avoiding Algorithms for Linear Algebra and Beyond | Jim Demmel | 28m |
A model counts flops, words moved and messages and proves a flops/√M bandwidth lower bound for many nested-loop array codes; a 2.5D replicated matrix multiply… | ||
| Consensus-Based Distributed Online Prediction and Optimization | Michael Rabbat | 30m |
Claims order O(√M) regret when using distributed mini‑batches with only approximate averaging, builds on Nesterov dual averaging and replaces exact all‑reduce… | ||
| Large-Scale Generalized Matching | Rainer Gemulla | 26m |
Presents scalable algorithms for generalized matching problems on very large datasets, focusing on parallel and distributed methods. Describes techniques for… | ||
| Stochastic Optimization for Big Data Machine Learning Problems | Tong Zhang | 33m |
Claims that SVRG and SDCA fix SGD by eliminating gradient variance and deliver linear convergence while touching one example per iteration, so per-iteration… | ||
| First Order Methods for Distributed Network Optimization | Angelia Nedich | 29m |
Proposes distributed first‑order methods for minimizing the sum of node objectives over time‑varying directed graphs while removing the hard requirement of… | ||
| nothing matches | ||