We consider the problem of black-box function optimization over the boolean
hypercube. Despite the vast literature on black-box function optimization over
continuous domains, not much attention has been paid to learning models for
optimization over combinatorial domains until recently. However, the
computational complexity of the recently devised algorithms are prohibitive
even for moderate numbers of variables; drawing one sample using the existing
algorithms is more expensive than a function evaluation for many black-box
functions of interest. To address this problem, we propose a computationally
efficient model learning algorithm based on multilinear polynomials and
exponential weight updates. In the proposed algorithm, we alternate between
simulated annealing with respect to the current polynomial representation and
updating the weights using monomial experts' advice. Numerical experiments on
various datasets in both unconstrained and sum-constrained boolean optimization
indicate the competitive performance of the proposed algorithm, while improving
the computational time up to several orders of magnitude compared to
state-of-the-art algorithms in the literature.

通过使用多线性多项式和指数权重更新，我们提出了一种基于模拟退火的计算有效模型学习算法，以优化布尔双立方体上的黑盒函数优化问题，并获得了比文献中现有算法快几个数量级的计算时间和具有竞争性的性能。

组合黑盒优化与专家建议

Combinatorial Black-Box Optimization with Expert Advice

A function defined on the Boolean hypercube is $k$-Fourier-sparse if it has
at most $k$ nonzero Fourier coefficients. For a function $f: \mathbb{F}_2^n
\rightarrow \mathbb{R}$ and parameters $k$ and $d$, we prove a strong upper
bound on the number of $k$-Fourier-sparse Boolean functions that disagree with
$f$ on at most $d$ inputs. Our bound implies that the number of uniform and
independent random samples needed for learning the class of $k$-Fourier-sparse
Boolean functions on $n$ variables exactly is at most $O(n \cdot k \log k)$.
As an application, we prove an upper bound on the query complexity of testing
Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic
factor and quadratically improves on a result due to Gur and Tamuz (Chicago J.
Theor. Comput. Sci., 2013).

该研究论文证明了具有至多 k 非零傅里叶系数的函数在布尔超立方体上的上限，证明了学习 k-Fourier-sparse 布尔函数类所需的随机样本数量上限，同时也得出了傅里叶稀疏函数的布尔性测试的查询复杂性的上界。

傅里叶稀疏布尔函数的列表译码大小

The List-Decoding Size of Fourier-Sparse Boolean Functions

We introduce a new model of membership query (MQ) learning, where the
learning algorithm is restricted to query points that are \emph{close} to
random examples drawn from the underlying distribution. The learning model is
intermediate between the PAC model (Valiant, 1984) and the PAC+MQ model (where
the queries are allowed to be arbitrary points).
Membership query algorithms are not popular among machine learning
practitioners. Apart from the obvious difficulty of adaptively querying
labelers, it has also been observed that querying \emph{unnatural} points leads
to increased noise from human labelers (Lang and Baum, 1992). This motivates
our study of learning algorithms that make queries that are close to examples
generated from the data distribution.
We restrict our attention to functions defined on the $n$-dimensional Boolean
hypercube and say that a membership query is local if its Hamming distance from
some example in the (random) training data is at most $O(\log(n))$. We show the
following results in this model:
(i) The class of sparse polynomials (with coefficients in R) over $\{0,1\}^n$
is polynomial time learnable under a large class of \emph{locally smooth}
distributions using $O(\log(n))$-local queries. This class also includes the
class of $O(\log(n))$-depth decision trees.
(ii) The class of polynomial-sized decision trees is polynomial time
learnable under product distributions using $O(\log(n))$-local queries.
(iii) The class of polynomial size DNF formulas is learnable under the
uniform distribution using $O(\log(n))$-local queries in time
$n^{O(\log(\log(n)))}$.
(iv) In addition we prove a number of results relating the proposed model to
the traditional PAC model and the PAC+MQ model.

本文提出了一种新的分布学习模型，即在分布数据的随机样例附近进行局部查询来学习，并证明在该模型下，一些多项式和决策树相关的问题可以通过局部查询在多项式时间内进行学习。