大数据分析中的算法 (2015年春季)

• 基本信息: (教学大纲)

• 课程代码：00136720 (本科生），00100863 （本研合）

• 课程内容： 侧重数据分析中的数值代数和最优化算法

• 教师信息： 文再文，wenzw@cqjj8.com

• 助教信息： 姜博川, jiangbochuan30871@163.com; 张静茹, zhangjingru81@126.com ; 姚金戈, yaojinge@cqjj8.com

• 上课地点：二教413

• 上课时间：

  • 1~16周 每周周二10~12节, 18:40pm-21:30pm

  • 亚洲成人在线一二三四五六区校历

• 其它信息：

  • 有微信的同学请加入课程微信群

  • 部分重要信息同时会在教学网 “001-00136720-1306182243-1: 大数据分析中的算法" 公布

• 参考材料 (部分材料的下载链接可以登录教学网 “001-00136720-1306182243-1: 大数据分析中的算法" 公告栏)：

  • “Introduction to Algorithms”, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press

  • “Mining of Massive Datasets”, Jure Leskovec, Anand Rajaraman, Jeff Ullman, Cambridge University Press

  • “Convex optimization”, Stephen Boyd and Lieven Vandenberghe

  • “Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer

  • “Optimization Theory and Methods”, Wenyu Sun, Ya-Xiang Yuan

  • “Matrix Computations”, Gene H. Golub and Charles F. Van Loan, The Johns Hopkins University Press

  • The Matrix Cookbook, Kaare Brandt Petersen, Michael Syskind Pedersen
    

• 数据分析相关的网站：

  • Mining Massive Data Sets, Stanford University

  • Jure Leskovec @ Stanford - Stanford Computer Science

  • Mining Massive Data Sets: Hadoop Labs, Stanford University

  • Big Data Analytics, Columbia University

  • Theoretical Foundations of Big Data Analysis, The Simons Institute for the Theory of Computing, UC Berkeley

  • Introduction to Data Science, University of Washington

  • Core Methods in Data Science, University of Washington

  • The Advanced Matrix Factorization Jungle
    

• 课程信息 （大致安排）

  • 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 deleted immediately.

  • 第1周，3月3日，课程简介: lecture notes
    线性规划，二次锥规划，半定规划简介: lecture notes
    

  • 第2周，3月10日，凸优化对偶理论: 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月17日，线性规划单纯形算法，内点算法: lecture notes
    “Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer, chapters 13 and 14

  • 第4周，3月24日，压缩感知和稀疏优化基本理论: lecture notes
    references: An Introduction to Compressive Sensing

  • 第5周，3月31日，稀疏优化的算法 lecture notes
    

  • 第6周，4月7日， 推荐系统与低秩矩阵恢复的算法 lecture notes
    

  • 第7周，4月14日，图和网络流问题: 最短路径问题 lecture notes
    

  • 第8周，4月21日，图和网络流问题: 最大流问题，组合优化与线性规划 lecture notes
    

  • 第9周，4月28日，Submodular 优化与数据挖掘 lecture notes
    

  • 第10周，5月5日，高维数据降维 lecture notes
    

  • 第11周，5月12日，support vector machine lecture notes
    

  • 第12周，5月19日，链接分析： page rank lecture notes
    

  • 第13周，5月26日，相位恢复以及低温电子显微镜 lecture notes
    

  • 第14周，6月2日，随机优化算法, 特征值分解，奇异值分解的随机算法 lecture notes
    

  • 第15周，6月9日，并行计算、分布式计算 lecture notes
    

  • 第16周，6月16日和 6月19日，课程项目报告
    6月19日地点为北京国际数学研究中心全斋09教室

  • 6月30日晚12点（不接受晚交报告），提交课堂报告文件和书面报告
    (包括latex源文件，程序等等打包发email给助教 (pkuopt@163.com, wendouble@gmail.com)。
    

• 作业

  • 作业一: Convex Optimization 习题： 4.11, 4.12, 4.25, 4.27, Convex Optimization, Additional exercises，习题： 3.11, 3.12, 交作业时间： 3月17日课堂上交（上课前）。

  • 作业二: Convex Optimization 习题： 5.11, 5.17, 5.19, “Numerical Optimization”, Jorge Nocedal and Stephen Wright, Springer，习题： 13.9, 14.6, 交作业时间： 3月24日课堂上交（上课前）。

  • 作业三: homework3.pdf homework3-solu.pdf交作业时间： 4月7日（上课前）。

  • 作业四: homework4.pdf 交作业时间： 5月12日（上课前）。

  • 作业五: homework5.pdf 交作业时间： 5月26日（上课前）。

• 课程项目

  • 课程项目一: project1.pdf 交作业时间： 2015年4月30日北京时间晚上24点前，不接受迟交作业。
    demo: sparsel1example.m

  • 课程项目二: 请见下面课程项目二细节

• 成绩评定
  

  • 大作业，包括习题和程序： 40%

  • 课程项目： 60%

  • 作业要求：可以同学间讨论或者找助教答疑，但不准抄袭。计算题要求写出必要的推算步骤，证明题要写出关键推理和论证。

• 课程项目报告文件

课程项目二细节

• 分组

  • 自由组合一般2至3人一组，可以一个人

  • 每一个组分配一位指导老师

  • 每位指导老师带2到3组学生，大三学生优先选组

• 选题

  • 大致分为文献综述，模型项目，算法项目，理论问题

  • 题目可以从 “课程项目文献” 里选择

  • 题目也可以自由选择。如果该项目在其它课程里或其他老师组里同时进行，请明确说明。 如果该课题是以往工作的延续，请明确说明。

  • 文献综述： 挑选一篇感兴趣的文献，写文献综述

  • 模型项目: 挑选你感兴趣的应用问题，探索用最优化算法或数值代数算法解决。

  • 算法项目: 挑选一个或者一类问题，提出新的算法或者已有算法的变形

  • 理论问题： 分析一些模型或算法的理论性质

• 指导老师

  • Prof. Wotao Yin, Department of Mathematics, UCLA

  • Prof. Zizhuo Wang, Department of Industrial and Systems Engineering, University of Minnesota

  • Prof. Xin Liu, The Institute of Computational Mathematics and Scientific/Engineering Computing, CAS

  • Prof. Yafeng Liu, The Institute of Computational Mathematics and Scientific/Engineering Computing, CAS

  • Prof. Sihong Shao, The School of Mathematical Sciences, PKU

  • Prof. Zaiwen Wen, BICMR, PKU

• 评分准则

  • 课程课堂报告： 准备15分钟报告 + 5分钟提问。 每个组员均需讲差不多长度的时间。成绩评定： 50% 其中小组之间相互评定和教师意见各 50% .
    小组之间相互评定，评分为1-10。 请每组填写presentation_evaluation.xlsx发给助教 (pkuopt@163.com, wendouble@gmail.com).
    每组负责收集自己组的评分。如果B组课堂上没有给A组评分，则A组收集B组的评分填写为10*（请标注*号），而B组计算平均分后将减1分，扣完为止。
    由于课堂报告分两组进行，相互评分只需评给当天报告的同学。
    

  • 书面报告： 每一组提交一份ppt （课堂报告文件）和一份读书报告 (包括latex源文件 )。如果文章中有数值算例，请写程序复制数值实验结果。成绩评定：占该项目的 50%
    

• 重要日期和提交内容：

  • 3月31日前，选择指导老师, 分组情况请查看此文件

  • 4月7日前，分组情况请于4月7日前填写调查问卷，需提供的信息： 姓名，学号，文章或项目题目, 指导老师

  • 5月19日, 中期报告请于前发email给助教 (pkuopt@163.com, wendouble@gmail.com)
    中期报告不超过3页纸（单面）。需要描述你们组的选题，已经完成的工作，你们将要做哪些事情
    提交的文件名为 “proj2rep1-name1-name2.pdf”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj2rep1-PengyuQian-JunziZhang.pdf

  • 6月16日和 6月19日，课堂报告. 选择第二个有空时间,
    分组情况及时间安排请查看此链接 presentation_schedule.xlsx

  • 6月30日晚12点（不接受晚交报告），课堂报告文件和书面报告 (包括latex源文件，程序等等打包发email给助教 (pkuopt@163.com, wendouble@gmail.com)。
    提交的文件请全部打包，文件名为 “proj2-name1-name2.zip”. 比如如果成员为Pengyu Qian 和 Junzi Zhang，则文件名为 proj2-PengyuQian-JunziZhang.zip

课程项目文献

• Programming related

  • Literature review on Spark and MLib. Implement some optimization algorithms based on Spark and MLib

  • J. Poulson, B. Marker, R. van de Geijn, J. Hammond, and N. Romero (2013). Elemental: A new framework for distributed memory dense matrix computations, ACM Transactions on Mathematical Software. Implement some optimization algorithms based on elemental

  • Parallel implementation of “X. Liu, Z. Wen, Y. Zhang, An Efficient Gauss-Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations”

• Optimization theory and algorithms

  • Ji Liu, Stephen J. Wright, Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

  • Convergence of alternating direction methods of multipliers for problems with multiblock of variables

  • Damek Davis, Wotao Yin, A Three-Operator Splitting Scheme and its Optimization Applications

  • Kazufumi Ito and Karl Kunisch, A variational approach to sparsity optimization based on Lagrange multiplier theory

  • Jérôme Bolte, Shoham Sabach, Marc Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems

  • Ruoyu Sun, Zhi-Quan Luo, Guaranteed Matrix Completion via Non-convex Factorization

  • Liuqin Yang, Defeng Sun, Kim-Chuan Toh, SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints

  • Afonso S. Bandeira, Christopher Kennedy, Amit Singer, Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups

  • Kunal N. Chaudhury, Yuehaw Khoo, Amit Singer, Global registration of multiple point clouds using semidefinite programming

  • Li Deng and Dong Yu, DEEP LEARNING: Methods and Applications, (This is a book. A group can select related chapters at their own interests.)

  • Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, Martin Riedmiller, Playing Atari with Deep Reinforcement Learning

  • Shipra Agrawal, Zizhuo Wang, Yinyu Ye, A Dynamic Near-Optimal Algorithm for Online Linear Programming

  • Y.-H. Kao and B. Van Roy, ‘‘Directed Principal Component Analysis,’’ Operations Research, Vol. 62, No. 4, pp. 957-972, 2014.

  • D. Russo and B. Van Roy, Learning to Optimize Via Information-Directed Sampling.

  • Ya-Feng Liu, Yu-Hong Dai, Zhi-Quan Luo, Joint Power and Admission Control via Linear Programming Deflation

  • Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, Matus Telgarsky, Tensor Decompositions for Learning Latent Variable Models

  • Andrzej CICHOCKI, Tensor Networks for Big Data Analytics and Large-Scale Optimization Problems

  • Martin Stoll and Tobias Breiten, A Low-Rank in Time Approach to PDE-Constrained Optimization

• Projects from industry

  • wind power forecasting models enhanced with factors such as temperature, pressure, etc. This topic is from a joint project with Prof. Pingwen Zhang.
    

  • detection of abnormal predicted wind speed. This topic is from a joint project with Prof. Pingwen Zhang
    

  • Recommendation of VIP customers, Joint projects with Prof. Dongdong Ge from Shanghai University of Finance and Economics, see problem