最佳化演算法
Optimization Algorithms
| 節 | 週一 |
|---|---|
N 12:20–13:10 | 最佳化演算法 ED302 3 節連堂 |
5 13:20–14:10 | |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
This graduate-level course is designed to introduce a variety of general-purpose optimization methods for solving engineering problems, such as machine learning, data networks, communication, and other related areas of computer science. We will cover topics from both convex and non-convex optimization, especially for the needs of the problems and applications in machine learning and net-works. The learning objectives can be summarized as follows. 1. Learn how to formulate real engineering problems as optimization problems. 2. Learn how to systematically solve optimization problems by leveraging var-ious algorithms and perform convergence analysis of these algorithms. 3. Learn how to implement optimization algorithms in a high-level language. 4. Learn how to solve optimization problems using optimization solvers (e.g., Gurobi). 5. Learn how to conduct original research and compile the results into a technical report.
• Undergraduate-level understanding of calculus, probability, and linear algebra. • Basic programming skills in a high-level language (e.g., Python or MATLAB).
Homework assignments: 60% (including math problems and programming tasks) Final Project: 40%
| 週次 | 主題 |
|---|---|
| 第 1 週 | Fundamentals: Useful structures in optimization problems - Convex sets - Convex functions - Conjugates - Subgradients and subdifferentials |
| 第 2 週 | Fundamentals: Optimality conditions for unconstrained problems - First-order sufficient conditions for global minimizers - Second-order sufficient conditions for global minimizers - First-order necessary conditions for local minimizers - Optimality conditions for constrained problems |
| 第 3 週 | Fundamentals: Optimality conditions for constrained problems - Lagrangian and dual functions - Weak and strong duality - Practical examples of constrained problems - Slater's condition for constraint verification - KKT conditions - Lagrange multiplier: Perturbation and sensitivity |
| 第 4 週 | First-order methods: Gradient descent (GD) - Convergence rate of GD for strongly convex and smooth problems - Convergence rate of GD for convex and smooth problems - Convergence rate of GD for non-convex problems |
| 第 5 週 | First-order methods: Stochastic Gradient descent (SGD) - Convergence results of SGD for convex and smooth problems - Convergence results of SGD for non-convex and smooth Functions - Applications |
| 第 6 週 | First-order methods: Variance reduction for SGD - A Intuitive Idea: Gradient Aggregation - Stochastic Variance-Reduced Gradient (SVRG) - A General Recipe of Variance Reduction |
| 第 7 週 | First-order methods: Subgradient and accelerated gradient - Heavy-ball method - Nesterov's accelerated gradient - Lower bounds of sub-optimality gap |
| 第 8 週 | First-order methods for constrained optimization: - Frank-Wolfe methods - Projected subgradient methods |
| 第 9 週 | Mirror descent (I) - Motivation: Non-homogeneity and non-Euclidean geometry - Bregman divergence - Mirror maps - Example: Entropic Mirror Descent (EMD) |
| 第 10 週 | Mirror descent (II) Online convex optimization - Proximal viewpoint of mirror descent - Mirror descent as “Follow-The-Regularized-Leader” (FTRL) |
| 第 11 週 | Quasi-Newton methods - Newton's step - Newton’s step without Hessian - Secant equation for Hessian approximation - Broyden-Fletcher-Goldfarb-Shanno (BFGS) Method - Limited-Memory BFGS (L-BFGS) |
| 第 12 週 | Zeroth-order / derivative-free methods - Coordinate descent methods - Bayesian optimization |
| 第 13 週 | Dual and primal-dual methods - Dual ascent methods - Alternating direction method of multipliers (ADMM) |
| 第 14 週 | Neural network optimization (I) - Backprop and SGD for neural networks - Mini-batches - Initialization - Batch normalization |
| 第 15 週 | Neural network optimization - Gradient clipping - Adaptive methods and momentum (e.g., Adam) - Escaping saddle points |
| 第 16 週 | Final Presentation - Lightning talks by the students |
The course material will be adapted from multiple textbooks as follows: • Yurii Nesterov, "Lectures on Convex Optimization," Springer, 2nd edition, 2018. • Amir Beck, "Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications With MATLAB," Society for Industrial and Applied Mathematics, 2014. • Leon Bottou, Frank Curtis, and Jorge Nocedal, "Optimization Methods for Large-Scale Machine Learning," 2018. • Dimitri Bertsekas, "Nonlinear Programming," Athena Scientific, 2nd edition, 1999.
- 地點
- EC418
- 時間
- TBD
- 聯絡方式
- Email: pinghsieh@nycu.edu.tw