Tractability And Overparametrization In Some Simple Models
Talkat Algorithmic Advances for Statistical Inference with Combinatorial Structure · 2021-10-11..10-15·
summary
Proves precise large-|kappa| asymptotics for when negative‑margin linear classifiers exist versus when they’re findable: the satisfiability threshold δ_S scales like (log|kappa|)/Φ(kappa) (pure noise) and gains an e^{α kappa} factor with linear signal, while the algorithmic lower bound sits near 1/Φ(kappa). Techniques combine Gaussian comparison (a tailored Gordon argument), a weighted second‑moment existence proof, and a simple convex algorithm — maximize a random linear functional (one‑step Frank‑Wolfe) — which succeeds but leaves a provable gap to the information limit.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 6:08Motivation
- 10:50Example
- 13:49Model
- 24:22Naive Calculation
- 29:17Algorithm
- 35:42Phase Diagrams
- 41:47Analysis
related talks
30mComputational Barriers For Learning Some Generalized Linear Models
37mEfficient Algorithms for Reliable Machine Learning
44mConcentration Inequalites in Learning with Kernels
59mTesting Assumptions of Learning Algorithms
01h 05mDistribution Estimation and Applications III
29mComputational Barriers to Estimation from Low-Degree Polynomials
48mBenign Overfitting in Linear Prediction
53mDesigning Robust Learners