大数据分析中的算法 (2018年春季)
本课程考核包括平时作业和程序，期中大项目，期末大项目，请谨慎选课
基本信息: (教学大纲)
课程代码：00136720 (本科生），00100863 （本研合）
课程内容： 侧重数据分析中的数值代数和最优化算法
教师信息： 文再文，wenzw at pku dot edu dot cn
助教信息： 赵明明: mmz102 at pku dot edu dot cn, 刘浩洋: liuhaoyang at pku dot edu dot cn
课程微信群（下面二维码3月6日失效）
 |
上课地点：理教102
上课时间：
1~16周 每周周二10~12节, 18:40pm-21:30pm
老师答疑时间: 单独和老师联系或者每次课后21:30pm-22:00pm
助教答疑时间: 根据反馈待定
先修课程要求:
年级要求: 大三，大四，研究生
不是必须先修但有帮助: 数值代数，最优化（凸优化），概率论
会Matlab或者Python程序编写
其它信息：
参考材料：
“Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer
“Matrix Computations”, Gene H. Golub and Charles F. Van Loan, The Johns Hopkins University Press
The Matrix Cookbook, Kaare Brandt Petersen, Michael Syskind Pedersen
Deep Learning, Ian Goodfellow and Yoshua Bengio and Aaron Courville
Theories of Deep Learning (STATS 385), Stanford University, Fall 2017
数据分析相关的网站：
课程信息 （大致安排）
Acknowledgement: quite a few materials are taken from slides or lecture notes online.
Please email me if the usage of any part is not appropriate and they will be deleted immediately.第1周，2月27日，课程简介: lecture notes
线性规划，二次锥规划，半定规划简介: lecture notes
read: “Convex optimization”, Stephen Boyd and Lieven Vandenberghe, chapters 2 and 3
思考题： 有哪些问题和应用可以化成线性规划，二次锥规划，半定规划？第2周，3月6日，凸优化对偶理论: lecture notes
线性规划，二次锥规划，半定规划例子: lecture notes
模型语言： CVX, YALMIP
LP, SOCP, SDP典型算法软件: SDPT3, MOSEK, CPLEX, GUROBI
Prof. Boyd lecture notes on Disciplined convex programming and CVX
“Convex optimization”, Stephen Boyd and Lieven Vandenberghe, chapters 4 and 5第3周，3月13日，线性规划单纯形算法，内点算法: lecture notes
“Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer, chapters 13 and 14第4周，3月20日，压缩感知和稀疏优化基本理论: lecture notes
references: An Introduction to Compressive Sensing
Compressive Sensing Resources第5周，3月27日，稀疏优化的算法 lecture notes
“Proximal Algorithms”, N. Parikh and S. Boyd, Foundations and Trends in Optimization, 1(3):123-231, 2014.
Amir Beck, Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
“Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”, S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Foundations and Trends in Machine Learning, 3(1):1–122, 2011
Junfeng Yang, Yin Zhang, Alternating direction algorithms for l1-problems in Compressed Sensing, SIAM Journal on Scientific Computing第6周，4月3日， 推荐系统与低秩矩阵恢复的算法 lecture notes
SVD: read section 2.5 in “Matrix Computations”, Gene H. Golub and Charles F. Van Loan, The Johns Hopkins University Press
chapter 9 in “Mining Massive Data Sets”, Stanford University
“Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization”, Benjamin Recht, Maryam Fazel, Pablo A. Parrilo第7周，4月10日， 并行计算、分布式计算 lecture notes
Some backgrounds on parallel computing can found at Prof. James Demmel's course
“Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”, S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Foundations and Trends in Machine Learning, 3(1):1–122, 2011
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent, Benjamin Recht, Christopher Re, Stephen Wright, Feng Niu第8周，4月17日， 随机优化算法 lecture notes
Joel A Tropp, An introduction to matrix concentration inequalities
Optimization Methods for Large-Scale Machine Learning, Léon Bottou, Frank E. Curtis, Jorge Nocedal
Introductory Lectures on Stochastic Optimization, by John Duchi
Deep Learning, Ian Goodfellow and Yoshua Bengio and Aaron Courville第9周，4月24日， 随机特征值分解算法 lecture notes
Petros Drineas, Ravi Kannan, and Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication, SIAM J. Comput., 36(1), 132–157
Petros Drineas, Ravi Kannan, and Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix, SIAM J. Comput., 36(1), 158–183
N. Halko, P. G. Martinsson, and J. A. Tropp, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions,SIAM Rev., 53(2), 217–288.第10周，5月1日，放假取消
第11周，5月8日，相位恢复以及低温电子显微镜 lecture notes
E. J. Candes, Y. Eldar, T. Strohmer and V. Voroninski. Phase retrieval via matrix completion. SIAM J. on Imaging Sciences 6(1), 199–225.
E. J. Candès, X. Li and M. Soltanolkotabi. Phase retrieval via Wirtinger flow: theory and algorithms. IEEE Transactions on Information Theory 61(4), 1985–2007.
A. Singer, Y. Shkolnisky, Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming, SIAM Journal on Imaging Sciences, 4 (2), pp. 543-572 (2011).
L. Wang, A. Singer, Z. Wen, ‘‘Orientation Determination from Cryo-EM images using Least Unsquared Deviations”, SIAM Journal on Imaging Sciences, 6(4), pp. 2450–2483 (2013).第12周，5月15日，高维数据降维 lecture notes
网络流问题选讲 lecture notes
A Global Geometric Framework for Nonlinear Dimensionality Reduction, Joshua B. Tenenbaum, Vin de Silva, John C. Langford
Unsupervised Learning of Image Manifolds by Semidefinite Programming, KILIAN Q. WEINBERGER AND LAWRENCE K. SAUL
A Duality View of Spectral Methods for Dimensionality Reduction, Lin Xiao, Jun Sun, Stephen Boyd
Dimensionality Reduction: A Comparative Review, Laurens van der Maaten, Eric Postma, Jaap van den Herik
support vector machine lecture notes
LIBLINEAR: A Library for Large Linear Classification
LIBSVM: A library for support vector machines
Working set selection using the second order information for training SVM R.-E. Fan, P.-H. Chen, and C.-J. Lin.
An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, CRISTIANINI, Nello, and John SHAWE-TAYLOR, Cambridge, UK: Cambridge University Press
图和网络流问题: 最短路径问题 lecture notes
“Network Flows: Theory, Algorithms, and Applications”, Ahuja, Magnanti, and Orlin
图和网络流问题: 最大流问题，组合优化与线性规划 lecture notes
“Network Flows: Theory, Algorithms, and Applications”, Ahuja, Magnanti, and Orlin
链接分析： page rank lecture notes
chapter 5, link analysis, Mining of Massive Datasets第13周，5月22日，Submodular 优化与数据挖掘 lecture notes
Learning with Submodular Functions: A Convex Optimization Perspective, Francis Bach
Learning with Submodular Functions, Francis Bach
EE596B - Submodular Functions, Optimization, and Applications to Machine Learning, Prof. Jeff A. Bilmes第14周，5月29日，dynamic programming 1 lecture notes
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction
Prof. Dimitri Bertsekas's lecture slides
Dimitri P. Bertsekas, Abstract Dynamic Programming第15周，6月5日，dynamic programming 2 lecture notes
第16周，6月12日，Reinforcement Learning lecture notes
作业和课程项目，重要日期和提交内容：
3月13日上课前, 作业一: Convex Optimization 习题： 4.11, 4.12, 4.25, 4.27, Convex Optimization, Additional exercises，习题： 3.11, 3.12
3月20日上课前, 作业二: Convex Optimization 习题： 5.11, 5.17, 5.19, “Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer，习题： 13.9, 14.6,
4月3日上课前，作业三文件
4月17日晚12点前, 课程项目一
demo: sparse_l1_example.m5月1日晚12点, homework-sto.pdf
5月8日晚12点, 提交项目二中期报告， 请点击此链接上传
中期报告不超过3页纸（单面）。需要描述你们组的选题，已经完成的工作，你们将要做哪些事情
提交的文件名为 “proj2rep1-name1-name2.pdf”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj2rep1-PengyuQian-JunziZhang.pdf5月15日晚12点前, homework-svd.pdf
5月29日晚12点前, homework-phase.pdf
6月5日上课前， homework7-2018.pdf
6月26日晚12点前，项目二书面报告 (包括latex源文件，程序等等打包， 请点击此链接上传
提交的文件请全部打包，文件名为 “proj2-name1-name2.zip”
课程项目
课程项目二: 请见下面课程项目二细节
成绩评定
迟交一天(24小时）打折10%， 不接受晚交4天的作业和项目（任何时候理由都不接受）
大作业，包括习题和程序： 40%
课程项目一： 30%
课程项目二： 30%
作业要求：i) 计算题要求写出必要的推算步骤，证明题要写出关键推理和论证。数值试验题应该同时提交书面报告和程序，其中书面报告有详细的推导和数值结果及分析。 ii) 可以同学间讨论或者找助教答疑，但不允许在讨论中直接抄袭，应该过后自己独立完成。 iii) 严禁从其他学生，从互联网，从往年的答案，其它课程等等任何途径直接抄袭。iv) 如果有讨论或从其它任何途径取得帮助，请列出来源。
课程项目二细节
分组: 自由组合一般2至3人一组，可以一个人
选题
大致分为文献综述，模型项目，算法项目，理论问题
题目请从 “课程项目文献” 里选择
文献综述：挑选一篇感兴趣的文献，写文献综述
模型项目: 挑选你感兴趣的应用问题，探索用最优化算法或数值代数算法解决。
算法项目: 挑选一个或者一类问题，提出新的算法或者已有算法的变形
理论问题：分析一些模型或算法的理论性质
重要日期和提交内容：
3月13日前，提交分组和选题信息， 具体课题在中期报告提交前还可以修改,
5月8日晚12点（不接受晚交报告）, 中期报告请点击此链接上传
中期报告不超过3页纸（单面）。需要描述你们组的选题，已经完成的工作，你们将要做哪些事情
提交的文件名为 “proj2rep1-name1-name2.pdf”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj2rep2-PengyuQian-JunziZhang.pdf6月26日晚12点（不接受晚交报告），书面报告 (包括latex源文件，程序等等打包, 请点击此链接上传
提交的文件请全部打包，文件名为 “proj2-name1-name2.zip”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj2-PengyuQian-JunziZhang.zip
课程项目文献
Programming related
Implement some optimization algorithms based on the Julia Language
Solve one practical application based on Google's Tensorflow
project on medical diagnosis using deep neural network
Optimization theory and algorithms
A list of papers maintained by Ju Sun, Provable Nonconvex Methods/Algorithms
Marco Mondelli, Andrea Montanari, On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
Shiyu Liang, Ruoyu Sun, Yixuan Li, R. Srikant, Understanding the Loss Surface of Neural Networks for Binary Classification
Haoyu Fu, Yuejie Chi, Yingbin Liang, Local Geometry of One-Hidden-Layer Neural Networks for Logistic Regression
Chulhee Yun, Suvrit Sra, Ali Jadbabaie, A Critical View of Global Optimality in Deep Learning
Itay Safran, Ohad Shamir, Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
Thomas Laurent, James von Brecht, The Multilinear Structure of ReLU Networks
Digvijay Boob, Guanghui Lan, Theoretical properties of the global optimizer of two layer neural network
Yi Zhou, Yingbin Liang, Critical Points of Neural Networks: Analytical Forms and Landscape Properties
M. Wang. Primal-Dual Pi Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
Y. Chen and M. Wang. Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
M. Wang. Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear Running Time
Ian Post, Yinyu Ye, The simplex method is strongly polynomial for deterministic Markov decision processes
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick, Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Chien-Chih Wang, Kent Loong Tan, Chun-Ting Chen, Yu-Hsiang Lin, S. Sathiya Keerthi, Dhruv Mahajan, S. Sundararajan, Chih-Jen Lin, Distributed Newton Methods for Deep Neural Networks
Minhyung Cho, Jaehyung Lee, Riemannian approach to batch normalization
Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, Michael I. Jordan, Averaging Stochastic Gradient Descent on Riemannian Manifolds
Teng Zhang, Yi Yang, Robust PCA by Manifold Optimization
Weijie Su, Yuancheng Zhu, Statistical Inference for Online Learning and Stochastic Approximation via Hierarchical Incremental Gradient Descent
Cong Ma, Kaizheng Wang, Yuejie Chi, Yuxin Chen, Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion and Blind Deconvolution
Jason D. Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I. Jordan, Benjamin Recht, First-order Methods Almost Always Avoid Saddle Points
Ji Chen, Xiaodong Li, Memory-efficient Kernel PCA via Partial Matrix Sampling and Nonconvex Optimization: a Model-free Analysis of Local Minima
Prateek Jain, Purushottam Kar, Non-convex Optimization for Machine Learning
Y. Chen and M. Wang. Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
S. Yang, M. Wang, E. Fang. Multi-Level Stochastic Gradient Methods for Nested Composition Optimization
Raghu Bollapragada, Dheevatsa Mudigere, Jorge Nocedal, Hao-Jun Michael Shi, Ping Tak Peter Tang, A Progressive Batching L-BFGS Method for Machine Learning
Raghu Bollapragada, Richard Byrd, Jorge Nocedal, Adaptive Sampling Strategies for Stochastic Optimization
Albert S. Berahas, Raghu Bollapragada, Jorge Nocedal, An Investigation of Newton-Sketch and Subsampled Newton Methods
Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto I. Oliveira, Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
Nathan Halko, PerGunnar Martinsson, and Joel Tropp, SIA, Finding structure with randomness: Probabilistic algorithms
Ruoyu Sun, Zhi-Quan Luo, Guaranteed Matrix Completion via Non-convex Factorization
Rong Ge, Jason D. Lee, Tengyu Ma, Matrix Completion has No Spurious Local Minimum
Rong Ge, Chi Jin, Yi Zheng, No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis