标题： DUST：一种基于对偶的精确多重变点检测剪枝方法 显示英文标题

标题： DUST: A Duality-Based Pruning Method For Exact Multiple Change-Point Detection

摘要： 我们通过优化从指数族模型中得出的惩罚似然来解决在大型时间序列中检测多个变化点的挑战。 动态规划算法可以在最多二次时间复杂度内精确解决此任务。 近年来，剪枝策略的发展显著提高了它们的计算效率。 然而，现有的两种方法存在明显的局限性：PELT在稀疏变化场景中剪枝效率不佳，而FPOP的结构不适用于多参数设置。 为了解决这些问题，我们引入了DUal Simple Test（DUST）框架，该框架通过将对偶函数与阈值进行比较来剪枝候选变化点。 这种方法高度灵活，可广泛应用于任何维度的参数模型。 在较弱的假设下，我们建立了基础非凸剪枝问题的强对偶性。 我们在各种变化点情形和模型中展示了DUST的有效性。 特别是对于单参数模型，DUST在保持PELT的简洁性的同时，具有FPOP的效率。 它在非高斯模型中的使用尤其有利。 最后，我们将DUST应用于变化方差模型下的小鼠监测时间序列，展示了其高效恢复最优变化点结构的能力。 显示英文摘要

摘要： We tackle the challenge of detecting multiple change points in large time series by optimising a penalised likelihood derived from exponential family models. Dynamic programming algorithms can solve this task exactly with at most quadratic time complexity. In recent years, the development of pruning strategies has drastically improved their computational efficiency. However, the two existing approaches have notable limitations: PELT struggles with pruning efficiency in sparse-change scenarios, while FPOP's structure is not adapted to multi-parametric settings. To address these issues, we introduce the DUal Simple Test (DUST) framework, which prunes candidate changes by evaluating a dual function against a threshold. This approach is highly flexible and broadly applicable to parametric models of any dimension. Under mild assumptions, we establish strong duality for the underlying non-convex pruning problem. We demonstrate DUST's effectiveness across various change-point regimes and models. In particular, for one-parametric models, DUST matches the simplicity of PELT with the efficiency of FPOP. Its use is especially advantageous for non-Gaussian models. Finally, we apply DUST to mouse monitoring time series under a change-in-variance model, illustrating its ability to recover the optimal change-point structure efficiently.