学习与选择建模的交集是研究的积极研究领域，并在电子商务，信息检索和社会科学中的应用。在某些应用程序（例如推荐系统）中，统计学家主要有兴趣使用被动收集的离散选择数据，即，用户从一组项目中选择一项项目多个项目。在这种实用的考虑方面，我们提出了基于选择的Borda Count算法，作为顶级$ k $ - 重新发现的快速准确的排名算法，即正确识别所有顶级$ K $项目。我们表明，基于选择的Borda计数算法具有最佳的样本复杂性，适用于$ K $恢复在广泛的随机实用程序模型下。我们证明，在极限上，基于选择的Borda计数算法与常用的最大似然估计方法产生相同的顶部$ K $估计值，但是前者的速度和简单性在实践中带来了可观的优势。合成数据集和真实数据集的实验表明，计数算法在准确性方面与常用的排名算法具有竞争力，同时更快地数量级。

混合模型被广泛用于拟合复杂和多模式数据集。在本文中，我们研究了具有高维稀疏潜在参数矢量的混合物，并考虑了支持这些向量的恢复的问题。尽管对混合模型中的参数学习进行了充分研究，但稀疏性约束仍然相对尚未探索。参数向量的稀疏性是各种设置的自然约束，支持恢复是参数估计的主要步骤。我们为支持恢复提供有效的算法，该算法具有对数样品的复杂性依赖于潜在空间的维度。我们的算法非常笼统，即它们适用于1）许多不同规范分布的混合物，包括统一，泊松，拉普拉斯，高斯人等。2）在统一参数的不同假设下，线性回归和线性分类器与高斯协变量的混合物与高斯协变量的混合物。在大多数这些设置中，我们的结果是对问题的首先保证，而在其余部分中，我们的结果为现有作品提供了改进。

Bradley-terry-luce（BTL）模型是一种流行的统计方法，用于使用成对比较估算项目集合的全局排名。为了确保准确的排名，必须在$ \ ell _ {\ infty} $损失中获得模型参数的精确估计。该任务的难度取决于给定项目对成对比较图的拓扑。但是，除了很少有良好的情况外，例如完整和ERD \“ OS-r \'enyi比较图，对$ \ ell_中BTL模型参数的最大似然估计量mLE的性能鲜为人知。 {\ infty} $ - 在更通用的图形拓扑下的损失。在本文中，我们在$ \ ell _ {\ infty} $估计错误的btl mLE估计误差上得出了小说的一般上限，该错误明确取决于比较的代数连接性图，跨项目和样本复杂性的最大性能差距。我们证明，与使用不同的损失函数以及更受限制的假设和图形拓扑获得的已知结果相比，派生的界限性能很好，并且在某些情况下相比更为敏锐。我们将结果仔细比较我们的结果与我们的结果进行比较。 Yan等人（2012年），它在精神上最接近我们的工作。我们进一步提供了$ \ ell _ {\ infty} $下的最小值下限 - 错误几乎与一类足够常规的图形拓扑相匹配。最后。 ，我们St udy，我们的$ \ ell _ {\ infty} $的含义是高效（离线）锦标赛设计的界限。我们通过各种示例和模拟来说明和讨论我们的发现。

This paper concerns with statistical estimation and inference for the ranking problems based on pairwise comparisons with additional covariate information such as the attributes of the compared items. Despite extensive studies, few prior literatures investigate this problem under the more realistic setting where covariate information exists. To tackle this issue, we propose a novel model, Covariate-Assisted Ranking Estimation (CARE) model, that extends the well-known Bradley-Terry-Luce (BTL) model, by incorporating the covariate information. Specifically, instead of assuming every compared item has a fixed latent score $\{\theta_i^*\}_{i=1}^n$, we assume the underlying scores are given by $\{\alpha_i^*+{x}_i^\top\beta^*\}_{i=1}^n$, where $\alpha_i^*$ and ${x}_i^\top\beta^*$ represent latent baseline and covariate score of the $i$-th item, respectively. We impose natural identifiability conditions and derive the $\ell_{\infty}$- and $\ell_2$-optimal rates for the maximum likelihood estimator of $\{\alpha_i^*\}_{i=1}^{n}$ and $\beta^*$ under a sparse comparison graph, using a novel `leave-one-out' technique (Chen et al., 2019) . To conduct statistical inferences, we further derive asymptotic distributions for the MLE of $\{\alpha_i^*\}_{i=1}^n$ and $\beta^*$ with minimal sample complexity. This allows us to answer the question whether some covariates have any explanation power for latent scores and to threshold some sparse parameters to improve the ranking performance. We improve the approximation method used in (Gao et al., 2021) for the BLT model and generalize it to the CARE model. Moreover, we validate our theoretical results through large-scale numerical studies and an application to the mutual fund stock holding dataset.

在这项工作中，我们研究了鲁布利地学习Mallows模型的问题。我们给出了一种算法，即使其样本的常数分数是任意损坏的恒定分数，也可以准确估计中央排名。此外，我们的稳健性保证是无关的，因为我们的整体准确性不依赖于排名的替代品的数量。我们的工作可以被认为是从算法稳健统计到投票和信息聚集中的中央推理问题之一的视角的自然输注。具体而言，我们的投票规则是有效的可计算的，并且通过一大群勾结的选民无法改变其结果。

我们研究了基于消费者的决策积极学习非参数选择模型的问题。我们提出一个负面结果，表明这种选择模型可能无法识别。为了克服可识别性问题，我们介绍了选择模型的有向无环图（DAG）表示，从某种意义上说，该模型可以捕获有关选择模型的更多信息，从而可以从理论上识别信息。然后，我们考虑在主动学习环境中学习与此DAG表示的近似的问题。我们设计了一种有效的主动学习算法，以估计非参数选择模型的DAG表示，该模型在多项式时间内运行时，当随机均匀地绘制频繁排名。我们的算法通过主动和反复提供各种项目并观察所选项目来了解最受欢迎的频繁偏好项目的分布。我们表明，与相应的非活动学习估计算法相比，我们的算法可以更好地恢复有关消费者偏好的合成和公开数据集的一组频繁偏好。这证明了我们的算法和主动学习方法的价值。

我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法，用于辅助性Subgaussian分布。在这项工作中，我们开发了第一个有效的算法，用于强大的稀疏平均值估计，而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布，带有“认证有限”的$ t $ tum-矩和足够轻的尾巴，我们的算法达到了$ o（\ epsilon^{1-1/t}）$带有样品复杂性$的错误（\ epsilon^{1-1/t}） m =（k \ log（d））^{o（t）}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况，我们的算法达到了$ \ tilde o（\ epsilon）$的接近最佳错误，带有样品复杂性$ m = o（k^4 \ mathrm {polylog}（d）（d））/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

我们提出了改进的算法，并为身份测试$ n $维分布的问题提供了统计和计算下限。在身份测试问题中，我们将作为输入作为显式分发$ \ mu $，$ \ varepsilon> 0 $，并访问对隐藏分布$ \ pi $的采样甲骨文。目标是区分两个分布$ \ mu $和$ \ pi $是相同的还是至少$ \ varepsilon $ -far分开。当仅从隐藏分布$ \ pi $中访问完整样本时，众所周知，可能需要许多样本，因此以前的作品已经研究了身份测试，并额外访问了各种有条件采样牙齿。我们在这里考虑一个明显弱的条件采样甲骨文，称为坐标Oracle，并在此新模型中提供了身份测试问题的相当完整的计算和统计表征。我们证明，如果一个称为熵的分析属性为可见分布$ \ mu $保留，那么对于任何使用$ \ tilde {o}（n/\ tilde {o}），有一个有效的身份测试算法Varepsilon）$查询坐标Oracle。熵的近似张力是一种经典的工具，用于证明马尔可夫链的最佳混合时间边界用于高维分布，并且最近通过光谱独立性为许多分布族建立了最佳的混合时间。我们将算法结果与匹配的$ \ omega（n/\ varepsilon）$统计下键进行匹配的算法结果补充，以供坐标Oracle下的查询数量。我们还证明了一个计算相变：对于$ \ {+1，-1，-1 \}^n $以上的稀疏抗抗铁磁性模型，在熵失败的近似张力失败的状态下，除非RP = np，否则没有有效的身份测试算法。

在偏好学习环境中，每个参与者都会在显示的一组候选人中选择$ k $最喜欢的物品的有序列表。（对于每个参与者，该集合可能都不同。）我们确定了人口偏好及其（排名）选择行为的基于距离的排名模型。排名模型类似于曲棍球模型，但使用了称为“反向主要索引（RMJ）”的新距离函数。我们发现，尽管需要对所有排列进行汇总，但基于RMJ的排名分布聚合物将其纳入（排名）选择概率，并具有简单的闭合形式表达式。我们开发有效的方法来估计模型参数并使用真实数据展示其概括功率，尤其是在显示集合有限的情况下。

Rankings are widely collected in various real-life scenarios, leading to the leakage of personal information such as users' preferences on videos or news. To protect rankings, existing works mainly develop privacy protection on a single ranking within a set of ranking or pairwise comparisons of a ranking under the $\epsilon$-differential privacy. This paper proposes a novel notion called $\epsilon$-ranking differential privacy for protecting ranks. We establish the connection between the Mallows model (Mallows, 1957) and the proposed $\epsilon$-ranking differential privacy. This allows us to develop a multistage ranking algorithm to generate synthetic rankings while satisfying the developed $\epsilon$-ranking differential privacy. Theoretical results regarding the utility of synthetic rankings in the downstream tasks, including the inference attack and the personalized ranking tasks, are established. For the inference attack, we quantify how $\epsilon$ affects the estimation of the true ranking based on synthetic rankings. For the personalized ranking task, we consider varying privacy preferences among users and quantify how their privacy preferences affect the consistency in estimating the optimal ranking function. Extensive numerical experiments are carried out to verify the theoretical results and demonstrate the effectiveness of the proposed synthetic ranking algorithm.

我们使用对单个的，相同的$ d $维状态的相同副本进行的测量来研究量子断层扫描和阴影断层扫描的问题。我们首先因Haah等人而重新审视已知的下限。 （2017年）在痕量距离上具有准确性$ \ epsilon $的量子断层扫描，当测量选择与先前观察到的结果无关（即它们是非适应性的）时。我们简要地证明了这一结果。当学习者使用具有恒定结果数量的测量值时，这会导致更强的下限。特别是，这严格确定了民间传说的最佳性``Pauli phymography''算法的样本复杂性。我们还得出了$ \ omega（r^2 d/\ epsilon^2）$和$ \ omega（r^2 d/\ epsilon^2）的新颖界限（ R^2 d^2/\ epsilon^2）$用于学习排名$ r $状态，分别使用任意和恒定的结果测量，在非适应性情况下。除了样本复杂性，对于学习量子的实际意义，是一种实际意义的资源状态是算法使用的不同测量值的数量。我们将下限扩展到学习者从固定的$ \ exp（o（d））$测量的情况下进行自适应测量的情况。这特别意味着适应性。没有使用可有效实现的单拷贝测量结果给我们任何优势。在目标是预测给定的可观察到给定序列的期望值的情况下，我们还获得了类似的界限，该任务被称为阴影层析成像。在适应性的情况下单拷贝测量可通过多项式大小的电路实现，我们证明了基于计算给定可观察物的样本平均值的直接策略是最佳的。

我们考虑一个矩阵完成问题，用于将社交或项目相似性图形作为侧面信息。我们开发了一种普遍的，无参数和计算的有效算法，该算法以分层图形聚类开始，然后迭代地改进图形聚类和矩阵额定值。在一个层次的随机块模型，尊重实际相关的社交图和低秩评级矩阵模型（要详细），我们证明了我们的算法实现了观察到的矩阵条目数量的信息 - 理论限制（即，最佳通过与较低的不可能结果一起导出的样本复杂性）通过最大似然估计。该结果的一个结果是利用社交图的层次结构，相对于简单地识别不同组的情况，在不诉诸于它们的情况下，可以产生相对于不同组的样本复杂性的大量增益。我们对合成和现实世界数据集进行了广泛的实验，以证实我们的理论结果，并展示了利用图形侧信息的其他矩阵完成算法的显着性能改进。

我们研究了测试有序域上的离散概率分布是否是指定数量的垃圾箱的直方图。$ k $的简洁近似值的最常见工具之一是$ k $ [n] $，是概率分布，在一组$ k $间隔上是分段常数的。直方图测试问题如下：从$ [n] $上的未知分布中给定样品$ \ mathbf {p} $，我们想区分$ \ mathbf {p} $的情况从任何$ k $ - 组织图中，总变化距离的$ \ varepsilon $ -far。我们的主要结果是针对此测试问题的样本接近最佳和计算有效的算法，以及几乎匹配的（在对数因素内）样品复杂性下限。具体而言，我们表明直方图测试问题具有样品复杂性$ \ widetilde \ theta（\ sqrt {nk} / \ varepsilon + k / \ varepsilon^2 + \ sqrt {n} / \ varepsilon^2）$。

鉴于$ n $ i.i.d.从未知的分发$ P $绘制的样本，何时可以生成更大的$ n + m $ samples，这些标题不能与$ n + m $ i.i.d区别区别。从$ p $绘制的样品？（AXELROD等人2019）将该问题正式化为样本放大问题，并为离散分布和高斯位置模型提供了最佳放大程序。然而，这些程序和相关的下限定制到特定分布类，对样本扩增的一般统计理解仍然很大程度上。在这项工作中，我们通过推出通常适用的放大程序，下限技术和与现有统计概念的联系来放置对公司统计基础的样本放大问题。我们的技术适用于一大类分布，包括指数家庭，并在样本放大和分配学习之间建立严格的联系。

在招聘，晋升和大学录取等选择过程中，众所周知，候选人的种族，性别或性取向等社会质量属性的隐性偏见会造成持久的不平等，并减少决策者的总效用。已经提出了诸如鲁尼规则及其概括之类的干预措施，这些干预措施要求决策者至少选择每个受影响组的指定数量的个体，以减轻隐性偏见在选择中的不利影响。最近的工作已经确定，在每个人最多属于一个受影响的群体的情况下，这种较低的约束对于改善总效用可能非常有效。但是，在某些情况下，个人可能属于多个受影响的群体，因此，由于这种交叉性，面临更大的隐含偏见。我们考虑独立绘制的实用程序，并表明在相交的情况下，上述非交流约束只能在没有隐性偏见的情况下恢复可实现的总效用的一部分。另一方面，我们表明，如果一个人在交叉点上包含适当的下限约束，那么在没有隐式偏见的情况下，几乎所有实用程序都可以恢复。因此，相交的约束可以比减少尺寸的非相互作用方法可提供显着优势，以减少不平等。

In the classical setting of self-selection, the goal is to learn $k$ models, simultaneously from observations $(x^{(i)}, y^{(i)})$ where $y^{(i)}$ is the output of one of $k$ underlying models on input $x^{(i)}$. In contrast to mixture models, where we observe the output of a randomly selected model, here the observed model depends on the outputs themselves, and is determined by some known selection criterion. For example, we might observe the highest output, the smallest output, or the median output of the $k$ models. In known-index self-selection, the identity of the observed model output is observable; in unknown-index self-selection, it is not. Self-selection has a long history in Econometrics and applications in various theoretical and applied fields, including treatment effect estimation, imitation learning, learning from strategically reported data, and learning from markets at disequilibrium. In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear. In the known-index case, we require poly$(1/\varepsilon, k, d)$ sample and time complexity to estimate all model parameters to accuracy $\varepsilon$ in $d$ dimensions, and can accommodate quite general selection criteria. In the more challenging unknown-index case, even the identifiability of the linear models (from infinitely many samples) was not known. We show three results in this case for the commonly studied $\max$ self-selection criterion: (1) we show that the linear models are indeed identifiable, (2) for general $k$ we provide an algorithm with poly$(d) \exp(\text{poly}(k))$ sample and time complexity to estimate the regression parameters up to error $1/\text{poly}(k)$, and (3) for $k = 2$ we provide an algorithm for any error $\varepsilon$ and poly$(d, 1/\varepsilon)$ sample and time complexity.

公司跨行业对机器学习（ML）的快速传播采用了重大的监管挑战。一个这样的挑战就是可伸缩性：监管机构如何有效地审核这些ML模型，以确保它们是公平的？在本文中，我们启动基于查询的审计算法的研究，这些算法可以以查询有效的方式估算ML模型的人口统计学率。我们提出了一种最佳的确定性算法，以及具有可比保证的实用随机，甲骨文效率的算法。此外，我们进一步了解了随机活动公平估计算法的最佳查询复杂性。我们对主动公平估计的首次探索旨在将AI治理置于更坚定的理论基础上。

我们考虑了贝叶斯的预测汇总模型，在观察了关于未知二进制事件的私人信号之后，$ n $专家向校长报告了有关事件的后验信念，然后将报告汇总为事件的单个预测。专家的信号和事件的结果遵循校长未知的联合分配，但校长可以访问I.I.D.来自分布的“样本”，每个样本都是专家报告的元组（不是信号）和事件的实现。使用这些样品，主要目的是找到$ \ varepsilon $ - 易于最佳（贝叶斯）聚合器。我们研究此问题的样本复杂性。我们表明，对于任意离散分布，样本的数量必须至少为$ \ tilde \ omega（m^{n-2} / \ varepsilon）$，其中$ m $是每个专家信号空间的大小。该样本复杂性在专家$ n $的数量中成倍增长。但是，如果专家的信号是独立的，以实现事件的实现为条件，那么样本复杂性将大大降低到$ \ tilde o（1 / \ varepsilon^2）$，这不取决于$ n $。

我们研究了情节块MDP中模型估计和无奖励学习的问题。在这些MDP中，决策者可以访问少数潜在状态产生的丰富观察或上下文。我们首先对基于固定行为策略生成的数据估算潜在状态解码功能（从观测到潜在状态的映射）感兴趣。我们在估计此功能的错误率上得出了信息理论的下限，并提出了接近此基本限制的算法。反过来，我们的算法还提供了MDP的所有组件的估计值。然后，我们研究在无奖励框架中学习近乎最佳政策的问题。根据我们有效的模型估计算法，我们表明我们可以以最佳的速度推断出策略（随着收集样品的数量增长大）的最佳策略。有趣的是，我们的分析提供了必要和充分的条件，在这些条件下，利用块结构可以改善样本复杂性，以识别近乎最佳的策略。当满足这些条件时，Minimax无奖励设置中的样本复杂性将通过乘法因子$ n $提高，其中$ n $是可能的上下文数量。

我们重新审视耐受分发测试的问题。也就是说，给出来自未知分发$ P $超过$ \ {1，\ dots，n \} $的样本，它是$ \ varepsilon_1 $ -close到或$ \ varepsilon_2 $ -far从引用分发$ q $（总变化距离）？尽管过去十年来兴趣，但在极端情况下，这个问题很好。在无噪声设置（即，$ \ varepsilon_1 = 0 $）中，样本复杂性是$ \ theta（\ sqrt {n}）$，强大的域大小。在频谱的另一端时，当$ \ varepsilon_1 = \ varepsilon_2 / 2 $时，样本复杂性跳转到勉强su​​blinear $ \ theta（n / \ log n）$。然而，非常少于中级制度。我们充分地表征了分发测试中的公差价格，作为$ N $，$ varepsilon_1 $，$ \ varepsilon_2 $，最多一个$ \ log n $ factor。具体来说，我们显示了\ [\ tilde \ theta \ left的样本复杂性（\ frac {\ sqrt {n}} {\ varepsilon_2 ^ {2}} + \ frac {n} {\ log n} \ cdot \ max \左\ {\ frac {\ varepsilon_1} {\ varepsilon_2 ^ 2}，\ left（\ frac {\ varepsilon_1} {\ varepsilon_2 ^ 2} \右）^ {\！\！\！2} \ \ \} \右） ，\]提供两个先前已知的案例之间的顺利折衷。我们还为宽容的等价测试问题提供了类似的表征，其中$ p $和$ q $均未赘述。令人惊讶的是，在这两种情况下，对样本复杂性的主数量是比率$ \ varepsilon_1 / varepsilon_2 ^ 2 $，而不是更直观的$ \ varepsilon_1 / \ varepsilon_2 $。特别是技术兴趣是我们的下限框架，这涉及在以往的工作中处理不对称所需的新颖近似性理论工具，从而缺乏以前的作品。