Convex Optimization: Fall 2013

Machine Learning 10-725
(cross-listed as Statistics 36-725)

Instructors:
Barnabas Poczos (bapoczos at cs dot cmu dot edu)
Ryan Tibshirani (ryantibs at stat dot cmu dot edu)

TAs:
Adona Iosif (aiosif at cs dot cmu dot edu)
Yifei Ma (yifeim at cs dot cmu dot edu)
Aaditya Ramdas (aramdas at cs dot cmu dot edu)
Sashank Reddi (sjakkamr at cs dot cmu dot edu)

Lecture times: Tuesdays and Thursdays 3-4:20pm, Doherty Hall 1212

Recitation times: Wednesdays 4:30-6pm, Gates 4307

Office hours:
BP: Thursdays 4:30-5:30pm, Gates 8231
RT: Wednesdays 10-11am, Baker 229B
AI: Wedsnesdays 2-3pm, Gates 8221
YM: Mondays 4:30-5:30pm, Gates 8223
AR: Tuesdays 4:30-5:30pm, Gates 8223
SR: Mondays 2-3pm, Gates 8223

Course syllabus: PDF

Scribing: Sign up for scribing here, and find the Latex scribing template here

Feedback: Tell us how we can make this course better for you! You can use this form to quickly give feedback about the instructors, the TAs, homework, ask us to re-explain a topic in more depth, or tell us about anything else we can do better.

Go to:   Lectures | Recitations | Videos | Assignments | Schedule

Lecture notes

  1. Introduction (Ryan)
  2. Linear programming I (Barnabas)
  3. Linear programming II (Barnabas)
  4. Convexity (Barnabas)
  5. Gradient descent (Ryan)
  6. Subgradients (Ryan)
  7. Subgradient method (Ryan)
  8. Generalized gradient descent and acceleration (Ryan)
  9. Newton method (Barnabas)
  10. Conjugate gradient (Barnabas)
  11. Quasi-Newton (Barnabas)
  12. Duality (Ryan)
  13. KKT conditions (Ryan)
  14. Duality uses and correspondences (Ryan)
  15. Ellipsoid methods (Barnabas)
  16. Penalty methods (Barnabas)
  17. Barrier methods (Barnabas)
  18. Semidefinite programming I (Barnabas)
  19. Semidefinite programming II (Barnabas)
  20. Independent components analysis (Barnabas)
  21. Putting it all together (Ryan)
  22. Simulated Annealing (Barnabas)
  23. Dual methods & ADMM (Ryan)
  24. Coordinate descent (Ryan)
  25. Nonconvex? No problem! (Ryan)
Top

Recitation notes

  1. Math review, alternate view of simplex (Aaditya)
  2. Convexity, strong convexity, Lipschitz gradients, etc. (Aaditya)
  3. Duality and the KKT conditions (Adona)
Top

Videos

Click here for lecture and recitation videos (YouTube playlist)



Top

Assignments

Top

Schedule

Here is the estimated class schedule. It is subject to change, depending on time and class interests. (R = Ryan, B = Barnabas)

Tues Aug 27 1. Introduction (R)
Thurs Aug 29 2. Linear programs I (B)
Tues Sept 3 3. Linear programs II (B)
Thurs Sept 5 4. Convexity (B) Hw 1 out
Tues Sept 10 5. Gradient descent (R)
Thurs Sept 12 6. Subgradients (R)
Tues Sept 17 7. Subgradient method (R)
Thurs Sept 19 8. Generalized gradient and acceleration (R) Hw 1 in; Hw 2 out
Tues Sept 24 9. Newton's method (B)
Thurs Sept 26 10. Conjugate gradient (B) Project milestone 1 in
Tues Oct 1 11. Quasi-Newton (B)
Thurs Oct 3 12. Duality (R) Hw 2 in; Hw 3 out
Tues Oct 8 13. KKT conditions (R)
Thurs Oct 10 14. Duality uses & correspondences (R)
Tues Oct 15 15. Ellipsoid methods (B)
Thurs Oct 17 16. Penalty methods (B) Hw 3 in; Hw 4 out
Tues Oct 22 17. Barrier methods (B)
Thurs Oct 24 18. Semidefinite programs I (B)
Tues Oct 29 19. Semidefinite programs II (B)
Thurs Oct 31 20. Semidefinite programs III (B) Hw 4 in
Tues Nov 5 Midterm (covers up to lec 18) Midterm
Thurs Nov 7 21. Putting it all together (R)
Tues Nov 12 22. Matrix differentials, nonconvex tools (B) Project milestone 2 in; Hw 5 out
Thurs Nov 14 23. Dual methods & ADMM (R)
Tues Nov 19 24. Coordinate-wise minimization (R)
Thurs Nov 21 25. Nonconvex? No problem! (R)
Tues Nov 26 26. Large-scale optimization (Guest) Hw 5 in
Thurs Nov 28 No class (Thanksgiving)
Tues Dec 3 Little test (covers up to lec 25) Little test
Thurs Dec 5 No class (work on projects)
Fri Dec 13, 1-4pm Final project presentations Final project in

Top