Can Non-Convex Optimization be Robust?

on YouTube ↗46m

" summary

Shows that if an unknown smooth objective F is pointwise close to an accessed function f with error nu ≤ O(ε^{3/2}/(√ρ · d)) then convolving f with a Gaussian and running a two-query stochastic gradient estimator finds an ε-second-order local minimum of F in polynomial time; a matching lower bound proves larger nu (by ~log^2 d) forces exp(log^2 d) queries. For matrix completion under a semi-random adversary, a polynomial-time spectral reweighting preprocessing (using graph spectral sparsification tools) produces a weighted nonconvex objective with no bad local minima.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:47Why is non-convex optimization "easy"?
3. 5:00Locally optimizable functions
4. 6:36What happens when assumptions fail?
5. 13:53Robust non-convex optimization with perturbed objective
6. 16:02Motivation: Empirical Risk vs. Population Risk.
7. 21:52Idea: Smoothing
8. 26:42Properties of Smoothing
9. 28:52Ideas of the Lower Bound
10. 31:06Matrix Completion
11. 34:39Semi-Random Adversary
12. 37:03Counter Examples
13. 38:16Preprocessing
14. 40:44Summary
15. 41:12Open Problems

" related talks

• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 29mImplicit Regularization in Nonconvex Statistical EstimationYuxin Chen · Optimization, Statistics and Uncertainty
• 01h 17mRobust Optimization and GeneralizationJohn Duchi · Modern Paradigms in Generalization Boot Camp 2024
• 57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max OptimizationNisheeth Vishnoi · Adversarial Approaches in Machine Learning 2022
• 42mOptimization Crash CourseAshia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)