Statistical learning theory 2023/24 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bauwens (обсуждение | вклад) |
Bauwens (обсуждение | вклад) |
||
| (не показаны 33 промежуточные версии этого же участника) | |||
| Строка 7: | Строка 7: | ||
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]. | 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]. | ||
| − | To discuss the materials, join the [https://t.me/+MeAiv65O8CwyNGY0 telegram group] The course is similar to [http://wiki.cs.hse.ru/Statistical_learning_theory_2022 last year]. | + | To discuss the materials and practical issues, join the [https://t.me/+MeAiv65O8CwyNGY0 telegram group] 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) | ||
| Строка 67: | Строка 72: | ||
|- | |- | ||
| [https://www.youtube.com/watch?v=8J5B9CCy-ws 10 Oct] | | [https://www.youtube.com/watch?v=8J5B9CCy-ws 10 Oct] | ||
| − | || Growth functions, VC-dimension and the characterization of sample comlexity with VC-dimensions | + | || 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/rpnh6288rdb3j8m/05slides.pdf?dl=0 sl05] | ||
| − | || [https://www.dropbox.com/s/eurz2vkvt1wa5zm/07book_growthFunctions.pdf?dl=0 ch07] [https://www.dropbox.com/ | + | || [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/wvj022mv9w82mlynp4t28/06sem.pdf?rlkey=k8bieoxn7zlkfkzyhi311n26s&dl=0 prob06] | ||
|| [https://www.dropbox.com/scl/fi/gcr4n00ef62ezrta7atll/06sol.pdf?rlkey=b9rgqxgmnlxouvsl5eevpwg3d&dl=0 sol06] | || [https://www.dropbox.com/scl/fi/gcr4n00ef62ezrta7atll/06sol.pdf?rlkey=b9rgqxgmnlxouvsl5eevpwg3d&dl=0 sol06] | ||
| Строка 76: | Строка 81: | ||
|| Risk decomposition and the fundamental theorem of statistical learning theory | || 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/s/0p8r5wgjy1hlku2/06slides.pdf?dl=0 sl06] | ||
| − | || [https://www.dropbox.com/ | + | || [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/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] | | [https://www.youtube.com/watch?v=yMsUH1brAs8 24 Oct] | ||
| − | || Bounded differences inequality, Rademacher complexity, symmetrization, contraction lemma. | + | || Bounded differences inequality, Rademacher complexity, symmetrization, contraction lemma. |
|| [https://www.dropbox.com/s/kfithyq0dgcq6h8/07slides.pdf?dl=0 sl07] | || [https://www.dropbox.com/s/kfithyq0dgcq6h8/07slides.pdf?dl=0 sl07] | ||
| − | || [https://www.dropbox.com/ | + | || [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'' | || ''Part 3. Margin risk bounds with applications'' | ||
|- | |- | ||
| − | | [https:// | + | | [https://www.youtube.com/watch?v=oU2AzubDXeo 07 Nov] |
|| Simple regression, support vector machines, margin risk bounds, and neural nets with dropout regularization | || 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/oo1qny9busp3axn/08slides.pdf?dl=0 sl08] | ||
| − | || [https://www.dropbox.com/s/573a2vtjfx8qqo8/12book_regression.pdf?dl=0 ch12] [https://www.dropbox.com/ | + | || [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] | | [https://youtu.be/9FhFxLHR4eE 14 Nov] | ||
|| Kernels: RKHS, representer theorem, risk bounds | || Kernels: RKHS, representer theorem, risk bounds | ||
|| [https://www.dropbox.com/s/jst60ww8ev4ypie/09slides.pdf?dl=0 sl09] | || [https://www.dropbox.com/s/jst60ww8ev4ypie/09slides.pdf?dl=0 sl09] | ||
| − | || [https://www.dropbox.com/ | + | || [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:// | + | | [https://www.youtube.com/watch?v=OgiaWrWh_WA 21 Nov] |
|| AdaBoost and the margin hypothesis | || AdaBoost and the margin hypothesis | ||
|| [https://www.dropbox.com/s/umum3kd9439dt42/10slides.pdf?dl=0 sl10] | || [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/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] | | [https://youtu.be/GL574ljefJ8 28 Nov] | ||
| − | || Implicit regularization of stochastic gradient descent in overparameterized neural nets | + | || 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/ | + | || [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 | | 12 Dec | ||
| Строка 158: | Строка 153: | ||
| − | == | + | == 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. [https://www.dropbox.com/scl/fi/3v82bosdnxdzm26foqg32/scores.ods?rlkey=zc4dqssbq5ssvf8hau72zc1sr&dl=0 Results.] | ||
| − | + | 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. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| Строка 177: | Строка 169: | ||
Maxim Kaledin: Write in Telegram, the time is flexible | Maxim Kaledin: Write in Telegram, the time is flexible | ||
| + | |||
| + | Artur Goldman: Write in Telegram, the time is flexible | ||
<!-- | <!-- | ||
Текущая версия на 23:44, 18 декабря 2023
Содержание
General Information
Lectures: Tuesday 14h40 -- 16h00, room S321 and in zoom by Bruno Bauwens and Maxim Kaledin,
Seminars: Monday 16h20 -- 17h40, room N506, and in zoom by Artur Goldman.
To discuss the materials and practical issues, join the telegram group The course is similar to last year.
Colloquium
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).
-- 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)
Course materials
| Video | Summary | Slides | Lecture notes | Problem list | Solutions |
|---|---|---|---|---|---|
| Part 1. Online learning | |||||
| 05 Sept | Philosophy. The online mistake bound model. The halving and weighted majority algorithms. | sl01 | ch00 ch01 | prob01 | sol01 |
| 12 Sept | The perceptron algorithm. Kernels. The standard optimal algorithm. | sl02 | ch02 ch03 | prob02 | sol02 |
| 19 Sept | Prediction with expert advice. Recap probability theory (seminar). | sl03 | ch04 ch05 | prob03 | sol03 |
| 26 Sept | Multi-armed bandids. | notes04 | prob04 | ||
| Part 2. Distribution independent risk bounds | |||||
| 03 Oct | Necessity of a hypothesis class. Sample complexity in the realizable setting, examples: threshold functions and finite classes. | sl04 | ch06 | prob05 | sol05 |
| 10 Oct | Growth functions, VC-dimension and the characterization of sample comlexity with VC-dimensions | sl05 | ch07 ch08 | prob06 | sol06 |
| 17 Oct | Risk decomposition and the fundamental theorem of statistical learning theory | sl06 | ch09 | prob07 | sol07 |
| 24 Oct | Bounded differences inequality, Rademacher complexity, symmetrization, contraction lemma. | sl07 | ch10 ch11 | prob08 | sol08 |
| Part 3. Margin risk bounds with applications | |||||
| 07 Nov | Simple regression, support vector machines, margin risk bounds, and neural nets with dropout regularization | sl08 | ch12 ch13 | prob09 | sol09 |
| 14 Nov | Kernels: RKHS, representer theorem, risk bounds | sl09 | ch14 | prob10 | sol10 |
| 21 Nov | AdaBoost and the margin hypothesis | sl10 | ch15 | prob11 | sol11 |
| 28 Nov | Implicit regularization of stochastic gradient descent in overparameterized neural nets (recording with many details about the Hessian) | ch16 ch17 | |||
| 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 Library Genesis (the link changes sometimes and sometimes vpn is needed).
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 November 27 December 4, seminar 11 before the start of the exam.
Email to brbauwens-at-gmail.com. Start the subject line with SLT-HW. Results.
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
