A Language and Smoothed Semantics for Convergent Stochastic Gradient Descent

on YouTube ↗18m

" summary

Provides a smoothed denotational semantics (in Frölicher spaces) plus a mild type system forbidding parameter-dependent guards that ensures any typable real-valued program reduces to piecewise polynomials with recorded branch constraints; replaces indicator jumps by tunable sigmoids and computes gradients with a backward-mode AD variant that tracks constraints. For each fixed smoothing the Monte‑Carlo gradient estimator is unbiased and gradients converge uniformly, and a diagonalization SGD that increases accuracy over iterations provably yields stationary accumulation points (or diverges). Ongoing experiments; no recursion yet.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 2:16Stochastic Gradient Descent
3. 2:27Primarization Gradient Estimator Is Biased for Non-Differentiable Models
4. 4:17Programming Language
5. 5:43Type System

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 28mSmoothness Analysis for Probabilistic Programs with Application to Optimised Var...Hongseok Yang, Wonyeol Lee, Xavier Rival · POPL 2023
• 01h 04mOptimization for Machine Learning IIElad Hazan · Foundations of Machine Learning Boot Camp 2017
• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 13mNon-Parametric Convergence Rates for Plain Vanilla Stochastic Gradient DescentRaphaël Berthier · Deep Learning Theory Symposium 2021
• 26mADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Progra...Vikash K. Mansinghka, Mathieu Huot, Alexander K. Lew, Sam Staton · POPL 2023
• 07mOn the Reparameterisation Gradient for Non-Differentiable but Continuous ModelsC.-H. Luke Ong, Dominik Wagner · LAFI 2023
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022