Conformal prediction is a popular, modern technique for providing valid
predictive inference for arbitrary machine learning models. Its validity relies
on the assumptions of exchangeability of the data, and symmetry of the given
model fitting algorithm as a function of the data. However, exchangeability is
often violated when predictive models are deployed in practice. For example, if
the data distribution drifts over time, then the data points are no longer
exchangeable; moreover, in such settings, we might want to use a nonsymmetric
algorithm that treats recent observations as more relevant. This paper
generalizes conformal prediction to deal with both aspects: we employ weighted
quantiles to introduce robustness against distribution drift, and design a new
randomization technique to allow for algorithms that do not treat data points
symmetrically. Our new methods are provably robust, with substantially less
loss of coverage when exchangeability is violated due to distribution drift or
other challenging features of real data, while also achieving the same coverage
guarantees as existing conformal prediction methods if the data points are in
fact exchangeable. We demonstrate the practical utility of these new tools with
simulations and real-data experiments on electricity and election forecasting.

本文提出一种新的针对预测模型的 Conformal prediction 泛化方法，通过引入加权分位数来抵御数据分布漂移的影响，同时设计一种新的随机化技术，允许不对称处理数据点的算法。实验表明，该方法在数据点不可交换的情况下具有较高的鲁棒性，并且在数据点可交换情况下达到了与现有方法相同的覆盖率保证。

超越交换性的合拍预测

Conformal prediction beyond exchangeability

We study preconditioned gradient-based optimization methods where the
preconditioning matrix has block-diagonal form. Such a structural constraint
comes with the advantage that the update computation is block-separable and can
be parallelized across multiple independent tasks. Our main contribution is to
demonstrate that the convergence of these methods can significantly be improved
by a randomization technique which corresponds to repartitioning coordinates
across tasks during the optimization procedure. We provide a theoretical
analysis that accurately characterizes the expected convergence gains of
repartitioning and validate our findings empirically on various traditional
machine learning tasks. From an implementation perspective, block-separable
models are well suited for parallelization and, when shared memory is
available, randomization can be implemented on top of existing methods very
efficiently to improve convergence.

本文研究了具有块对角形式的预处理矩阵的梯度优化方法。作者证明，随机分配坐标在优化过程中可以显著提高这些方法的收敛性能，并在各种传统机器学习任务中进行了实证验证。从实现的角度来看，块可分离的模型非常适合并行化，当共享内存可用时，随机化可以在现有方法的基础上非常有效地实现来提高收敛速度。

并行学习的随机块对角线预处理

Randomized Block-Diagonal Preconditioning for Parallel Learning

Existing fixed-length feedback communication schemes are either specialized
to particular channels (Schalkwijk--Kailath, Horstein), or apply to general
channels but either have high coding complexity (block feedback schemes) or are
difficult to analyze (posterior matching). This paper introduces a new
fixed-length feedback coding scheme which achieves the capacity for all
discrete memoryless channels, has an error exponent that approaches the sphere
packing bound as the rate approaches the capacity, and has $O(n\log n)$ coding
complexity. These benefits are achieved by judiciously combining features from
previous schemes with new randomization technique and encoding/decoding rule.
These new features make the analysis of the error probability for the new
scheme easier than for posterior matching.

本文引入一种新的固定长度反馈编码方案，通过糅合前作品的特点，以及引入新的随机化技术和编码 / 解码规则，能够实现离散无记忆信道的全容量，并具有接近球装填界的误差指数，以及 O（nlogn）的编码复杂度。