Gradient-Based Empirical Risk Minimization Using Local Polynomial Regression

References

• Agarwal A, Shah D, Shen D, Song D (2021) On robustness of principal component regression. J. Amer. Statist. Assoc. 116(536):1731–1745.Google Scholar
• Agarwal A, Wainwright MJ, Bartlett PL, Ravikumar PK (2009) Information-theoretic lower bounds on the oracle complexity of convex optimization. Proc. Adv. Neural Inform. Processing Systems 22 NeurIPS (Curran Associates Inc., Red Hook, NY), 1–9.Google Scholar
• Apostol TM (1974) Mathematical Analysis, 2nd ed. (Addison-Wesley, Reading, MA).Google Scholar
• Ausset G, Clémençon S, Portier F (2021) Nearest neighbour based estimates of gradients: Sharp nonasymptotic bounds and applications. Proc. 24th Internat. Conf. Artificial Intelligence Statist. AISTATS (PMLR, New York), 532–540.Google Scholar
• Belkin M, Niyogi P (2001) Laplacian eigenmaps and spectral techniques for embedding and clustering. Proc. Adv. Neural Inform. Processing Systems 14 NeurIPS (MIT Press, Cambridge, MA), 585–591.Google Scholar
• Bishop CM (2006) Pattern Recognition and Machine Learning, Information Science and Statistics (Springer, New York).Google Scholar
• Bottou L, Curtis FE, Nocedal J (2018) Optimization methods for large-scale machine learning. SIAM Rev. 60(2):223–311.Google Scholar
• Bubeck S (2015) Convex Optimization: Algorithms and Complexity, Foundations and Trends in Machine Learning, vol. 8 (Now Publishers Inc., Hanover, MA).Google Scholar
• Carmon Y, Duchi JC, Hinder O, Sidford A (2021) Lower bounds for finding stationary points II: First-order methods. Math. Program. Ser. A 185:315–355.Google Scholar
• Chatterjee S (2015) Matrix estimation by universal singular value thresholding. Ann. Statist. 43(1):177–214.Google Scholar
• Chen GH, Shah D (2018) Explaining the Success of Nearest Neighbor Methods in Prediction, Foundations and Trends in Machine Learning, vol. 10 (Now Publishers Inc., Hanover, MA).Google Scholar
• Chihara TS (2011) An Introduction to Orthogonal Polynomials (Dover, New York).Google Scholar
• Choi E, Xiao C, Stewart WF, Sun J (2018) MiME: Multilevel medical embedding of electronic health records for predictive healthcare. Proc. Adv. Neural Inform. Processing Systems 32 NeurIPS (Curran Associates Inc., Red Hook, NY), 4547–4557.Google Scholar
• Cleveland WS, Loader C (1996) Smoothing by local regression: Principles and methods. Härdle W, Schimek MG, eds. Statistical Theory and Computational Aspects of Smoothing: Proceedings of the COMPSTAT ‘94 Satellite Meeting Held in Semmering, Austria August 27-28, 1994, Contributions to Statistics (Physica-Verlag, Heidelberg, Germany), 10–49.Google Scholar
• Coifman RR, Lafon S (2006) Diffusion maps. Appl. Comput. Harmonic Anal. 21(1):5–30.Google Scholar
• Cover TM, Hart PE (1967) Nearest neighbor pattern classification. IEEE Trans. Inform. Theory IT-13(1):21–27.Google Scholar
• Cui C, Zhang K, Daulbaev T, Gusak J, Oseledets I, Zhang Z (2020) Active subspace of neural networks: Structural analysis and universal attacks. SIAM J. Math. Data Sci. 2(4):1096–1122.Google Scholar
• Dasgupta S, Gupta A (2003) An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures Algorithms 22(1):60–65.Google Scholar
• De Brabanter K, De Brabanter J, De Moor B, Gijbels I (2013) Derivative estimation with local polynomial fitting. J. Machine Learn. Res. 14(1):281–301.Google Scholar
• Dekel O, Gilad-Bachrach R, Shamir O, Xiao L (2012) Optimal distributed online prediction using mini-batches. J. Machine Learn. Res. 13(6):165–202.Google Scholar
• Delecroix M, Rosa AC (1996) Nonparametric estimation of a regression function and its derivatives under an ergodic hypothesis. J. Nonparametric Statist. 6(4):367–382.Google Scholar
• Devolder O, Glineur F, Nesterov Y (2013) First-order methods with inexact oracle: The strongly convex case. CORE Discussion Papers 2013(16), Université catholique de Louvain, Louvain-la-Neuve, Belgium.Google Scholar
• Dutton RD, Brigham RC (1986) Computationally efficient bounds for the Catalan numbers. Eur. J. Combin. 7(3):211–213.Google Scholar
• Fan J, Gijbels I (1996) Local Polynomial Modeling and Its Applications, Monographs on Statistics and Applied Probability, vol. 66 (Chapman and Hall, London).Google Scholar
• Fang C, He H, Long Q, Su WJ (2021) Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proc. Natl. Acad. Sci. USA 118(43):1–12.Google Scholar
• Feller W (1968) An Introduction to Probability Theory and Its Applications, vol. 1, 3rd ed. (John Wiley & Sons, Inc., New York).Google Scholar
• Fix E, Hodges JL (1951) Discriminatory analysis. Nonparametric discrimination: Consistency properties. Technical report, University of California, Berkeley, CA, and USAF School of Aviation Medicine, Randolph Field, San Antonio, TX.Google Scholar
• Forbes C, Evans M, Hastings N, Peacock B (2011) Statistical Distributions, 4th ed. (John Wiley & Sons, Inc., Hoboken, NJ).Google Scholar
• Friedlander MP, Schmidt M (2012) Hybrid deterministic-stochastic methods for data fitting. SIAM J. Sci. Comput. 34(3):A1380–A1405.Google Scholar
• Galanti T, Siegel ZS, Gupte A, Poggio T (2023) SGD and weight decay provably induce a low-rank bias in neural networks. Preprint, submitted January 27, https://arxiv.org/abs/2206.05794v3.Google Scholar
• Gooneratne M, Sim KC, Zadrazil P, Kabel A, Beaufays F, Motta G (2020) Low-rank gradient approximation for memory-efficient on-device training of deep neural network. Proc. IEEE Internat. Conf. Acoustics Speech Signal Processing ICASSP (IEEE, Piscataway, NJ), 3017–3021.Google Scholar
• Gur-Ari G, Roberts DA, Dyer E (2018) Gradient descent happens in a tiny subspace. Preprint, submitted December 12, https://arxiv.org/abs/1812.04754.Google Scholar
• Hastie T, Tibshirani R, Friedman J (2009) The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed., Springer Series in Statistics (Springer, New York).Google Scholar
• Horn RA, Johnson CR (2013) Matrix Analysis, 2nd ed. (Cambridge University Press, New York).Google Scholar
• Hotelling H (1933) Analysis of a complex of statistical variables into principal components. J. Ed. Psych. 24(6):417–441, 498–520.Google Scholar
• Hotelling H (1936) Relations between two sets of variates. Biometrika 28(3/4):321–377.Google Scholar
• Huang SL, Makur A, Wornell GW, Zheng L (2024) Universal Features for High-Dimensional Learning and Inference, Foundations and Trends in Communications and Information Theory, vol. 21 (Now Publishers Inc., Hanover, MA).Google Scholar
• Hui L, Belkin M, Nakkiran P (2022) Limitations of neural collapse for understanding generalization in deep learning. Preprint, submitted February 17, https://arxiv.org/abs/2202.08384.Google Scholar
• Jadbabaie A, Makur A, Shah D (2023) Federated optimization of smooth loss functions. IEEE Trans. Inform. Theory 69(12):7836–7866.Google Scholar
• Jain P, Kar P (2017) Non-Convex Optimization for Machine Learning, Foundations and Trends in Machine Learning, vol. 10 (Now Publishers Inc., Hanover, MA).Google Scholar
• Johnson R, Zhang T (2013) Accelerating stochastic gradient descent using predictive variance reduction. Proc. Adv. Neural Inform. Processing Systems 26 NeurIPS (Curran Associates Inc., Red Hook, NY), 315–323.Google Scholar
• Jolliffe IT (1982) A note on the use of principal components in regression. J. Roy. Statist. Soc. Ser. C. Appl. Statist. 31(3):300–303.Google Scholar
• Körner TW (1988) Fourier Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Krantz SG, Parks HR (2002) A Primer of Real Analytic Functions, 2nd ed., Birkhäuser Advanced Texts: Basler Lehrbücher (Birkhäuser, Boston).Google Scholar
• Le T, Jegelka S (2022) Training invariances and the low-rank phenomenon: Beyond linear networks. Proc. Tenth Internat. Conf. Learn. Representations (ICLR, Appleton, WI), 1–26.Google Scholar
• Le Roux N, Schmidt M, Bach F (2012) A stochastic gradient method with an exponential convergence rate for finite training sets. Proc. Adv. Neural Inform. Processing Systems 25 NeurIPS (Curran Associates Inc., Red Hook, NY), 1–9.Google Scholar
• Makur A (2019) Information contraction and decomposition. ScD thesis in Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Marshall AW, Olkin I, Arnold BC (2011) Inequalities: Theory of Majorization and Its Applications, 2nd ed., Springer Series in Statistics (Springer, New York).Google Scholar
• Masry E (1996) Multivariate regression estimation local polynomial fitting for time series. Stochastic Processes Appl. 65(1):81–101.Google Scholar
• Masry E (1999) Multivariate regression estimation of continuous-time processes from sampled data: Local polynomial fitting approach. IEEE Trans. Inform. Theory 45(6):1939–1953.Google Scholar
• Merikoski JK, Virtanen A (1997) Bounds for eigenvalues using the trace and determinant. Linear Algebra Appl. 264:101–108.Google Scholar
• Mukherjee S, Wu Q (2006) Estimation of gradients and coordinate covariation in classification. J. Machine Learn. Res. 7(88):2481–2514.Google Scholar
• Mukherjee S, Zhou DX (2006) Learning coordinate covariances via gradients. J. Machine Learn. Res. 7(18):519–549.Google Scholar
• Nadaraya EA (1964) On estimating regression. Theory Probab. Appl. 9(1):141–142.Google Scholar
• Nechyba MC, Xu Y (1994) Neural network approach to control system identification with variable activation functions. Proc. 9th IEEE Internat. Sympos. Intelligent Control (IEEE, Piscataway, NJ), 358–363.Google Scholar
• Nedić A (2015) Distributed optimization. Baillieul J, Samad T, eds. Encyclopedia of Systems and Control (Springer, London), 308–317.Google Scholar
• Nelles O (2001) Nonlinear System Identification: From Classical Approaches to Neural Networks and Fuzzy Models (Springer, Berlin, Heidelberg).Google Scholar
• Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4):1574–1609.Google Scholar
• Nemirovskiĭ AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons Inc., New York).Google Scholar
• Nesterov YE (1983) A method of solving a convex programming problem with convergence rate O(1k2). Dokl. Akad. Nauk SSSR 269(3):543–547.Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, vol. 87 (Springer, New York).Google Scholar
• Netrapalli P (2019) Stochastic gradient descent and its variants in machine learning. J. Indian Inst. Sci. 99(2):201–213.Google Scholar
• Nguyen Q, Valizadegan H, Hauskrecht M (2011) Learning classification with auxiliary probabilistic information. Proc. IEEE Internat. Conf. Data Mining ICDM (IEEE, Piscataway, NJ), 477–486.Google Scholar
• Papyan V (2019) The full spectrum of deepnet Hessians at scale: Dynamics with SGD training and sample size, Preprint, submitted June 3, https://arxiv.org/abs/1811.07062.Google Scholar
• Papyan V, Han XY, Donoho DL (2020) Prevalence of neural collapse during the terminal phase of deep learning training. Proc. Natl. Acad. Sci. USA 117(40):24652–24663.Google Scholar
• Pearson K (1901) On lines and planes of closest fit to systems of points in space. Philos. Mag. 2(11):559–572.Google Scholar
• Poggio T, Banburski A, Liao Q (2020) Theoretical issues in deep networks. Proc. Natl. Acad. Sci. USA 117(48):30039–30045.Google Scholar
• Polyak BT (1964) Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5):1–17.Google Scholar
• Rudin W (1976) Principles of Mathematical Analysis, 3rd ed., International Series in Pure and Applied Mathematics (McGraw Hill, New York).Google Scholar
• Sagun L, Evci U, Güney VU, Dauphin Y, Bottou L (2018) Empirical analysis of the Hessian of over-parametrized neural networks. Proc. Sixth Internat. Conf. Learn. Representations ICLR Workshop (ICLR, Appleton, WI), 1–14.Google Scholar
• Schmidt M, Le Roux N, Bach F (2017) Minimizing finite sums with the stochastic average gradient. Math. Program. Ser. A 162:83–112.Google Scholar
• Shalev-Shwartz S, Zhang T (2013) Stochastic dual coordinate ascent methods for regularized loss minimization. J. Mach. Learn. Res. 14:567–599.Google Scholar
• Singh SP, Bachmann G, Hofmann T (2021) Analytic insights into structure and rank of neural network Hessian maps. Proc. Adv. Neural Inform. Processing Systems 34 NeurIPS, 23914–23927.Google Scholar
• So AMC, Zhou Z (2017) Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity. Optim. Methods Softw. 32(4):963–992.Google Scholar
• Stein EM, Shakarchi R (2003a) Complex Analysis, Princeton Lectures in Analysis, vol. 2 (Princeton University Press, Princeton, NJ).Google Scholar
• Stein EM, Shakarchi R (2003b) Fourier Analysis: An Introduction, Princeton Lectures in Analysis, vol. 1 (Princeton University Press, Princeton, NJ).Google Scholar
• Stone CJ (1977) Consistent nonparametric regression. Ann. Statist. 5(4):595–620.Google Scholar
• Tsybakov AB (2009) Introduction to Nonparametric Estimation, Springer Series in Statistics (Springer, New York).Google Scholar
• Wang Y, Du SS, Balakrishnan S, Singh A (2018) Stochastic zeroth-order optimization in high dimensions. Proc. 21st Internat. Conf. Artificial Intelligence Statist. AISTATS (PMLR, New York), 1356–1365.Google Scholar
• Wasserman L (2019) Statistical methods for machine learning. Lecture Notes 36–708, Department of Statistics and Data Science, Carnegie Mellon University, Pittsburgh.Google Scholar
• Watson GS (1964) Smooth regression analysis. Sankhya Ser. A 26(4):359–372.Google Scholar
• Wu Y, Zhu X, Wu C, Wang A, Ge R (2021) Dissecting Hessian: Understanding common structure of Hessian in neural networks. Preprint, submitted June 16, https://arxiv.org/abs/2010.04261v5.Google Scholar
• Xu J (2018) Rates of convergence of spectral methods for graphon estimation. Proc. 35th Internat. Conf. Machine Learn. ICML (PMLR, New York), 5433–5442.Google Scholar
• Zhang ZG, Chan SC (2011) On kernel selection of multivariate local polynomial modelling and its application to image smoothing and reconstruction. J. Signal Processing Systems 64(3):361–374.Google Scholar
• Zhou S, Wolfe DA (2000) On derivative estimation in spline regression. Statist. Sinica 10(1):93–108.Google Scholar