Given a collection of $n$ points in $\mathbb{R}^d$, the goal of the
$(k,z)$-clustering problem is to find a subset of $k$ "centers" that minimizes
the sum of the $z$-th powers of the Euclidean distance of each point to the
closest center. Special cases of the $(k,z)$-clustering problem include the
$k$-median and $k$-means problems. Our main result is a unified two-stage
importance sampling framework that constructs an $\varepsilon$-coreset for the
$(k,z)$-clustering problem. Compared to the results for $(k,z)$-clustering in
[Feldman and Langberg, STOC 2011], our framework saves a $\varepsilon^2 d$
factor in the coreset size. Compared to the results for $(k,z)$-clustering in
[Sohler and Woodruff, FOCS 2018], our framework saves a
$\operatorname{poly}(k)$ factor in the coreset size and avoids the
$\exp(k/\varepsilon)$ term in the construction time. Specifically, our coreset
for $k$-median ($z=1$) has size $\tilde{O}(\varepsilon^{-4} k)$ which, when
compared to the result in [Sohler and Woodruff, STOC 2018], saves a $k$ factor
in the coreset size. Our algorithmic results rely on a new dimensionality
reduction technique that connects two well-known shape fitting problems:
subspace approximation and clustering, and may be of independent interest. We
also provide a size lower bound of $\Omega\left(k\cdot \min \left\{2^{z/20},d
\right\}\right)$ for a $0.01$-coreset for $(k,z)$-clustering, which has a
linear dependence of size on $k$ and an exponential dependence on $z$ that
matches our algorithmic results.

本研究提出了一种统一的两阶段重要性采样框架，可构建 (k,z) 聚类问题的 ε-coreset。该算法依赖于将两个形状拟合问题连接起来的新的降维技术，绕过了之前的构造时间和核心集大小的限制，并提供了一个核心集的下界。

欧几里得空间聚类的核心集：重要性采样几乎是最佳的

Coresets for Clustering in Euclidean Spaces: Importance Sampling is  Nearly Optimal

Rendering bridges the gap between 2D vision and 3D scenes by simulating the
physical process of image formation. By inverting such renderer, one can think
of a learning approach to infer 3D information from 2D images. However,
standard graphics renderers involve a fundamental discretization step called
rasterization, which prevents the rendering process to be differentiable, hence
able to be learned. Unlike the state-of-the-art differentiable renderers, which
only approximate the rendering gradient in the back propagation, we propose a
truly differentiable rendering framework that is able to (1) directly render
colorized mesh using differentiable functions and (2) back-propagate efficient
supervision signals to mesh vertices and their attributes from various forms of
image representations, including silhouette, shading and color images. The key
to our framework is a novel formulation that views rendering as an aggregation
function that fuses the probabilistic contributions of all mesh triangles with
respect to the rendered pixels. Such formulation enables our framework to flow
gradients to the occluded and far-range vertices, which cannot be achieved by
the previous state-of-the-arts. We show that by using the proposed renderer,
one can achieve significant improvement in 3D unsupervised single-view
reconstruction both qualitatively and quantitatively. Experiments also
demonstrate that our approach is able to handle the challenging tasks in
image-based shape fitting, which remain nontrivial to existing differentiable
renderers.

本文提出了一种新的可微分渲染框架，可以使用可微分函数直接渲染彩色网格，并能够从各种图像表示形式中向网格顶点及其属性反馈高效监督信号，并通过实验，证明提出的渲染器可以在三维无监督单视图重建方面实现显著改善，并能够处理基于图像的形状拟合等具有挑战性的任务。

基于图像的三维推理差分渲染器

Soft Rasterizer: A Differentiable Renderer for Image-based 3D Reasoning

Given a set $F$ of $n$ positive functions over a ground set $X$, we consider
the problem of computing $x^*$ that minimizes the expression $\sum_{f\in
F}f(x)$, over $x\in X$. A typical application is \emph{shape fitting}, where we
wish to approximate a set $P$ of $n$ elements (say, points) by a shape $x$ from
a (possibly infinite) family $X$ of shapes. Here, each point $p\in P$
corresponds to a function $f$ such that $f(x)$ is the distance from $p$ to $x$,
and we seek a shape $x$ that minimizes the sum of distances from each point in
$P$. In the $k$-clustering variant, each $x\in X$ is a tuple of $k$ shapes, and
$f(x)$ is the distance from $p$ to its closest shape in $x$.
Our main result is a unified framework for constructing {\em coresets} and
{\em approximate clustering} for such general sets of functions. To achieve our
results, we forge a link between the classic and well defined notion of
$\varepsilon$-approximations from the theory of PAC Learning and VC dimension,
to the relatively new (and not so consistent) paradigm of coresets, which are
some kind of "compressed representation" of the input set $F$. Using
traditional techniques, a coreset usually implies an LTAS (linear time
approximation scheme) for the corresponding optimization problem, which can be
computed in parallel, via one pass over the data, and using only
polylogarithmic space (i.e, in the streaming model).
We show how to generalize the results of our framework for squared distances
(as in $k$-mean), distances to the $q$th power, and deterministic
constructions.

该研究考虑了针对一组正函数的最小化问题，给出了一个压缩表示法（coresets），用于形状拟合（shape fitting）和近似聚类（approxiate clustering）问题。他们将 epsilon-approximations 与 PAC Learning 和 VC dimension 相联系，并给出了一般函数集的 coresets 的线性时间近似计算方法。