Large Scale Machine Learning and Convex Optimization - Lecture 3

Explore the intricacies of large-scale machine learning and convex optimization in this comprehensive lecture. Delve into the challenges of handling big data in machine learning and signal processing, focusing on online algorithms like stochastic gradient descent. Examine the optimal convergence rates for general convex and strongly-convex functions. Discover how the smoothness of loss functions can be leveraged to design innovative algorithms with improved performance. Learn about a novel Newton-based stochastic approximation algorithm that achieves faster convergence rates without strong convexity assumptions. Investigate the practical applications of combining batch and online algorithms for strongly convex problems. Cover topics such as subgradient descent, stochastic approximation, adaptive algorithms for logistic regression, self-concordance, and least-mean-square algorithms. Gain insights through theoretical proofs and synthetic example simulations.

Intro
Main motivating examples
Subgradient method/descent (Shor et al., 1985)
Subgradient descent for machine learning Assumptions is the expected risk, the empirical risk
Summary: minimizing convex functions
Relationship to online learning
Stochastic subgradient "descent" /method
Convex stochastic approximation Existing work • Known global minimax rates of convergence for non-smooth problems (Nemirovsky and Yudin, 1983; Agarwal et al., 2012)
Robustness to wrong constants for = Cn
Robustness to lack of strong convexity
Beyond stochastic gradient method
Outline
Adaptive algorithm for logistic regression
Self-concordance
Least-mean-square algorithm
Markov chain interpretation of constant step sizes
Least-squares - Proof technique
Simulations - synthetic examples