Three-Toed Sloth

Optimization III: Stochastic, Constrained, and Penalized Optimization (Introduction to Statistical Computing)

Lecture 19: Stochastic, Constrained, and Penalized Optimization.

Constrained optimization: maximizing multinomial likelihood as an example of why constraints matter. The method of Lagrange multipliers for equality constraints. Lagrange multipliers as shadow prices, indicating how much a marginal weakening of the constraint would improve the optimum. Inequality constraints and their Lagrange multipliers. Mathematical programming. Barrier methods for inequality constraints. The correspondence between constrained and penalized optimization.

Stochastic optimization: Difficulties of optimizing statistical functions when the data is large. Sampling as an alternative to averaging over the whole data. Stochastic gradient descent and stochastic Newton's method as an application of sampling. Simulated annealing to escape local minima.

Optional reading 1: Léon Bottou and Olivier Bosquet, "The Tradeoffs of Large Scale Learning"

Optional reading 2: Francis Spufford, Red Plenty (cf.); Herbert Simon, The Sciences of the Artificial, especially chapters 5 and 8.

Introduction to Statistical Computing