# CS6515: Stochastic optimization

## Course information

**When**: Jan-May 2023**Lectures**: Slot J**Where**: TBA**Teaching Assistants**: TBA

## Course Content

#### Module 1: Introduction

Examples: Least squares, matrix factorization, SVM, logistic regression, MCMC, nonlinear urns, RL

Preliminaries: Selected topics in probability and linear algebra

#### Module 2: Foundations - Convexity and smoothness

Taylor's theorem, minima of smooth functions

Convex sets and functions

#### Module 3: Foundations - Stochastic approximation

ODE approach and asymptotic convergence

#### Module 4: Descent methods

Descent directions

Convergence and rates

#### Module 5: Stochastic gradient algorithms

Convergence analysis for convex case

Sum of smooth and strongly convex functions

Convegence for general case

Noise reduction, e.g. SVRG, SAG and iterate averaging

Second-order methods

#### Module 6: Zeroth order optimization

Gradient estimation

Convergence analysis

#### Module 7: Other topics (if time permits)

Fixed point iterations, RL, MCMC, co-ordinate descent

## Textbooks/References

Stephen J. Wright, and Benjamin Recht. Optimization for data analysis. Cambridge University Press, 2022.

V.S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Texts and Readings in Mathematics, 2022.

Sebastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 2015.

## Grading

Mid-term exam: 25%

Final exam and viva: 20%

Project: 25%

Paper review: 5%

Scribing: 10%

Mini-quizzes: 15%

## Important Dates

Mini-quizzes: Feb 27, Mar 20, Apr 10

Mid-term: Mar 9

Final: May 9

Project: Apr 27

Paper review: Apr 10

## Paper review

Students form a team of size at most two, and read a paper on stochastic optimization, either from a list (to be shared) or a paper outside the list that has the instructor's approval. Each team submits a 1-page *critical* review that identifies the strengths and areas of improvement of the paper studied. A paraphrase of the paper content is strongly discouraged.

## Course project

The students work in teams of size at most two.

The project could be theoretical and/or practical, i.e., the course project could involve implementation of existing stochastic optimization algorithms and/or original research in the form of either a novel stochastic optimization algorithm or extension of existing theoretical results for such algorithms. Given the limited timeframe of the course, working out a new result or a sufficiently novel extension of an existing result may not be completely feasible and in that case, the project report could turn into a survey of existing literature that the students familiarized with, while attempting to formulate/solve a stochastic optimization problem.

For theoretically-oriented projects, the report is expected to provide a detailed description of the problem, accompanying algorithms and convergence analysis. For the projects geared towards performance evaluation of existing stochastic optimization algorithms, the report is expected to summarize the findings of the empirical investigation, with sufficient implementation details that would help reproduce the results.

The evaluation would be as follows: 5% for the project proposal, 10% for the final report and 10% for a project presentation/viva by the instructor.