Просмотр исходного текста страницы Statistical learning theory 2023/24


== General Information ==


Lectures: Tuesday 14h40 -- 16h00, room S321 and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens] and [https://www.hse.ru/staff/mkaledin Maxim Kaledin], 

Seminars: Monday 16h20 -- 17h40, room N506, and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/org/persons/225526439 Artur Goldman].

The course is similar to [http://wiki.cs.hse.ru/Statistical_learning_theory_2022 last year].


== Colloquium ==

[https://www.dropbox.com/scl/fi/80u1zfr34nt1il8q0avxs/colloqQuest.pdf?rlkey=n8y51ykull9urd0cryv8435nr&dl=0 Rules and questions.] 

Date: Tuesday December 19th during the lecture. (It is possible to come on 12.12 during the lecture or on 12.19 after 18h10 to room ??, but notify Bruno by email.)


== Problems exam ==

December 22th, 13h--16h, room D507, (it is a computer room). <br>
-- You may use handwritten notes, lecture materials from this wiki (either printed or through your PC), Mohri's book  <br>
-- You may not search on the internet or interact with other humans (e.g. by phone, forums, etc) 


== Course materials ==

{| class="wikitable"
|-
! Video !! Summary !! Slides !! Lecture notes !! Problem list !! Solutions
|-
| 
|| ''Part 1. Online learning'' 
|-
| [https://www.youtube.com/watch?v=YfMbst5xIH8 05 Sept]
|| Philosophy. The online mistake bound model. The halving and weighted majority algorithms. <!-- [https://drive.google.com/drive/folders/1NXiLbhmO2Ml7jFmnLtjqhOgCoHg7yn9T?usp=sharing movies] -->
|| [https://www.dropbox.com/scl/fi/j2vqqp3e86yx7pkgmkky6/01slides_all.pdf?rlkey=lxzhu3xd3epypia8j49v25erg&dl=0 sl01]
|| [https://www.dropbox.com/s/oncvg4mxulbt56d/00book_intro.pdf?dl=0 ch00] [https://www.dropbox.com/s/i9pc4kf0zsdeksb/01book_onlineMistakeBound.pdf?dl=0 ch01]
|| [https://www.dropbox.com/scl/fi/qs5wqr97qoyh3l2gfju48/01sem.pdf?rlkey=6lvzcbfkw6lj9y77ep64nq7lk&dl=0 prob01]
|| [https://www.dropbox.com/scl/fi/kksvt6ttgf06u8uce6g9z/01sol.pdf?rlkey=ldcqaewvg7cqdlfqkt7ltckej&dl=0 sol01]
|-
| [https://www.youtube.com/watch?v=gQm1G3Ep-5s 12 Sept]
|| The perceptron algorithm. Kernels. The standard optimal algorithm.
|| [https://www.dropbox.com/s/sy959ee81mov5cr/02slides.pdf?dl=0 sl02] 
|| [https://www.dropbox.com/s/p3auugqwc89132b/02book_sequentialOptimalAlgorithm.pdf?dl=0 ch02] [https://www.dropbox.com/s/b00dcqk1rob7rdz/03book_perceptron.pdf?dl=0 ch03]
|| [https://www.dropbox.com/scl/fi/di1k87aq44ss07mq4s6pi/02sem.pdf?rlkey=yu476v8z77bal6ma029frnilm&dl=0 prob02]
|| [https://www.dropbox.com/scl/fi/d2wuka77bu18j9plivwl5/02sol.pdf?rlkey=yp2eprgxpc7r2antyidjd8qiw&dl=0 sol02]
|-
| [https://www.youtube.com/watch?v=H7kvz2rxX4o 19 Sept]
|| Prediction with expert advice. Recap probability theory (seminar). 
|| [https://www.dropbox.com/s/a60p9b76cxusgqy/03slides.pdf?dl=0 sl03]
|| [https://www.dropbox.com/scl/fi/oetz6dwz77jdlta1k03li/04book_predictionWithExperts.pdf?rlkey=f0u947kiq9bjjaa46iv68lr7j&dl=0 ch04] [https://www.dropbox.com/scl/fi/cx7hsxzwg2f8ep4qcuefc/05book_introProbability.pdf?rlkey=rfq0y9cgzqvl1dlxkccc3qebv&dl=0 ch05]
|| [https://www.dropbox.com/scl/fi/3w9yk9rb7l0pb2l6q94fc/03sem.pdf?rlkey=jt40nnw35t7e8je9nj1ef22f1&dl=0 prob03]
|| [https://www.dropbox.com/scl/fi/w26siug25arwoilgb5t7i/03sol.pdf?rlkey=7waf3ddt4fvz0xeicicayoilt&dl=0 sol03]
|-
| [https://www.youtube.com/watch?v=pxVD5U-csQk 26 Sept]
|| Multi-armed bandids.
|| [https://disk.yandex.ru/i/N0Clt9hZRuaL0A notes04]
|| 
|| [https://disk.yandex.ru/i/vxJaNGtgtq39ow prob04]
|| 
|-
| 
|| ''Part 2. Distribution independent risk bounds'' 
|-
| [https://www.youtube.com/watch?v=ycfYXvmKF0I 03 Oct]
|| Necessity of a hypothesis class. Sample complexity in the realizable setting, examples: threshold functions and finite classes. 
|| [https://www.dropbox.com/s/pi0f3wab1xna6d7/04slides.pdf?dl=0 sl04]
|| [https://www.dropbox.com/s/nh4puyv7nst4ems/06book_sampleComplexity.pdf?dl=0 ch06] 
|| [https://www.dropbox.com/scl/fi/n4004z5mmrn3nbr9ggtt9/05sem.pdf?rlkey=sntvs95trliffbc2vh5vge06b&dl=0 prob05]
|| [https://www.dropbox.com/scl/fi/55530savq0vn6apra7oo4/05sol.pdf?rlkey=ql9q3a7s7k5dkggymul4p4s2o&dl=0 sol05]
|- 
| [https://www.youtube.com/watch?v=8J5B9CCy-ws 10 Oct]
|| Growth functions, VC-dimension and the characterization of sample comlexity with VC-dimensions 
|| [https://www.dropbox.com/s/rpnh6288rdb3j8m/05slides.pdf?dl=0 sl05]
|| [https://www.dropbox.com/s/eurz2vkvt1wa5zm/07book_growthFunctions.pdf?dl=0 ch07] [https://www.dropbox.com/scl/fi/50oxlmjkx59hjrq82yqvx/08book_VCdimension.pdf?rlkey=5dtlcis378kqu24ttko6s7zpf&dl=0 ch08]
|| [https://www.dropbox.com/scl/fi/wvj022mv9w82mlynp4t28/06sem.pdf?rlkey=k8bieoxn7zlkfkzyhi311n26s&dl=0 prob06]
|| [https://www.dropbox.com/scl/fi/gcr4n00ef62ezrta7atll/06sol.pdf?rlkey=b9rgqxgmnlxouvsl5eevpwg3d&dl=0 sol06]
|-
| [https://www.youtube.com/watch?v=zHau8Br_UFQ 17 Oct]
|| Risk decomposition and the fundamental theorem of statistical learning theory
|| [https://www.dropbox.com/s/0p8r5wgjy1hlku2/06slides.pdf?dl=0 sl06]
|| [https://www.dropbox.com/scl/fi/15zjsv1w9coq2py9djlai/09book_riskBounds.pdf?rlkey=4lnyo8kcd226qlybrdgyt36i8&dl=0 ch09]
|| [https://www.dropbox.com/scl/fi/neso7q9vq8ouix208u841/07sem.pdf?rlkey=k8dxkxwqdxf3kjsclzt9vwiw5&dl=0 prob07]
|| [https://www.dropbox.com/scl/fi/dw3u10rhy33pv37z5zf5m/07sol.pdf?rlkey=wssi52zoiveccmpy2197ry5pt&dl=0 sol07]
|-
| [https://www.youtube.com/watch?v=yMsUH1brAs8 24 Oct]
|| Bounded differences inequality, Rademacher complexity, symmetrization, contraction lemma. 
|| [https://www.dropbox.com/s/kfithyq0dgcq6h8/07slides.pdf?dl=0 sl07]
|| [https://www.dropbox.com/scl/fi/ohtmf1fwsu9c6vkrj6e5a/10book_measureConcentration.pdf?rlkey=dqsgskp8slui6xoq9c7tx680b&dl=0 ch10] [https://www.dropbox.com/s/hfrvhebbsskbk6g/11book_RademacherComplexity.pdf?dl=0 ch11]
|| [https://www.dropbox.com/scl/fi/g278mmezenlyxd1my0ta9/08sem.pdf?rlkey=hvqmbumpd0xb6pumdgv5bqx6u&dl=0 prob08]
|| [https://www.dropbox.com/scl/fi/06yobqe58fiecsobp4yrb/08sol.pdf?rlkey=9c7t1y4nxxtg14vpndsyyko2u&dl=0 sol08]
|-
| 
|| ''Part 3. Margin risk bounds with applications'' 
|-
| [https://www.youtube.com/watch?v=oU2AzubDXeo 07 Nov]
|| Simple regression, support vector machines, margin risk bounds, and neural nets with dropout regularization
|| [https://www.dropbox.com/s/oo1qny9busp3axn/08slides.pdf?dl=0 sl08]
|| [https://www.dropbox.com/s/573a2vtjfx8qqo8/12book_regression.pdf?dl=0 ch12] [https://www.dropbox.com/scl/fi/hxeh5btc0bb2f52fnqh5f/13book_SVM.pdf?rlkey=dw3u2rtfstpsb8mi9hnuc8poy&dl=0 ch13]
|| [https://www.dropbox.com/scl/fi/rp2m0dvovdjbvzdl7t1bl/09sem.pdf?rlkey=v1jsm5dagh7tymci5pkqn5gox&dl=0 prob09]
|| [https://www.dropbox.com/scl/fi/e598w1t8tzqxfvn1d4ww1/09sol.pdf?rlkey=yr1gzu8kg2rdkubaelicljj46&dl=0 sol09]
|-
| [https://youtu.be/9FhFxLHR4eE 14 Nov]
|| Kernels: RKHS, representer theorem, risk bounds
|| [https://www.dropbox.com/s/jst60ww8ev4ypie/09slides.pdf?dl=0 sl09]
|| [https://www.dropbox.com/scl/fi/lozpqk5nnm8us77qfhn7x/14book_kernels.pdf?rlkey=s8e7a46rm3znkw13ubj3fzzz0&dl=0 ch14]
|| [https://www.dropbox.com/scl/fi/9mjmb6deu08ipf38s57bh/10sem.pdf?rlkey=z1khm4i8r39eeqmhargte24s4&dl=0 prob10]
|| [https://www.dropbox.com/scl/fi/a5c0buap9b1h1ojdbhp3u/10sol.pdf?rlkey=8ft5tjyy1sl5dkj4p4hh8phbc&dl=0 sol10]
|- 
| [https://www.youtube.com/watch?v=OgiaWrWh_WA 21 Nov]
|| AdaBoost and the margin hypothesis
|| [https://www.dropbox.com/s/umum3kd9439dt42/10slides.pdf?dl=0 sl10]
|| [https://www.dropbox.com/s/e7m1cs7e8ulibsf/15book_AdaBoost.pdf?dl=0 ch15]
|| [https://www.dropbox.com/scl/fi/ykbzx314pdn3mn3jiehli/11sem.pdf?rlkey=hpmtks20a3k5zsvr8jm1iqc35&dl=0 prob11]
|| [https://www.dropbox.com/scl/fi/c805j4f54ioiozphvh9j0/11sol.pdf?rlkey=6rrxlweaiko1lm0z2ua4k7mqk&dl=0 sol11]
|- 
| [https://youtu.be/GL574ljefJ8 28 Nov]
|| Implicit regularization of stochastic gradient descent in overparameterized neural nets ([https://www.youtube.com/watch?v=ygVHVW3y3wM recording] with many details about the Hessian)
|| 
|| [https://www.dropbox.com/scl/fi/1t6e6x839tkr4uv6yn4uu/16book_lossLandscapeNeuralNet.pdf?rlkey=4fttpoe1zcowpgi48ovvyvajt&dl=0 ch16] [https://www.dropbox.com/scl/fi/2g3qj1f861a4xllog4ibo/17book_implicitRegularization.pdf?rlkey=i3qhmryll0cn0lnh5bdvgjhor&dl=0 ch17] 
|| 
|| 
|-
| [https://www.youtube.com/watch?v=RDTK7hBqiJY 05 Dec]
|| Part 2 of previous lecture: Hessian control and stability of the NTK. 
|| 
|| 
|| 
|| 
|-
| 12 Dec
|| ''Colloquium'' (you may choose between 12 Dec and 19 Dec).
|}

Background on multi-armed bandits: A. Slivkins, [Introduction to multi-armed bandits https://arxiv.org/pdf/1904.07272.pdf], 2022.

The lectures in October and November are based on the book:
Foundations of machine learning 2nd ed, Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalker, 2018. This book can be downloaded from [https://libgen.is Library Genesis] (the link changes sometimes and sometimes vpn is needed).

<!-- A gentle introduction to the materials of the first 3 lectures and an overview of probability theory, can be found in chapters 1-6 and 11-12 of the following book:
Sanjeev Kulkarni and Gilbert Harman: An Elementary Introduction to Statistical Learning Theory, 2012.-->

== Grading formula ==

 Final grade = 0.35 * [score of homeworks] + 0.35 * [score of colloquium] + 0.3 * [score on the exam] + bonus from quizzes.

All homework questions have the same weight. Each solved extra homework task increases the score of the final exam by 1 point. 

There is no rounding except on the final grade. Arithmetic rounding is used. 

Autogrades: if you only need 6/10 on the exam to pass with maximal final score, it will be given automatically. This may happen because of extra questions and bonuses from quizzes. 


== Homeworks ==

Deadline every 2 weeks, before the seminar at 16h00. Homework problems from

seminars 1 and 2 on September 25, seminars 3 and 4 on October 9, seminars 5 and 6 on November 6, seminars 7 and 8 on November 13, seminars 9 and 10 on <s>November 27</s> <span style="color:red">December 4</span>, seminar 11 before the start of the exam. 

Email to brbauwens-at-gmail.com. Start the subject line with SLT-HW.

Late policy: 1 homework can be submitted at most 24 late without explanations. 3 HW tasks that were not submitted before can be submitted at any moment before the beginning of the exam.


== Office hours ==

Bruno Bauwens: Wednesday 13h-16h, Friday 14h-20h, (better send an email in advance).   

Maxim Kaledin: Write in Telegram, the time is flexible  

Artur Goldman: Write in Telegram, the time is flexible  

<!--
== Russian texts  ==

The following links might help students who have trouble with English.  A [http://www.machinelearning.ru/wiki/images/d/d9/Voron-2011-tnop.pdf  lecture] on VC-dimensions was given by K. Vorontsov.
A [http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9D._%D0%9A._%D0%96%D0%B8%D0%B2%D0%BE%D1%82%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9) course] on Statistical Learning Theory by Nikita Zhivotovsky is given at MIPT. Some short description about PAC learning on p136 in the [http://gen.lib.rus.ec/search.php?req=%D0%9D%D0%B0%D1%83%D0%BA%D0%B0+%D0%B8+%D0%B8%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%D0%B2%D0%BE+%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D1%8F+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2%2C+%D0%BA%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D0%B5+%D0%B8%D0%B7%D0%B2%D0%BB%D0%B5%D0%BA%D0%B0%D1%8E%D1%82+%D0%B7%D0%BD%D0%B0%D0%BD%D0%B8%D1%8F+%D0%B8%D0%B7+%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&lg_topic=libgen&open=0&view=simple&res=25&phrase=0&column=def book] 
``Наука и искусство построения алгоритмов, которые извлекают знания из данных'', Петер Флах. On [http://www.machinelearning.ru machinelearning.ru] 
you can find brief and clear definitions.
-->