Learning is Pruning
The strong lottery ticket hypothesis (LTH) postulates that any neural network can be approximated by simply pruning a sufficiently larger network of random weights.
Recent work establishes that the strong LTH is true if the random network to be pruned is a large poly factor wider than the target one. This polynomial over-parameterization is at odds with recent experimental research that achieves good approximation by pruning networks that are only a small factor wider than the target one. In this talk I will tell you how we close this gap and offer an exponential improvement to the over-parameterization requirement.
I will give a sketch of the proof that any target network can be approximated by pruning a random one that is only a logarithmic factor wider. This is possible by establishing a connection between pruning random ReLU networks and random instances of the weakly NP-hard SubsetSum problem.
Our work indicates the existence of a universal striking phenomenon: neural network training is equivalent to pruning slightly overparameterized networks of random weights.
About the Speaker
Dimitris Papailiopoulos is an Assistant Professor of Electrical and Computer Engineering and Computer Sciences (by courtesy) at the University of Wisconsin-Madison, a faculty fellow of the Grainger Institute for Engineering, and a faculty affiliate at the Wisconsin Institute for Discovery.
His research interests span machine learning, information theory, and distributed systems, with a current focus on communication-efficient training algorithms and coding-theoretic techniques that guarantee robustness during training and inference.
Between 2014 and 2016, Dimitris was a postdoctoral researcher at UC Berkeley and a member of the AMPLab. Dimitris earned his Ph.D. in ECE from UT Austin in 2014, under the supervision of Alex Dimakis. In 2007 he received his ECE Diploma and in 2009 his M.Sc. degree from the Technical University of Crete, in Greece.
Dimitris is a recipient of the NSF CAREER Award (2019), a Sony Faculty Innovation Award (2019), the Benjamin Smith Reynolds Award for Excellence in Teaching (2019), a joint IEEE ComSoc/ITSoc Best Paper Award (2020), and an IEEE Signal Processing Society, Young Author Best Paper Award (2015). In 2018, he co-founded MLSys, a new conference that targets research at the intersection of machine learning and systems. In 2018 and 2020 he was program co-chair for MLSys, and in 2019 he co-chaired the 3rd Midwest Machine Learning Symposium.