<!DOCTYPE HTML PUBLIC "-//SQ//DTD HTML 2.0 + all extensions//EN" "hmpro3.dtd"> <html> <head> <title>Theoretical Machine Learning: Home Page</title> </head> <body BGColor="ffffff"> <table BORDER="0" WIDTH="80%" CELLPADDING="5" CELLSPACING="0"> <tr> <td VALIGN="TOP" align="center"><img src="./pulogo.jpg" height="120"> </td> <td VALIGN="middle" align="center"><h2>COS 511<br> Theoretical Machine Learning <br> <a href="http://www.cs.princeton.edu/~ehazan/">Elad Hazan</a></h2> </td> <td VALIGN="middle" align="center "><h3><large>Spring 2015</large></h3> </td> </tr> </table> <hr align="center"> <h2>Course Summary</h2> <blockquote> <p>Can the mechanism of learning be automated and implemented by a machine? </br> In this course we formally define and study various models that have been proposed for learning. The course will present and contrast the statistical, computational and game-theoretic models for learning. We will present and rigorously analyze some of the most successful algorithms in machine learning that are extensively used today. Likely topics include: intro to statistical learning theory and bounds on the number of random examples needed to learn; learning in adversarial settings and the on-line learning model; using convex optimization to model and solve learning problems; learning with partial observability; how to boost the accuracy of a weak learning algorithm; universal portfolio selection; learning in games. </blockquote> <hr> <p><a name="ADMIN"></a></p> <h2>Administrative Information</h2> <h4>Lectures: Tue 13:30-16:20 in CS building, room 105.</h4> <p><b>Professor: </b><a href="http://www.cs.princeton.edu/~ehazan/">Elad Hazan</a>, CS building 407, <b>Reception hours:</b> Tue 11-12, or by appointment. <p><b>Teaching Assistant: </b><a href="mailto:kalai@cs.technion.ac.il">Kevin Lai</a>, CS building 003, <b>Reception hours:</b> Mon 15:30-16:30, Wed 15:30-16:30 </p> <p><b> Requirements: </b> This is a graduate-level course that requires mathematical background. Recommended background courses: probability, discrete math, calculus, analysis, linear algebra, algorithms and data structures, theory of computation / complexity theory, linear programming. </p> <p><b> Attendance and the use of electronic devices:</b> Attendance is expected at all lectures. The use of laptops and similar devices for note-taking is permitted. </p> <hr> <h2><a name="Textbook">Textbook and readings</a></h2> <b>Textbooks:</b> </br> 1. An Introduction To Computational Learning Theory, by M.J. Kearns and U. Vazirani </br> 2. Prediction, Learning and Games, by N. Cesa-Bianchi and G. Lugosi </br> 3. Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David </br> 4. Boosting: Foundations and Algorithms, by R. E. Schapire and Y. Freund <br> 5. (draft) Introduction to Online Convex Optimization, by E. Hazan, available <a href="http://ocobook.cs.princeton.edu">here</a> <br> 6. Foundations of Machine Learning, by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar <br> </br> We'll post additional optional reading as the course progresses. </p> <hr> <h2 align="left"><a name="Grading_and_workload">Grading and collaboration</a></h2> <b>Grading: </b> homework assignments (65%) and a final project (35%). There will be 6-8 homework assignments, which will be given roughly every week or two, and will each consist of a small number of problems (optional programming). Credit for all assignments is the same. Details of the final project will be given towards the end of the course. <br> <b>Turning in assignments and late policy:</b> Coordinate submission of assignments with the TA. Every late day reduces the attainable credit for the excercise by 10%. <br> <b>Scribe notes: </b> These are optional, but are graded and give extra credit equal to one additional exercise. Every student that is interested will have the option of scribing. <br> <b>Collaboration:</b> Collaboration on the problem sets is allowed. Final project should be done independently. The people you collaborated with on assignments should be clearly detailed: before the solution to each question, list all people that you collaborated with on that particlar question. </p> <hr> <p> <h2> Lecture notes and schedule </h2> </b>Student taking or auditing the course can volunteer to write scribe notes for a lecture using the latex system. Latex tutorials: <a href="https://www.tug.org/twg/mactex/tutorials/ltxprimer-1.0.pdf">tutorial 1</a> and <a href="http://www.maths.tcd.ie/~dwilkins/LaTeXPrimer/GSWLaTeX.pdf">tutorial 2</a>. </br> Relevant style files appear <a href="latex/scribe.tex">here</a> and definitions <a href="latex/defs.tex">here</a>. Scribes should strive for good mathematical style.&nbsp; <a href="latex/knuth.pdf">A few pages </a>from <em>Mathematical Writing</em> by by Knuth, Larrabee, and Roberts provide some good hints.</p> <br> <table border="1"> <tr> <th>Topic</th> <th>Lecture notes</th> <th>Extra reading</th> <th>Problem sets</th> </tr> <tr> <td> &nbsp Introduction to Learning Theory <br> &nbsp Statistical Learning model &nbsp &nbsp &nbsp</td> <td> &nbsp <a href="./notes/lec1.pdf"> lecture1 </a> &nbsp </td> <td> &nbsp chapters 1-2 in books 1-3 </a> &nbsp </td> <td> </td> </tr> <tr> <td> &nbsp PAC learning <br> &nbsp start VC-theory &nbsp &nbsp &nbsp</td> <td> &nbsp <a href="./notes/lec2.pdf"> lecture2 </a> &nbsp </td> <td> &nbsp &nbsp </td> <td> &nbsp <a href="./notes/hw1.pdf"> hw1 </a> &nbsp </td> </tr> <tr> <td> finish VC-theory, efficient linear classification &nbsp &nbsp &nbsp</td> <td> &nbsp <a href="./notes/lec3.pdf">lecture 3 part1 </a> &nbsp <br> &nbsp <a href="./notes/lec3N.pdf"> lecture 3 part 2 </a> &nbsp </td> <td> &nbsp &nbsp </td> <td> &nbsp <a href="./notes/hw2.pdf"> hw2 </a> &nbsp </td> </tr> <tr> <td> special guest talk (the juggling professor) + &nbsp <br> + decision making, multiplicative updates &nbsp &nbsp</td> <td> &nbsp <a href="./notes/lec4.pdf">lecture4-Jake</a> </br> &nbsp <a href="http://ocobook.cs.princeton.edu"> part 2 = chapter1 </a> &nbsp </td> <td> &nbsp <a href="http://theoryofcomputing.org/articles/v008a006/">MW survey </a> &nbsp </td> <td> &nbsp &nbsp </td> </tr> <tr> <td> online convex optimization, convex modelling &nbsp &nbsp</td> <td> &nbsp <a href="http://ocobook.cs.princeton.edu"> chapter 2-3 (5) </a> &nbsp <br> &nbsp <a href="./notes/lec5_kiran.pdf"> lecture 5 (unedited) </a> </td> <td> &nbsp <a href="http://www.cs.cmu.edu/~maz/publications/techconvex.pdf"> Zinkevich's paper </a> &nbsp </td> <td> &nbsp <a href="./notes/hw3.pdf"> hw3 </a> &nbsp </td> </tr> <tr> <td> portfolio selection, second order methods &nbsp &nbsp</td> <td> &nbsp <a href="http://ocobook.cs.princeton.edu"> chapter 4 (5) </a> &nbsp <br> &nbsp <a href="./notes/lec_6_kiran.pdf"> lecture 6 (unedited) </a> </td> <td> &nbsp <a href="http://www-isl.stanford.edu/~cover/papers/paper93.pdf"> Cover's paper </a> <br> simpler analysis <a href="http://ie.technion.ac.il/~ehazan/papers/thesis.pdf"> here </a> &nbsp </td> <td> &nbsp <a href="./notes/hw4.pdf"> hw4 </a> &nbsp </td> </tr> <tr> <td> regularization, perturbation and stability &nbsp &nbsp</td> <td> &nbsp <a href="http://ocobook.cs.princeton.edu"> chapter 5 (5) </a> &nbsp <br> &nbsp <a href="./notes/lec_7_kiran.pdf"> lecture 7 (unedited) </a> </td> <td> &nbsp <a href="http://research.microsoft.com/en-us/um/people/adum/publications/2005-Efficient_Algorithms_for_Online_Decision_Problems.pdf"> Kalai and Vempala's paper </a> <br> &nbsp <a href="http://www-stat.wharton.upenn.edu/~steele/Resources/Projects/SequenceProject/Hannan.pdf"> Hannan's original paper </a> &nbsp </td> <td> &nbsp none this week &nbsp </td> </tr> <tr> <td> online 2 batch, bandits &nbsp &nbsp</td> <td> &nbsp <a href="http://ocobook.cs.princeton.edu"> chapters 6,9 (5) </a> <br> &nbsp <a href="./notes/lec_8_kiran.pdf"> lecture 8 (unedited) </a> &nbsp </td> <td> &nbsp <a href="http://research.microsoft.com/en-us/um/people/adum/publications/2005-online_convex_optimization_in_the_bandit_setting.pdf"> Flaxman, Kalai, Mcmahan </a> <br> &nbsp <a href="http://colt2008.cs.helsinki.fi/papers/123-Abernethy.pdf"> competing in the dark </a> &nbsp </td> <td> &nbsp <a href="./notes/hw5.pdf"> hw5 </a> &nbsp </td> </tr> <tr> <td> special guest lecture: Prof. Arora &nbsp &nbsp</td> <td> &nbsp <a href="./notes/lec_9_kiran.pdf"> lecture 9 (unedited) </a> <br> &nbsp </td> <td> <a href="http://www.cs.princeton.edu/courses/archive/spring15/cos598D/"> &nbsp Prof. Arora's course</a> </td> <td> &nbsp &nbsp </td> </tr> <tr> <td> bandits cont. , Boosting &nbsp &nbsp</td> <td> &nbsp <a href="http://ocobook.cs.princeton.edu"> chapters 6,10 (5) </a> <br> &nbsp <a href="./notes/lec_10_kiran.pdf"> lecture 10 (unedited) </a> &nbsp </td> <td> &nbsp Boosting: Foundations and Algorithms, by R. E. Schapire and Y. Freund <br> &nbsp <a href="https://www.cs.princeton.edu/courses/archive/spring07/cos424/papers/boosting-survey.pdf"> Schapire survey </a> &nbsp </td> <td> &nbsp <a href="./notes/hw6.pdf"> hw6 </a> &nbsp </td> </tr> <tr> <td> Games, Duality and Regret &nbsp &nbsp</td> <td> &nbsp <a href="http://ocobook.cs.princeton.edu"> chapter 8 (5) </a> <br> &nbsp <a href="./notes/lec_11_kiran.pdf"> lecture 11 (unedited) </a> &nbsp </td> <td> &nbsp <a href="http://dl.acm.org/citation.cfm?id=1536486">convergence of regret minimization dynamics in concave games</a> &nbsp </td> <td> &nbsp &nbsp </td> </tr> <tr> <td> Computational aspects of learning &nbsp &nbsp</td> <td> &nbsp <a href="http://arxiv.org/abs/1504.02089"> research paper </a> <br> &nbsp <a href="./notes/lec_12_kiran.pdf"> lecture 12 (unedited) </a> &nbsp </td> <td> &nbsp <a href="http://www.cs.cmu.edu/~avrim/Papers/sepmodels.pdf">Blum's hardness result </a> &nbsp </td> <td> &nbsp &nbsp </td> </tr> </table> <br> <p>&nbsp;</p> </body> </html>