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.

本研究比较了使用纯粹外推梯度信息和比较有效解的两种方法，以解决离散优化问题在机器学习应用中的使用，首先概述了这两种方法及其缺点，然后通过实验证明了它们的性能差异。

当离散优化规模与神经网络一样大时该如何处理？

What to Do When Your Discrete Optimization Is the Size of a Neural  Network?

The traditional way of tackling discrete optimization problems is by using
local search on suitably defined cost or fitness landscapes. Such approaches
are however limited by the slowing down that occurs when local minima, that are
a feature of the typically rugged landscapes encountered, arrest the progress
of the search process. Another way of tackling optimization problems is by the
use of heuristic approximations to estimate a global cost minimum. Here we
present a combination of these two approaches by using cover-encoding maps
which map processes from a larger search space to subsets of the original
search space. The key idea is to construct cover-encoding maps with the help of
suitable heuristics that single out near-optimal solutions and result in
landscapes on the larger search space that no longer exhibit trapping local
minima. The processes that are typically employed involve some form of
coarse-graining, and we suggest here that they can be viewed as avatars of
renormalisation group transformations.

文章介绍了利用局部搜索和启发式逼近相结合的方法来解决离散优化问题，通过构建适当的启发式覆盖映射，实现从较大的搜索空间映射到原始搜索空间的子集，来避免困局性局部最小值的出现，并指出这种方法实际上可以被看做是重正化群变换的一种应用。