imported>Bauwens: Migrated current public revision from wiki.cs.hse.ru

2024-12-18T13:41:02Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

== General Information ==

Lectures: on Tuesday 9h30--10h50 in room M302 and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]

Seminars: online in [https://us06web.zoom.us/j/85239566702?pwd=y4uhpPrdjSVKOS2LkDIcKCzBXtCbFb.1 Zoom] by [https://www.hse.ru/org/persons/225553845/ Nikita Lukianenko].

Please join the [https://t.me/+1begXb8SomhmODI8 telegram group] The course is similar to [http://wiki.cs.hse.ru/Statistical_learning_theory_2023/24 last year].

[https://docs.google.com/spreadsheets/d/1eo4OvNObJicoY-sfMTMUg7dhjbgcpfkGDs9dIehpUA0/edit?usp=sharing Results]

== Problems exam ==

Friday 20 December 11h-14h, D507<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)

About questions<br>
-- 4 questions of the difficulty of the homework. (Many homework questions were from former exams.)<br>
-- I always ask to calculate VC dimension and to give/prove some risk bound with Rademacher complexity.

== Homeworks ==

Deadline every 2 weeks, before the lecture. The tasks are at the end of each problem list. (Problem lists will be updated, check the year.)

Before 3rd lecture, submit HW from problem lists 1 and 2.
Before 5th lecture, from lists 3 and 4. Etc.

[https://classroom.google.com/c/NzE5NzA4OTg1ODA4?cjc=imgrl43 Classroom] to submit homeworks. You may submit in English or Russian, as latex or as pictures. Results [https://docs.google.com/spreadsheets/d/1k9hivwCzCp3YcR-1n4WnQow94zyQBCjVcgWYaq-PHx8/edit?usp=sharing are here].

Late policy: 1 homework can be submitted at most 24 late without explanations.

== Course materials ==

{| class="wikitable"
|-
! Video !! Summary !! Slides !! Lecture notes !! Problem list !! Solutions
|-
|
|| ''Part 1. Online learning''
|-
| [https://www.youtube.com/watch?v=N_JUBxw3sZo 21 Sep]
|| Philosophy. The online mistake bound model. The halving and weighted majority algorithms.
|| [https://www.dropbox.com/scl/fi/nbxsehlcl8hqodcaho7sg/01slides_all.pdf?rlkey=7u4smvn3jaofhscwrddh6mcoy&st=yb9esz0d&dl=0 sl01]
|| [https://www.dropbox.com/scl/fi/svgelu3iwijls092ehqqf/00book_intro.pdf?rlkey=jxdya4290kfc0hfl06b0y7k4b&st=lnv8chxf&dl=0 ch00] [https://www.dropbox.com/scl/fi/uqa9615215wy7ievgr50y/01book_onlineMistakeBound.pdf?rlkey=jiqzz84b5ipaw4t6cff7b17sl&st=mc354l04&dl=0 ch01]
|| [https://www.dropbox.com/scl/fi/luee4if0mrd4f440q69hd/01sem.pdf?rlkey=8702taq325mvb4ifh15stvvto&st=sq946cf3&dl=0 prob01]
|| [https://www.dropbox.com/scl/fi/kswtqmyxw3pv336g1vdd6/01sol.pdf?rlkey=bpwnrcsj6ru3nbo4xwq2lp6g0&st=hftnu87m&dl=0 sol01]
|-
| [https://www.youtube.com/watch?v=gQm1G3Ep-5s 24 Sep]
|| The standard optimal algorithm. The perceptron algorithm.
|| [https://www.dropbox.com/s/sy959ee81mov5cr/02slides.pdf?dl=0 sl02]
|| [https://www.dropbox.com/scl/fi/9016w6j87oclagapah8dt/02book_sequentialOptimalAlgorithm.pdf?rlkey=r729ir0a47ncqip8rooq9txxo&st=zx2tu8gp&dl=0 ch02] [https://www.dropbox.com/scl/fi/iwclbc321iv4k9fmljwpb/03book_perceptron.pdf?rlkey=9v27bt1b9qc2q382l6lwyrkic&st=ni0n8482&dl=0 ch03]
|| [https://www.dropbox.com/scl/fi/darlkflu0p8idh1smsvqc/02sem.pdf?rlkey=9rxky51dscu0d1pvh0h3iun1i&st=whkfpp78&dl=0 prob02]
|| [https://www.dropbox.com/scl/fi/d2wuka77bu18j9plivwl5/02sol.pdf?rlkey=yp2eprgxpc7r2antyidjd8qiw&dl=0 sol02]
|-
| [https://www.youtube.com/watch?v=Fk1-QI9PRAI 01 Oct]
|| Kernel perceptron algorithm. 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/7pn3dyf2890p9zuyxleyl/04book_predictionWithExperts.pdf?rlkey=0capmeeu6pwp9wz2mhi0t5h58&st=f4c4n9wo&dl=0 ch04] [https://www.dropbox.com/scl/fi/cx7hsxzwg2f8ep4qcuefc/05book_introProbability.pdf?rlkey=rfq0y9cgzqvl1dlxkccc3qebv&dl=0 ch05]
|| [https://www.dropbox.com/scl/fi/bkuydm0u3xonnld8qlbl3/03sem.pdf?rlkey=xg2e9sbpe8c2071pxgcohlcab&st=ezxf2zgq&dl=0 prob03]
|| [https://www.dropbox.com/scl/fi/wjksi4t5r4ng894uiaj8b/03sol.pdf?rlkey=madshl3vupmwkuyzs44ut23ry&st=caroyl3r&dl=0 sol03]
|-
|
|| ''Part 2. Distribution independent risk bounds''
|-
| [https://www.youtube.com/watch?v=ycfYXvmKF0I 08 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/x12se5y3heqtyfzo7qx30/04sem.pdf?rlkey=0hd5hphnbj90jc24nqsw63ka7&st=1zie6tp0&dl=0 prob04] ''update 12.10''
|| [https://www.dropbox.com/scl/fi/g6j0n39zhm1he8kfena8d/04sol.pdf?rlkey=hcg1cr6s4cca9ekqua67ehlhf&st=81bpsm1a&dl=0 sol04]
|-
| [https://www.youtube.com/watch?v=8J5B9CCy-ws 15 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/1n9jdc70ia7vu957mls02/05sem.pdf?rlkey=8x89v3fkm1q61b4frirb9nqke&st=7pfvhuq6&dl=0 prob05]
|| 
|-
| [https://www.youtube.com/watch?v=zHau8Br_UFQ 22 Oct]
|| Risk decomposition and the fundamental theorem of statistical learning theory (previous [https://www.youtube.com/watch?v=zHau8Br_UFQ recording] covers more)
|| [https://www.dropbox.com/s/0p8r5wgjy1hlku2/06slides.pdf?dl=0 sl06]
|| [https://www.dropbox.com/scl/fi/th4r5t2gm29en4hejareq/09book_riskBounds.pdf?rlkey=4ox3f26kygxorxft8jlijuf0f&st=fg0fdyx2&dl=0 ch09]
|| [https://www.dropbox.com/scl/fi/15y2x2pq3pp77144nzee5/06sem.pdf?rlkey=72zoca4wgs472df4izvq2dd3t&st=5m9u4q2u&dl=0 prob06]
|| [https://www.dropbox.com/scl/fi/w8kc0izfc12sqjyd8hfou/06sol.pdf?rlkey=a09f6yx9e0ifohus9vt2ybthd&st=09qmm3m6&dl=0 sol06]
|-
| [https://youtube.com/live/G5fglRAaXMo 05 Nov]
|| 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/701h3asvj5a6kj7d9p1tm/07sem.pdf?rlkey=dsnhc90gp0nd7jqgy3oicds4i&st=fu4nf10i&dl=0 prob07]
|| [https://www.dropbox.com/scl/fi/kd3osu95m7bmilv6z6bxm/07sol.pdf?rlkey=9ycz3obscp65uc05pg2dt3zww&st=9d8g3jkf&dl=0 sol07]
|-
|
|| ''Part 3. Margin risk bounds with applications''
|-
| [https://www.youtube.com/watch?v=oU2AzubDXeo 12 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/ekrdaba2gzpxdp58yvfwo/08sem.pdf?rlkey=vsljva82ekk6ol6k7w1g87pz6&st=146i9y67&dl=0 prob08]
|| [https://www.dropbox.com/scl/fi/fcu1kbczqnxjbvtjpxst7/08sol.pdf?rlkey=irlhu14q6d12poymmc25xmh6q&st=pt7euz9i&dl=0 sol08]
|-
| [https://youtube.com/live/77-rZFzX2O8 19 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/t7jv4gulwbdluc278sadi/09sem.pdf?rlkey=wzitr8cwastoq5koyvpsj252o&st=cdik5cp7&dl=0 prob09]
|| [https://www.dropbox.com/scl/fi/2pxx6ctc7qv4xpvc4esla/09sol.pdf?rlkey=dg9pncbr6d294gz5me3efzrwp&st=v49ksm24&dl=0 sol09]
|-
| [https://www.youtube.com/watch?v=OgiaWrWh_WA 26 Nov]
|| AdaBoost and the margin hypothesis
|| [https://www.dropbox.com/s/umum3kd9439dt42/10slides.pdf?dl=0 sl10]
|| [https://www.dropbox.com/scl/fi/ef1ti9gagjv49mdky1364/15book_AdaBoost.pdf?rlkey=h6myd1zxm74quktq1cy2rc2ae&st=r2at7eha&dl=0 ch15]
|| [https://www.dropbox.com/scl/fi/y3mbpbcoau67i1nfjg7lr/10sem.pdf?rlkey=mfye4kcfgm9gf6aos6z8nd6q4&st=n1btlv8c&dl=0 prob10]
|| [https://www.dropbox.com/scl/fi/5lbthnkjkn35y68ohmhm4/10sol.pdf?rlkey=0w0twp97ohfrlcsspnzfg0wgh&st=74hhghgd&dl=0 sol10]
|-
| [https://youtube.com/live/DUgksR6gOQ8 03 Dec]
|| Losses of neural nets are not locally convex. Gradient descent with stable gradients. ([https://www.youtube.com/watch?v=ygVHVW3y3wM Old recording] about Hessians)
||
|| [https://www.dropbox.com/scl/fi/ipsngdfvo4bvhofxh4377/16book_lossLandscapeNeuralNet.pdf?rlkey=3018bx9wczc4rpu7xq0wxdc2q&st=64mz3r2p&dl=0 ch16]
|| [https://www.dropbox.com/scl/fi/dc86iowe91nlzf3fu1h71/11sem.pdf?rlkey=87a7uqqpy4n39bcm3dxbsidew&st=t1gemioe&dl=0 prob11]
|| [https://www.dropbox.com/scl/fi/topptsvelhdpog2qucfpr/11sol.pdf?rlkey=ceev18140kz2ly8y8crxixf03&st=lvk4j2rz&dl=0 sol11]
|-
| [https://youtube.com/live/URjcCXEMPv4 10 Dec]
|| Lazy training and the neural tangent kernel.
||
|| [https://www.dropbox.com/scl/fi/9b3vkvxqbjbhn30mgab8z/17book_implicitRegularization.pdf?rlkey=efc6epjwi9yqr1cjb7pbhpzi3&st=l47hs8jq&dl=0 ch17]
||
||
|-
| 17 Dec
|| Colloquium 9h30 - 12h30 (room D725) and 18h10 - 21h (different building Старая Басманная А-125). [https://www.dropbox.com/scl/fi/e2692ns95pg0kj0m4e0wo/colloqQuest.pdf?rlkey=peey4u0dxz0vohv39a3oc67ft&st=c87t9kqu&dl=0 Rules and questions.] Reserve in [https://docs.google.com/spreadsheets/d/17pJaioWm3Vo2aYB2J3msTyxj9NSovbZHOC_w6Cxvsj8/edit?usp=sharing shedule.]
|}



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.

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. At the end of the lectures there is a short quiz in which you may earn 0.1 bonus points on the final non-rounded grade.

There is no rounding except for transforming the final grade to the official grade. Arithmetic rounding is used.

Autogrades: if you only need 6/10 on the exam to have the maximal 10/10 for the course, this will be given automatically. This may happen because of extra homework questions and bonuses from quizzes.

== Colloquium ==

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

Date: TBA

== Office hours ==

Bruno Bauwens: Bruno Bauwens: Tuesday 12h -- 20h. Friday 15h -- 17h30. Better send me an email in advance.

Nikita Lukianenko: Write in Telegram, the time is flexible

Statistical learning theory 2024/25 - История изменений

imported>Bauwens: Migrated current public revision from wiki.cs.hse.ru