High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks

References

• Alford S, Robinett R, Milechin L, Kepner J (2018) Pruned and structurally sparse neural networks. Preprint, submitted September 30, https://arxiv.org/abs/1810.00299.Google Scholar
• Allen-Zhu Z, Li Y, Liang Y (2019) Learning and generalization in overparameterized neural networks, going beyond two layers. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook), 6155–6166. https://proceedings.neurips.cc/paper/2019/file/62dad6e273d32235ae02b7d321578ee8-Paper.pdf.Google Scholar
• Barron AR, Klusowski JM (2018) Approximation and estimation for high-dimensional deep learning networks. Preprint, submitted September 30, https://arxiv.org/abs/1809.03090.Google Scholar
• Bartlett PL, Foster DJ, Telgarsky MJ (2017) Spectrally-normalized margin bounds for neural networks. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Inc., Red Hook, NY), 6240–6249. https://proceedings.neurips.cc/paper/2017/file/b22b257ad0519d4500539da3c8bcf4dd-Paper.pdf.Google Scholar
• Bartlett P, Jordan M, McAuliffe J (2006) Convexity, classification, and risk bounds. J. Amer. Statist. Assoc. 101(473):138–156.Crossref, Google Scholar
• Belloni A, Chernozhukov V (2011) ℓ1-penalized quantile regression in high-dimensional sparse models. Ann. Statist. 39(1):82–130.Crossref, Google Scholar
• Bian W, Chen X, Ye Y (2015) Complexity analysis of interior point algorithms for non-lipschitz and non-convex minimization. Math. Programming Ser. A 149(1-2):301–327.Crossref, Google Scholar
• Bickel P, Ritov Y, Tsybakov A (2009) Simultaneous analysis of lasso and dantzig selector. Ann. Statist. 37(4):1705.Crossref, Google Scholar
• Brutzkus A, Globerson A, Malach E, Shalev-Shwartz S (2017) SGD learns over-parameterized networks that provably generalize on linearly separable data. Preprint, submitted October 27, https://arxiv.org/abs/1710.10174.Google Scholar
• Bühlmann P, van de Geer S (2011) Statistics for High-Dimensional Data: Methods Theory and Applications (Springer Science & Business Media, New York).Crossref, Google Scholar
• Candes E (2006) Modern statistical estimation via oracle inequalities. Acta Numerics 15:257–325.Crossref, Google Scholar
• Candes E, Tao T (2007) The dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. 35(6):2313–2351.Crossref, Google Scholar
• Cao Y, Gu Q (2019) Generalization bounds of stochastic gradient descent for wide and deep neural networks. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook), 10835–10845. https://proceedings.neurips.cc/paper/2019/file/cf9dc5e4e194fc21f397b4cac9cc3ae9-Paper.pdf.Google Scholar
• Cao Y, Gu Q (2020) Generalization error bounds of gradient descent for learning over-parameterized deep relu networks. Proc. AAAI Conf. Artificial Intelligence 34(4):3349–3356. https://ojs.aaai.org//index.php/AAAI/article/view/5736.Crossref, Google Scholar
• Chen X, Xu F, Ye Y (2010) Lower bound theory of nonzero entries in solutions of 2-p minimization. SIAM J. Sci. Comput. 32(5):2832–2852.Crossref, Google Scholar
• Clémençon S, Lugosi G, Vayatis N (2008) Ranking and empirical minimization of u-statistics. Ann. Statist. 36(2):844–874.Crossref, Google Scholar
• Daniely A (2017) Sgd learns the conjugate kernel class of the network. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Inc., Red Hook, NY), 2422–2430. https://proceedings.neurips.cc/paper/2017/file/489d0396e6826eb0c1e611d82ca8b215-Paper.pdf.Google Scholar
• Dettmers T, Zettlemoyer L (2019) Sparse networks from scratch: Faster training without losing performance. Preprint, submitted July 10, https://arxiv.org/abs/1907.04840.Google Scholar
• DeVore RA, Howard R, Micchelli C (1989) Optimal nonlinear approximation. Manuscripta Math. 63(4):469–478.Crossref, Google Scholar
• DeVries T, Taylor GW (2017) Improved regularization of convolutional neural networks with cutout. Preprint, submitted August 15, https://arxiv.org/abs/1708.04552.Google Scholar
• Du S, Lee J, Li H, Wang L, Zhai X (2019) Gradient descent finds global minima of deep neural networks. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learning, Proceedings of Machine Learning Research Series, vol. 97 (PMLR), 1675–1685. https://proceedings.mlr.press/v97/du19c.html.Google Scholar
• Fan J, Li R (2001) Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. 96(456):1348–1360.Crossref, Google Scholar
• Fan J, Lv J (2011) Non-concave penalty likelihood with np-dimensionality. IEEE Trans. Inform. Theory 57(8):5467–5484.Crossref, Google Scholar
• Fan J, Xue L, Zou H (2014) Strong oracle optimality of folded concave penalized estimation. Annals Statist. 42(3):819.Crossref, Google Scholar
• Frank L, Friedman J (1993) A statistical view of some chemometrics regression tools. Technometrics 35(2):109–135.Crossref, Google Scholar
• Gastaldi X (2017) Shake-shake regularization. Preprint, submitted May 21, https://arxiv.org/abs/1705.07485.Google Scholar
• Ghaoui LE, Viallon V, Rabbani T (2010) Safe feature elimination for the lasso and sparse supervised learning problems. Preprint, submitted September 21, https://arxiv.org/abs/1009.4219.Google Scholar
• Glorot X, Bordes A, Bengio Y (2011) Deep sparse rectifier neural networks. Gordon G, Dunson D, Dudík M, eds. Proc. 14th Internat. Conf. on Artificial Intelligence and Statist., Proceedings of Machine Learning Research Series, vol. 15 (PMLR), 315–323. https://proceedings.mlr.press/v15/glorot11a.html.Google Scholar
• Haeffele B, Vidal R (2017) Global optimality in neural network training. Proc. IEEE Conf. on Computer Vision and Pattern Recognition (IEEE), 7331–7339.Google Scholar
• Haeser G, Liu H, Ye Y (2019) Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary. Math. Programming Ser. A 178(1):263–299.Crossref, Google Scholar
• Han S, Pool J, Tran J, Dally W (2015) Learning both weights and connections for efficient neural network. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Inc., Red Hook, NY), 1135–1143. https://proceedings.neurips.cc/paper/2015/file/ae0eb3eed39d2bcef4622b2499a05fe6-Paper.pdf.Google Scholar
• Hardt M, Recht B, Singer Y (2016) Train faster, generalize better: Stability of stochastic gradient descent. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research Series, vol. 48 (PMLR), 1225–1234. https://proceedings.mlr.press/v48/hardt16.html.Google Scholar
• Harris E, Marcu A, Painter M, Niranjan M, Prügel-Bennett A, Hare J (2020) Fmix: Enhancing mixed sample data augmentation. Preprint, submitted February 7, https://arxiv.org/abs/2002.12047.Google Scholar
• He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. Proc. IEEE Conf. on Computer Vision and Pattern Recognition (IEEE), 770–778.Google Scholar
• Huang G, Sun Y, Liu Z, Sedra D, Weinberger KQ (2016) Deep networks with stochastic depth. Leibe B, Matas J, Sebe N, Welling M, eds. Computer Vision – ECCV 2016. Lecture Notes in Computer Science, vol. 9908 (Springer, Cham, Switzerland), 646–661. https://doi.org/10.1007/978-3-319-46493-0_39.Google Scholar
• Jakubovitz D, Giryes R, Rodrigues MR (2019) Generalization error in deep learning. Compressed Sensing and Its Applications (Springer, Berlin), 153–193.Crossref, Google Scholar
• Koltchinskii V (2010) Rademacher complexities and bounding the excess risk in active learning. J. Machine Learn. Res. 11:2457–2485.Google Scholar
• Krizhevsky A (2009) Learning multiple layers of features from tiny images. Accessed May 1, 2021, https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf.Google Scholar
• LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436–444.Crossref, Google Scholar
• LeCun Y, Cortes C, Burges C (2013) The mnist database of handwritten digits. Accessed May 1, 2021, http://yann.lecun.com/exdb/mnist/.Google Scholar
• LeCun Y, Jackel L, Bottou L, Brunot A, Cortes C, Denker J, Drucker H (1995) Comparison of learning algorithms for handwritten digit recognition. Fogelman F, Gallinari P, eds. Proc. Internat. Conf. on Artificial Neural Networks, vol. 60 (EC2 & Cie., Paris, France), 53–60.Google Scholar
• Li W (2019) Cifar-zoo: Pytorch implementation of cnns for cifar data set. Accessed May 1, 2021, https://github.com/BIGBALLON/CIFAR-ZOO.Google Scholar
• Li Y, Liang Y (2018) Learning overparameterized neural networks via stochastic gradient descent on structured data. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY), 8157–8166. https://proceedings.neurips.cc/paper/2018/file/54fe976ba170c19ebae453679b362263-Paper.pdf.Google Scholar
• Li X, Lu J, Wang Z, Haupt J, Zhao T (2018) On tighter generalization bound for deep neural networks: CNNs, resNets, and beyond. Preprint, submitted June 13, https://arxiv.org/abs/1806.05159.Google Scholar
• Liang S, Sun R, Lee J, Srikant R (2018) Adding one neuron can eliminate all bad local minima. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY), 4350–4360. https://proceedings.neurips.cc/paper/2018/file/a012869311d64a44b5a0d567cd20de04-Paper.pdf.Google Scholar
• Liu H, Yao T, Li R, Ye Y (2017) Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theories on local solutions. Math. Programming Ser. A 166(1-2):207–240.Crossref, Google Scholar
• Liu H, Wang X, Yao T, Li R, Ye Y (2019) Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming. Math. Programming 178(1):69–108.Crossref, Google Scholar
• Loh P-L (2017) Statistical consistency and asymptotic normality for high-dimensional robust mestimators. Ann. Statist. 45(2):866–896.Crossref, Google Scholar
• Loh P-L, Wainwright M (2015) Regularized m estimators with nonconvexity: Statistical and algorithmic theory for local optima. J. Machine Learn. Res. 16:559–616.Google Scholar
• Louizos C, Welling M, Kingma DP (2017) Learning sparse neural networks through l0 regularization. Preprint, submitted December 4, https://arxiv.org/abs/1712.01312.Google Scholar
• Mhaskar HN (1996) Neural networks for optimal approximation of smooth and analytic functions. Neural Comput. 8(1):164–177.Crossref, Google Scholar
• Mhaskar H, Poggio T (2016) Deep vs. shallow networks: An approximation theory perspective. Anal. Appl. 14(6):829–848.Google Scholar
• Ndiaye E, Fercoq O, Gramfort A, Salmon J (2017) Gap safe screening rules for sparsity enforcing penalties. J. Machine Learn. Res. 18(1):4671–4703.Google Scholar
• Negahban SN, Ravikumar P, Wainwright MJ, Yu B, et al. (2012) A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statist. Sci. 27(4):538–557.Crossref, Google Scholar
• Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Crossref, Google Scholar
• Nesterov Y, Polyak BT (2006) Cubic regularization of newton method and its global performance. Math. Programming 108(1):177–205.Crossref, Google Scholar
• Neyshabur B, Tomioka R, Srebro N (2015) Norm-based capacity control in neural networks. Grünwald P, Hazan E, Kale S, eds. Proc. 28th Conf. Learn. Theory, Proceedings of Machine Learning Research Series, vol. 40 (PMLR), 1376–1401. https://proceedings.mlr.press/v40/Neyshabur15.html.Google Scholar
• Nøkland A, Eidnes LH (2019) Training neural networks with local error signals. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research Series, vol. 97 (PMLR), 4839–4850. https://proceedings.mlr.press/v97/nokland19a.html.Google Scholar
• Owen A (2007) A robust hybrid of lasso and ridge regression. Contempory Math. 443(7):59–72.Crossref, Google Scholar
• Paszke A, Gross S, Chintala S, Chanan G, Yang E, DeVito Z, Lin Z, et al. (2017) Automatic differentiation in pytorch. Accessed May 1, 2021, https://openreview.net/forum?id=BJJsrmfCZ.Google Scholar
• Peng B, Wang L, Wu Y (2016) An error bound for l1-norm support vector machine coefficients in ultra-high dimension. J. Machine Learn. Res. 17(1):8279–8304.Google Scholar
• Raskutti G, Wainwright MJ, Yu B (2011) Minimax rates of estimation for high-dimensional linear regression over ℓq-balls. IEEE Trans. Inform. Theory 57(10):6976–6994.Crossref, Google Scholar
• Scardapane S, Comminiello D, Hussain A, Uncini A (2017) Group sparse regularization for deep neural networks. Neurocomput. 241:81–89.Crossref, Google Scholar
• Schmidhuber J (2015) Deep learning in neural networks: An overview. Neural Networks 61:85–117.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Shen X, Pan W, Zhu Y, Zhou H (2013) On constrained and regularized high-dimensional regression. Ann. Institute Statist. Math. 65(5):807–832.Crossref, Google Scholar
• Simonyan K, Zisserman A (2014) Very deep convolutional networks for large-scale image recognition. Preprint, submitted September 4, 2017, https://arxiv.org/abs/1409.1556.Google Scholar
• Srivastava N, Hinton G, Krizhevsky A, Sutskever I, Salakhutdinov R (2014) Dropout: A simple way to prevent neural networks from overfitting. J. Machine Learn. Res. 15(1):1929–1958.Google Scholar
• Sun R (2019) Optimization for deep learning: theory and algorithms. Preprint, submitted December 19, https://arxiv.org/abs/1912.08957.Google Scholar
• Tibshirani R (2011) Regression shrinkage and selection via the lasso: A retrospective. J. Roy. Statist. Soc. Ser. B Statist. Methodology 73(3):273–282.Crossref, Google Scholar
• van de Geer SA, Bühlmann P (2009) On the conditions used to prove oracle results for the lasso. Electronic J. Statist. 3:1360–1392.Crossref, Google Scholar
• Vershynin R (2012) Introduction to the non-asymptotic analysis of random matrices. Compressed Sensing, Theory and Applications (Cambridge University Press, Cambridge, UK), 210–268.Crossref, Google Scholar
• Wan L, Zeiler M, Zhang S, Le Cun Y, Fergus R (2013) Regularization of neural networks using dropconnect. Proc. Internat. Conf. on Machine Learn., 1058–1066.Google Scholar
• Wang L (2013) The l1 penalized lad estimator for high dimensional linear regression. J. Multivariate Anal. 120:135–151.Crossref, Google Scholar
• Wang G, Giannakis G, Chen J (2019) Learning relu networks on linearly separable data: Algorithm, optimality, and generalization. IEEE Trans. Signal Processing 67(9):2357–2370.Crossref, Google Scholar
• Wang L, Kim Y, Li R (2013) Calibrating nonconvex penalized regression in ultra-high dimension. Ann. Statist. 41(5):2505–2536.Crossref, Google Scholar
• Wang Z, Liu H, Zhang T (2014) Optimal computational and statistical rates of convergence for sparse nonconvex learning problems. Ann. Statist. 42:2164–2201.Crossref, Google Scholar
• Wen W, Wu C, Wang Y, Chen Y, Li H (2016) Learning structured sparsity in deep neural networks. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 29 (Curran Associates, Inc., Red Hook), 2074–2082. https://proceedings.neurips.cc/paper/2016/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf.Google Scholar
• Yarotsky D (2017) Error bounds for approximations with deep relu networks. Neural Networks 94:103–114.Crossref, Google Scholar
• Ye Y (1992) On affine scaling algorithms for non-convex quadratic programming. Math. Programming 56:285–300.Crossref, Google Scholar
• Ye Y (1998) On the complexity of approximating a kkt point of quadratic programming. Math. Programming 80:195.Crossref, Google Scholar
• Zhang C (2010) Nearly unbiased variable selection under minimax concave penalty. Ann. Statist. 28:894–942.Google Scholar
• Zhang C, Zhang T (2012) A general theory of concave regularization for high dimensional sparse estimation problems. Statist. Sci. 27(4):576–593.Crossref, Google Scholar
• Zhang H, Ahn J, Lin X, Park C (2006) Gene selection using support vector machines with non-convex penalty. Bioinformatics 22(1):88–95.Crossref, Google Scholar
• Zhang H, Cisse M, Dauphin YN, Lopez-Paz D (2017) mixup: Beyond empirical risk minimization. Preprint, submitted October 25, https://arxiv.org/abs/1710.09412.Google Scholar
• Zhang X, Wu Y, Wang L, Li R (2016b) Variable selection for support vector machines in moderately high dimensions. J. Roy. Statist. Soc. Part B 78:1–53.Google Scholar
• Zhang X, Wu Y, Wang L, Li R (2016c) A consistent information criterion for support vector machines in diverging model spaces. J. Machine Learn. Res. 17(1):1–26.Google Scholar
• Zhang C, Bengio S, Hardt M, Recht B, Vinyals O (2021) Understanding Deep Learning (Still) Requires Rethinking Generalization, vol. 64 (Association for Computing Machinery, New York), 107–115. https://doi.org/10.1145/3446776.Google Scholar
• Zou H (2006) The adaptive lasso and its oracle properties. J. Amer. Statist. Assoc. 101(476):1418–1429.Crossref, Google Scholar
• Zou H, Li R (2008) One-step sparse estimation in non-concave penalized likelihood models. Ann. Statist. 36(4):1509.Google Scholar