A Stochastic Newton Algorithm for Distributed Convex Optimization

on YouTube ↗35m

" summary

A distributed stochastic Newton algorithm for homogeneous convex problems introduces a stochastic Hessian-vector product oracle and solves constrained quadratic subproblems by running local SGD for k inner iterations between R communication rounds. The method proves convergence for quasi-self-concordant objectives (e.g., logistic regression), reduces the number and frequency of communication rounds versus prior methods, matches lower bounds in limited-communication regimes under assumptions, and shows empirical wins in the low-communication setting.

AI-written summary · about

" chapters (19)

1. 0:00Large-scale optimization intro
2. 1:30Stochastic gradient descent & higher-order methods
3. 3:40Distributed optimization & bottlenecks
4. 5:29Federated Stochastic Newton overview
5. 6:54Optimization setup & assumptions
6. 8:20Convex & smooth formulation
7. 10:48Communication structure
8. 12:18Local SGD & quadratic benefits
9. 14:28Newton’s method & second-order info
10. 16:17Quadratic subproblems & Hessian products
11. 18:27Stochastic Hessian-vector oracle
12. 19:34Quasi-self-concordance condition
13. 21:29Method design & constrained minimization
14. 22:59Convergence guarantees
15. 24:00Comparison with FedAc & bounds
16. 26:15Empirical results & efficiency
17. 27:39Open problems & future work
18. 29:06Conclusion
19. 29:52Q&A