Statistical learning theory 2025 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Brbauwens (обсуждение | вклад) (Новая страница: «== General Information == Lectures: on TBA in room TBA and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.h…») |
Brbauwens (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
|| [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/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/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.dropbox.com/scl/fi/kswtqmyxw3pv336g1vdd6/01sol.pdf?rlkey=bpwnrcsj6ru3nbo4xwq2lp6g0&st=hftnu87m&dl=0 sol01] --> |
|- | |- | ||
| [https://www.youtube.com/watch?v=gQm1G3Ep-5s ?? Sep] | | [https://www.youtube.com/watch?v=gQm1G3Ep-5s ?? Sep] | ||
| Строка 40: | Строка 40: | ||
|| [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/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/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.dropbox.com/scl/fi/d2wuka77bu18j9plivwl5/02sol.pdf?rlkey=yp2eprgxpc7r2antyidjd8qiw&dl=0 sol02] --> |
|- | |- | ||
| [https://www.youtube.com/watch?v=Fk1-QI9PRAI ?? Oct] | | [https://www.youtube.com/watch?v=Fk1-QI9PRAI ?? Oct] | ||
| Строка 47: | Строка 47: | ||
|| [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/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/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] | + | || <!-- [https://www.dropbox.com/scl/fi/wjksi4t5r4ng894uiaj8b/03sol.pdf?rlkey=madshl3vupmwkuyzs44ut23ry&st=caroyl3r&dl=0 sol03] --> |
|- | |- | ||
| | | | ||
| Строка 57: | Строка 57: | ||
|| [https://www.dropbox.com/s/nh4puyv7nst4ems/06book_sampleComplexity.pdf?dl=0 ch06] | || [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/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.dropbox.com/scl/fi/g6j0n39zhm1he8kfena8d/04sol.pdf?rlkey=hcg1cr6s4cca9ekqua67ehlhf&st=81bpsm1a&dl=0 sol04] --> |
|- | |- | ||
| [https://www.youtube.com/watch?v=8J5B9CCy-ws ?? Oct] | | [https://www.youtube.com/watch?v=8J5B9CCy-ws ?? Oct] | ||
| Строка 71: | Строка 71: | ||
|| [https://www.dropbox.com/scl/fi/th4r5t2gm29en4hejareq/09book_riskBounds.pdf?rlkey=4ox3f26kygxorxft8jlijuf0f&st=fg0fdyx2&dl=0 ch09] | || [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/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://www.dropbox.com/scl/fi/w8kc0izfc12sqjyd8hfou/06sol.pdf?rlkey=a09f6yx9e0ifohus9vt2ybthd&st=09qmm3m6&dl=0 sol06] --> |
|- | |- | ||
| [https://youtube.com/live/G5fglRAaXMo ?? Nov] | | [https://youtube.com/live/G5fglRAaXMo ?? Nov] | ||
| Строка 78: | Строка 78: | ||
|| [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/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/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] | + | || <!-- [https://www.dropbox.com/scl/fi/kd3osu95m7bmilv6z6bxm/07sol.pdf?rlkey=9ycz3obscp65uc05pg2dt3zww&st=9d8g3jkf&dl=0 sol07] --> |
|- | |- | ||
| | | | ||
| Строка 88: | Строка 88: | ||
|| [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/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/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://www.dropbox.com/scl/fi/fcu1kbczqnxjbvtjpxst7/08sol.pdf?rlkey=irlhu14q6d12poymmc25xmh6q&st=pt7euz9i&dl=0 sol08] --> |
|- | |- | ||
| [https://youtube.com/live/77-rZFzX2O8 ?? Nov] | | [https://youtube.com/live/77-rZFzX2O8 ?? Nov] | ||
| Строка 95: | Строка 95: | ||
|| [https://www.dropbox.com/scl/fi/lozpqk5nnm8us77qfhn7x/14book_kernels.pdf?rlkey=s8e7a46rm3znkw13ubj3fzzz0&dl=0 ch14] | || [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/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.dropbox.com/scl/fi/2pxx6ctc7qv4xpvc4esla/09sol.pdf?rlkey=dg9pncbr6d294gz5me3efzrwp&st=v49ksm24&dl=0 sol09] --> |
|- | |- | ||
| [https://www.youtube.com/watch?v=OgiaWrWh_WA ?? Nov] | | [https://www.youtube.com/watch?v=OgiaWrWh_WA ?? Nov] | ||
| Строка 102: | Строка 102: | ||
|| [https://www.dropbox.com/scl/fi/ef1ti9gagjv49mdky1364/15book_AdaBoost.pdf?rlkey=h6myd1zxm74quktq1cy2rc2ae&st=r2at7eha&dl=0 ch15] | || [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/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://www.dropbox.com/scl/fi/5lbthnkjkn35y68ohmhm4/10sol.pdf?rlkey=0w0twp97ohfrlcsspnzfg0wgh&st=74hhghgd&dl=0 sol10] --> |
|- | |- | ||
| [https://youtube.com/live/DUgksR6gOQ8 ?? Dec] | | [https://youtube.com/live/DUgksR6gOQ8 ?? Dec] | ||
| Строка 109: | Строка 109: | ||
|| [https://www.dropbox.com/scl/fi/ipsngdfvo4bvhofxh4377/16book_lossLandscapeNeuralNet.pdf?rlkey=3018bx9wczc4rpu7xq0wxdc2q&st=64mz3r2p&dl=0 ch16] | || [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/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://www.dropbox.com/scl/fi/topptsvelhdpog2qucfpr/11sol.pdf?rlkey=ceev18140kz2ly8y8crxixf03&st=lvk4j2rz&dl=0 sol11] --> |
|- | |- | ||
| [https://youtube.com/live/URjcCXEMPv4 ?? Dec] | | [https://youtube.com/live/URjcCXEMPv4 ?? Dec] | ||
Версия 21:18, 15 сентября 2025
Содержание
General Information
Lectures: on TBA in room TBA and in zoom by Bruno Bauwens
Seminars: on TBA in room TBA online in Zoom probably by Nikita Lukianenko.
Please join the telegram group The course is similar to last year.
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 homework from problem lists 1 and 2. Before 5th lecture, from lists 3 and 4. Etc.
Use --this link-- to submit homeworks. You may submit in English or Russian, as latex or as pictures. Results are here.
Late policy: 1 homework can be submitted at most 24 late without explanations.
Course materials
| Video | Summary | Slides | Lecture notes | Problem list | Solutions |
|---|---|---|---|---|---|
| Part 1. Online learning | |||||
| ?? Sep | Philosophy. The online mistake bound model. The halving and weighted majority algorithms. | sl01 | ch00 ch01 | prob01 | |
| ?? Sep | The standard optimal algorithm. The perceptron algorithm. | sl02 | ch02 ch03 | prob02 | |
| ?? Oct | Kernel perceptron algorithm. Prediction with expert advice. Recap probability theory (seminar). | sl03 | ch04 ch05 | prob03 | |
| Part 2. Distribution independent risk bounds | |||||
| ?? Oct | Necessity of a hypothesis class. Sample complexity in the realizable setting, examples: threshold functions and finite classes. | sl04 | ch06 | prob04 update 12.10 | |
| ?? Oct | Growth functions, VC-dimension and the characterization of sample comlexity with VC-dimensions | sl05 | ch07 ch08 | prob05 | |
| ?? Oct | Risk decomposition and the fundamental theorem of statistical learning theory (previous recording covers more) | sl06 | ch09 | prob06 | |
| ?? Nov | Bounded differences inequality, Rademacher complexity, symmetrization, contraction lemma. | sl07 | ch10 ch11 | prob07 | |
| Part 3. Margin risk bounds with applications | |||||
| ?? Nov | Simple regression, support vector machines, margin risk bounds, and neural nets with dropout regularization | sl08 | ch12 ch13 | prob08 | |
| ?? Nov | Kernels: RKHS, representer theorem, risk bounds | sl09 | ch14 | prob09 | |
| ?? Nov | AdaBoost and the margin hypothesis | sl10 | ch15 | prob10 | |
| ?? Dec | Losses of neural nets are not locally convex. Gradient descent with stable gradients. (Old recording about Hessians) | ch16 | prob11 | ||
| ?? Dec | Lazy training and the neural tangent kernel. | ch17 |
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
Rules and questions from last year.
Date: TBA
Problems exam
Date: TBA
-- You may use handwritten notes, lecture materials from this wiki (either printed or through your PC), Mohri's book
-- You may not search on the internet or interact with other humans (e.g. by phone, forums, etc)
About questions
-- 4 questions of the difficulty of the homework. (Many homework questions were from former exams.)
-- I always ask to calculate VC dimension and to give/prove some risk bound with Rademacher complexity.
Office hours
Bruno Bauwens: TBA. Better send me an email in advance.
Nikita Lukianenko: Write in Telegram, the time is flexible
