CS 7301: Spring 2021 Course on Advanced Topics in Optimization for Machine Learning
Video Lectures are on this youtube playlist: https://www.youtube.com/playlist?list=PLGod0_zT9w92_evaYrf3-rE67AmgPJoUU
https://github.com/rishabhk108/OptimizationDemos
https://docs.google.com/spreadsheets/d/1UHHFlo_8QAvmXjWqoU02Calq86S-ewYl7Jczjhgr0wY/edit?usp=sharing
Deadline for finalizing on the papers to cover: February 26th
Deadine for finalizing on the project topic: March 5th
- Week 1
- Logistics, Outline of this Course
- Continuous Optimization in ML
- Convex Sets and Basics of Convexity
- Week 2: Gradient Descent and Family
- Convex Functions, Properties, Minima, Subgradients
- Gradient Descent and Line Search
- Week 3: Gradient Descent Cont.
- Accelerated Gradient Descent
- Projected and Proximal Gradient Descent
- Week 4
- Projected GD and Conditional GD (Constrained Case)
- Second Order Methods (Newton, Quasi-Newton, BFGS, LBFGS)
- Week 5
- Second Order Methods Completed
- Barzelia Borwein and Conjugate GD
- Coordinate Descent Family
- Week 6
- Stochastic Gradient and Family (SGD, SVRG)
- SGD for Non-Convex Optimization. Modern variants of SGD particularly for deep learning (e.g. Adagrad, Adam, AdaDelta, RMSProp, Momentum etc.)
- Week 7
- Submodular Optimization: Basics, Definitions, Properties, and Examples.
- Week 8
- Submodular Information Measures: Conditional Gain, Submodular Mutual Information, Submodular Span, Submodular Multi-Set Mutual Information
- Week 9
- Submodular Minimization and Continuous Extensions of Submodular Functions. Submodular Minimization under constraints
- Week 10
- Submodular Maximization Variants, Submodular Set Cover, Approximate submodularity. Algorithms under different constraints and monotone/non-monotone settings. Also, distributed and streaming algorithms, DS Optimization, Submodular Optimization under Submodular Constraints
- Week 11
- Applications of Discrete Optimization: Data Subset Selection, Data Summarization, Feature Selection, Active Learning etc.
- Rest of the Weeks
- Paper Presentations/Project Presentations by the Students
- 10% for Class Participation (Interaction, asking questions, answering questions)
- 30% Assignments (2 Assignments, one on continuous optimization and one on discrete optimization)
- 30% Paper Presentations (1-2 papers per student)
- 30% for the Final Project
- Take a new dataset/problem and study how existing optimization algorithms work on them
- Take an existing problem and compare all optimization algorithms with your implementation from scratch
- Design a ML optimization toolkit with algorithms implemented from scratch -- if one of you would like to extend my current python demos for optimization, that will be an awesome contribution and I might pick it up for my future classes and acknowledge you :)
- Convex Optimization: https://blogs.princeton.edu/imabandit/orf523-the-complexities-of-optimization/
- Convex Optimization: http://www.cs.cmu.edu/~pradeepr/convexopt/
- Convex Optimization: https://ee227c.github.io/
- Convex Optimization: https://github.com/epfml/OptML_course
- Convex Optimization: https://www.cs.ubc.ca/~schmidtm/Courses/LecturesOnML/
- Combinatorial Optimization: http://www-math.mit.edu/~goemans/18433S15/18433.html
- Subodular Optimization: https://people.ece.uw.edu/bilmes/classes/ee563_spring_2018/
- Martin Jaggi's EPFL Course notes on Convex Optimization: https://github.com/epfml/OptML_course/blob/master/lecture_notes/lecture-notes.pdf
- Sebastian Bubeck's Monograph on Convex Optimization: https://arxiv.org/pdf/1405.4980.pdf
- Submodular Optimization Survey: http://www.bioinfo.org.cn/~dbu/AlgorithmCourses/Lectures/Lec7-SubModular-Golovin.pdf
- Francis Bach's Monograph on Submodular Optimizationn and Convexity: https://arxiv.org/pdf/1111.6453.pdf
- Online convex optimization by Elad Hazan: https://sites.google.com/view/intro-oco/