Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron
Jul 24, 2023
Speakers
Jingfeng Wu
Speaker · 0 followers
Zixiang Chen
Speaker · 0 followers
Vladimir Braverman
Speaker · 0 followers
Quanquan Gu
Speaker · 5 followers
Sham M. Kakade
Speaker · 0 followers
About
This paper considers the problem of learning single ReLU neuron with squared loss (a.k.a., ReLU regression) in the overparameterized regime, where the input dimension can exceed the number of samples. We analyze a Perceptron-type algorithm called GLM-tron [Kakade et al. 2011], and provide its dimension-free risk upper bounds for high-dimensional ReLU regression in both well-specified and misspecified settings. Our risk bounds recover several existing results as special cases. Moreover, in the well-specified setting, we also provide an instance-wise matching risk lower bound for GLM-tron. Our upper and lower risk bounds provide a sharp characterization of the high-dimensional ReLU regression problems that can be learned via GLM-tron. On the other hand, we provide some negative results for stochastic gradient descent (SGD) for ReLU regression with symmetric Bernoulli data: if the model is well-specified, the excess risk of SGD is provably no better than that of GLM-tron ignoring constant factors, for each problem instance; and in the noiseless case, GLM-tron can achieve a small risk while SGD unavoidably suffers from a constant risk in expectation. These results together suggest that GLM-tron might be more preferable than SGD for high-dimensional ReLU regression.This paper considers the problem of learning single ReLU neuron with squared loss (a.k.a., ReLU regression) in the overparameterized regime, where the input dimension can exceed the number of samples. We analyze a Perceptron-type algorithm called GLM-tron [Kakade et al. 2011], and provide its dimension-free risk upper bounds for high-dimensional ReLU regression in both well-specified and misspecified settings. Our risk bounds recover several existing results as special cases. Moreover, in the we…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling
Watch later
Yunfan Li, …
ODS: Test-Time Adaptation in the Presence of Open-World Data Shift
Watch later
Zhi Zhou, …
Representation Driven Reinforcement Learning
Watch later
Ofir Nabati, …
Emergent deception and skepticism via theory of mind
Watch later
Lion Schulz, …
Collapsed Inference for Bayesian Deep Learning
Watch later
Zhe Zeng, …
Men Also Do Laundry: Multi-Attribute Bias Amplification
Watch later
Dora Zhao, …