Pruning at Initialization - A Sketching Perspective.

Area of Science:

• Machine Learning
• Deep Learning Theory
• Neural Network Optimization

Background:

• The lottery ticket hypothesis (LTH) proposes that dense neural networks contain smaller subnetworks that, when trained in isolation, can reach similar accuracy.
• Pruning neural networks at initialization is a key area of research for efficient model design.

Purpose of the Study:

• To analyze the lottery ticket hypothesis (LTH) in the linear setting.
• To establish a theoretical connection between LTH and the sketching problem for efficient matrix multiplication.
• To develop improved algorithms for pruning neural networks at initialization.

Main Methods:

• Studying the lottery ticket hypothesis (LTH) in the linear model setting.
• Establishing an equivalence between finding a sparse mask at initialization and the matrix sketching problem.
• Bounding the approximation error of pruned linear models using initialization masks.
• Analyzing the data-independent nature of sparse network search.

Main Results:

• Finding a sparse mask at initialization is equivalent to matrix sketching.
• Theoretical justification for the data-independent search for sparse networks.
• A novel, generic improvement to existing pruning algorithms at initialization.
• Demonstrated benefits of the proposed improvement in data-independent scenarios.

Conclusions:

• The sketching perspective provides a powerful framework for understanding and analyzing the lottery ticket hypothesis (LTH).
• The proposed algorithmic improvement enhances pruning efficiency, particularly in data-independent settings.
• This work bridges theoretical insights from matrix sketching with practical neural network pruning strategies.