We present the first nontrivial procedure for configuring heuristic
algorithms to maximize the utility provided to their end users while also
offering theoretical guarantees about performance. Existing procedures seek
configurations that minimize expected runtime. However, very recent theoretical
work argues that expected runtime minimization fails to capture algorithm
designers' preferences. Here we show that the utilitarian objective also
confers significant algorithmic benefits. Intuitively, this is because mean
runtime is dominated by extremely long runs even when they are incredibly rare;
indeed, even when an algorithm never gives rise to such long runs,
configuration procedures that provably minimize mean runtime must perform a
huge number of experiments to demonstrate this fact. In contrast, utility is
bounded and monotonically decreasing in runtime, allowing for meaningful
empirical bounds on a configuration's performance. This paper builds on this
idea to describe effective and theoretically sound configuration procedures. We
prove upper bounds on the runtime of these procedures that are similar to
theoretical lower bounds, while also demonstrating their performance
empirically.

我们提出了第一个非平凡的程序，用于配置启发式算法以最大化其为最终用户提供的效用，并同时提供关于性能的理论保证。我们展示了实用目标也带来了相当大的算法好处，在平均运行时间最小化无法捕捉到算法设计者的偏好的情况下表现出更好的性能。本文基于此思想描述了有效且具有理论基础的配置程序，并在理论下界类似的情况下证明了这些程序的运行时间上界，同时通过实验证明了它们的性能。

功利主义算法配置

Utilitarian Algorithm Configuration

We can compare the expressiveness of neural networks that use rectified
linear units (ReLUs) by the number of linear regions, which reflect the number
of pieces of the piecewise linear functions modeled by such networks. However,
enumerating these regions is prohibitive and the known analytical bounds are
identical for networks with same dimensions. In this work, we approximate the
number of linear regions through empirical bounds based on features of the
trained network and probabilistic inference. Our first contribution is a method
to sample the activation patterns defined by ReLUs using universal hash
functions. This method is based on a Mixed-Integer Linear Programming (MILP)
formulation of the network and an algorithm for probabilistic lower bounds of
MILP solution sets that we call MIPBound, which is considerably faster than
exact counting and reaches values in similar orders of magnitude. Our second
contribution is a tighter activation-based bound for the maximum number of
linear regions, which is particularly stronger in networks with narrow layers.
Combined, these bounds yield a fast proxy for the number of linear regions of a
deep neural network.

通过使用基于概率推断和特征的经验阈值来近似神经网络的线性区域数量，提供了一种可快速获得深度神经网络线性区域数量之近似值的方法。