Spring 2022.

Instructor: Dr. Swati Gupta,
Assistant Professor and Fouts Family Early Career Professor,
School of Industrial and Systems Engineering,
Affiliations: Center for Machine Learning, ACO Program, Algorithms and Randomness Center, Physical Internet Lab, Parker H. Petit Institute, Institute for Data Engineering and Science, School of Computer Science

Office: Groseclose Building 437
Contact: swatig@gatech.edu
Lectures: Tu, Th 3:30-4:45 PM, Groseclose 402. 

Office Hours: By appointment.

Description: We will study classical as well as recent results in submodular function optimization, with a focus on both discrete and continuous optimization perspectives. We will cover the following topics: 

(i) Submodularity: Definitions, Base polyhedra, Facial Structure, Lovasz Extension, Submodular Function Minimization (SF-min), Multilinear Relaxation, SF Maximization (SF-max).

(ii) Convex optimization methods and applications: Conditional Gradient Descent, Mirror Descent, Cutting Plane methods, Alternating Projections, Separable Optimization over Base Polytopes and SF-min, Rounding Techniques like Swap Rounding, Applications of Submodular Penalties to Learning. 

(iii) Recent results in submodular optimization: Critiques, reading and discussion of selected recent results on submodular optimization problems including SF-min, SFM-max, matroid intersection, decomposable submodular functions, submodular partitioning, submodular secretary and ordering problems. 

Recommended Reading:

Grading: Homeworks (40%), Midterm (20%), Paper Presentation (10%), Class Project (30%)

Preliminaries: Linear inequalities (ISyE 7661) or Advanced Combinatorial Optimization (ISyE 7686), or permission of the instructor.  

Tentative List of Lectures:

  1. Submodularity – definition, examples, polyhedra, matroids, examples, optimization problems. Convex perspective. 

2. Facial structure of Polyhedra, Vertices, Properties, Total Dual Integrality

3. Lovasz Extension and Submodular Function Minimization using Ellipsoid Algorithm. 

4. General Convex Minimization over the Base Polytope

5. Parametric Submodular Function Minimization, Line Search in Submodular Polytopes and Partition Functions (Applications to Document Summarization)

6. Approximation Algorithms for Submodular Ordering Problem and Submodular Partitioning 

7. Multilinear Extension and Submodular Function Maximization

8. Cardinality Constrained Submodular Function Maximization and Variants

9. Rounding within Base Polytope – Dependent Rounding, Swap Rounding

10. Mirror Descent (Projected Gradient Descent) and Conditional Gradient Method

11. Improved Approximations for SFM using Projected Gradient Descent on Lovasz Extension

12. Primal View: Separable Optimization over Base Polytopes using Combinatorial Methods

13. Structured Regression using Submodular Penalties 

14. Kelley’s Cutting Plane Algorithms and Duality with Conditional Gradient Method

15. Other Continuous Optimization Methods: Alternating Minimization 

16. Recent advances in Submodular Optimization Problems

Course Policies: 

  • The assignments have to be submitted online, with typed up solutions in LaTeX. 
  • You are encouraged to discuss homework/assignments problems with your fellow students. But your final answers should be based on your own understanding unless it is a group assignment, which will be announced on Canvas. Copying others’ work is NOT acceptable and violates the honor code. Write the names of students you have discussed the assignments with. In case answers are found copied from another student, both the students (the one who allowed copying, and the one who copied) will both get a 0 and might also result in obtaining a D or F grade overall.  
  • Late assignments: We will allow a grace period of 1 hour for every assignment. For every hour that the assignment is submitted late, the grade will be reduced by 10% (linearly interpolated), without exceptions. The only official extensions for late assignments will be granted with a letter from the Dean of Student’s Office to be received before the assignment is due.   
  • Exams: Missing an exam will be accommodated only in case of Institute approved absences with a letter from the Dean of Students. Alternative arrangements will be made on a case by case basis, but the instructor must be informed at least two weeks prior to the exam.
  • Academic Honor Code
    It is your responsibility to get familiar with the Georgia Tech Honor Code and you are bound by its requirements. For any questions any Academic Honor Code issues, please consult me, my teaching assistants, or www.honor.gatech.edu. (Links to an external site.)

Mutual Respect and Expectations
ISyE 7687 is an advanced graduate level course. You are expected to have an attitude to learn, instead of just getting a grade. To produce a positive teaching and learning environment, instructors and students must partner with one another in and out of the classroom. Mutual respect is at the heart of such a partnership and is characterized by respectful language and imagery, punctuality and care for others’ time, clear and thorough communication, access to resources, and an openness to dialogue and debate. As a Georgia Tech faculty member, I am committed to such respect and I invite you to join me in working towards the best possible learning environment, so that all can meet their highest ambitions. Further, we will not tolerate discrimination towards any group of students. For more information about faculty and student expectations, as recognized in Georgia Tech policy, please see the following web page: http://www.catalog.gatech.edu/rules/22.php (Links to an external site.)

Office of Disability Services
If you are a student with learning needs that require special accommodation, please contact the Office of Disability Services (http://disabilityservices.gatech.edu/) at (404)894-2563 as soon as possible to make an appointment to discuss your special needs and to obtain an accommodations letter. Please also e-mail me as soon as possible in order to set up a time to discuss your learning needs.