On the Approximation Power of Two-Layer Networks of Random ReLUs

Abstract: This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching upper- and lower-bounds for L2-approximation in terms of the Lipschitz constant, the desired accuracy, and the dimension of the problem, as well as similar results in terms of Sobolev norms. Our positive results employ tools from harmonic analysis and ridgelet representation theory, while our lower-bounds are based on (robust versions of) dimensionality arguments.

19/08/2021

Machine Learning, Dimensionality Reduction, Explainable/Interpretable Machine Learning, Kernel Methods, Unsupervised Learning

13:48

12/07/2020

On the Approximation Power of Two-Layer Networks of Random ReLUs

Daniel Hsu, Clayton H Sanford, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis

Comments

Similar Papers

Improved Guarantees and a Multiple-descent Curve for Column Subset Selection and the Nystrom Method (Extended Abstract)

Michał Dereziński, Rajiv Khanna, Michael W. Mahoney

Keywords Abstract Paper

Machine Learning, Dimensionality Reduction, Explainable/Interpretable Machine Learning, Kernel Methods, Unsupervised Learning

Provable Smoothness Guarantees for Black-Box Variational Inference

Justin Domke

Keywords Abstract Paper

Probabilistic Inference - Approximate, Monte Carlo, and Spectral Methods

Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport

François-Pierre Paty, Alexandre d'Aspremont, Marco Cuturi

Keywords Abstract Paper

Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method

Michal Derezinski, Rajiv Khanna, Michael W Mahoney

Keywords Abstract Paper

Regularized Submodular Maximization at Scale

Ehsan Kazemi, shervin minaee, Moran Feldman, Amin Karbasi

Keywords Abstract Paper

Optimization, Combinatorial Optimization

The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities

Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

Keywords Abstract Paper

Gradient Descent Maximizes the Margin of Homogeneous Neural Networks

Kaifeng Lyu, Jian Li

Keywords Abstract Paper

margin, homogeneous, gradient descent

KALE Flow: A Relaxed KL Gradient Flow for Probabilities with Disjoint Support

Pierre Glaser, Michael Arbel, Arthur Gretton

Keywords Abstract Paper

generative model, kernel methods, optimal transport

Direct loss minimization for sparse gaussian processes

Yadi Wei, Rishit Sheth, Roni Khardon

Keywords Abstract Paper

Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction

Radu Alexandru Dragomir, Mathieu Even, Hadrien Hendrikx

Keywords Abstract Paper

Optimization, Convex Optimization

On the computability of continuous maximum entropy distributions with applications

Jonathan Leake, Nisheeth K. Vishnoi

Keywords Abstract Paper

Optimization, Entropy, Quantum entropy

Robustness Analysis of Non-Convex Stochastic Gradient Descent using Biased Expectations

Kevin Scaman, Cedric Malherbe

Keywords Abstract Paper

On Convergence of Gradient Expected Sarsa(λ)

Long Yang, Gang Zheng, Yu Zhang and Qian Zheng, Pengfei Li, Gang Pan

Keywords Abstract Paper

The Wasserstein Proximal Gradient Algorithm

Adil Salim, Anna Korba, Giulia Luise

Keywords Abstract Paper

Optimal Underdamped Langevin MCMC Method

Zhengmian Hu, Feihu Huang, Heng Huang

Keywords Abstract Paper

generative model

Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

Gergely Neu, Gintare Karolina Dziugiate, Mahdi Haghifam, Daniel M. Roy

Keywords Abstract Paper

The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation

Thibault Sejourne, Francois-Xavier Vialard, Gabriel Peyré

Keywords Abstract Paper

optimization, machine learning, domain adaptation, optimal transport

Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II

Yossi Arjevani, Michael Field

Keywords Abstract Paper

theory, deep learning, optimization

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

Keywords Abstract Paper

Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

Lénaïc Chizat, Pierre Roussillon, Flavien Léger and François-Xavier Vialard, Gabriel Peyré

Keywords Abstract Paper

Distributed Saddle-Point Problems Under Data Similarity

Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, Alexander Gasnikov

Keywords Abstract Paper

optimization

Calibrated adaptive probabilistic ODE solvers

Nathanael Bosch, Philipp Hennig, Filip Tronarp

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Long Yang, Gang Zheng, Yu Zhang and
Qian Zheng, Pengfei Li, Gang Pan

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Lénaïc Chizat, Pierre Roussillon, Flavien Léger and
François-Xavier Vialard, Gabriel Peyré

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Wenlong Mou, Chris Junchi Li, Martin Wainwright and
Peter Bartlett, Michael Jordan

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Christian Borgs, Jennifer Chayes, Tyler Helmuth and
Will Perkins, Prasad Tetali

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Erik Daxberger, Eric Nalisnick, James Allingham and
Javier Antorán, Jose Miguel Hernandez-Lobato

Keywords Paper

Keywords Paper

Keywords Paper