Machine learning and data mining techniques are effective tools to classify
large amounts of data. But they tend to preserve any inherent bias in the data,
for example, with regards to gender or race. Removing such bias from data or
the learned representations is quite challenging. In this paper we study a
geometric problem which models a possible approach for bias removal. Our input
is a set of points P in Euclidean space R^d and each point is labeled with k
binary-valued properties. A priori we assume that it is "easy" to classify the
data according to each property. Our goal is to obstruct the classification
according to one property by a suitable projection to a lower-dimensional
Euclidean space R^m (m < d), while classification according to all other
properties remains easy.
What it means for classification to be easy depends on the classification
model used. We first consider classification by linear separability as employed
by support vector machines. We use Kirchberger's Theorem to show that, under
certain conditions, a simple projection to R^(d-1) suffices to eliminate the
linear separability of one of the properties whilst maintaining the linear
separability of the other properties. We also study the problem of maximizing
the linear "inseparability" of the chosen property. Second, we consider more
complex forms of separability and prove a connection between the number of
projections required to obstruct classification and the Helly-type properties
of such separabilities.

研究了一种减少数据偏差的方法，使用几何问题对学习到的表示进行建模，在低维空间中通过简单的投影即可消除数据的线性可分性，同时保持其他性质的线性可分性；同时，文中还探讨了更复杂的分离性质和分类障碍与其 Helly 属性的关系。

通过投影阻碍分类

Obstructing Classification via Projection

Computing Wasserstein barycenters is a fundamental geometric problem with
widespread applications in machine learning, statistics, and computer graphics.
However, it is unknown whether Wasserstein barycenters can be computed in
polynomial time, either exactly or to high precision (i.e., with
$\textrm{polylog}(1/\varepsilon)$ runtime dependence). This paper answers these
questions in the affirmative for any fixed dimension. Our approach is to solve
an exponential-size linear programming formulation by efficiently implementing
the corresponding separation oracle using techniques from computational
geometry.

使用计算几何技术有效地实现对应的分离神器来解决指数大小的线性规划问题，为任何固定维度的 Wasserstein barycenters 问题提供确定或高精确度计算的多项式时间算法。

Wasserstein 重心可以在固定维度的多项式时间内计算

Wasserstein barycenters can be computed in polynomial time in fixed  dimension

In the Sparse Linear Regression (SLR) problem, given a $d \times n$ matrix
$M$ and a $d$-dimensional query $q$, the goal is to compute a $k$-sparse
$n$-dimensional vector $\tau$ such that the error $||M \tau-q||$ is minimized.
This problem is equivalent to the following geometric problem: given a set $P$
of $n$ points and a query point $q$ in $d$ dimensions, find the closest
$k$-dimensional subspace to $q$, that is spanned by a subset of $k$ points in
$P$. In this paper, we present data-structures/algorithms and conditional lower
bounds for several variants of this problem (such as finding the closest
induced $k$ dimensional flat/simplex instead of a subspace).
In particular, we present approximation algorithms for the online variants of
the above problems with query time $\tilde O(n^{k-1})$, which are of interest
in the "low sparsity regime" where $k$ is small, e.g., $2$ or $3$. For $k=d$,
this matches, up to polylogarithmic factors, the lower bound that relies on the
affinely degenerate conjecture (i.e., deciding if $n$ points in $\mathbb{R}^d$
contains $d+1$ points contained in a hyperplane takes $\Omega(n^d)$ time).
Moreover, our algorithms involve formulating and solving several geometric
subproblems, which we believe to be of independent interest.

本文提出了用于解决初始情况下 $k$ 的大小小于等于 $3$ 的在线问题的近似算法，其中问题的目标是计算一个 $k$-sparse n 维向量，使误差最小化。假设给定一个 $d$ 维的点集，本文还会探讨如何在这个点集中找到最接近查询点 $q$ 的由 $k$ 个点张成的子空间的问题，以及该类问题的数据结构 / 算法和条件下界。