Statistics 8711 (Geyer) Spring 2006

Course Announcement

• Statistical Computing
• Stat 8711
• Spring 2006

The departmental course description says

(3 cr.; prereq. 8701)
Basic numerical analysis for statisticians. Numerical methods for linear algebra, eigen-analysis, integration, optimization and their statistical applications.

This course hasn't been taught in a while, and it's hard to know what to put in it. Possible topics are

• numerical linear algebra
• optimization
  • classical methods for local optima
  • branch-and-bound methods for global optima
  • random search methods for global optima
• computational geometry

Too much stuff for a semester course. We will have to pick and choose. Students can pick topics, even topics not mentioned above.

The main purpose of the course is to acquaint students with really good stuff from numerical analysis, optimization, and computer science that most statisticians don't know about.

A secondary purpose is to break a lot of bad habits statisticians pick up from other statisticians.

• Think you want to calculate a matrix inverse? Generally you don't. You want to think you are solving linear equations, finding x that solves A x = b.
• Think EM or IRLS or IPF are good algorithms? They only have linear (not superlinear) convergence.

Numerical Linear Algebra

For numerical linear algebra, a very good textbook is Trefethen and Bau (1997), which covers not only the classic stuff like LU and QR but modern iterative methods for large scale problems like GMRES and Arnoldi.

Optimization

Classical Methods for Local Optima

This includes Newton, quasi-Newton, conjugate gradients, linear programming, quadratic programming, sequential quadratic programming, and the like -- all methods for unconstrained and constrained optimization that find local optima by deterministic search.

For this, a very good textbook is Nocedal and Wright (1999).

Branch-and-Bound Methods for Global Optima

Most statisticians are unaware this area exists, but it should eventually become important.

For this Hansen and Walster (2003), Hoang (1997), and Horst, Pardalos, and Thoai, (1996) look interesting (I only have seen the latter).

Since this is a new area, we probably don't want to buy these books and go through them, but we should probably spend some time on the subject.

Random Search Methods for Global Optima

Unlike the preceding section, this is well known to statisticians. It includes adaptive random search methods, such as so-called simulated annealing and genetic algorithms. There are lots of books, but none I care to recommend at this time.

Computational Geometry

Another topic of recent local interest, not mentioned in the departmental course description is computational geometry. This was used in Radu Lazar's thesis and Yumin Huang's thesis. These use (among many other things) the cddlib library written by Komei Fukuda and its R interface (rcdd) that I wrote. Try library(rcdd) and help(scdd) in R.