Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent

on YouTube ↗11m

" summary

Defines proxy convexity: two auxiliary functions h and g that sandwich a nonconvex objective so first-order guarantees transfer. Proves a proxy PL inequality that lower-bounds gradient by g minus a slack term ψ, and applies it to concrete settings: single ReLU neuron (GD finds a near-optimal solution despite worst-case hardness) and a noisy half-space where g becomes the negative derivative of the logistic loss and ψ equals the label corruption rate, implying all stationary points have error O(noise).

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 0:52Understanding the success of neural networks
3. 3:48Ideal non-convex framework for NNs
4. 9:02Proxy PL inequality - example
5. 9:44Summary

" related talks

• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 01h 11m(Hidden) Symmetries of Computational Problems (continued)Michael Walter, Avi Wigderson · Geometric Methods in Optimization and Sampling Boot Camp
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max OptimizationNisheeth Vishnoi · Adversarial Approaches in Machine Learning 2022
• 46mAnalyzing Optimization and Generalization in Deep Learning via Trajectories of Gradient DescentNadav Cohen · Frontiers of Deep Learning 2019
• 35mOn the Global Convergence and Approximation Benefits of Policy Gradient MethodsDaniel Russo · Mathematics of Online Decision Making 2020
• 55mZeroth-Order Methods for Convex-Concave Minmax Problems: Learning from Strategically Generated DataChinmay Maheshwari · Adversarial Approaches in Machine Learning 2022
• 49mDiscrete Optimization using Log-Concave PolynomialsNima Anari · Hyperbolic Polynomials and Hyperbolic Programming