A PAC Approach to Application-Specific Algorithm Selection
summary
Proposes a PAC-style solution to pick algorithms from parametric families (e.g. greedy independent‑set rules weight/(deg+1)^rho) and gives two concrete models: an online model with an adversary that yields a no-regret impossibility for proper learning, plus a positive bound if instance weights get randomized (smoothing) giving inverse‑poly(n) average regret; and a statistical PAC model using pseudo‑dimension to bound sample complexity, showing many natural families (greedy, local search, step‑size choices for gradient descent) have low pseudo‑dimension so they are learnable from polynomially many samples.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:33Motivation
- 0:52Example
- 3:21Graph Coloring
- 4:29Broadcasting Incentive Auction
- 5:23Choosing Independent Sets
- 8:30Auction Mechanism
- 12:47General Setup
- 13:05Family of Algorithms
- 16:15Online Learning
- 20:42Multiplicative weights
- 26:33Proof
- 32:33Second Model
related talks
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
44mParsimonious Learning-Augmented Algorithms
40mApproximation Algorithms for Optimization under Uncertainty
45mStudying Generalization in Deep Learning via PAC-Bayes
27mDistribution Learning Meets Graph Structure Sampling
48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from Samples
38mMulti-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!
01h 01mRobustness, Stochastics, Uncertainty 2