There are no silver bullets in algorithm design, and no single algorithmic idea is powerful and flexible enough to solve every computational problem. Nor are there silver bullets in algorithm analysis, as the most enlightening method for analyzing an algorithm often depends on the problem and the application. However, typical algorithms courses rely almost entirely on a single analysis framework, that of worst-case analysis, wherein an algorithm is assessed by its worst performance on any input of a given size. The purpose of this book is to popularize several alternatives to worst-case analysis and their most notable algorithmic applications, from clustering to linear programming to neural network training. Forty leading researchers have contributed introductions to different facets of this field, emphasizing the most important models and results, many of which can be taught in lectures to beginning graduate students in theoretical computer science and machine learning.
Author(s): Tim Roughgarden (Editor)
Edition: 1
Publisher: Cambridge University Press
Year: 2021
Language: English
Commentary: Vector PDF
Pages: 704
City: Cambridge, UK
Tags: Algorithms; Algorithms Design Techniques; Algorithm Analysis; Algorithm Complexity
Cover
Half-title
Title page
Copyright information
Contents
Preface
List of Contributors
1 Introduction
1.1 The Worst-Case Analysis of Algorithms
1.2 Famous Failures and the Need for Alternatives
1.3 Example: Parameterized Bounds in Online Paging
1.4 Overview of the Book
1.5 Notes
Part One Refinements of Worst-Case Analysis
2 Parameterized Algorithms
2.1 Introduction
2.2 Randomization
2.3 Structural Parameterizations
2.4 Kernelization
2.5 Hardness and Optimality
2.6 Outlook: New Paradigms and Application Domains
2.7 The Big Picture
2.8 Notes
3 From Adaptive Analysis to Instance Optimality
3.1 Case Study 1: Maxima Sets
3.2 Case Study 2: Instance-Optimal Aggregation Algorithms
3.3 Survey of Additional Results and Techniques
3.4 Discussion
3.5 Selected Open Problems
3.6 Key Takeaways
3.7 Notes
4 Resource Augmentation
4.1 Online Paging Revisited
4.2 Discussion
4.3 Selfish Routing
4.4 Speed Scaling in Scheduling
4.5 Loosely Competitive Algorithms
4.6 Notes
Part Two Deterministic Models of Data
5 Perturbation Resilience
5.1 Introduction
5.2 Combinatorial Optimization Problems
5.3 Designing Certified Algorithms
5.4 Examples of Certified Algorithms
5.5 Perturbation-Resilient Clustering Problems
5.6 Algorithm for 2-Perturbation-Resilient Instances
5.7 (3+ ε)-Certified Local Search Algorithm for k-Medians
5.8 Notes
6 Approximation Stability and Proxy Objectives
6.1 Introduction and Motivation
6.2 Definitions and Discussion
6.3 The k-Median Problem
6.4 k-Means, Min-Sum, and Other Clustering Objectives
6.5 Clustering Applications
6.6 Nash Equilibria
6.7 The Big Picture
6.8 Open Questions
6.9 Relaxations
6.10 Notes
7 Sparse Recovery
7.1 Sparse Recovery
7.2 A Simple Insertion-Only Streaming Algorithm
7.3 Handling Deletions: Linear Sketching Algorithms
7.4 Uniform Algorithms
7.5 Lower Bound
7.6 Different Measurement Models
7.7 Matrix Recovery
7.8 Notes
Part Three Semirandom Models
8 Distributional Analysis
8.1 Introduction
8.2 Average-Case Justifications of Classical Algorithms
8.3 Good-on-Average Algorithms for Euclidean Problems
8.4 Random Graphs and Planted Models
8.5 Robust Distributional Analysis
8.6 Notes
9 Introduction to Semirandom Models
9.1 Introduction
9.2 Why Study Semirandom Models?
9.3 Some Representative Work
9.4 Open Problems
10 Semirandom Stochastic Block Models
10.1 Introduction
10.2 Recovery via Semidefinite Programming
10.3 Robustness Against a Monotone Adversary
10.4 Information Theoretic Limits of Exact Recovery
10.5 Partial Recovery and Belief Propagation
10.6 Random versus Semirandom Separations
10.7 Above Average-Case Analysis
10.8 Semirandom Mixture Models
11 Random-Order Models
11.1 Motivation: Picking a Large Element
11.2 The Secretary Problem
11.3 Multiple-Secretary and Other Maximization Problems
11.4 Minimization Problems
11.5 Related Models and Extensions
11.6 Notes
12 Self-Improving Algorithms
12.1 Introduction
12.2 Information Theory Basics
12.3 The Self-Improving Sorter
12.4 Self-Improving Algorithms for 2D Maxima
12.5 More Self-Improving Algorithms
12.6 Critique of the Self-Improving Model
Part Four Smoothed Analysis
13 Smoothed Analysis of Local Search
13.1 Introduction
13.2 Smoothed Analysis of the Running Time
13.3 Smoothed Analysis of the Approximation Ratio
13.4 Discussion and Open Problems
13.5 Notes
14 Smoothed Analysis of the Simplex Method
14.1 Introduction
14.2 The Shadow Vertex Simplex Method
14.3 The Successive Shortest Path Algorithm
14.4 LPs with Gaussian Constraints
14.5 Discussion
14.6 Notes
15 Smoothed Analysis of Pareto Curves in Multiobjective Optimization
15.1 Algorithms for Computing Pareto Curves
15.2 Number of Pareto-optimal Solutions
15.3 Smoothed Complexity of Binary Optimization Problems
15.4 Conclusions
15.5 Notes
Part Five Applications in Machine Learning and Statistics
16 Noise in Classification
16.1 Introduction
16.2 Model
16.3 The Best Case and the Worst Case
16.4 Benefits of Assumptions on the Marginal Distribution
16.5 Benefits of Assumptions on the Noise
16.6 Final Remarks and Current Research Directions
17 Robust High-Dimensional Statistics
17.1 Introduction
17.2 Robust Mean Estimation
17.3 Beyond Robust Mean Estimation
17.4 Notes
18 Nearest Neighbor Classification and Search
18.1 Introduction
18.2 The Algorithmic Problem of Nearest Neighbor Search
18.3 Statistical Complexity of k-Nearest Neighbor Classification
18.4 Notes
19 Efficient Tensor Decompositions
19.1 Introduction to Tensors
19.2 Applications to Learning Latent Variable Models
19.3 Efficient Algorithms in the Full-Rank Setting
19.4 Smoothed Analysis and the Overcomplete Setting
19.5 Other Algorithms for Tensor Decompositions
19.6 Discussion and Open Questions
20 Topic Models and Nonnegative Matrix Factorization
20.1 Introduction
20.2 Nonnegative Matrix Factorization
20.3 Topic Models
20.4 Epilogue: Word Embeddings and Beyond
21 Why Do Local Methods Solve Nonconvex Problems?
21.1 Introduction
21.2 Analysis Technique: Characterization of the Landscape
21.3 Generalized Linear Models
21.4 Matrix Factorization Problems
21.5 Landscape of Tensor Decomposition
21.6 Survey and Outlook: Optimization of Neural Networks
21.7 Notes
22 Generalization in Overparameterized Models
22.1 Background and Motivation
22.2 Tools to Reason About Generalization
22.3 Overparameterization: Empirical Phenomena
22.4 Generalization Bounds for Overparameterized Models
22.5 Empirical Checks and Holdout Estimates
22.6 Looking Ahead
22.7 Notes
23 Instance Optimal Distribution Testing and Learning
23.1 Testing and Learning Discrete Distributions
23.2 Instance Optimal Distribution Learning
23.3 Identity Testing
23.4 Digression: An Automatic Inequality Prover
23.5 Beyond Worst-Case Analysis for Other Testing Problems
23.6 Notes
Part Six Further Applications
24 Beyond Competitive Analysis
24.1 Introduction
24.2 The Access Graph Model
24.3 The Diffuse Adversary Model
24.4 Stochastic Models
24.5 Direct Comparison of Online Algorithms
24.6 Where Do We Go from Here?
24.7 Notes
25 On the Unreasonable Effectiveness of SAT Solvers
25.1 Introduction: The Boolean SAT Problem and Solvers
25.2 Conflict-Driven Clause Learning SAT Solvers
25.3 Proof Complexity of SAT Solvers
25.4 Proof Search, Automatizability, and CDCL SAT Solvers
25.5 Parameteric Understanding of Boolean Formulas
25.6 Proof Complexity, Machine Learning, and Solver Design
25.7 Conclusions and Future Directions
26 When Simple Hash Functions Suffice
26.1 Introduction
26.2 Preliminaries
26.3 Hashing Block Sources
26.4 Application: Chained Hashing
26.5 Optimizing Block Source Extraction
26.6 Application: Linear Probing
26.7 Other Applications
26.8 Notes
27 Prior-Independent Auctions
27.1 Introduction
27.2 A Crash Course in Revenue-Maximizing Auctions
27.3 Defining Prior-Independence
27.4 Sample-Based Approach: Single Item
27.5 Competition-Based Approach: Multiple Items
27.6 Summary
27.7 Notes
28 Distribution-Free Models of Social Networks
28.1 Introduction
28.2 Cliques of c-Closed Graphs
28.3 The Structure of Triangle-Dense Graphs
28.4 Power-Law Bounded Networks
28.5 The BCT Model
28.6 Discussion
28.7 Notes
29 Data-Driven Algorithm Design
29.1 Motivation and Context
29.2 Data-Driven Algorithm Design via Statistical Learning
29.3 Data-Driven Algorithm Design via Online Learning
29.4 Summary and Discussion
30 Algorithms with Predictions
30.1 Introduction
30.2 Counting Sketches
30.3 Learned Bloom Filters
30.4 Caching with Predictions
30.5 Scheduling with Predictions
30.6 Notes
Index
