Statistical learning theory and the Probably Approximately Correct (PAC)
criterion are the common approach to mathematical learning theory. PAC is
widely used to analyze learning problems and algorithms, and have been studied
thoroughly. Uniform worst case bounds on the convergence rate have been well
established using, e.g., VC theory or Radamacher complexity. However, in a
typical scenario the performance could be much better. In this paper, we
consider PAC learning using a somewhat different tradeoff, the error exponent -
a well established analysis method in Information Theory - which describes the
exponential behavior of the probability that the risk will exceed a certain
threshold as function of the sample size. We focus on binary classification and
find, under some stability assumptions, an improved distribution dependent
error exponent for a wide range of problems, establishing the exponential
behavior of the PAC error probability in agnostic learning. Interestingly,
under these assumptions, agnostic learning may have the same error exponent as
realizable learning. The error exponent criterion can be applied to analyze
knowledge distillation, a problem that so far lacks a theoretical analysis.

在本文中，我们通过考虑错误指数这一在信息理论中广泛应用的分析方法，研究了统计学习理论和可能近似正确（PAC）准则。在一定的稳定性假设下，我们发现二分类问题中 PAC 错误概率的指数行为，从而建立了对无知学习中可能近似正确学习的理论分析基础。有趣的是，在这些假设下，无知学习可能具有与可实现学习相同的错误指数。此错误指数准则可用于分析在缺少理论分析的知识蒸馏问题。

对于无偏 PAC 学习的误差指数

Error Exponent in Agnostic PAC Learning

We investigate the problem of probably approximately correct and fair (PACF)
ranking of items by adaptively evoking pairwise comparisons. Given a set of $n$
items that belong to disjoint groups, our goal is to find an $(\epsilon,
\delta)$-PACF-Ranking according to a fair objective function that we propose.
We assume access to an oracle, wherein, for each query, the learner can choose
a pair of items and receive stochastic winner feedback from the oracle. Our
proposed objective function asks to minimize the $\ell_q$ norm of the error of
the groups, where the error of a group is the $\ell_p$ norm of the error of all
the items within that group, for $p, q \geq 1$. This generalizes the objective
function of $\epsilon$-Best-Ranking, proposed by Saha & Gopalan (2019).
By adopting our objective function, we gain the flexibility to explore
fundamental fairness concepts like equal or proportionate errors within a
unified framework. Adjusting parameters $p$ and $q$ allows tailoring to
specific fairness preferences. We present both group-blind and group-aware
algorithms and analyze their sample complexity. We provide matching lower
bounds up to certain logarithmic factors for group-blind algorithms. For a
restricted class of group-aware algorithms, we show that we can get reasonable
lower bounds. We conduct comprehensive experiments on both real-world and
synthetic datasets to complement our theoretical findings.

透过自适应调用两两比较来研究可能近似正确且公平（PACF）排名问题，目标是根据我们提出的公平目标函数找出一个（ϵ，δ）-PACF 排名。我们使用的目标函数要求最小化组的误差 lq 范数，其中组的误差是组内所有项误差的 lp 范数，p,q≥1。我们提供了群体不可见和群体感知算法，并分析了其样本复杂度。我们对真实数据集和合成数据集进行了全面的实验以补充我们的理论结果。

基于配对偏好的公平主动排名

Fair Active Ranking from Pairwise Preferences

Cyber-physical systems (CPS) like autonomous vehicles, that utilize learning
components, are often sensitive to noise and out-of-distribution (OOD)
instances encountered during runtime. As such, safety critical tasks depend
upon OOD detection subsystems in order to restore the CPS to a known state or
interrupt execution to prevent safety from being compromised. However, it is
difficult to guarantee the performance of OOD detectors as it is difficult to
characterize the OOD aspect of an instance, especially in high-dimensional
unstructured data.
To distinguish between OOD data and data known to the learning component
through the training process, an emerging technique is to incorporate
variational autoencoders (VAE) within systems and apply classification or
anomaly detection techniques on their latent spaces. The rationale for doing so
is the reduction of the data domain size through the encoding process, which
benefits real-time systems through decreased processing requirements,
facilitates feature analysis for unstructured data and allows more explainable
techniques to be implemented.
This study places probably approximately correct (PAC) based guarantees on
OOD detection using the encoding process within VAEs to quantify image features
and apply conformal constraints over them. This is used to bound the detection
error on unfamiliar instances with user-defined confidence. The approach used
in this study is to empirically establish these bounds by sampling the latent
probability distribution and evaluating the error with respect to the
constraint violations that are encountered. The guarantee is then verified
using data generated from CARLA, an open-source driving simulator.

本文利用变分自编码器实现了对开放分布数据（OOD）的检测，在对结果进行了准确度量和规范约束后，使用 CARLA 数据集对此方法进行了验证。