Some important topics will be omitted because high-quality solutions are already available in most software. For example, the generation of pseudo-random numbers is a classic topic, but existing methods built in to standard software packages will suffice for our needs. On the other hand, we will spend a bit of time on some classical numerical linear algebra ideas, because choosing the right method for solving a linear equation (for example) can have a huge impact on the time it takes to solve a problem in practice, particularly if there is some special structure that we can exploit.

Deterministic optimization

- Newton-Raphson, conjugate gradients, preconditioning, quasi-Newton methods, Fisher scoring, EM and its various derivatives

- Numerical recipes for linear algebra: matrix inverse, LU, Cholesky decompositions, low-rank updates, SVD, banded matrices, Toeplitz matrices and the FFT, Kronecker products (separable matrices), sparse matrix solvers

- Convex analysis: convex functions, duality, KKT conditions, interior point methods, projected gradients, augmented Lagrangian methods, convex relaxations

- Applications: support vector machines, splines, Gaussian processes, isotonic regression, LASSO and LARS regression

Graphical models: dynamic programming, hidden Markov models, forward-backward algorithm, Kalman filter, Markov random fields

Stochastic optimization: Robbins-Monro and Kiefer-Wolfowitz algorithms, simulated annealing, stochastic gradient methods

Deterministic integration: Gaussian quadrature, quasi-Monte Carlo. Application: expectation propagation

Monte Carlo methods

- Rejection sampling, importance sampling, variance reduction methods (Rao-Blackwellization, stratified sampling)

- MCMC methods: Gibbs sampling, Metropolis-Hastings, Langevin methods, Hamiltonian Monte Carlo, slice sampling. Implementation issues: burnin, monitoring convergence

- Sequential Monte Carlo (particle filtering)

- Variational and stochastic variational inference

Givens and Hoeting (2005) Computational statistics

Robert and Casella (2004) Monte Carlo Statistical Methods

Boyd and Vandenberghe (2004), Convex Optimization.

Press et al, Numerical Recipes

Sun and Yuan (2006), Optimization theory and methods

Fletcher (2000) Practical methods of optimization

Searle (2006) Matrix Algebra Useful for Statistics

Spall (2003), Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control

Shewchuk (1994), An Introduction to the Conjugate Gradient Method Without the Agonizing Pain

Boyd et al (2011), Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

Date | Topic | Reading | Notes |
---|---|---|---|

Jan 12 | Introduction | Ch. 1-2 of Givens+Hoeting | See Sun and Yuan (2006) for further details on convergence analysis. Berland's notes on automatic differentiation. Mahsereci and Hennig (2016) on Bayesian linesearch. HW: derive the convergence rate of the secant method. |

Jan 19 | Gaussian processes | Gardner et al '19, Loper et al '20 for fast GP inference. | See Rasmussen and Williams (2006) for more background on GP regression. Also notes by John Cunningham. Rahimi+Recht '07 on random features; Drineas + Mahoney '16 on randomized linear algebra. Also Shewchuk (1994) for (beautiful) background on conjugate gradients and Chan and Ng (1996) on PCG for Toeplitz systems. HW: code up a GP regression. |

Jan 26 | Stochastic gradient descent | Bottou et al (2018), Wilson et al (2018), Zhang et al (2015) | |

Feb 2 | Prox methods and acceleration | Bubeck (2014), Bach et al (2011), Schmidt et al (2011) | Nesterov (1998), Devolder et al (2014), nice lecture notes from Y. Chen (2019) |

Feb 9, 16 | Graphical models; dynamic programming; message passing | Rabiner tutorial, Wainwright lecture notes | Background: Wainwright and Jordan (2008), MP and AMP notes by A. Maleki, Sarkka and Garcia-Fernandez (2019) on parallelizing HMM inference, Schniter et al (2016), Rush and Venkataramanan (2018) on VAMP and AMP |

Feb 23 | Scaling quasi-Newton methods | Goldfarb et al '21, Martens + Grosse `20 | |

Feb 16, 23, Mar 16 | Monte Carlo methods | Lam and Mottet (2015), Lam and Mottet (2018), Park and Casella (2008), Yang and Narisetty (2020), Chowdhury and Jermaine (2018) | Forman-Mackey et al (2012) |

Mar 2 | Spring break | ||

Mar 9 | 2-minute project idea presentations | ||

Mar 23 | Sequential Monte Carlo | Doucet and Johansen (2011), Pitt and Shephard (1999), Naesseth et al (2017), Le et al (2018), Lux (2018) | Further reading collected by A. Doucet; Kantas et al (2014), Abdessalem et al (2017) |

Mar 30 | Variational inference and optimal transport | Dempster et al (1977), Neal and Hinton (1999), Blei et al (2018), Peyre and Cuturi (2020) | |

Apr 6 | Gradients for discrete models; expectation propagation | Grathwohl et al (2018), Yin and Zhou (2019), Vehtari et al (2019) | |

Apr 13 | A bit of queuing theory | Daley et al (1992) | |

Apr 20 | Project presentations | Send me your report as a .pdf by the end of the week. |