CS 769: Optimization in Machine Learning

Instructor: Ganesh Ramakrishnan

Class Timings: (Slot 2 as of now, TTC has been requested to move our class to slot 1) 9:30-10:25 AM Mondays, Tuesdays 10:35-11:30 and Thursdays 11:35 AM -12:30 PM
Venue: MS Teams: Code will be shared on moodle with those who register with this course.
Venue: The course content will be organized on Moodle
Office hours: 3 PM - 4 PM on Wednesdays (preferred). If this time does not suit you, you could take an appointment with me for clearing doubts etc over email(s)
TAs:
Course Calendar from last offering of CS709 Convex Optimization, Playlist of lectures from last offering of CS709, and recently uploaded on youtube and all detailed course notes for CS709 Current Course Calendar (being moved to Moodle) (All recordings from current semester will be stored here

Tentative (Superset of) Syllabus

  1. Application of Continuous optimization in learning model parameters and application of discrete optimization in inference and auxiliary tasks such as feature selection, data subset selection, model compression etc.
  2. Basics of Continuous Optimization, Convexity, Gradient Descent, Projected/Proximal GD, Subgradient Descent, Accelerated Gradient Descent, Newton & Quasi Newton
  3. Lagrange and Fenchel Duality
  4. Important standard classes such as linear and quadratic programming, semidefinite programming, (possibly also second-order cone programming), etc.
  5. Fundamentals of discrete optimization, basic forms of combinatorial optimization (knapsack, s-t cuts/paths, matchings and matroids) and then discuss submodular functions (DPPs) and their applications
  6. Submodular Functions and Applications in Machine Learning, Submodularity and Convexity, Submodular Minimization, Submodular Maximization, Sub-gradient methods for non-differentiable functions
  7. Real world applications in feature selection, summarization and diversified search, structured prediction, data subset selection and model compression



Course Calendar from last offering of CS709 Convex Optimization (having all slides and with around 50% overlap with this course)), Playlist of lectures from last offering of CS709, and recently uploaded on youtube and all detailed course notes for CS709

Slides for the intro lecture (Friday, 8th Jan) and lecture 1 (Monday, 11th Jan), Recording of intro lecture (Friday, 8th Jan)

Credit/Audit Requirements: Anyone who does an exceptional course project that has the potential to be a publishable paper is eligible for a straight AA grade. Otherwise the grading breakup would be:
  • 20% Mid-semester exam
  • 30% End semester exam
  • 20% Project: A basic project will take any of the algorithms we study or any related papers, implement the algorithms in the paper, do a basic performance study and diagnose the performance. However, I would expect most projects to suggest ideas for improvement (atleast in specific settings such as multi core or multiple nodes or reasonable assumptions on matrices etc in the problem for which greater speedup is possible). A more advanced project would take a problem specification for which no solution is publicly available, figure out how to solve it, and implement the solution.
  • 10% Reading and paper presentation.
  • 20% 2 Programming Assignments
  • Audit students have to perform reading assignments and project.
  • Prerequisites: Sound understanding of linear algebra and mathematical foundations.


  • You can check out
    this link for a growing list of papers that we plan to cover in the assignments/projects or sometimes through discussions in the class. Please start looking at these papers for your seminar and/or projects. We also have some papers on submodularity. Roughly, submodularity is for discrete optimisation what convexity is for continuous optimisation. Check this out.




    References

    1. Lecture Notes and Books
    2. Convex Optimization: Algorithms and Complexity by S├ębastien Bubeck
    3. Convex Optimization by Stephen Boyd and Lieven Vandenberghe
    4. Lectures on Modern Convex Optimization by Aharon Ben-Tal and Arkadi Nemirovski
    5. Convex Analysis by R. T. Rockafellar, Vol. 28 of Princeton Math. Series, Princeton Univ. Press, 1970 (470 pages)
    6. Linear Algebra and Its Applications by Gilbert Strang
    7. Nonlinear Programming: 2nd Edition by Dimitri P. Bertsekas
    8. Numerical Optimization by Nocedal, Jorge, Wright, Stephen
    9. Learning with submodular functions: A convex optimization perspective by Bach, Francis, Foundations and Trends in Machine Learning 6.2-3 (2013): 145-373.
    10. Submodular functions and optimization by Fujishige, Satoru.
    11. cijver, Alexander, CWI, Kruislaan 413 (2003): 1098.
    12. An Introduction to Optimization by E.K.P Chong and S.H.Zak
    13. Introduction to Nonlinear Optimization - Theory, Algorithms and Applications by Amir Beck


    You can check out this link for a growing list of resource material (slides/videos/code/lecture notes, etc) for optimisation in general, and convex optimisation in particular. Please let me know if you come across some useful resource material that I could add to this list.


    Course Notes
    Lecture Notes

    Some applets for illustration purposes
    Link to spreadsheet

    Course Exercises
    Exercises

    Sample Matlab Files
    Sample Matlab Files

    Homework Solutions
    Homework Solutions