Math 285J: Operators, Splitting, and First-Order Optimization Algorithms

Links

  • Location MS 6201

  • First meeting on Friday, September 23rd, 3pm. If necessary, we will change the time for future meetings

  • Q&A and lecture notes on piazza.com. Send me an email if you need the access.

Topics

  1. Overview of optimization, operators, splitting, and first-order algorithm

  2. Subgradients and subgradient algorithms for nonsmooth optimization

  3. Proximal operators and related algorithms

  4. Convergence of fixed-point iterations

  5. Monotone operators and properties

  6. Operator splitting methods

  7. Duality and dual algorithms

  8. Primal-dual algorithms

  9. Coordinate update algorithms

  10. Parallel versions algorithms for structured problems

  11. Convex optimization convergence analysis

  12. Stochastic approximation algorithms

  13. Asynchronous parallel algorithms

  14. Nonconvex optimization algorithms

  15. Distributed and decentralized algoritms

Lecture slides and notes will be provided.

Mild workload

  • Voluntary exercises on each topic, not graded

  • Notes taking for one topic

  • Reading some papers in one topic, either alone or with another student in a group, and giving a 20-minute presentation

  • No exams

Final projects

  1. Slide Latex template. Suggested but not mandatory

  2. Each group has either one or two members. Justification (e.g., difficult tasks) is needed for any group of three or more.

  3. Presentations are scheduled for Monday Nov 28th and Wednesday Nov 30th. If you need more time, I can schedule your presentation in the final week.

  4. Please either pick your own paper (written by you or others) or one of the following candidate papers

Candidate papers:

  1. Stochastic Three-Composite Convex Minimization Yurtsever, Alp; Vu, Cong Bang; Cevher, Volkan

  2. Infimal convolution of data discrepancies for mixed noise removal Luca Calatroni, Juan Carlos De Los Reyes, Carola-Bibiane Schonlieb

  3. A first-order primal-dual algorithm with linesearch Yura Malitsky, Thomas Pock

  4. Disciplined Multi-Convex Programming Xinyue Shen, Steven Diamond, Madeleine Udell, Yuantao Gu, Stephen Boyd

  5. Generalized Kalman Smoothing: Modeling and Algorithms A.Y. Aravkin, J.V. Burke, L. Ljung, A. Lozano, G. Pillonetto

  6. Block-proximal methods with spatially adapted acceleration Tuomo Valkonen

  7. A descent Lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications HH Bauschke, J Bolte, M Teboulle

  8. On Convergence Rate of Distributed Stochastic Gradient Algorithm for Convex Optimization with Inequality Constraints Deming Yuan, Daniel W. C. Ho, and Yiguang Hong

  9. On the convergence rate of the three operator splitting scheme Fabian Pedregosa

  10. Learning Fast Approximations of Sparse Coding Karol Gregor and Yann LeCun

  11. Asynchronous Doubly Stochastic Proximal Optimization with Variance Reduction Bin Gu, Zhouyuan Huo, Heng Huang

  12. Training Neural Networks Without Gradients: A Scalable ADMM Approach Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, Tom Goldstein

  13. Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford

  14. Level-Set Methods For Convex Optimization A. Y. Aravkin, J. V. Burke, D. Drusvyatskiy, M. P. Friedlander, S. Roy

  15. Fast Stochastic Methods for Nonsmooth Nonconvex Optimization Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola

  16. Regularized Nonlinear Acceleration Damien Scieur, Alexandre d'Aspremont, Francis Bach

  17. The non-convex Burer-Monteiro approach works on smooth semidefinite programs Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira

  18. A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programs Hao Yu, Michael J. Neely

  19. Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization Xiao Wang, Shiqian Ma, Donald Goldfarb, Wei Liu

  20. Second Order Stochastic Optimization in Linear Time Naman Agarwal, Brian Bullins, Elad Hazan

  21. Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications Yat Tin Chow, Tianyu Wu, Wotao Yin

  22. Coordinate Friendly Structures, Algorithms and Applications Zhimen Peng, Tianyu Wu, Yangyang Xu, Ming Yan, and Wotao Yin


« Back