We examine the extent to which sublinear-sample property testing and
estimation applies to settings where samples are independently but not
identically distributed. Specifically, we consider the following distributional
property testing framework: Suppose there is a set of distributions over a
discrete support of size $k$, $\textbf{p}_1, \textbf{p}_2,\ldots,\textbf{p}_T$,
and we obtain $c$ independent draws from each distribution. Suppose the goal is
to learn or test a property of the average distribution,
$\textbf{p}_{\mathrm{avg}}$. This setup models a number of important practical
settings where the individual distributions correspond to heterogeneous
entities -- either individuals, chronologically distinct time periods,
spatially separated data sources, etc. From a learning standpoint, even with
$c=1$ samples from each distribution, $\Theta(k/\varepsilon^2)$ samples are
necessary and sufficient to learn $\textbf{p}_{\mathrm{avg}}$ to within error
$\varepsilon$ in TV distance. To test uniformity or identity -- distinguishing
the case that $\textbf{p}_{\mathrm{avg}}$ is equal to some reference
distribution, versus has $\ell_1$ distance at least $\varepsilon$ from the
reference distribution, we show that a linear number of samples in $k$ is
necessary given $c=1$ samples from each distribution. In contrast, for $c \ge
2$, we recover the usual sublinear sample testing of the i.i.d. setting: we
show that $O(\sqrt{k}/\varepsilon^2 + 1/\varepsilon^4)$ samples are sufficient,
matching the optimal sample complexity in the i.i.d. case in the regime where
$\varepsilon \ge k^{-1/4}$. Additionally, we show that in the $c=2$ case, there
is a constant $\rho > 0$ such that even in the linear regime with $\rho k$
samples, no tester that considers the multiset of samples (ignoring which
samples were drawn from the same $\textbf{p}_i$) can perform uniformity
testing.

在非独立同分布的样本情况下，研究子线性样本属性测试和估计在哪些情形适用；给定一组分布，考虑学习或测试平均分布的属性，在某些情况下需要 $\Theta (k/\varepsilon^2)$ 样本；对于均匀性或相似性的测试，给定 $c=1$ 个样本，需要线性数量级的 $k$ 样本；$c \geq 2$ 时，恢复了独立同分布的亚线性样本测试，需要 $O (\sqrt {k}/\varepsilon^2 + 1/\varepsilon^4)$ 样本，且在 $c=2$ 的情况下，即使是线性数量级的 $\rho k$ 样本，也不能进行均匀性测试。

非同分布样本的测试

Testing with Non-identically Distributed Samples

The labor market is a complex ecosystem comprising diverse, interconnected
entities, such as industries, occupations, skills, and firms. Due to the lack
of a systematic method to map these heterogeneous entities together, each
entity has been analyzed in isolation or only through pairwise relationships,
inhibiting comprehensive understanding of the whole ecosystem. Here, we
introduce $\textit{Labor Space}$, a vector-space embedding of heterogeneous
labor market entities, derived through applying a large language model with
fine-tuning. Labor Space exposes the complex relational fabric of various labor
market constituents, facilitating coherent integrative analysis of industries,
occupations, skills, and firms, while retaining type-specific clustering. We
demonstrate its unprecedented analytical capacities, including positioning
heterogeneous entities on an economic axes, such as
`Manufacturing--Healthcare'. Furthermore, by allowing vector arithmetic of
these entities, Labor Space enables the exploration of complex inter-unit
relations, and subsequently the estimation of the ramifications of economic
shocks on individual units and their ripple effect across the labor market. We
posit that Labor Space provides policymakers and business leaders with a
comprehensive unifying framework for labor market analysis and simulation,
fostering more nuanced and effective strategic decision-making.

通过应用大规模的语言模型和微调技术，我们引入了 “劳动空间”，这是一种异质劳动力市场实体的向量空间嵌入，揭示了各种劳动力市场构成部分的复杂关系网络，有助于行业、职业、技能和公司的综合分析，并保留了类型特定的聚类，为政策制定者和商业领导者提供了劳动力市场分析和模拟的全面统一框架。