Reading List for my Research Group

In this post I collect a list of books that I recommend for getting up to speed on the most common types of math and optimization used in my research.

The first three sections are most directly related to my research. After that I give some suggestions on general CS, math, and programming background.

Optimization

The following are my two favorite resources for getting started on various aspects of optimization:

• Introduction to Linear Optimization by Bertsimas and Tsitsiklis. Great starting point. Most other optimization topics rely on linear optimization results covered here. Chapters 1,2, and 4 are most important.
• Convex Optimization by Boyd and Vandenberghe. An excellent book for getting started with more general convex optimization. Chapters 2-5, 9, and 10.

The following are more advanced and/or specialized books:

• Optimization by Vector Space Methods by Luenberger. This book is a classic for a more abstract treatment of optimization. Chapter 8 is my favorite coverage of convex duality in vector spaces.
• A Modern Introduction to Online Learning by Orabona. Excellent coverage of contemporary (circa 2019) online learning.
• Lectures on Modern Convex Optimization by Nemirovski. Comprehensive treatment of topics such as conic programming, SDPs, interior point methods, and mirror descent/mirror prox-type algorithms. I reopen Chapter 5 of these lecture notes on a yearly basis for various papers.
• Fundamentals of Convex Analysis by Hiriart-Urruty and Lemaréchal. A nice text for a more mathy treatment of convex analysis.
• First-Order Methods in Optimization by Amir Beck. This is a good source for things like proximal algorithms and ADMM. Only recommended if you’re directly interested in these types of algorithms.

Game Theory Foundations

The AGT book has excellent introductions to many areas of game theory, targeted at computer scientists.

• Algorithmic Game Theory (AGT) by Nisan, Roughgarden, Tardos, and Vazirani (it’s free). Most relevant to my research is Chapters 1-6, and 9-11.

If one is interested in auction theory, then the following book is a good starting point:

• Auction Theory by Vijay Krishna

The following are useful but slightly more topical in nature:

• Multiagent Systems (MS) by Leyton-Brown & Shoham (it’s free)
• Twenty Lectures on Algorithmic Game Theory (TLAGT) by Tim Roughgarden (the individual notes can be found on Tim’s website under the course “Algorithmic Game Theory”). Highly recommend reading these on the particular topics that interest you.
• Lecture notes from my PhD class.

Probability Theory

While not of primary importance in my research, I sometimes find myself needing to use concentration inequalities under various assumptions. When that happens, I consult the below resources.

• Wikipedia This gives a nice overview of quite a few of the most useful concentration inequalities
• Concentration Inequalities by Boucheron, Lugosi, and Bousquet. When Wikipedia fails you, this short text can sometimes be of help.

Linear Algebra and Other Math

It is a truth universally acknowledged, that a researcher in possession of a good problem, must be in want of linear algebra.

• Numerical Linear Algebra by Trefethen and Bau III. This books is great for building linear algebra intuition. Read and reread parts I, II, and V. Factorizations such as QR and SVD are incredibly helpful in understanding problems in machine learning, optimization, AI, statistics, etc.

• The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities by J. Michael Steele. This book helps develop problem-solving skills, and having a strong grasp of Cauchy-Schwarz, AM-GM, etc is very valuable. This is my favorite book for seeing the fun side of math. Not as important as other books listed here, from a strict foundations perspective.

Computer Science Foundations

• Algorithm Design by Kleinberg and Tardos. Being able to recognize when a problem is NP-hard, and proving it, is an important skill when working on combinatorial problems; even if one does applied research! For example, it tells you when you need to think about integer-programming rather than convex optimization.

Programming Skills

The following pieces of numerical software provide a good foundation that enables most research that I do. It’s all based on a python stack. A reasonable alternative is julia with the incredible JuMP package for mathematical optimization. Just beware that python is more likely to be used in industry.

• numpy A general familiarity with numpy and scipy is extremely useful for running simulations, testing hypotheses, or implementing algorithms. I recommend installing via the anaconda distribution.

• CVXPY. CVXPY is great for easily constructing mathematical programs and solving them with a variety of solvers.

• Gurobi get a free academic license and install this as a backend to CVXPY. It’s the best way to solve linear programs and mixed-integer programs.

• Mosek get a free academic license and install this as a backend to CVXPY. It’s the best way to solve certain conic programs, such as those for computing market equilibria.

It’s also important to be able to do data analysis/plotting. For those purposes Pandas and seaborn are good python packages. That said, the R tidyverse is incredibly good for data analysis. I find it much more enjoyable to work with than python. If you’re willing to learn two languages, I recommend:

• R for Data Science by Grolemund and Wickham.