A core principle in statistical learning is that smoothness of target
functions allows to break the curse of dimensionality. However, learning a
smooth function through Taylor expansions requires enough samples close to one
another to get meaningful estimate of high-order derivatives, which seems hard
in machine learning problems where the ratio between number of data and input
dimension is relatively small. Should we really hope to break the curse of
dimensionality based on Taylor expansion estimation? What happens if Taylor
expansions are replaced by Fourier or wavelet expansions? By deriving a new
lower bound on the generalization error, this paper investigates the role of
constants and transitory regimes which are usually not depicted beyond
classical learning theory statements while that play a dominant role in
practice.

本文通过推导一种新的泛化误差下限，研究了通常在经典学习理论陈述之外通常未描述的常数和瞬态区域在实践中起到的支配作用，并探讨了基于 Fourier 或小波展开替代 Taylor 展开所带来的影响，进一步研究了统计学习中的核心原则 - 平滑性如何打破维数诅咒的问题。

利用平滑性需要多少样本？

How many samples are needed to leverage smoothness?

Optimization of real-world black-box functions defined over purely
categorical variables is an active area of research. In particular,
optimization and design of biological sequences with specific functional or
structural properties have a profound impact in medicine, materials science,
and biotechnology. Standalone search algorithms, such as simulated annealing
(SA) and Monte Carlo tree search (MCTS), are typically used for such
optimization problems. In order to improve the performance and sample
efficiency of such algorithms, we propose to use existing methods in
conjunction with a surrogate model for the black-box evaluations over purely
categorical variables. To this end, we present two different representations, a
group-theoretic Fourier expansion and an abridged one-hot encoded Boolean
Fourier expansion. To learn such representations, we consider two different
settings to update our surrogate model. First, we utilize an adversarial online
regression setting where Fourier characters of each representation are
considered as experts and their respective coefficients are updated via an
exponential weight update rule each time the black box is evaluated. Second, we
consider a Bayesian setting where queries are selected via Thompson sampling
and the posterior is updated via a sparse Bayesian regression model (over our
proposed representation) with a regularized horseshoe prior. Numerical
experiments over synthetic benchmarks as well as real-world RNA sequence
optimization and design problems demonstrate the representational power of the
proposed methods, which achieve competitive or superior performance compared to
state-of-the-art counterparts, while improving the computation cost and/or
sample efficiency, substantially.

该研究提出了一种基于代理模型和傅立叶展开的算法，用于优化纯分类型变量的黑盒函数，并在 RNA 序列优化和设计问题中取得了竞争性或优越性能，显著提高了计算成本和样本效率。

基于类别变量的黑盒优化的傅里叶表示

Fourier Representations for Black-Box Optimization over Categorical Variables

High-dimensional depth separation results for neural networks show that
certain functions can be efficiently approximated by two-hidden-layer networks
but not by one-hidden-layer ones in high-dimensions $d$. Existing results of
this type mainly focus on functions with an underlying radial or
one-dimensional structure, which are usually not encountered in practice. The
first contribution of this paper is to extend such results to a more general
class of functions, namely functions with piece-wise oscillatory structure, by
building on the proof strategy of (Eldan and Shamir, 2016). We complement these
results by showing that, if the domain radius and the rate of oscillation of
the objective function are constant, then approximation by one-hidden-layer
networks holds at a $\mathrm{poly}(d)$ rate for any fixed error threshold.
A common theme in the proofs of depth-separation results is the fact that
one-hidden-layer networks fail to approximate high-energy functions whose
Fourier representation is spread in the domain. On the other hand, existing
approximation results of a function by one-hidden-layer neural networks rely on
the function having a sparse Fourier representation. The choice of the domain
also represents a source of gaps between upper and lower approximation bounds.
Focusing on a fixed approximation domain, namely the sphere $\mathbb{S}^{d-1}$
in dimension $d$, we provide a characterisation of both functions which are
efficiently approximable by one-hidden-layer networks and of functions which
are provably not, in terms of their Fourier expansion.

本文通过对深度分离结果的研究，在高维情况下，展示了某些函数可以通过两层神经网络高效近似，但是无法通过单层网络近似，在解决常见的一些函数中出现了限制，并提供了一些方法进行一层网络的高效近似。