Random Sketching for Neural Networks With ReLU

Area of Science:

• Machine Learning
• Optimization Theory
• Applied Mathematics

Background:

• Neural network training involves complex, non-convex optimization, hindering high-quality estimator design.
• Rectified Linear Unit (ReLU) networks are widely used but computationally intensive to train.
• Existing optimization algorithms often lack perfect convergence guarantees.

Purpose of the Study:

• To develop an efficient training method for shallow ReLU nets.
• To transform the non-convex optimization problem in neural network training into a tractable linear least-squares problem.
• To analyze the theoretical and numerical efficiency of the proposed random sketching strategy.

Main Methods:

• Applied random sketching, a technique from kernel methods, to shallow ReLU nets.
• Utilized the localized approximation property of ReLU nets.
• Incorporated a dimensionality-leveraging scheme for efficient sketching.
• Performed theoretical analysis and numerical experiments to validate the approach.

Main Results:

• Demonstrated that random sketching transforms shallow ReLU net training into a linear least-squares problem.
• Provided theoretical guarantees showing the random sketching scheme is almost optimal in approximation and learning.
• Showcased significant reduction in computational burden for backpropagation algorithms.
• Confirmed that random sketching maintains the learning performance of shallow ReLU nets.

Conclusions:

• Random sketching is an effective strategy for training shallow ReLU nets, offering computational efficiency.
• The proposed method theoretically ensures near-optimal performance without compromising accuracy.
• This approach alleviates the computational challenges associated with training deep learning models.