# 2022 Reading Group

** Published:**

**Aim:** rate of learning is a function space with uniform convergence property(As an example: Holder functions) in different settings.

## Textbook and Reference

- weak convergence and empirical processes by van der Vaart [WCEP]
- Concentration inequalities: a nonasymptotic theory of independence by Boucheron et al. [CI]
- Asymptotic Statistics, by van der Vaart [AS]
- High Dimensional Probability, by Roman Vershynin [HDP]
- High Dimensional Statistics, by Martin Wainwright [HDS]
- Empirical Processes in M-Estimation by van der Vaart [M-Estimate]
- Introduction to Semi-parametric Statistics by Bodhisattva Sen [Semi-Para]
- Introduction to Nonparametric Statistics by Bodhisattva Sen [Non-para]
- Mathematical Statistics: A Non-asymptotic Approach by A.Rakhlin

## Syllabus

#### Week 1: Concentration Inequality and Basic Asymptotic Statistics

- Basic Concentration Inequality for Sub-gaussian/Sub-exp random variables
- Asymptotic normality, delta method, moment method
- Efficiency of the models, local asymptotic normality Reference:
- [HDP] Chapter 1
- [AS] Chapter 2 3 4 5
- [Semi-Para] Chapter 2 and Chapter 3 Reading:
- Han J, Hu R, Long J. A class of dimension-free metrics for the convergence of empirical measures. Stochastic Processes and their Applications, 2023, 164: 242-287.

#### Week 2: Uniform Law of Large Number

- Symmetrization
- Covering Number, Duley Integral Reference:
- [WCEP] Chapter 2

#### Week3: Uniform Center Limit Theorem(Optional)

- Motivation: Goodness-of-fit test, Kolmogorov and Smironv Statistics
- Uniform Center Limit Theorem, functional delta methods Reference:
- Applications of Empirical Process Theory Section 4.2 Reading:
- Quantifying the Empirical Wasserstein Distance to a Set of Measures: Beating the Curse of Dimensionality (NeurIPS), 2020
- Gretton A, Borgwardt K M, Rasch M J, et al. A kernel two-sample test. The Journal of Machine Learning Research, 2012, 13(1): 723-773.

#### Week4: Nonparametric Statistics 1: RKHS(Optional)

Reading:

- Dieuleveut A, Bach F. Nonparametric stochastic approximation with large step-sizes
- Fischer S, Steinwart I. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 2020, 21(205): 1-38.

#### Week5: Min-Max Lower Bound

Reference:

- https://web.stanford.edu/class/ee378c/

#### Week6: Nonparametric Statistics 2: Localized Complexity

Reference:

- Applications of Empirical Process Theory Section 4.3
- geoffrey chinot‘s thesis : section 1
- Lecture Note 2: Generalization Errors by Taiji Suzuki(In Japaness)
- Towards Problem-dependent Optimal Learning Rates (More detailed version: Xu Y, Zeevi A. Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory. arXiv preprint arXiv:2011.06186, 2020.)
- Rakhlin A, Sridharan K, Tsybakov A B. Empirical entropy, minimax regret and minimax risk. Bernoulli, 2017, 23(2): 789-824.
- Variance Regularized Slow rate in [Orthogonal Statistical Learning paper] Reading:
- 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization by Vladimir Koltchinskii
- Yang J, Sun S, Roy D M. Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processes NeurIPS. 2019: 10802-10812.
- Rakhlin A, Sridharan K, Tsybakov A B. Empirical entropy, minimax regret and minimax risk. Bernoulli, 2017, 23(2): 789-824.
- Kur G, Putterman E, Rakhlin A. On the Variance, Admissibility, and Stability of Empirical Risk Minimization. Advances in Neural Information Processing Systems, 2024, 36.

#### Week8: Non-parametric Statistics 4: Deep Learning

- Neural Scaling Laws and explaining Neural Scaling Laws by non-parametric statistics Reference:
- Explaining Neural Scaling Laws by Yasaman Bahr et al. arxiv:2102.06701
- Suzuki T. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality ICLR2019
- Chen M, Jiang H, Liao W, et al. Nonparametric regression on low-dimensional manifolds using deep relu networks Neurips 2019
- Singh S, Uppal A, Li B, et al. Nonparametric density estimation under adversarial losses Neurips 2018
- local radamencher complexity of DNN: http://ibis.t.u-tokyo.ac.jp/suzuki/lecture/2020/intensive2/%E8%AC%9B%E7%BE%A92.pdf

#### Week 9: Non-parametric Statistics 5: Classification

- Tsybakov A B. Optimal aggregation of classifiers in statistical learning[J]. The Annals of Statistics, 2004, 32(1): 135-166.
- Kim Y, Ohn I, Kim D. Fast convergence rates of deep neural networks for classification[J]. arXiv preprint arXiv:1812.03599, 2018. Using Inf covering number
- Bos T, Schmidt-Hieber J. Convergence rates of deep ReLU networks for multiclass classification. arXiv preprint arXiv:2108.00969, 2021.
- Audibert J Y, Tsybakov A B. Fast learning rates for plug-in classifiers[J]. The Annals of statistics, 2007, 35(2): 608-633.

#### Week9: Semi-parametric Statistics

Reference:

- [Semi-Para] section 3 4
- Foster D J, Syrgkanis V. Orthogonal statistical learning. arXiv preprint arXiv:1901.09036, 2019.
- Mackey L, Syrgkanis V, Zadik I. Orthogonal machine learning: Power and limitations International Conference on Machine Learning. PMLR, 2018: 3375-3383.
- Causal Inference Tutorial by Rahul Singh

- Stats361: Causal Inference by Stefan Wager Reading:
- Knowledge Distillation as Semi-Parametric Inference ICLR 2021
- Demirer M, Syrgkanis V, Lewis G, et al. Semi-parametric efficient policy learning with continuous actions. arXiv preprint arXiv:1905.10116, 2019.
- Chernozhukov V, Chetverikov D, Demirer M, et al. Double/debiased machine learning for treatment and structural parameters. 2018. Reading：
- Chernozhukov V, Newey W, Singh R, et al. Adversarial Estimation of Riesz Representers. arXiv preprint arXiv:2101.00009, 2020. https://arxiv.org/pdf/2105.15197.pdf

#### Week11: Non-parametric Bandits

Reference

- Foster D, Rakhlin A. Beyond UCB: Optimal and efficient contextual bandits with regression oracles International Conference on Machine Learning. PMLR, 2020: 3199-3210.
- Hu Y, Kallus N, Mao X. Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes Conference on Learning Theory. PMLR, 2020: 2007-2010.
- Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. Conference on Learning Theory (COLT), page 54, 2010.
- Krishnamurthy S K, Hadad V, Athey S. Adapting to misspecification in contextual bandits with offline regression oracles[J]. arXiv preprint arXiv:2102.13240, 2021. Reading
- Wang T, Rudin C. Bandits for BMO Functions International Conference on Machine Learning. PMLR, 2020: 9996-10006.
- Wang T, Ye W, Geng D, et al. Towards practical Lipschitz stochastic bandits. arXiv preprint arXiv:1901.09277, 2019.

#### Week12: Non-parametric Weakly Supervised Learning

- Active Learning, Disagreement factor-based methods
- Non-parametric transfer learning Reference:
- Works by Samory Kpotufe
- Cai T T, Wei H. Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 2021, 49(1): 100-128.
- Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13 (Jan):67–90, 2012a.
- Castro R M, Nowak R D. Minimax bounds for active learning[J]. IEEE Transactions on Information Theory, 2008, 54(5): 2339-2353.

#### Week13: Empirical Landscape: uniform convergence of gradients

Reference:

- https://github.com/tengyuma/cs229m_notes/blob/main/Winter2021/pdf/02-17-2021.pdf
- https://github.com/tengyuma/cs229m_notes/blob/main/Winter2021/pdf/03-01-2021.pdf
- https://github.com/tengyuma/cs229m_notes/blob/main/Winter2021/pdf/03-03-2021.pdf
- Mei S, Bai Y, Montanari A. The landscape of empirical risk for nonconvex losses. Annals of Statistics, 2018, 46(6A): 2747-2774.
- Foster D J, Sekhari A, Sridharan K. Uniform convergence of gradients for non-convex learning and optimization[J]. arXiv preprint arXiv:1810.11059, 2018.

#### Week 14: Drawback Of Empirical Process, interpolation estimators

Reference:

- Yang Z, Bai Y, Mei S. Exact gap between generalization error and uniform convergence in random feature models[J]. arXiv preprint arXiv:2103.04554, 2021.
- Average case complexity, reference:

#### Week 15: non-P-Donscker

Example: log-concave densities, convex functions. Cases that ERM is not optimal References:

- Kur, Gil, Yuval Dagan, and Alexander Rakhlin. “Optimality of maximum likelihood for log-concave density estimation and bounded convex regression.” arXiv preprint arXiv:1903.05315 (2019).
- Kur G, Rakhlin A. On the Minimal Error of Empirical Risk Minimization. arXiv preprint arXiv:2102.12066, 2021.

#### Week16 Learning Dynamic systems

- Hang H, Steinwart I. A Bernstein-type inequality for some mixing processes and dynamical systems with an application to learning[J]. The Annals of Statistics, 2017, 45(2): 708-743.
- Foster D, Sarkar T, Rakhlin A. Learning nonlinear dynamical systems from a single trajectory Learning for Dynamics and Control. PMLR, 2020: 851-861.
- Nickl R, Ray K. Nonparametric statistical inference for drift vector fields of multi-dimensional diffusions. The Annals of Statistics, 2020, 48(3): 1383-1408.
- Hang H, Steinwart I. Fast learning from α-mixing observations[J]. Journal of Multivariate Analysis, 2014, 127: 184-199.

## Reading List

- Fusheng Liu, Haizhao Yang, Soufiane Hayou, and Qianxiao Li. Connecting optimization and generalization via gradient flow path length. arXiv preprint arXiv:2202.10670, 2022.
- Adaptive learning rates for support vector machines working on data with low intrinsic dimension
- Which Spaces can be Embedded in Reproducing Kernel Hilbert Spaces?