For any subgroup $G$ of the symmetric group $\mathcal{S}_n$ on $n$ symbols,
we present results for the uniform $\mathcal{C}^k$ approximation of
$G$-invariant functions by $G$-invariant polynomials. For the case of totally
symmetric functions ($G = \mathcal{S}_n$), we show that this gives rise to the
sum-decomposition Deep Sets ansatz of Zaheer et al. (2018), where both the
inner and outer functions can be chosen to be smooth, and moreover, the inner
function can be chosen to be independent of the target function being
approximated. In particular, we show that the embedding dimension required is
independent of the regularity of the target function, the accuracy of the
desired approximation, as well as $k$. Next, we show that a similar procedure
allows us to obtain a uniform $\mathcal{C}^k$ approximation of antisymmetric
functions as a sum of $K$ terms, where each term is a product of a smooth
totally symmetric function and a smooth antisymmetric homogeneous polynomial of
degree at most $\binom{n}{2}$. We also provide upper and lower bounds on $K$
and show that $K$ is independent of the regularity of the target function, the
desired approximation accuracy, and $k$.

给定对称群 $S_n$ 的任何子群 $G$，我们研究了 $G$ 的不变函数对 $G$ 的不变多项式的均匀 $C^k$ 逼近，特别是对于完全对称函数的情况，我们表明这导致了 Zaheer 等人（2018）关于和分解 Deep Sets 的假设，其中内部和外部函数都可以选择为光滑函数，并且内部函数可以选择与所逼近的目标函数无关。

G - 不变和反对称函数的统一 C^k 逼近、嵌入维度和多项式表示

Uniform $\mathcal{C}^k$ Approximation of $G$-Invariant and Antisymmetric  Functions, Embedding Dimensions, and Polynomial Representations

We consider the problem of discovering subgroup $H$ of permutation group
$S_{n}$. Unlike the traditional $H$-invariant networks wherein $H$ is assumed
to be known, we present a method to discover the underlying subgroup, given
that it satisfies certain conditions. Our results show that one could discover
any subgroup of type $S_{k} (k \leq n)$ by learning an $S_{n}$-invariant
function and a linear transformation. We also prove similar results for cyclic
and dihedral subgroups. Finally, we provide a general theorem that can be
extended to discover other subgroups of $S_{n}$. We also demonstrate the
applicability of our results through numerical experiments on image-digit sum
and symmetric polynomial regression tasks.

我们考虑寻找置换群 S_n 的子群 H 的问题。我们提出了一种方法，可以在满足一定条件的情况下发现隐藏的子群 H。我们的结果表明通过学习一个 S_n 不变函数和一个线性变换可以发现任何类型为 S_k (k ≤ n) 的子群。我们还证明了循环子群和二面体子群的类似结果。最后，我们提供了一个可以扩展到发现 S_n 的其他子群的通用定理。我们还通过图像位数和对称多项式回归任务的数值实验验证了我们的结果的适用性。

置换子群的神经发现

Neural Discovery of Permutation Subgroups

The most prevalent notions of fairness in machine learning are statistical
definitions: they fix a small collection of pre-defined groups, and then ask
for parity of some statistic of the classifier across these groups. Constraints
of this form are susceptible to intentional or inadvertent "fairness
gerrymandering", in which a classifier appears to be fair on each individual
group, but badly violates the fairness constraint on one or more structured
subgroups defined over the protected attributes. We propose instead to demand
statistical notions of fairness across exponentially (or infinitely) many
subgroups, defined by a structured class of functions over the protected
attributes. This interpolates between statistical definitions of fairness and
recently proposed individual notions of fairness, but raises several
computational challenges. It is no longer clear how to audit a fixed classifier
to see if it satisfies such a strong definition of fairness. We prove that the
computational problem of auditing subgroup fairness for both equality of false
positive rates and statistical parity is equivalent to the problem of weak
agnostic learning, which means it is computationally hard in the worst case,
even for simple structured subclasses.
We then derive two algorithms that provably converge to the best fair
classifier, given access to oracles which can solve the agnostic learning
problem. The algorithms are based on a formulation of subgroup fairness as a
two-player zero-sum game between a Learner and an Auditor. Our first algorithm
provably converges in a polynomial number of steps. Our second algorithm enjoys
only provably asymptotic convergence, but has the merit of simplicity and
faster per-step computation. We implement the simpler algorithm using linear
regression as a heuristic oracle, and show that we can effectively both audit
and learn fair classifiers on real datasets.

在机器学习中，通过使用受保护的属性定义的结构化函数类来提议一种新的公平统计定义，从而语义上定义了指数级（或无限个）子组内的统计不变性，并证明了公平子组审核的计算问题与弱自适应学习问题等价，提出了两种算法，证明了这些算法在解决自治学习问题的情况下可以收敛，其中第二种方法具有简单和更快的步骤计算的优点。