課程資訊
 課程名稱 最佳化演算法Optimization Algorithms 開課學期 107-1 授課對象 電機資訊學院  資訊工程學研究所 授課教師 李彥寰 課號 CSIE5410 課程識別碼 922 U4500 班次 學分 3.0 全/半年 半年 必/選修 選修 上課時間 星期四7,8,9(14:20~17:20) 上課地點 綜401 備註 總人數上限：30人 課程簡介影片 核心能力關聯 核心能力與課程規劃關聯圖 課程大綱 為確保您我的權利,請尊重智慧財產權及不得非法影印 課程概述 Optimization has become a prevalent tool in modern algorithm design. In this course, we will study optimization algorithms from the perspective of machine learning theory. We will focus on the black-box approach; that is, we consider accessing information about the function to be optimized via an oracle, and derive non-asymptotic worst-case oracle complexity bounds with respect to a given class of objective functions. This course consists of two parts. The first part introduces basic notions in convex analysis, and standard convex optimization algorithms. The second part focuses on online optimization algorithms, which allow one to do model-free sequential predictions, and can be computationally efficient when the data size is large. 課程目標 After taking this course, the students are expected to have the ability to: ．Characterize the pros and cons of an optimization algorithm. ．Choose an appropriate optimization algorithm for a given application scenario. ．Do basic complexity analyses of optimization algorithms. ．Read advanced literature in optimization and algorithm design. 課程要求 Prerequisites: Calculus, linear algebra, and probability. Knowledge in convex analysis, statistics, and/or machine learning can be helpful but not necessary. 預期每週課後學習時數 Office Hours 指定閱讀 There is no textbook. Relevant literature will be pointed out by the instructor. Most of the course material can be found in 參考書目. 參考書目 1. Yu. Nesterov. 2004. Introductory Lectures on Convex Optimization. 2. S. Bubeck. 2015. Convex Optimization: Algorithms and Complexity. (Available online: http://sbubeck.com/Bubeck15.pdf) 3. A. Ben-Tal and A. Nemirovski. 2015. Lectures on Modern Convex Optimization.(Available online: http://www2.isye.gatech.edu/~nemirovs/LMCO_LN.pdf) 4. N. Cesa-Bianchi and G. Lugosi. 2006. Prediction, Learning, and Games. 5. S. Bubeck. 2011. Introduction to Online Optimization. (Available online: http://sbubeck.com/BubeckLectureNotes.pdf) 6. S. Shalev-Shwartz. 2012. Online Learning and Online Convex Optimization. 7. E. Hazan. 2016. Introduction to Online Convex Optimization. (Available online: http://ocobook.cs.princeton.edu/) 評量方式(僅供參考)
 課程進度
 週次 日期 單元主題 第1週 9/13 Course organization. Optimization problems in machine learning. 第2週 9/20 Convexity. Smoothness. Strong convexity. 第3週 9/27 Gradient descent. Accelerated gradient descent. 第4週 10/04 Mirror descent. Subgradient. 第5週 10/11 Proximal gradient method. 第6週 10/18 Frank-Wolfe method. 第7週 10/25 Stochastic gradient descent (SGD) 第8週 11/01 Variance-reduced SGD. 第9週 11/08 Midterm. 第10週 11/15 Online optimization problems. Regret. Online-to-batch conversion. 第11週 11/22 Follow the leader. Follow the regularized leader. Follow the perturbed leader. 第12週 11/29 Multiplicative weight update method. Learning with expert advice. 第13週 12/06 Online mirror descent. 第14週 12/13 Online Newton step. Exp-concavity. 第15週 12/20 Optimistic online optimization methods. 第16週 12/27 Accelerated gradient descent revisited. Duality. 第17週 1/03 Bandit optimization. 第18週 1/10 Project presentations.