Isotonic regression with unknown permutations: Statistics, computation and adaptation
未知排列下的保序回归：统计、计算与自适应AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要主要研究通用形状约束估计，虽由多项比较数据启发，但未明确建立离散选择模型。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
未知排列下的保序回归：统计、计算与自适应
- 研究问题
- 当各维设计点顺序未知时，多维保序函数估计的最坏情形风险与分段常数自适应能力受到怎样的统计和计算限制？
- 方法与思路
- 作者重点研究三维及以上模型的经验平方损失与自适应指数，提出Mirsky分割估计量，并借助平均情形复杂性假设分析计算障碍。
- 材料陈述的贡献
- 摘要称，所提估计量达到极小极大最优风险及多项式时间程序可达的最小自适应指数；未知排列下的自适应存在条件性统计计算差距。
- 阅读关注点
- 核对自适应指数与函数类的定义、维数对风险的影响，以及最坏情形最优性和自适应计算障碍为何能够同时成立。
- 阅读边界
- 仅据版本未注明的OpenAlex摘要；风险速率、算法细节与复杂性假设未完整提供，不能将最坏情形结果解释为不存在自适应计算障碍。
原文摘要
Motivated by models for multiway comparison data, we consider the problem of estimating a coordinatewise isotonic function on the domain [0,1]d from noisy observations collected on a uniform lattice, but where the design points have been permuted along each dimension. While the univariate and bivariate versions of this problem have received significant attention, our focus is on the multivariate case d≥3. We study both the minimax risk of estimation (in empirical L2 loss) and the fundamental limits of adaptation (quantified by the adaptivity index) to a family of piecewise constant functions. We provide a computationally efficient Mirsky partition estimator that is minimax optimal while also achieving the smallest adaptivity index possible for polynomial time procedures. Thus, from a worst-case perspective and in sharp contrast to the bivariate case, the latent permutations in the model do not introduce significant computational difficulties over and above vanilla isotonic regression. On the other hand, the fundamental limits of adaptation are significantly different with and without unknown permutations: Assuming a hardness conjecture from average-case complexity theory, a statistical-computational gap manifests in the former case. In a complementary direction, we show that natural modifications of existing estimators fail to satisfy at least one of the desiderata of optimal worst-case statistical performance, computational efficiency and fast adaptation. Along the way to showing our results, we improve adaptation results in the special case d=2 and establish some properties of estimators for vanilla isotonic regression, both of which may be of independent interest.