While it is commonly observed in practice that pruning networks to a certain
level of sparsity can improve the quality of the features, a theoretical
explanation of this phenomenon remains elusive. In this work, we investigate
this by demonstrating that a broad class of statistical models can be optimally
learned using pruned neural networks trained with gradient descent, in
high-dimensions.
We consider learning both single-index and multi-index models of the form $y
= \sigma^*(\boldsymbol{V}^{\top} \boldsymbol{x}) + \epsilon$, where $\sigma^*$
is a degree-$p$ polynomial, and $\boldsymbol{V} \in \mathbbm{R}^{d \times r}$
with $r \ll d$, is the matrix containing relevant model directions. We assume
that $\boldsymbol{V}$ satisfies a certain $\ell_q$-sparsity condition for
matrices and show that pruning neural networks proportional to the sparsity
level of $\boldsymbol{V}$ improves their sample complexity compared to unpruned
networks. Furthermore, we establish Correlational Statistical Query (CSQ) lower
bounds in this setting, which take the sparsity level of $\boldsymbol{V}$ into
account. We show that if the sparsity level of $\boldsymbol{V}$ exceeds a
certain threshold, training pruned networks with a gradient descent algorithm
achieves the sample complexity suggested by the CSQ lower bound. In the same
scenario, however, our results imply that basis-independent methods such as
models trained via standard gradient descent initialized with rotationally
invariant random weights can provably achieve only suboptimal sample
complexity.

通过在高维度中训练剪枝神经网络并与梯度下降算法结合，我们研究了剪枝网络对广泛类统计模型学习的影响，发现剪枝神经网络在样本复杂度上相比未剪枝网络有提升，并引入了相关统计查询下界来支持这一观点。

高维空间中学习稀疏特征的最优修剪

Pruning is Optimal for Learning Sparse Features in High-Dimensions

One-shot neural architecture search allows joint learning of weights and
network architecture, reducing computational cost. We limit our search space to
the depth of residual networks and formulate an analytically tractable
variational objective that allows for obtaining an unbiased approximate
posterior over depths in one-shot. We propose a heuristic to prune our networks
based on this distribution. We compare our proposed method against manual
search over network depths on the MNIST, Fashion-MNIST, SVHN datasets. We find
that pruned networks do not incur a loss in predictive performance, obtaining
accuracies competitive with unpruned networks. Marginalising over depth allows
us to obtain better-calibrated test-time uncertainty estimates than regular
networks, in a single forward pass.

采用一次性神经架构搜索的方式，以削减计算成本，通过深度限定残差网络搜索空间，并提出基于分布的启发式算法进一步剪枝网络，验证预测性能不会受到影响，同时计算测试时不确定性估计比传统网络更加准确。