DSC 211, Winter 2024 – Introduction to Optimization

Lectures: Tuesdays/Thursdays 5:00 pm -6:20 pm PST

Location: PCYNH (Pepper Canyon Hall) 121

Instructors:

• Jun-Kun Wang (jkw005 at ucsd.edu)

• Yuan (Merlin) Chang

• Marialena Sfyraki

Office hours:

• Jun-Kun Wang (3PM-4PM, Jacobs Hall Room 6404)

• Yuan (Merlin) Chang (Monday 1PM-2PM, HDSI Room 336)

• Marialena Sfyraki (Wednesday 5PM-6PM, HDSI Room 355)

Syllabus: Available on Canvas

Course description

This course covers the theoretical and algorithmic foundations of optimization. We will walk through classical optimization algorithms such as Gradient Descent, Coordinate Descent, the Frank-Wolfe Method, Accelerated Methods, Mirror Descent, Stochastic Gradient Descent, and Online Gradient Descent. We will put particular emphasis on understanding the behaviors and the convergence rate guarantees of these algorithms, as well as the tools and techniques to analyze them. We will also cover some convex analysis and duality theory. Students will learn the basic foundations of deterministic convex optimization, stochastic optimization, online convex optimization, min-max optimization, and non-convex optimization

A tentative list of topics that we will cover include

• Mathematical background and Gradient Flow.

• Convexity.

• Gradient Descent for smooth, smooth and strongly convex functions.

• Reduction

• Projected Gradient Descent and Frank-Wolfe Method.

• Coordinate Descent

• Duality Theory; Stochastic Dual Coordinate Ascent

• Mirror Descent

• SGD

• SGD and variance reduction

• Online Convex Optimization

• Min-Max Optimization

• Acceleration via the Chebyshev Polynomial

• Momentum Methods

• Nonconvex optimization

Students are expected to sign up on Piazza and GradeScope B2XR7X. Discussions will happen on Piazza. The homework should be turned in and will be graded on GradeScope. Important announcements will be made via Canvas.

Pre-requisites

This course assumes basic knowledge in linear algebra and calculus.

Course grade

• 40% homework (5 problem sets; will drop the lowest score)

• 25% midterm exam (in class; one page of hand-written cheat sheet allowed)

• 25% final project

• 10% scribing and 5% extra credit for course attendance/participation

Schedule

Final Projects

Final project: You can form a group of size up to 3 members for the final project.

Grading of the final project: 1% for a checkpoint report, 12% for a written report, 12 % for an oral presentation.

Written report of the final project :

• Describe an optimization paper in detail using your own words. The paper you focus on should be a peer-reviewed paper from top venues such as ICML, NeurIPS, ICLR, COLT, JMLR, Mathematical Programming, or SIAM Journal on Optimization from the past three years. Focusing on papers not from these venues requires discussion with the instructor and obtaining approval first.

Students are required to submit a typed write-up for the final project consisting of 4-6 pages (the list of references does not count toward the page limit). Submitting a report that is less than 4 full pages (references excluded) will result in a score deduction. The write-up must contain a significant theoretical component. Please use the Latex template provided in this link Latex Template

The report should include the motivation, a description of the algorithm, the underlying algorithmic design principles, and a clear reproduction or summary of the theoretical analysis . When reproducing the proof, ask yourself: What is the most essential part of the analysis? Can you significantly simplify the proofs without trivializing the results? Because of the page limit, you should avoid presenting every step in the analysis in your written report. Focus on conveying the logical flow and key steps of the theoretical analysis.

Students are encouraged to perform simple simulations to test the proposed algorithm(s) in the paper and report their findings in the report, if the paper includes experiments. Code snippets and additional simulation results can be provided in the appendix (after the list of references if any) and do not contribute to the page limit, but the instructor does not have an obligation to read the appendix. The simulations of the method(s) in the paper can be conducted using small, toy, and synthetic data created by your own to showcase the convergent behavior of the algorithm(s) and their baselines. Students do not need to precisely follow the setting nor use the same data as described in the paper. Some papers are purely theoretical without any numerical experiments. In this case, students are still encouraged to create their own synthetic data or come up with a simulation scenario to verify the theoretical results. However, the evaluation of the written report will be focused on whether you can present the motivation, the algorithm, the idea behind the algorithm design, and reproducing/summarizing the analysis clearly. Simulations are optional and will only be considered for the assessment if the other aforementioned components of the written report are not strong.

The due date of the written report is Thursday, March 21, 2024, 6:00 pm.

Additional Tasks (Optional) include (1) identifying the limitations and proposing a way to overcome them (theoretically and/or empirically), (2) or improving the results in the paper, such as obtaining a tighter bound or modifying the algorithms to be faster (theoretically and/or empirically), (3) or proposing a new algorithm in the same setting. Final projects which include an additional task with a solid result may receive extra credits. If an additional task is conducted, students should highlight what they have accomplished in the main text of the written report and may provide further detail in the appendix after Page 6, but the instructor does not have an obligation to read the appendix.

Final presentation for the project:

The session for oral presentations is scheduled for Thursday, March 21, 2024, from 7:00 pm to 9:59 pm (the final exam time). Each team has 10 minutes (subject to change) for their presentation and 1 minute (subject to change) for the Q&A. A team can earn extra credits in their oral presentation by asking a good question or making a constructive remark on the presentations of other teams during the Q&A.

Given the limited time available for each oral presentation, each team should not walk through the proof but a discussion of theoretical results (e.g. convergence rates) and/or empirical results is encouraged. The first couple of minutes/slides should be allocated to describe the setup as clear as possible and/or provide necessary background so that the audience can be on the same page. Subsequently, the main results of the paper should be clearly summarized. If you think you have completed an additional task listed in Additional Tasks above, make sure to allocate at least one-third of time to highlight what you have accomplished.

Checkpoint report of the Final Project: In the checkpoint report, students are required to include the following information:

• The name of each team member.

• The title of the paper that you will focus on.

It is emphasized that every member in the team should submit a checkpoint report. The checkpoint report is due on Feb. 23 Friday at 11:59PM .

References

There is no required textbooks. The course will draw some of the materials from the following references. All the following materials are accessible online or accessible via UCSD library online portal.

• Dmitriy Drusvyatskiy Convex Analysis and Nonsmooth Optimization

• Francesco Orabona A Modern Introduction to Online Learning

• Aaron Sidford Optimization Algorithms

• Stephen Boyd and Lieven Vandenberghe Convex Optimization

• John Duchi Introductory Lectures on Stochastic Convex Optimization

• Arkadi Nemirovski Lectures on Modern Convex Optimization

• Nisheeth K. Vishnoi Algorithms for Convex Optimization

• Sebastien Bubeck Convex Optimization: Algorithms and Complexity.

• Yin Tat Lee and Santosh Vempala Techniques in Optimization and Sampling

• Shai Shalev-Shwartz Online Learning and Online Convex Optimization

• Elad Hazan Introduction to Online Convex Optimization

• Alexandre d'Aspremont, Damien Scieur, Adrien Taylor Acceleration Methods

• Benjamin Recht and Stephen J. Wright Optimization for Modern Data Analysis

• Guanghui Lan First-order and Stochastic Optimization Methods for Machine Learning

• Yurii Nesterov Introductory Lectures on Convex Optimization

• Amir Beck Introduction to Nonlinear Optimization - Theory, Algorithms and Applications

Great youtube channels for learning optimization

• Constantine Caramanis Optimization Algorithms

Acknowledgments

The design of this course is inspired by the following excellent courses:

• Convex Optimization and Approximation at UC Berkeley by Moritz Hardt.

• Large-Scale Optimization for Data Science at University of Pennsylvania by Yuxin Chen.

• Optimization for Machine Learning at Boston University by Ashok Cutkosky.

• Introduction to Optimization Theory at Standford by Aaron Sidford.

• Convex Optimization at CMU by Ryan Tibshirani.

The course webpage and the course policy is inspired by the following excellent courses:

• Semidefinite and Sum-of-squares Optimization at UC San Diego by Yang Zheng

• Machine Learning Theory at Georgia Tech by Jacob Abernethy

• Statistical Reinforcement Learning at UIUC by Nan Jiang