Stochastic Second Order Optimization Methods I
summary
Covers using subsampled Newton methods for finite-sum empirical risk: form a sub-sampled Hessian and solve the positive-definite linear system approximately with CG, using a relative residual theta = 1/√kappa to recover near-exact Newton rates; combines global guarantees (convergence from anywhere) with local linear–quadratic error recursion and shows that after enough iterations the algorithm accepts unit step size 1 and becomes problem-independent. Also surveys sketching (leverage sampling, randomized transforms), Neumann-series inverse approximations, proximal- and semi-smooth-Newton variants.
AI-written summary · about
chapters (6)
- 0:00Start
- 2:31Problem Statement
- 7:18First Order Methods
- 11:01Second Order Methods
- 27:10Sub-Sampling Hessian
- 54:22Semi-Smooth Newton-type Methods
related talks
01h 18mOptimization I
01h 01mRobustness, Stochastics, Uncertainty 2
42mOptimization Crash Course
27mTalk by Ali Kavis (UT Austin)
34mFast Algorithms for Multivariate ODEs arising in Sampling and Learning
01h 07mOptimization Crash Course (continued)
47mThe Importance of Better Models in Stochastic Optimization...
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms