Beyond Big-O: Statistical Analysis of Performance Scaling

on YouTube ↗52m

" summary

Empirical analysis fits explicit scaling models, uses bootstrap confidence intervals on median runtimes, and finds per-size runtimes are roughly log-normal runtime distributed so bands for 5–95% quantiles are predictable. Exact TSP solver Concord matches a root-exponential model on uniform Euclidean instances and extrapolates from 1,500 to 4,500 cities with predictions captured by the bootstrap bands. Automated parameter configuration shrinks scaling: Lingeling goes from ~3s to 0.16s (orders of magnitude), EAX’s fitted model drops to ~0.25·1.23^{√n} and can become effectively polynomial.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:45Matrix Multiplication
3. 4:03Empirical Algorithmics
4. 4:44Concorde on RUE: scaling of mean running time according to Applegate et al., 2006 (p. 495)
5. 7:51Concorde on RUE: Model fitting
6. 11:28Concorde on RUE: Extrapolation challenge
7. 17:19Dependence of empirical scaling models on given set (= sample) of instances?
8. 18:56Concorde on RUE: Model validation
9. 20:03Distribution of run time over sets of instances for fixed
10. 22:18Empirical Scaling of Inexact TSP Solvers on RUE
11. 25:14Empirical Scaling of Complete SAT Solvers on Phase-Transition Random 3-SAT
12. 32:12Lingeling on software verification
13. 33:07CPLEX on Wildlife Corridor Design
14. 33:23Knuth's sat13 on diverse set of instances
15. 35:17Can (automated) configuration improve scaling behaviour?
16. 35:33Effect of Automated Configuration on Empirical Scaling of TSP Solver EAX on RUE
17. 36:52Effect of PSM Configuration on Empirical Scaling of TSP Solver EAX on RUE

" related talks

• 23mSome New Results on Random Points in the Unit SquareAlan Frieze · KARPfest80
• 34mError Estimation for Randomized Numerical Linear Algebra: Bootstrap MethodsMiles Lopes · Randomized Numerical Linear Algebra and Applications 2018
• 32mStatistics for EngineersHeinrich Hartmann · SREcon22 Europe/Middle East/Africa
• 30mA physicist's approach to Data ScienceElad Berkman · PyCon Israel 2017
• 01h 10mPrincipled Performance AnalyticsNarayan Desai, Brent Bryan · SREcon22 Americas
• 47mThe Importance of Better Models in Stochastic Optimization...John Duchi · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 31mScaling up Lyft’s Growth via Causal ML and BanditsLei Tang · MLconf 2022 San Francisco
• 32mAdventures with Randomized Algebra for Extreme-Scale Signal ProcessingAnshumali Shrivastava · Randomized Numerical Linear Algebra and Applications 2018