What to Do When Your Discrete Optimization Is the Size of a Neural Network?
This work addresses scalability issues in discrete optimization for neural networks, which is important for researchers and practitioners in machine learning, though it is incremental as it compares existing approaches rather than introducing a new method.
The paper tackles the challenge of solving discrete optimization problems in neural networks, such as pruning and binary network training, by comparing continuation path (CP) and Monte Carlo (MC) methods, finding that CP methods generally outperform MC methods in terms of solution quality and efficiency across various experiments.
Oftentimes, machine learning applications using neural networks involve solving discrete optimization problems, such as in pruning, parameter-isolation-based continual learning and training of binary networks. Still, these discrete problems are combinatorial in nature and are also not amenable to gradient-based optimization. Additionally, classical approaches used in discrete settings do not scale well to large neural networks, forcing scientists and empiricists to rely on alternative methods. Among these, two main distinct sources of top-down information can be used to lead the model to good solutions: (1) extrapolating gradient information from points outside of the solution set (2) comparing evaluations between members of a subset of the valid solutions. We take continuation path (CP) methods to represent using purely the former and Monte Carlo (MC) methods to represent the latter, while also noting that some hybrid methods combine the two. The main goal of this work is to compare both approaches. For that purpose, we first overview the two classes while also discussing some of their drawbacks analytically. Then, on the experimental section, we compare their performance, starting with smaller microworld experiments, which allow more fine-grained control of problem variables, and gradually moving towards larger problems, including neural network regression and neural network pruning for image classification, where we additionally compare against magnitude-based pruning.