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

2025-12-21T08:40:48Z

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

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

== General Information ==

Lectures: on Tuesdays 13h00 -- 14h20 in Pokrovkaya, see [https://docs.google.com/spreadsheets/d/1EAbqb8wf48evEi5Bf2M0xmZXQSrpd_FJbsnevXDQxaQ/edit?gid=614347250#gid=614347250 here] for the room a few hours before the lecture, and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]

Seminars: on Tuesdays 14h40 -- 16h00 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/+JX7BTfez1sYyODFk telegram group] The course is similar to [http://wiki.cs.hse.ru/Statistical_learning_theory_2024/25 last year].

== Homeworks ==

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

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

Submit homeworks in [https://classroom.google.com/c/ODE1MTM3NzkzNjMz?cjc=rfmqiyik google class]. You may submit preferably in English, as latex or as pictures (if in Russian, you should type it). Results [https://docs.google.com/spreadsheets/d/1ef5FanXBoxh7xO0rpvU8xJfxBtmfmXev1onvyvN27UQ/edit?usp=sharing are here].

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

== Course materials ==

{| class="wikitable"
|-
! Video !! Summary !! Slides !! Lecture notes !! Problem list !! Solutions
|-
|
|| ''Part 1. Online learning''
|-
| [https://rutube.ru/video/private/73eda00904d975a1860151ad0203b529/?p=TSJicLPrAw5Tz1Q67j9jKw 16 Sep]
|| Philosophy. The online mistake bound model. The halving and weighted majority algorithms.
|| [https://www.dropbox.com/scl/fi/954v3zn1d3zn68crzr85l/01slides_all.pdf?rlkey=7b613hrqwbho2qqtoekj8ua3s&st=lcg46pnb&dl=0 sl01]
|| [https://www.dropbox.com/scl/fi/x07bx3n4col196mm3twnv/00book_intro.pdf?rlkey=zexicpaviliqm8141n056h61z&st=puhs63f2&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/37lvjuq06v3yaejqsbn4v/01sem.pdf?rlkey=7940pxuyduvrinz0639axglx7&st=jt3lchhd&dl=0 prob01]
|| [https://www.dropbox.com/scl/fi/kswtqmyxw3pv336g1vdd6/01sol.pdf?rlkey=bpwnrcsj6ru3nbo4xwq2lp6g0&st=hftnu87m&dl=0 sol01]
|-
| [https://rutube.ru/video/8d4e5fd67a791b8f0b46603c2dd4cffe 23 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/ytjjgu9fcjcqm1a0h015q/02sem.pdf?rlkey=oj132041fc6g3i5tbjezlj7fv&st=q3lr807c&dl=0 prob02]
|| [https://www.dropbox.com/scl/fi/0a00da9ls8bsb2zuhgor1/02sol.pdf?rlkey=x9wkfvqfu9j6x6nnf9im24w0x&st=xg427cef&dl=0 sol02]
|-
| [https://rutube.ru/video/private/1182e518bc57807ba63fcb1e4d34a2df/?p=7Oox56EgTf8lCAUwLPir2A 30 Sep]
|| 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/vgqy4yp5dl6ip6ydunm69/03sem.pdf?rlkey=cgmdzvg4dn2eesspy0196l2v5&st=n6864cld&dl=0 prob03] Upd 7 Oct
|| [https://www.dropbox.com/scl/fi/rwq6u32ld68bcdz3mk4cl/03sol.pdf?rlkey=2b8q1vih0byz6ipu1s2tbfzet&st=8ea131vr&dl=0 sol03]
|-
|
|| ''Part 2. Distribution independent risk bounds''
|-
| [https://rutube.ru/video/c1efb4a0af21e2309d9353e5cc5616fa/ 07 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/3g1r1gqfsilr2xuf0s5wc/04sem.pdf?rlkey=7rtmzxsynqf4340duzsqof2k0&st=uod3vu0z&dl=0 prob04]
|| [https://www.dropbox.com/scl/fi/kbjujf1wazsirzg9cno6p/04sol.pdf?rlkey=lcbilxedmhi1toghgenaiy2nu&st=c29aqpjw&dl=0 sol04]
|-
| [https://www.youtube.com/watch?v=8J5B9CCy-ws 14 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/jhcildh8546dr0u9kkz5n/05sem.pdf?rlkey=l8wz1fyl2svmcu2w8tbd0rzjh&st=5lipe8jy&dl=0 prob05]
|| [https://www.dropbox.com/scl/fi/70z0umh656y5kt45vsbt9/05sol.pdf?rlkey=6jpu3usc6uri7duj78l9wr8wq&st=w8gjtn1i&dl=0 sol05]
|-
| [https://rutube.ru/video/e50aeb873359ba63e4df48d52fa8cb67 21 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/orntdt6b6u8y4b408dkfz/06sem.pdf?rlkey=3j6sajyqdvtfph49ao73mj6ly&st=i5j8itjr&dl=0 prob06]
|| [https://www.dropbox.com/scl/fi/53b0wro00u20tkpqb6206/06sol.pdf?rlkey=u1hpkkrrz96ol7i49ifdrhpud&st=bbs9e6yr&dl=0 sol06]
|-
| [https://rutube.ru/video/fb0bb984a0461b9e5b9ea2e6973f8252/ 23 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/spcnkcm5opa432mqeh95s/07sem.pdf?rlkey=roht5zgpdaatx4h9dy24lryoi&st=wu6ubcdi&dl=0 prob07]
|| [https://www.dropbox.com/scl/fi/icn16qpdb5bfyb46nn72x/07sol.pdf?rlkey=smcllfyfub5jsk530i2igdg3w&st=efos9f1f&dl=0 sol07]
|-
|
|| ''Part 3. Margin risk bounds with applications''
|-
| [https://rutube.ru/video/43cde71591a0ee78e27d4818daddc313/ 06 Nov]
|| Simple regression, support vector machines, margin risk bounds, and dropout in neural nets (switch to [https://rutube.ru/video/43cde71591a0ee78e27d4818daddc313/ old recording] for SVM stuff).
|| [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/kb8njw77xqohcul0meeik/08sem.pdf?rlkey=c0cewf8l34skxcanhtbc29wrk&st=kd7d535j&dl=0 prob08]
|| [https://www.dropbox.com/scl/fi/17idg180n115gu2cd5qqu/08sol.pdf?rlkey=mo07u28tszof7l3fzxahj8cm1&st=oy758osr&dl=0 sol08]
|-
| [https://youtube.com/live/77-rZFzX2O8 11 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/72ze9ki1si6v9wnaw6ioi/09sem.pdf?rlkey=5junztvzv8rxguts9lv4xyh7g&st=5xplcduo&dl=0 prob09]
|| [https://www.dropbox.com/scl/fi/pod6vizxg2y6gjhmz9kip/09sol.pdf?rlkey=jvdyl6d0z4yw7stdgszfsan7z&st=8coxi1hv&dl=0 sol09]
|-
| [https://rutube.ru/video/private/5ffc7d4c3dbcf8f60f7f553b87fd555a/?p=eYr_yyIUJ2yHdB7CFygpbg 18 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/hhsmkjr0g5fwk56wicdok/10sem.pdf?rlkey=c6rntxw1zhs2fe9tajmdhvlsa&st=b1wi8bwd&dl=0 prob10]
|| [https://www.dropbox.com/scl/fi/petas7wseh2p1igpjjonk/10sol.pdf?rlkey=zubelzltmtgyvxwpfssm4vdvi&st=geg7yxi1&dl=0 sol10]
|-
|
|| ''Part 4. Neural nets''
|-
| [https://rutube.ru/video/private/0880b08b276d73b298680531eb2f50ec/?p=Q0Yuxh016gjGtW8887Dnpw 25 Nov]
|| Exponential (and cross entropy loss) find maximal margin solutions. Losses of neural nets are not locally convex.
||
|| [https://www.dropbox.com/scl/fi/i30jfjbqwp3uryst3q350/16book_lossLandscapeNeuralNet.pdf?rlkey=k601mv0bcnvg79gbbbncaeipz&st=htto7z78&dl=0 ch16]
|| See next
||
|-
| [https://rutube.ru/video/eec59ac42390d487b0b9e20258ddc7de 02 Dec]
|| Lazy training and the neural tangent kernel in overparameterized nets.
||
|| [https://www.dropbox.com/scl/fi/8b415o6xl07jkzbf9ey01/17book_implicitRegularization.pdf?rlkey=byvcf6qg0ogqm9ipq4tznkfhl&st=qin9wihv&dl=0 ch17]
|| [https://www.dropbox.com/scl/fi/ygnglg7z6sb40ygbvb1id/11sem.pdf?rlkey=jo7hzregeo7l0pdef3cxrqt6g&st=z5gmibhm&dl=0 prob11]
|| [https://www.dropbox.com/scl/fi/topptsvelhdpog2qucfpr/11sol.pdf?rlkey=ceev18140kz2ly8y8crxixf03&st=lvk4j2rz&dl=0 sol11]
|-
| [https://rutube.ru/video/2433020134d99071e0a591a23b595f00/ 09 Dec]
|| Finnish previous lecture. Optional: a label dependent risk bound for overparameterized nets.
||
|| [https://www.dropbox.com/scl/fi/vqt63hgp15ea0tqrsy8li/18book_fineGrainedAnalyses.pdf?rlkey=ufsc4tev9h7w8lev13ww8ntyo&st=v03nuk8x&dl=0 ch18]
|| Consult 15.12
||
|-
| 16 Dec
|| Colloquium [https://www.dropbox.com/scl/fi/4k5s7yrarztkj9xhh8gh2/colloqQuest.pdf?rlkey=36tqup19jwjs89x7y5qdgvsxr&st=iww3fo1v&dl=0 Rules and questions]. Select a [https://docs.google.com/spreadsheets/d/1aaetd-Mh9Y_OaJXYprfsrWz7wkt5fvg12VJRpqkqMTc/edit?usp=sharing timeslot].
|}



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.

== Problems exam ==

Date: Saturday 20.12, 13h-17h, room D203<br>
-- You may use handwritten notes, lecture materials from this wiki (either printed or through your PC, it is a computer room), 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 or 5 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.
-- [https://www.dropbox.com/scl/fi/nsmp6azkhh63s5x0chkby/exampleExam.pdf?rlkey=b95kbp6ujm6d4gsn8yp2blho2&st=t1ehcbap&dl=0 Example] of an exam (a bit easier, during COVID).

If you have a passing grade without attending the exam, you may skip the exam and I will mark you as present by default.

== Office hours ==

Bruno Bauwens: Tuesday 15h-21h Better send me an email in advance.

Nikita Lukianenko: Write in Telegram, the time is flexible

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

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