We propose to focus on the problem of discovering neural network
architectures efficient in terms of both prediction quality and cost. For
instance, our approach is able to solve the following tasks: learn a neural
network able to predict well in less than 100 milliseconds or learn an
efficient model that fits in a 50 Mb memory. Our contribution is a novel family
of models called Budgeted Super Networks (BSN). They are learned using gradient
descent techniques applied on a budgeted learning objective function which
integrates a maximum authorized cost, while making no assumption on the nature
of this cost. We present a set of experiments on computer vision problems and
analyze the ability of our technique to deal with three different costs: the
computation cost, the memory consumption cost and a distributed computation
cost. We particularly show that our model can discover neural network
architectures that have a better accuracy than the ResNet and Convolutional
Neural Fabrics architectures on CIFAR-10 and CIFAR-100, at a lower cost.

本文提出了一种名为 BSN 的新型神经网络，采用基于预算学习的梯度下降技术，在不假设成本性质的条件下，以最大允许成本作为目标函数，解决了神经网络预测效率和成本之间的平衡问题，并通过对计算成本、内存消耗成本和分布式计算成本的三种代价的处理，实现了优于 ResNet 和 Convolutional Neural Fabrics 的结构发现与学习能力。

具有预算的超级网络的时间 / 内存高效深度架构学习

Learning Time/Memory-Efficient Deep Architectures with Budgeted Super  Networks

In the stochastic knapsack problem, we are given a knapsack of size B, and a
set of jobs whose sizes and rewards are drawn from a known probability
distribution. However, we know the actual size and reward only when the job
completes. How should we schedule jobs to maximize the expected total reward?
We know O(1)-approximations when we assume that (i) rewards and sizes are
independent random variables, and (ii) we cannot prematurely cancel jobs. What
can we say when either or both of these assumptions are changed?
The stochastic knapsack problem is of interest in its own right, but
techniques developed for it are applicable to other stochastic packing
problems. Indeed, ideas for this problem have been useful for budgeted learning
problems, where one is given several arms which evolve in a specified
stochastic fashion with each pull, and the goal is to pull the arms a total of
B times to maximize the reward obtained. Much recent work on this problem focus
on the case when the evolution of the arms follows a martingale, i.e., when the
expected reward from the future is the same as the reward at the current state.
What can we say when the rewards do not form a martingale?
In this paper, we give constant-factor approximation algorithms for the
stochastic knapsack problem with correlations and/or cancellations, and also
for budgeted learning problems where the martingale condition is not satisfied.
Indeed, we can show that previously proposed LP relaxations have large
integrality gaps. We propose new time-indexed LP relaxations, and convert the
fractional solutions into distributions over strategies, and then use the LP
values and the time ordering information from these strategies to devise a
randomized adaptive scheduling algorithm. We hope our LP formulation and
decomposition methods may provide a new way to address other correlated bandit
problems with more general contexts.

该论文研究了随机背包问题和预算学习问题中的 LP 松弛，并提出了一种新的基于随机化的适应性调度算法，为处理其他相关的赌博机问题提供了新的方法。