Source-linked AI summary
Learning ReLUs via Gradient Descent
Mahdi Soltanolkotabi
TL;DR
The paper studies nonlinear data fitting with ReLUs, where the effectiveness of gradient-based local search remains poorly understood. It analyzes projected gradient descent with projection onto a constraint set and proves linear convergence to the original weight vector, including for nonconvex regularizers, while noting that its constants are unspecified.
Problem
The paper studies fitting Rectified Linear Units to supervised-learning data, motivated by the unresolved reasons for gradient-based local search's empirical effectiveness.
Method
The approach uses projected gradient descent, initialized at zero, with Euclidean projection onto the constraint set K.
Results
Projected gradient descent provably learns the original weight vector without getting trapped in local optima, even with nonconvex objectives and regularizers.
Takeaways & Limitations
Linear convergence requires O(log(1/ε)) iterations and yields computational complexity O(nd log(1/ε)), optimal in its dependence on matrix dimensions.
Takeaways & Limitations
The convergence characterization uses unspecified constants, preventing a more accurate characterization.
Abstract
from arXiv · showhide
In this paper we study the problem of learning Rectified Linear Units (ReLUs) which are functions of the form $max(0,<w,x>)$ with $w$ denoting the weight vector. We study this problem in the high-dimensional regime where the number of observations are fewer than the dimension of the weight vector. We assume that the weight vector belongs to some closed set (convex or nonconvex) which captures known side-information about its structure. We focus on the realizable model where the inputs are chosen i.i.d.~from a Gaussian distribution and the labels are generated according to a planted weight vector. We show that projected gradient descent, when initialization at 0, converges at a linear rate to the planted model with a number of samples that is optimal up to numerical constants. Our results on the dynamics of convergence of these very shallow neural nets may provide some insights towards understanding the dynamics of deeper architectures.
1 Introduction
The paper studies high-dimensional ReLU fitting and asks why gradient-based local search can succeed despite nonconvex loss and regularization. It frames convergence, sample complexity, prior knowledge, regularization, and iteration count as central questions.
- 1 Introduction: The paper fits Rectified Linear Units, functions φ_w:R^d→R, to supervised-learning data consisting of feature–output pairs.ReLUs are the nonlinear models studied throughout the paper.
- 1 Introduction: Least-squares minimization provides a natural objective for fitting ReLUs to data, with regularization encoding prior information about the weight vector.The regularized formulation combines data misfit with structural information about the weights.
- 1 Introduction: Gradient and stochastic-gradient local search methods are widely effective empirically, but the reasons for their success on nonlinear data-fitting problems remain mysterious.The paper motivates theory for this empirical phenomenon.
- 1 Introduction: For ReLU fitting, both the loss and regularizer may be nonconvex, making convergence of gradient descent and escape from local optima or saddle points unclear.The paper also asks how sample requirements depend on prior knowledge and regularizer choice, and how many iterations accurate recovery requires.
2 Precise measures for statistical resources
The paper measures how well a regularizer captures a planted weight vector through its descent cone and Gaussian width. These quantities define a minimal sample function tied to structured recovery requirements.
- 2 Precise measures for statistical resources: For approximately sparse weights, an ℓ1 regularizer is described as superior to an ℓ2 regularizer because it better captures the available prior knowledge.Sample requirements depend on how well the regularizer captures the weight structure.
- 2 Precise measures for statistical resources: The descent cone contains directions along which the regularizer can descend from the planted weight vector, and its size reflects regularizer suitability.A smaller descent cone indicates that the regularizer better captures the properties of the unknown weight vector.
- 2 Precise measures for statistical resources: Gaussian width quantifies the size of the descent cone using an expectation over a standard Gaussian vector.The paper uses this geometric quantity to quantify the regularizer’s ability to capture structure.
- 2 Precise measures for statistical resources: The minimal number of samples is defined from the descent cone and regularizer at the unknown weight vector.The notation n0=M(R,w*) abbreviates this minimal sample function.
- 2 Precise measures for statistical resources: For convex regularizers, n0 is exactly the minimum sample count for high-probability recovery from linear measurements.The paper states this characterization for the corresponding structured signal-recovery problem.
3 Theoretical results for learning ReLUs
The paper analyzes projected gradient descent for fitting ReLUs under potentially nonconvex regularization, Gaussian inputs, and high-dimensional realizable data. It shows convergence from zero initialization at a linear rate with near-minimal sample requirements, despite nonconvexity.
- Projected gradient descent: The loss is differentiable except at isolated points, so generalized gradients define updates at nondifferentiable locations.This permits projected gradient descent despite the loss function's nondifferentiability.
- Projected gradient descent: Projected gradient descent uses updates wτ+1 = PK(wτ − µτ∇L(wτ)), where K constrains the regularizer and PK is Euclidean projection.The step size is µτ, and K = {w ∈ R^d: R(w) ≤ R} encodes prior information about the weight vector.
- Theorem 3.1: Theorem 3.1 assumes arbitrary w*, a proper convex or nonconvex regularizer, and i.i.d. Gaussian feature vectors with planted labels.The method starts from w0 = 0, uses K = {w: R(w) ≤ R(w*)}, unit learning parameters, and a sample lower bound n0 = M(R,w*).
- Theorem 3.1: With a near-minimal number of samples, projected gradient descent learns w* without becoming trapped in local optima, even when both objective and regularizer are nonconvex.The result holds with high probability under the theorem's assumptions.
- Convergence and complexity: Linear convergence requires O(log(1/ε)) iterations to reach relative error ε, with overall complexity O(ndlog(1/ε)).For dense feature matrices, this dependence is optimal because verifying a good solution already requires O(nd) time.
4 Discussions and prior art
The discussion contrasts the paper's Gaussian, high-dimensional realizable ReLU setting with prior methods that use broader distributions or models but different assumptions and guarantees. Direct comparisons are therefore limited.
- Single Index Models: Single Index Model methods learn a nondecreasing Lipschitz link and weight vector, and the Isotron can in principle fit ReLUs.These methods use more general distributions and models but impose boundedness assumptions on features, outputs, and weights.
- Single Index Models: Unlike the paper's setting, Isotron results do not apply when observations are significantly fewer than parameters.In the realizable case, the cited Isotron result requires O(1/ε) iterations for ε objective error, whereas this paper reports log(1/ε) iterations for relative parameter error.
- Prior ReLU results: Prior ReLU results permit learning under very general bounded distributions but require poly(1/ε) time for accuracy ε.The paper instead reports log(1/ε) iterations for reliable parameter estimation, while noting that the settings differ.
5 Proofs
The proofs establish high-probability bounds for the projected-gradient-descent error by combining Gaussian concentration, cone lemmas, and term-by-term control of the loss gradient.
- 5.1 Preliminaries: The analysis uses concentration results for Gaussian processes and extensions of Gordon’s escape-through-the-mesh lemma.These preliminaries apply to cones that need not be convex and to Gaussian matrices with independent entries.
- 5.2 Convergence proof: The proof initializes projected gradient descent at w0 = 0 and analyzes its first iteration before establishing a general recurrence.The recurrence controls the distance between each iterate and the planted vector over a constrained error set.
- 5.2 Convergence proof: The loss-gradient analysis decomposes the error expression into four terms and bounds them using concentration inequalities and cone-based lemmas.The four bounds are combined to obtain a uniform high-probability inequality over directions in the descent cone and nearby feasible weights.
- 5.2 Convergence proof: Combining the uniform bounds yields the recurrence required for the theorem’s convergence result, with high probability over all relevant directions and nearby weights.The final combination uses the bounds from equations (5.15), (5.22), (5.26), and (5.28), with δ = 10^-4 and ϵ = 7/200.