We consider active, semi-supervised learning in an offline transductive
setting. We show that a previously proposed error bound for active learning on
undirected weighted graphs can be generalized by replacing graph cut with an
arbitrary symmetric submodular function. Arbitrary non-symmetric submodular
functions can be used via symmetrization. Different choices of submodular
functions give different versions of the error bound that are appropriate for
different kinds of problems. Moreover, the bound is deterministic and holds for
adversarially chosen labels. We show exactly minimizing this error bound is
NP-complete. However, we also introduce for any submodular function an
associated active semi-supervised learning method that approximately minimizes
the corresponding error bound. We show that the error bound is tight in the
sense that there is no other bound of the same form which is better. Our
theoretical results are supported by experiments on real data.

我们在离线转导的半监督场景中考虑主动学习，通过替换图割（graph cut）为任意对称子模函数来泛化以前提出的主动学习的误差界。在对称化之后，可以使用任意非对称子模函数。不同的子模函数选择提供了适用于不同问题的误差限制的不同版本。此外，该限制是确定性的，并适用于对手所选择的标签。我们在任意子模函数中引入了一种相关的主动半监督学习方法，该方法可以近似最小化相应的误差限制。我们证明了误差界是紧致的，这意味着没有其他同形式的误差界比它更好。我们的理论结果得到了真实数据实验的支持。

使用子模函数的主动半监督学习

Active Semi-Supervised Learning using Submodular Functions

Suppose we would like to know all answers to a set of statistical queries C
on a data set up to small error, but we can only access the data itself using
statistical queries. A trivial solution is to exhaustively ask all queries in
C. Can we do any better?
+ We show that the number of statistical queries necessary and sufficient for
this task is---up to polynomial factors---equal to the agnostic learning
complexity of C in Kearns' statistical query (SQ) model. This gives a complete
answer to the question when running time is not a concern.
+ We then show that the problem can be solved efficiently (allowing arbitrary
error on a small fraction of queries) whenever the answers to C can be
described by a submodular function. This includes many natural concept classes,
such as graph cuts and Boolean disjunctions and conjunctions.
While interesting from a learning theoretic point of view, our main
applications are in privacy-preserving data analysis:
Here, our second result leads to the first algorithm that efficiently
releases differentially private answers to of all Boolean conjunctions with 1%
average error. This presents significant progress on a key open problem in
privacy-preserving data analysis.
Our first result on the other hand gives unconditional lower bounds on any
differentially private algorithm that admits a (potentially
non-privacy-preserving) implementation using only statistical queries. Not only
our algorithms, but also most known private algorithms can be implemented using
only statistical queries, and hence are constrained by these lower bounds. Our
result therefore isolates the complexity of agnostic learning in the SQ-model
as a new barrier in the design of differentially private algorithms.

本研究提出了两个结果，第一个结果说明了在 Kearns' SQ 模型中，对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度；第二个结果能高效地解决问题，只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用，使其得到了重大进展。

私密发布合取和统计查询障碍

Privately Releasing Conjunctions and the Statistical Query Barrier

We present an efficient algorithm to find non-empty minimizers of a symmetric
submodular function over any family of sets closed under inclusion. This for
example includes families defined by a cardinality constraint, a knapsack
constraint, a matroid independence constraint, or any combination of such
constraints. Our algorithm make $O(n^3)$ oracle calls to the submodular
function where $n$ is the cardinality of the ground set. In contrast, the
problem of minimizing a general submodular function under a cardinality
constraint is known to be inapproximable within $o(\sqrt{n/\log n})$ (Svitkina
and Fleischer [2008]).
The algorithm is similar to an algorithm of Nagamochi and Ibaraki [1998] to
find all nontrivial inclusionwise minimal minimizers of a symmetric submodular
function over a set of cardinality $n$ using $O(n^3)$ oracle calls. Their
procedure in turn is based on Queyranne's algorithm [1998] to minimize a
symmetric submodular

提出了一种高效算法，可在任何基于包含关闭的集合家族中找到对称次模函数的非空最小化器，包括基于基数约束、背包约束、拟阵独立约束或这些约束的任何组合。

具有遗传族群约束条件的对称次模函数最小化

Symmetric Submodular Function Minimization Under Hereditary Family  Constraints

Submodularity is a fundamental phenomenon in combinatorial optimization.
Submodular functions occur in a variety of combinatorial settings such as
coverage problems, cut problems, welfare maximization, and many more.
Therefore, a lot of work has been concerned with maximizing or minimizing a
submodular function, often subject to combinatorial constraints. Many of these
algorithmic results exhibit a common structure. Namely, the function is
extended to a continuous, usually non-linear, function on a convex domain.
Then, this relaxation is solved, and the fractional solution rounded to yield
an integral solution. Often, the continuous extension has a natural
interpretation in terms of distributions on subsets of the ground set. This
interpretation is often crucial to the results and their analysis. The purpose
of this survey is to highlight this connection between extensions,
distributions, relaxations, and optimization in the context of submodular
functions. We also present the first constant factor approximation algorithm
for minimizing symmetric submodular functions subject to a cardinality
constraint.

本文介绍了子模函数的连续松弛及其在优化问题中的应用，同时提出了一种基于对称子模函数的基数约束下，最小化函数的常系数逼近算法。