Set-functions appear in many areas of computer science and applied
mathematics, such as machine learning, computer vision, operations research or
electrical networks. Among these set-functions, submodular functions play an
important role, similar to convex functions on vector spaces. In this tutorial,
the theory of submodular functions is presented, in a self-contained way, with
all results shown from first principles. A good knowledge of convex analysis is
assumed.

介绍了子模函数的理论，包括在计算机科学和应用数学（如机器学习，计算机视觉，运筹学或电力网络）中发挥重要作用的集合函数，类似于向量空间上的凸函数。假定掌握了凸分析的基础知识。

带次模函数的凸分析与优化：一个教程

Convex Analysis and Optimization with Submodular Functions: a Tutorial

Sparse methods for supervised learning aim at finding good linear predictors
from as few variables as possible, i.e., with small cardinality of their
supports. This combinatorial selection problem is often turned into a convex
optimization problem by replacing the cardinality function by its convex
envelope (tightest convex lower bound), in this case the L1-norm. In this
paper, we investigate more general set-functions than the cardinality, that may
incorporate prior knowledge or structural constraints which are common in many
applications: namely, we show that for nondecreasing submodular set-functions,
the corresponding convex envelope can be obtained from its \lova extension, a
common tool in submodular analysis. This defines a family of polyhedral norms,
for which we provide generic algorithmic tools (subgradients and proximal
operators) and theoretical results (conditions for support recovery or
high-dimensional inference). By selecting specific submodular functions, we can
give a new interpretation to known norms, such as those based on
rank-statistics or grouped norms with potentially overlapping groups; we also
define new norms, in particular ones that can be used as non-factorial priors
for supervised learning.

本文研究了一种新的稀疏学习方法，提出了一种新的凸优化方法，利用一些子模函数的拓展得到了一类较通用的多面规范，并提供算法工具和理论结果。

子模函数引导的结构稀疏惩罚范数

Structured sparsity-inducing norms through submodular functions

Upper and lower bounds are obtained for the joint entropy of a collection of
random variables in terms of an arbitrary collection of subset joint entropies.
These inequalities generalize Shannon's chain rule for entropy as well as
inequalities of Han, Fujishige and Shearer. A duality between the upper and
lower bounds for joint entropy is developed. All of these results are shown to
be special cases of general, new results for submodular functions-- thus, the
inequalities presented constitute a richly structured class of Shannon-type
inequalities. The new inequalities are applied to obtain new results in
combinatorics, such as bounds on the number of independent sets in an arbitrary
graph and the number of zero-error source-channel codes, as well as new
determinantal inequalities in matrix theory. A new inequality for relative
entropies is also developed, along with interpretations in terms of hypothesis
testing. Finally, revealing connections of the results to literature in
economics, computer science, and physics are explored.

通过子集联合熵的任意集合，得到一组随机变量的联合熵的上下界，同时展现了这些不等式对拟模函数的一般新结果的特殊情况，进而得到解决组合学问题、矩阵理论、相对熵等方面的新不等式。

联合分布的信息不等式：解释与应用

Information Inequalities for Joint Distributions, with Interpretations  and Applications

We introduce several generalizations of classical computer science problems
obtained by replacing simpler objective functions with general submodular
functions. The new problems include submodular load balancing, which
generalizes load balancing or minimum-makespan scheduling, submodular sparsest
cut and submodular balanced cut, which generalize their respective graph cut
problems, as well as submodular function minimization with a cardinality lower
bound. We establish upper and lower bounds for the approximability of these
problems with a polynomial number of queries to a function-value oracle. The
approximation guarantees for most of our algorithms are of the order of
sqrt(n/ln n). We show that this is the inherent difficulty of the problems by
proving matching lower bounds. We also give an improved lower bound for the
problem of approximately learning a monotone submodular function. In addition,
we present an algorithm for approximately learning submodular functions with
special structure, whose guarantee is close to the lower bound. Although quite
restrictive, the class of functions with this structure includes the ones that
are used for lower bounds both by us and in previous work. This demonstrates
that if there are significantly stronger lower bounds for this problem, they
rely on more general submodular functions.

本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广，包括子模型负载平衡，子模型最稀疏切割和子模型平衡切割等，并建立了这些问题的近似界限。