DUST: A Duality-Based Pruning Method For Exact Multiple Change-Point Detection Vincent Runge, Charles Truong, Simon Querné Abstract 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. Keywords: Multiple change-point detection, dynamic programming, pruning, duality theory, time efficiency 1 Introduction Single and multiple change-point detection are well-established unsupervised machine learning tasks within the field of time-series analysis, with foundational work dating back to the 1950s page1954continuous ; page1955test . Over the past decades, the topic has been the subject of extensive research, resulting in numerous monographs series1994change ; brodsky2013nonparametric ; csorgo1997limit ; chen2000parametric and comprehensive review articles jandhyala2013inference ; aminikhanghahi2017survey ; truong2020selective . Until recently, the long-standing focus of the scientific community has mainly been the statistical modelling and the calibration challenge for detecting and localising change points. With the rise of big data, the demand for computationally efficient algorithms has become increasingly pressing. Time efficiency is particularly crucial in many application domains, including genomics jia2022efficient ; liehrmann2023diffsegr , econometrics bai2003computation ; gu2013fast , climatology reeves2007review ; shi2022changepoint , speech processing harchaoui2009regularized ; chang2010fast , and network analysis zhou2022asymptotic ; banerjee2020change , to name just a few. This work addresses the computational challenge of recovering multiple change points in a time series of fixed length. We consider change-point problems based on optimizing a penalised likelihood whose penalty is proportional to the number of changes. Although algorithms with quadratic time complexity have been available for some time auger1989algorithms ; jackson2005algorithm , the central objective is to approach quasi-linear execution time as closely as possible, while preserving the exact resolution of the underlying optimisation problem. Detecting multiple change points requires carefully designed algorithmic strategies often balancing exactness with computational efficiency. Although the quasi-linear Binary Segmentation (BS) algorithm scott1974cluster ; sen1975tests ; zbMATH03766903 has historically been the dominant (approximate) method, recent advances in (exact) sub-quadratic dynamic programming (DP) techniques are beginning to challenge its prominence. We illustrate this with a simple example. With a time budget of 10 seconds, we estimate the maximum data length that an algorithm can segment when the signal consists of 10 segments of equal length. The observations follow y_{t}\sim\mathcal{N}(\mu_{t},1) , with piecewise constant means \mu_{t}\in\{0,1\} . BS stopping at 10 segments can process up to approximately n=75\times 10^{6} data points. In contrast, the classical exact quadratic-time Optimal Partitioning (OP) algorithm jackson2005algorithm with BIC penalty yao1988estimating is limited to around n=120\times 10^{3} . However, improved exact algorithms such as FPOP can handle up to n=30\times 10^{6} data points within the same time budget, while the DUST algorithm can analyse around n=42\times 10^{6} data points 1 1 1 Simulations were conducted on a MacBook Pro equipped with an Apple M1 chip (8-core CPU: 4 performance cores and four efficiency cores), 16GB of unified memory, running macOS Sequoia 15.5 . The code was implemented in R and executed using our dust Rcpp package (for DUST and OP) and the fpop packages provided in maidstone2017optimal (for FPOP and BS). . DP methods have experienced a period of renaissance with the development of accelerating pruning strategies, making their execution time competitive with BS on simulations (as just illustrated) and on real data sets (see Figure 6 in maidstone2017optimal ). Among them, inequality-based pruning (PELT) killick2012optimal and functional-based pruning (FPOP) maidstone2017optimal are the two extreme pruning strategies available on the “pruning scale”. In the latest developments, DP with functional pruning has made possible the inference of complex structured models that constrain the successive segment parameter values (throughout a graph of constraints) Hocking2020 ; JSSv106i06 . One-parametric model with exponential decays jewell2020fast or data modelled with auto-correlation and random drift romano2022detecting can also be considered, among others. PELT pruning is efficient for time series with many changes and is simple to code, but does not prune well when there are only a few changes. FPOP pruning is well-suited for problems with a one-parametric functional description. However, extensions to multivariate problems are uneasy as the parameter space description made of intervals in a one-parametric cost function is no longer possible. In this case, the partition of the parameter space is made of potential non-convex and unconnected elements runge2020finite . Approximations of the parameter space with sphere-like or rectangle-like sets have been tested and significantly improve the time complexity, but only for small dimensions in the independent Gaussian multivariate setting pishchagina2024geometricbased . This work proposes a new pruning method called DUST that goes beyond these limitations. To do so, we recast the pruning task as a constrained optimisation problem. Within this framework, we explicitly derive the dual formulation for multivariate data drawn from the exponential family. We analyse its properties and, in particular, establish a strong duality result that underpins the effectiveness of our pruning rule. The proposed DUST rule consists of evaluating a dual function and comparing it to a threshold – yielding a test as simple as that used in PELT. For one-parameter cost functions (corresponding essentially to univariate data), we further derive a simple inequality-based rule by maximising the dual function explicitly. The PELT criterion corresponds to evaluating the dual at zero and is provably upper-bounded by the DUST value. Normalising the dual into a decision function simplifies its interpretation and opens the door to more sophisticated DUST rules applicable to multivariate time series. A comprehensive simulation study confirms the efficiency and versatility of DUST, highlighting in particular its time robustness across all change-point regimes and under misspecified calibration parameters. We apply DUST for change in variance to large-scale data collected from mouse monitoring via a force platform aimed at quantifying muscle fatigue. This paper has the following structure. In Section 2 we present the functional problem for pruning in the context of multiple change-point detection. In Section 3 we describe DUST in the one-constraint case and illustrate DUST on a first simple example. Astonishingly, the one-parametric case leads to a simple closed formula for the positivity test associated with the dual. The general presentation of the duality method is given in Section 4 . The simulation study of Section 5 explores the efficiency of DUST. We eventually describe an example on a real-world data set in Section 6 . If not in the main body of the article, proofs are given in the appendix. 2 Change-point problem and its functional description 2.1 Model and optimisation problem We consider a time series consisting of n data points, denoted by y_{1},y_{2},\ldots,y_{n} , where each point is drawn independently from a distribution belonging to the exponential family. A segment, denoted by y_{ab} , refers to a contiguous sub-sequence of the data, y_{a+1},\ldots,y_{b} , where 0\leq at . In other words, it means that inner functions which are unseen in the minimisation at some time step t for all values in the parametric space \Theta will never be seen again later and can therefore be safely discarded. This insight follows directly from the additive property ( 2 ), which implies the equivalence q_{t}^{r}(\boldsymbol{\theta})t . Functional pruning is the most efficient pruning strategy. Proposition 1 . (FPOP maximal pruning) The FPOP-like pruning presented in Definition 1 is the maximal possible pruning for the optimisation problem of type ( 4 ) with additive cost property ( 2 ). Say differently, at each time step t , the index set \mathcal{T}_{t} obtained by FPOP is minimal: a smaller \mathcal{T}_{t} would potentially lead to an under-optimal solution. The proof relies on the following argument. If we remove an index s_{0} in \mathcal{T}_{t} such that Q_{t}(\boldsymbol{\theta})=q_{t}^{s_{0}}(\boldsymbol{\theta}) in a neighbourhood of \boldsymbol{\theta}_{0} , we can prove that, by adding data points "centred on \theta_{0} " at further iterations (with unitary cost A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\nabla A(\boldsymbol{\theta}_{0}) ), the last segment in ( 6 ) would start at index s_{0}+1 at some later time t_{0} . However, since s_{0} was pruned, the solution of the DP algorithm is no longer exact. It is important to note that, although pruning rules can drastically reduce execution time in practice, there exist examples of data for which no pruning rule could discard any index, leading back to the worst-case quadratic complexity of the optimal partitioning algorithm. We construct such examples using increasing time series where all inner cost functions attain the same minimal value at time n . We first illustrate this phenomenon in the simple univariate Gaussian case. Proposition 2 . We consider the Gaussian univariate model with fixed variance. Its inner cost functions are given by relations q_{t}^{s}(\theta)=Q_{s}+\frac{t-s}{2}\theta^{2}-S_{st}\theta+\beta with S_{st}=\sum_{i=s+1}^{t}y_{i} and y_{i}\in\mathbb{R} . If we observe the following data points: y_{t}=\sqrt{\frac{\beta}{n}}\Big(\sqrt{n-1}-\sqrt{t(n-t)}+\sqrt{(t-1)(n-t+1)}\Big)\,,\quad t=1,\dots,n (8) then no pruning happens, that is \mathcal{T}_{n}=\{0,\ldots,n-1\} . We extend the result to a broader class of continuous distributions within the natural exponential family in Appendix B.3 . 2.3 Functional pruning rule as an optimisation problem In the evolution of the dynamic programming algorithm, if an inner function q_{t}^{s} is still accessible, it can be discarded only by the last introduced function at time t+1 , that is Q_{t}+c(y_{t(t+1)};\boldsymbol{\theta})+\beta (due to the additive property ( 2 )). This naturally leads to the following pruning strategy: compare each inner function at time t with the constant threshold Q_{t}+\beta . We denote by \Theta_{t}^{s}\subset\Theta the set of parameter values for which the function q_{t}^{s} attains the minimum among all candidate functions at time t , defined explicitly as: \Theta_{t}^{s}:=\{\boldsymbol{\theta}\in\Theta\,|\,\forall r\in\mathcal{T}_{t}\setminus\{s\},\ q_{t}^{s}(\boldsymbol{\theta})\leq q_{t}^{r}(\boldsymbol{\theta})\}\,. (9) The criterion " \Theta_{t}^{s}=\emptyset ?" forms the basis of the functional pruning rule introduced in FPOP maidstone2017optimal for univariate data, and has since been adopted in several one-dimensional extensions jewell2020fast ; romano2022detecting . For multivariate problems, a recent method proposes to approximate the set \Theta_{t}^{s} using simple geometric shapes pishchagina2024geometricbased . However, this approach becomes challenging to implement efficiently for non-Gaussian cost functions, resulting in relatively slow updates (see also runge2020finite ). Instead, with DUST, we propose to evaluate the minimal value of q_{t}^{s} over its visibility region \Theta_{t}^{s} , and compare it directly to the threshold Q_{t}+\beta . While this may appear to introduce additional computation, it avoids the need to characterise the potentially complex shape of \Theta_{t}^{s} explicitly. Thus, the task reduces to finding a single value – or a lower bound on it – which is often more tractable in practice. Proposition 3 (Functional pruning with minimum value rule) . We define R_{t}^{s}:=\min_{\boldsymbol{\theta}\in\Theta_{t}^{s}}q_{t}^{s}(\boldsymbol{\theta}) with \Theta_{t}^{s} given in ( 9 ). By convention, if \Theta_{t}^{s}=\emptyset , then R_{t}^{s}=+\infty . The functional pruning condition is as follows. If there exists s in \mathcal{T}_{t} satisfying: R_{t}^{s}>Q_{t}+\beta, (10) then s can never be the last change point of a segmentation of y_{0t^{\prime}} for all t^{\prime}>t : that is s\not\in\mathcal{T}_{t^{\prime}} . Proof. Let \boldsymbol{\theta}\not\in\Theta_{t}^{s} . By definition of \Theta_{t}^{s} there exists r such that \ q_{t}^{s}(\boldsymbol{\theta})>q_{t}^{r}(\boldsymbol{\theta}) and therefore \ q_{t^{\prime}}^{s}(\boldsymbol{\theta})>q_{t^{\prime}}^{r}(\boldsymbol{\theta}) . Let \boldsymbol{\theta}\in\Theta_{t}^{s} . If the functional pruning condition ( 10 ) holds, we have q_{t^{\prime}}^{s}(\boldsymbol{\theta})=q_{t}^{s}(\boldsymbol{\theta})+c(y_{tt^{\prime}},\boldsymbol{\theta})>Q_{t}+\beta+c(y_{tt^{\prime}},\boldsymbol{\theta})=q_{t^{\prime}}^{t}(\boldsymbol{\theta}) which means that index s is never seen in the minimisation problem (it is hidden by index t ) and can be discarded. ∎ Unfolding the definition of \Theta_{t}^{s} , we observe that the central challenge in pruning for multiple change-point detection is a problem of constrained optimisation. Its dual formulation forms the core of the DUST pruning method. Definition 2 (Pruning problem) . The pruning problem for multiple change-point detection at time t for testing change point s is the following problem of optimisation under constraints: \left\{\begin{aligned} &\min_{\boldsymbol{\theta}\in\Theta}q_{t}^{s}(\boldsymbol{\theta})\,,\\ &\hbox{ s.t.}\,\,q_{t}^{s}(\boldsymbol{\theta})-q_{t}^{r}(\boldsymbol{\theta})\leq 0\quad\hbox{for all}\quad r\in\mathcal{T}_{t}\setminus\{s\}\subset\{0,\ldots,t-1\}\,.\end{aligned}\right. (11) A result greater than threshold Q_{t}+\beta implies that the function q_{t}^{s}(\boldsymbol{\theta}) can be removed and the index s pruned. We aim to compute either the exact solution or a tight lower bound using a highly efficient algorithm. To this end, we begin by considering a simplified version of the pruning problem with a single constraint, which allows us to derive a lower bound. This setting offers a clear framework to introduce and illustrate our dual approach. Furthermore, in the case of one-parametric cost functions, this formulation enables the design of a particularly efficient pruning test. 2.4 Notations for dual and decision functions For clarity, we compile below all the notations related to dual and decision functions used in the sequel. The function \mathcal{D^{*}} is given by \mathcal{D^{*}}(x)=x\cdot(\nabla A)^{-1}(x)-A((\nabla A)^{-1}(x)) and is strictly convex. We introduce the following mean values: \overline{\mathbf{S}}_{rs}=\left\{\begin{aligned} &\frac{{\mathbf{S}}_{rs}}{s-r}\quad\hbox{if}\quad rs , the obtained (convex) problem ( 12 ) leads to a very inefficient pruning. The optimal value of ( 12 ) is defined as R_{t}^{rs} . We can easily write down the Lagrangian function as: \displaystyle\mathcal{L}(\boldsymbol{\theta},\mu) \displaystyle=q_{t}^{s}(\boldsymbol{\theta})+\mu(q_{t}^{s}(\boldsymbol{\theta})-q_{t}^{r}(\boldsymbol{\theta}))\,, \displaystyle=\Big((t-s)-\mu(s-r)\Big)\Big(A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\frac{\mathbf{S}_{st}-\mu\mathbf{S}_{rs}}{(t-s)-\mu(s-r)}\Big)+\mu(Q_{s}-Q_{r})+Q_{s}+\beta\,, or with a change of variable \mu\to\mu\frac{t-s}{s-r} and the parametric mean \mathbf{m}(\mu)=\frac{\overline{\mathbf{S}}_{st}-\mu\overline{\mathbf{S}}_{rs}}{1-\mu} : \mathcal{L}(\boldsymbol{\theta},\mu)=(t-s)\Big((1-\mu)(A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\mathbf{m}(\mu))+\mu\frac{Q_{s}-Q_{r}}{s-r}\Big)+Q_{s}+\beta\,. The dual function presented in the following proposition serves as a lower bound for the target quantity R_{t}^{s} (see Proposition 3 ). Proposition 4 . The dual function \mathcal{D}:[0,\mu_{max})\to\mathbb{R} to Problem ( 12 ) with inner cost functions ( 7 ) and cost ( 1 ) for pruning index s using index r with rQ_{t}+\beta , for some \mu_{0}\in[0,\mu_{\text{max}}) . The solution R_{t}^{rs} to Problem ( 12 ) is smaller than the solution R_{t}^{s} to Problem ( 11 ), and is lower bounded by the dual function: for all \mu\in[0,\mu_{\text{max}}) , we have: \mathcal{D}(\mu)\leq R_{t}^{rs}\leq R_{t}^{s} . Therefore, using any value \mu_{0}\in[0,\mu_{\text{max}}) , pruning based on the condition \mathcal{D}(\mu_{0})>Q_{t}+\beta is safe: it guarantees that R_{t}^{s}>Q_{t}+\beta , so no index is removed by mistake. Ideally, we would evaluate the dual function at its maximum or some value close to it. 3.2 DUST decision rule Pruning relies on the existence of a value \mu_{0} such that \mathcal{D}(\mu_{0})-(Q_{t}+\beta)>0 . Since dividing the left-hand side by any positive function does not change the decision, we normalise the dual function \mathcal{D} from Proposition 4 to allow its direct maximisation (with a closed formula) in some particular cases. The new function \mathbb{D} , called the decision function, has this simple property: pruning of index s occurs as soon as \mathbb{D} returns a positive value for some point in its domain. Proposition 5 . The decision function \mathbb{D}:[0,x_{max})\to\mathbb{R} to Problem ( 12 ) with inner cost functions ( 7 ) and cost ( 1 ) for pruning index s using index r with rQ_{t}+\beta\,. (15) Note that certain special cases must be handled before testing inequality ( 15 ), such as x_{\max}=0 , \overline{S}_{st}=\overline{S}_{rs} (i.e., the decision function is linear) and x^{\star}\notin(0,x_{\max}) . This theorem advantageously replaces the PELT pruning rule, which was given by q_{t}^{s}((\nabla A)^{-1}(\overline{S}_{st}))>Q_{t}+\beta . We will highlight the effectiveness of the DUST rule in simulation Section 5 . 3.3 DUST algorithm We have designed our new pruning method to be as straightforward and practical as the PELT rule. The DUST multiple change-point detection algorithm is described in Algorithm 1 . Here, the value c(y_{st}) is defined as the minimum of the segment cost function \boldsymbol{\theta}\mapsto c(y_{st};\boldsymbol{\theta}) . For the smallest index in \mathcal{T}_{t} , we use the standard PELT pruning rule by default. The index r is selected from a given probability distribution p_{r} over the indices in \mathcal{T}_{t} that are smaller than s , while the value \mu_{0} is sampled from a distribution p_{\mu} supported on the segment [0,\mu_{\text{max}}\leq 1) . For one-parametric cost functions, we can consider a Dirac data-dependent p_{\mu} which matches relation ( 15 ) in addition to its limit cases. Simulations (Section 5 ) explore several choices for the distributions p_{r} and p_{\mu} . In the single-constraint setting, an effective strategy is to select r as the closest index below s , and to choose \mu_{0} as the argument that maximises the dual function, using a simple iterative maximisation procedure or relation ( 15 ) for one-parametric cost functions. For simplicity, the algorithm is presented with the dual \mathcal{D} with bounded domain, but a similar algorithm can be written with decision function \mathbb{D} . From the output of Algorithm 1 , we can easily recover the optimal segmentation for the initial problem ( 4 ) via a standard backtracking step described in Algorithm 2 . Algorithm 1 DUST algorithm 1: Time series y_{0n} , penalty value \beta>0 , rules p_{r} , p_{\mu} 2: Sequences of global costs Q_{0n} and last changes \hat{s}_{0n} 3: Q_{0}\leftarrow 0,\quad\mathcal{T}_{1}\leftarrow\{0\} 4: for t=1,\dots,n do \triangleright OP step 5: Q_{t}\leftarrow\min_{s\in\mathcal{T}_{t}}\left\{Q_{s}+c(y_{st})+\beta\right\} 6: \hat{s}_{t}\leftarrow\argmin_{s\in\mathcal{T}_{t}}\left\{Q_{s}+c(y_{st})+\beta\right\} 7: for s\in\mathcal{T}_{t} do \triangleright DUST pruning step 8: Draw r in \mathcal{T}_{t} such that rQ_{t}+\beta then \triangleright DUST test 12: \mathcal{T}_{t}\leftarrow\mathcal{T}_{t}\backslash\{s\} 13: end if 14: end for 15: \mathcal{T}_{t+1}\leftarrow\mathcal{T}_{t}\cup\{t\} 16: end for Algorithm 2 Backtracking the change-point locations 1: \hat{s}_{0n} 2: Set of optimal change point indices \widehat{\mathcal{T}}=\{\tau_{1},\tau_{2},\dots\} 3: \tau\leftarrow n , \widehat{\mathcal{T}}\leftarrow\emptyset 4: while \tau>0 do 5: \widehat{\mathcal{T}}\leftarrow(\tau,\widehat{\mathcal{T}}) , t\leftarrow\hat{s}_{\tau} 6: end while Remark 1 . DUST extends PELT by evaluating the dual function beyond zero. While PELT applies the test \mathcal{D}(0)>Q_{t}+\beta , derived from the unconstrained form of Problem ( 12 ), DUST samples \mu_{0} in [0,\mu_{\text{max}}) , potentially yielding stronger pruning. This makes DUST especially effective in time series with few change points, where PELT tends to prune poorly. Despite its improved pruning, DUST maintains a complexity close to PELT, with minimal overhead from computing \mu_{\text{max}} and selecting r and \mu_{0} . 3.4 Example of the change-in-mean-and-variance problem Detecting changes in both the mean and variance of a large Gaussian time series is challenging. To the best of our knowledge, no efficient implementation currently exists in this setting due to two main difficulties. First, the problem involves two parameters, which limit the applicability of methods like FPOP maidstone2017optimal . Second, a logarithmic term in the cost function complicates root-finding, making methods such as geomFPOP pishchagina2024geometricbased difficult to apply. We address this challenge using the DUST method. We write down the likelihood of segment y_{st} with mean m and variance \sigma^{2} , \mathcal{L}(y_{st};[m;\sigma^{2}])=\prod_{i=s+1}^{t}\biggr[\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\Big(-\frac{(m-y_{i})^{2}}{2\sigma^{2}}\Big)\biggr]\,, and its associated cost: c(y_{st};[m;\sigma^{2}])=(t-s)\Big(\frac{(m-\overline{y}_{st})^{2}+V(y_{st})}{2\sigma^{2}}+\frac{1}{2}\log(\sigma^{2})\Big)\,. With the change of variable (\theta_{1},\theta_{2})=(\frac{m}{\sigma^{2}};-\frac{1}{2\sigma^{2}})\in\mathbb{R}\times\mathbb{R}^{-} , we obtain the canonical form of Example 2 with A(\theta_{1},\theta_{2})=-\frac{\theta_{1}^{2}}{4\theta_{2}}+\frac{1}{2}\log(-\frac{1}{2\theta_{2}}) . We can now derive the exact maximum value of the associated decision function. Lemma 1 . The one-dimensional decision function for the change-in-mean-and-variance problem with a single constraint from the cost function ( 3 ) is given by the function: \mathbb{D}(x)=\frac{1}{2}\Bigg[1+\log\Big(\overline{S^{2}_{st}}+x\Delta\overline{S_{rst}^{2}}-(\overline{S}_{st}+x\Delta\overline{S}_{rst})^{2}\Big)\Bigg]-\Big(\overline{Q}_{st}+x\Delta\overline{Q}_{rst}\Big)\,, with x\in(x_{0}-\sqrt{x_{1}},x_{0}+\sqrt{x_{1}}) and x_{0}=\frac{1}{2}\Big(\frac{V(y_{st})-V(y_{rs})}{(\Delta\overline{S}_{rst})^{2}}-1\Big)\,\quad x_{1}=x_{0}^{2}+\frac{V(y_{st})}{(\Delta\overline{S}_{rst})^{2}} and its maximum, with notation x_{2}=\Delta\overline{Q}_{rst} , is evaluated in: x^{\star}=\max\Big\{0,x_{0}+(2x_{2})^{-1}-\operatorname{sign}(x_{2})\sqrt{x_{1}+(2x_{2})^{-2}}\Big\}\,. In Figure 1 , we evaluate the efficiency of DUST for this example. For each index s considered for pruning, we choose the biggest non-pruned index smaller than s and evaluate the dual at its maximum position x^{\star} . With n=10^{4} , \beta=4\log(n) and data with no change ( \mathcal{N}(0,1) ), only 2.95\% of the indices remain non-pruned and the overall number of indices to be considered is reduced by a factor 28 compared to PELT (left panel). Figure 1: For data with no change, the number of indices saved by DUST over time is consistently much less than PELT (no pruning), for the one-constraint DUST (left) and the two-constraint case (right). A higher lower bound for R_{t}^{s} is obtained when we consider two constraints: q_{t}^{s}-q_{t}^{r_{1}}\leq 0 and q_{t}^{s}-q_{t}^{r_{2}}\leq 0 . This leads to a bi-parametric decision function: \mathbb{D}(x_{1},x_{2})=\frac{1}{2}\Bigg[1+\log\Big(\overline{S^{2}_{st}}+x_{1}\Delta\overline{S_{r_{1}st}^{2}}+x_{2}\Delta\overline{S_{r_{2}st}^{2}})-(\overline{S}_{st}+x_{1}\overline{S}_{r_{1}st}+x_{2}\overline{S}_{r_{2}st})^{2}\Big)\Bigg] -\Big(\overline{Q}_{st}+x_{1}\Delta\overline{Q}_{r_{1}st}+x_{2}\Delta\overline{Q}_{r_{2}st}\Big)\,. Such a general dual and its properties are studied in the next Section. In this mean-and-variance problem, explicit maximal values are available for the three values to be tested: \max_{x_{1}}\mathbb{D}(x_{1},0) , \max_{x_{2}}\mathbb{D}(0,x_{2}) and \max_{x_{1},x_{2}}\mathbb{D}(x_{1},x_{2}) with positive x_{1},x_{2} . In Figure 1 (right panel) we run the same simulation as in the left panel but with a bi-parametric dual, built from the two highest indices smaller than s ( r_{1}0 and x_{2}>0 ). We recall that this DUST pruning procedure does not involve any iterative routine, but relies solely on three inequality tests (as PELT) evaluated at three points of the decision function, each computed from a closed-form expression. With 10^{6} data point, the percentage of remaining indices drops to 0.5\% . 4 Duality function in change-point problems 4.1 The shape of the dual We consider the pruning problem ( 11 ): \min_{\boldsymbol{\theta}\in\Theta}q_{t}^{s}(\boldsymbol{\theta}) under constraints q_{t}^{s}(\boldsymbol{\theta})-q_{t}^{r}(\boldsymbol{\theta})\leq 0 for all indices r\neq s in \{0,\ldots,t-1\} . As for the single-constraint case, the dual and the decision functions can be explicitly written in closed form. Theorem 7 . The dual function \mathcal{D}_{st}:(\mathbb{R}^{+})^{t-1}\to\mathbb{R} to problem ( 11 ) with inner cost functions ( 7 ) and cost ( 1 ) for pruning index s using all indices r with r\neq s is given by: \mathcal{D}_{st}(\mu)=(t-s)\Bigg[-l(\mu)\mathcal{D^{*}}(\mathbf{m}(\mu))+\sum_{r\neq s}\mu_{r}\psi_{rs}\overline{Q}_{rs}\Bigg]+Q_{s}+\beta\,, with \mu=(\mu_{r})_{0\leq r0 for some chosen \mathbf{x}_{0} in the domain \Omega_{\mathbf{x}} . Notice that \mathbf{m}(\mu) is a vector if the statistics \mathbf{S}_{st} are vector-valued. The case \overline{\mathbf{S}}_{st}=\overline{\mathbf{S}}_{rs} for all r\neq s can be left apart. It corresponds to \mathbf{m}(\mu)=\overline{\mathbf{S}}_{st} and the dual \mathcal{D}_{st} becomes a linear function. The values of the decision function can be interpreted as evaluations of (t-s)^{-1}(q_{t}^{s}-(Q_{t}+\beta)) where values \overline{\mathbf{S}}_{st} and \overline{Q}_{st} are replaced by linear combinations of the available \Delta\overline{\mathbf{S}}_{rst} and \Delta\overline{Q}_{rst} . Remark 2 . With constraints of type " r0 . The shape of the domains ( \Omega_{\mathbf{x}} and \Omega_{\mu} ) depends on the underlying distribution used. Definition 3 (DUST pruning rule with multiple constraints) . We consider the dual function \mathcal{D}_{st}:\Omega_{\mu}\to\mathbb{R} and the decision function \mathbb{D}_{st}:\Omega_{\mathbf{x}}\to\mathbb{R} . At time t , we prune index s using candidate indices from a set \mathcal{R}\subset\{0,\ldots,t-1\}\setminus\{s\} to construct the dual, if there exists \mu_{0}\in\Omega_{\mu} such that \mathcal{D}_{st}(\mu_{0})>Q_{t}+\beta , or equivalently, if there exists \mathbf{x}_{0}\in\Omega_{\mathbf{x}} such that \mathbb{D}_{st}(\mathbf{x}_{0})>0 . This definition leaves implicit three important choices that must be addressed: (i) the selection of candidate indices in \mathcal{R} , (ii) the method for identifying a suitable evaluation point ( \mu_{0} or \mathbf{x}_{0} ), and (iii) a precise characterisation of the domain of definition ( \Omega_{\mu} or \Omega_{\mathbf{x}} ). Since these domains always lie within the positive orthant, solving the equation \nabla\mathbb{D}_{st}(\mathbf{x})=0 is never a valid option. For now, we address the problem using a quasi-Newton iterative algorithm or random sampling, based on a carefully chosen distribution over \Omega_{\mu} . This domain is defined through the mean parameter space \mathcal{M} wainwright2008graphical . We can show that the correct number q of constraints to consider is upper bounded by the dimension d of the parameter space \Theta\subset\mathbb{R}^{d} . 4.2 d-Strong duality Geometrically, the solution to our optimisation problem ( 11 ) lies at the intersection of at most d+1 inner functions in a parameter space of dimension d . This implies that no more than d constraints can be active at the solution point. Identifying the correct subset of q\leq d active constraints seems out of reach. Nevertheless, focusing on at most d constraints among the available t-1 is particularly appealing: in this case, the maximum of the dual function coincides with the solution of the original optimisation problem. Theorem 8 . When the dual function \mathcal{D}_{st} is built with at most d constraints for d-parametric cost functions, there is no duality gap: R_{t}^{s}:=\min_{\boldsymbol{\theta}\in\Theta_{t}^{s}(\mathcal{R})\subset\mathbb{R}^{d}}\Big\{q_{t}^{s}(\boldsymbol{\theta})\Big\}=\max_{\mu\in\Omega_{\mu}\subset\mathbb{R}^{q}}\Big\{\mathcal{D}_{st}(\mu)\Big\}\,, where \Theta_{t}^{s}(\mathcal{R}) is the feasible set defined by the q constraints with q\leq d such that q_{t}^{s}(\boldsymbol{\theta})-q_{t}^{r_{i}}(\boldsymbol{\theta})\leq 0 with r_{i}\in\mathcal{R} , i=1,\ldots,q=|\mathcal{R}| (see also ( 9 )). The proof provided in Appendix D.2 is based on the geometric interpretation of duality. We consider d arbitrary constraints. In case, qd by showing that it does not hold with d+1 constraints. This is demonstrated using a simple example of a one-dimensional Gaussian cost with three data points, (y_{1},y_{2},y_{3})=(2,-1,0) , penalty \beta=2 , and initial cost Q_{0}=-\beta . These data points yield the following functions: q_{3}^{0}(\boldsymbol{\theta})=\frac{3}{2}\theta^{2}-\theta , q_{3}^{1}(\boldsymbol{\theta})=\theta^{2}+\theta and q_{3}^{2}(\boldsymbol{\theta})=\frac{1}{2}\theta^{2}+\frac{3}{2} . In this example, the dual function (without normalising the Lagrangian parameters) for testing index 2 with indices 0 and 1 is given by: \mathcal{D}(\mu_{1},\mu_{2})=\frac{1}{2}\frac{(\mu_{1}-\mu_{2})^{2}}{1-2\mu_{1}-\mu_{2}}+\frac{3}{2}(1+\mu_{1}+\mu_{2})\,, which attains a maximum value of 2.5 . The solution to the corresponding optimisation problem is \frac{10+\sqrt{7}}{4} , as illustrated in Figure 2 . Figure 2: Illustration of the dual maximum value ( 2.5 ) and the true threshold (\frac{10+\sqrt{7}}{4}) , solution of the optimisation problem ( 11 ). We use a Gaussian cost with three points, (y_{1},y_{2},y_{3})=(2,-1,0) , penalty \beta=2 and initial cost Q_{0}=-\beta . 4.3 Gaussian case The maximum of the dual function can be explicitly expressed in closed form in the single-constraint case. When the time series contains no change points and the penalty parameter is appropriately chosen, the expression simplifies further using the relation Q_{u}=-\frac{u}{2}\|\overline{\mathbf{S}}_{0u}\|^{2} . Proposition 9 . In d -variate Gaussian model the maximum value of the dual with one constraint ( r\sqrt{\frac{s}{t}}\|\Delta\overline{\mathbf{S}}_{0st}\|\,. With d (independent) constraints, the maximum of the dual can still be obtained using basic linear algebra, provided the positivity of \mu is not enforced. The true dual solution is recovered only when the maximum lies strictly within the positive orthant. 4.4 Maximum of the non-constrained decision function The decision function admits a closed-form expression for its critical point thanks to its simple structure. However, this point may fall outside the positive orthant. Enforcing this constraint analytically remains intractable at present, necessitating an iterative optimisation algorithm. Proposition 10 . In the d -variate model, the maximum of the decision function with q constraints – when solved over the entire space \mathbb{R}^{q} rather than the constrained set \Omega_{\mathbf{x}} – i.e., \max_{\mathbf{x}\in\mathbb{R}^{q}}\mathbb{D}(\mathbf{x}) , corresponds to the solution of the following system of equations, involving \mathbf{x}\in\mathbb{R}^{q} and an instrumental variable \mathbf{y}\in\mathbb{R}^{d} : \left\{\begin{aligned} &(\Delta\overline{\mathbf{S}}_{\bullet st})\,\mathbf{x}=\nabla A(\mathbf{y})-\overline{\mathbf{S}}_{st}\,,\\ &(\Delta\overline{\mathbf{S}}_{\bullet st})^{T}\,\mathbf{y}=-\Delta\overline{Q}_{\bullet st}\,,\end{aligned}\right. where (\Delta\overline{\mathbf{S}}_{\bullet st}) is the matrix of size d\times|\mathcal{R}| gathering all vectors \Delta\overline{\mathbf{S}}_{rst} in columns and \Delta\overline{Q}_{\bullet st}\in\mathbb{R}^{|\mathcal{R}|} . If q=d and the matrix (\Delta\overline{\mathbf{S}}_{\bullet st}) is invertible, we get the solution: \mathbf{x}^{\star}=(\Delta\overline{\mathbf{S}}_{\bullet st})^{-1}\Bigg(\nabla A\Big(-((\Delta\overline{\mathbf{S}}_{\bullet st})^{T})^{-1}\Delta\overline{Q}_{\bullet st}\Big)-\overline{\mathbf{S}}_{st}\Bigg)\,. (18) The explicit solution ( 18 ) is promising, but it fails to incorporate constraint inequalities, particularly the simple positivity constraint on \mathbf{x} . Relation ( 18 ) generalises the simpler result of Equation ( 15 ). 4.5 General decision function The form of the decision function naturally leads to the introduction of a more general function that encapsulates all duality tests across all indices s . This function can take the following general form: \mathbb{GD}(\mathbf{z})=-\mathcal{D}^{*}\Big(\sum_{i=1}^{|\mathcal{T}_{t}|-1}z_{i}\overline{\mathbf{S}}_{s_{i}s_{i+1}}\Big)-\Big(\sum_{i=1}^{|\mathcal{T}_{t}|-1}z_{i}\overline{Q}_{s_{i}s_{i+1}}\Big)\,, (19) with s_{i}\in\mathcal{T}_{t} sorted in increasing order with s_{|\mathcal{T}_{t}|}=t and constraint \sum_{i=1}^{|\mathcal{T}_{t}|-1}z_{i}=1 . We recall that \mathcal{T}_{t} is the set of non-pruned indices at time t . The case where the vector \mathbf{z} is equal to \overline{\mathbf{z}}(s_{uv}) , defined as \overline{\mathbf{z}}(s_{uv})=\Big(0,\ldots,0,\frac{s_{u+1}-s_{u}}{s_{v}-s_{u}},\frac{s_{u+2}-s_{u+1}}{s_{v}-s_{u}},\ldots,\frac{s_{v}-s_{v-1}}{s_{v}-s_{u}},0,\ldots,0\Big)\,, corresponds to the standard PELT rule for pruning index s_{u} at time s_{v} as we get -\mathcal{D}^{*}(\overline{\mathbf{S}}_{s_{u}s_{v}})-\overline{Q}_{s_{u}s_{v}} . The single-constraint case of Section 3 with rt . In the DUST framework, pruning is reformulated as a (generally non-convex) optimisation problem, along with its relaxations obtained by removing constraints, which we analyse via their dual and decision representations. Pruning occurs when the computed value exceeds a specified threshold. We prove that there is no duality gap when the number of constraints does not exceed the dimension of the parameter space of the cost function derived from the exponential family. We focused on the one-parameter case, essentially corresponding to univariate data, for which an inequality-based pruning test as simple as PELT can be designed. Unlike PELT, however, this test remains highly efficient across all change-point regimes, whether or not there are many or few changes. This new approach can be viewed as a natural extension of PELT, where PELT corresponds to the dual evaluation at zero. In this simple case, DUST evaluates a decision function with a closed formula, equivalent to the maximum evaluation of the dual. FPOP-like algorithms can efficiently tackle one-parameter problems. DUST has been proven to be very efficient in our simulation study, saving a slightly greater number of indices than FPOP. FPOP’s reduced runtime can be attributed to the iterative root-finding algorithm used in handling the non-Gaussian cost during functional cost updates, where the piecewise structure is maintained through a sequence of intervals. Extensions of DUST to higher dimensions are straightforward and we still get an efficient pruning in low-dimensional settings with a single constraint. Two-parameter cases involving two constraints are particularly attractive – for instance, in Gaussian change-point detection for the mean and variance, the maximum of the decision function can be computed exactly. However, designing an optimal approach for scenarios with multiple constraints remains an open challenge. This would require new theoretical developments or an extensive simulation study. Current results are promising; we leave this direction for future work. Using a DUST pruning rule is a natural step that could be introduced in many change-point detection algorithms to efficiently prune indices in all change-point regimes. Even if the explicit maximum of the dual or decision function cannot be explicitly derived, evaluating at one point only (e.g., randomly) is a simple rule, fast to test, with high potential for pruning. The exact evaluation in the one-parameter case provides a very efficient inequality-based test; this test should be further studied with the hope of proving time complexity bounds for very generic underlying data processes. Appendix A Useful relations between means Proposition 11 . For all i\in\{1,\ldots,t-1\} we have \displaystyle tV(y_{0t})-(t-i) \displaystyle V(y_{it})-iV(y_{0i}) \displaystyle=\frac{(t-i)i}{t}\left(\overline{y}_{it}-\overline{y}_{0i}\right)^{2} (20) \displaystyle=\frac{ti}{t-i}\left(\overline{y}_{0t}-\overline{y}_{0i}\right)^{2} (21) \displaystyle=\frac{t(t-i)}{i}\left(\overline{y}_{0t}-\overline{y}_{it}\right)^{2} (22) \displaystyle=i\left(\overline{y}_{0t}-\overline{y}_{0i}\right)^{2}+(t-i)\left(\overline{y}_{0t}-\overline{y}_{it}\right)^{2} (23) Proof. For any (a,b)\in(\mathbb{N}^{*})^{2} with aq_{t}^{s_{0}}(\boldsymbol{\theta}_{0})\,,\end{aligned}\right. (26) we show that removing s_{0} could lead to an under-optimal solution for ( 6 ) and then for ( 4 ) at some data time t_{0}>t . We will choose data points after time t to create such a solution, i.e., with \argmin_{\boldsymbol{\theta}}Q_{t_{0}}(\boldsymbol{\theta}) attained by a value on function q_{t_{0}}^{s_{0}} . To that end, for all further iteration t^{\prime}>t we choose data points y_{t^{\prime}} with unitary cost: c(y_{t^{\prime}};\theta)=A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\mathbf{T}(y_{t^{\prime}})=A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\nabla A(\boldsymbol{\theta}_{0})=c(\boldsymbol{\theta})\,. Case 1: non-optimal indices s\neq s_{0}\in\{0,\ldots,t-1\} . By continuity of function Q_{t}(\cdot) there exists a ball centred on \boldsymbol{\theta}_{0} with small radius \epsilon , B(\boldsymbol{\theta}_{0},\epsilon) , such that Q_{t}(\boldsymbol{\theta})=q_{t}^{s_{0}}(\boldsymbol{\theta})0 such that: c(\boldsymbol{\theta})>c(\boldsymbol{\theta}_{0})+a\|\boldsymbol{\theta}-\boldsymbol{\theta}_{0}\|^{2}\geq c(\boldsymbol{\theta}_{0})+a\epsilon^{2}\,, for all \boldsymbol{\theta} outside B(\boldsymbol{\theta}_{0},\epsilon) . We also write \Delta=q_{t}^{s_{0}}(\boldsymbol{\theta}_{0})-Q_{t}\geq 0 . We consider T=\lceil\frac{\Delta}{a\epsilon^{2}}\rceil , then: Tc(\boldsymbol{\theta})>Tc(\boldsymbol{\theta}_{0})+aT\epsilon^{2}\geq Tc(\boldsymbol{\theta}_{0})+\Delta\,. Thus, Q_{t}+Tc(\boldsymbol{\theta})>Q_{t}+Tc(\boldsymbol{\theta}_{0})+\Delta=Tc(\boldsymbol{\theta}_{0})+q_{t}^{s_{0}}(\boldsymbol{\theta}_{0})\,, for all \boldsymbol{\theta} outside B(\boldsymbol{\theta}_{0},\epsilon) . Thus, the minimum of Q_{t_{0}}(\cdot)=Q_{t+T}(\cdot) can only be in the ball. All points outside the ball corresponding to indices s\neq s_{0} in \{0,\ldots,t-1\} are not optimal, which proves case 1. Case 2: non-optimal indices s\in\{t,\ldots,t+T\} . We first consider s=t . The second assumption in Equation ( 26 ) ( Q_{t}+\beta>q_{t}^{s_{0}}(\boldsymbol{\theta}_{0}) ) ensures that values visible for function q_{t}^{s_{0}} are not all too large and pruned by function q_{t+1}^{t} . We have: \displaystyle q_{t_{0}}^{t}(\boldsymbol{\theta})=Q_{t}+Tc(\boldsymbol{\theta})+\beta \displaystyle>q_{t}^{s_{0}}(\boldsymbol{\theta}_{0})+Tc(\boldsymbol{\theta})\,, \displaystyle\geq q_{t}^{s_{0}}(\boldsymbol{\theta}_{0})+Tc(\boldsymbol{\theta}_{0})\,, \displaystyle=q_{t+T}^{s_{0}}(\boldsymbol{\theta}_{0})=q_{t_{0}}^{s_{0}}(\boldsymbol{\theta}_{0})\,. All points on the function q_{t_{0}}^{t} are higher than q_{t_{0}}^{s_{0}}(\boldsymbol{\theta}_{0}) , consequently index t can not be optimal. For s\in\{t+1,\ldots,t+T\} , we have for index \overline{s}\frac{\beta}{n}+\mathcal{D^{*}}(Y)\,, there exists an increasing sequence of data y_{1},\ldots,y_{n} with zero pruning solving ( 4 ) which verifies: \left\{\begin{aligned} &Y=\overline{y}_{0n}=\frac{1}{n}\sum_{t=1}^{n}y_{t}\,,\\ &x=s_{t}\quad\hbox{solution of}\quad E(t)\,,\\ &y_{t}=ts_{t}-(t-1)s_{t-1}\quad t=1,\ldots,n\,,\quad\hbox{with}\quad s_{0}=0\,.\end{aligned}\right. Proof. The proof is an extension of the evidence of Proposition 2 and is based on a similar strategy. We look for data configurations for which the minimum of functions q_{t}^{s} , denoted m_{t}^{s} , are all the same: m_{n}^{0}=m_{n}^{1}=\cdots=m_{n}^{n-1} . There is no possible pruning if we find an increasing time series realising such conditions. For density from the natural exponential family, we get the relations: m_{n}^{t}=Q_{t}+(n-t)(A(\rho_{t})-\overline{y}_{tn}\cdot\rho_{t})+\beta=Q_{0}+n(A(\rho_{0})-\overline{y}_{0n}\cdot\rho_{0})+\beta=m_{n}^{0}\,, with \rho_{i}=(\nabla A)^{-1}(\overline{y}_{in}) . We have also Q_{0}=0 and Q_{t}=t(A((\nabla A)^{-1}(\overline{y}_{0t}))-\overline{y}_{0t}\cdot(\nabla A)^{-1}(\overline{y}_{0t}))+\beta as data is not spit into segments (we have only one large segment and the minimum for Q_{t}(\cdot) is attained on q_{t}^{0} ). This leads to: \frac{t}{n}\mathcal{D^{*}}(\overline{y}_{0t})+\frac{n-t}{n}\mathcal{D^{*}}\Big(\overline{y}_{tn}\Big)=\frac{\beta}{n}+\mathcal{D^{*}}(\overline{y}_{0n})\,, with \mathcal{D^{*}}(x)=x\cdot(\nabla A)^{-1}(x)-A((\nabla A)^{-1}(x)) . We get Equations ( 27 ) denoted E(t) with x=\overline{y}_{0t} , Y=\overline{y}_{0n} and relation \frac{nY-tx}{n-t}=\overline{y}_{tn} . It remains to find conditions for the existence of a solution. We define g_{t}(x)=\frac{t}{n}\mathcal{D^{*}}(x)+\frac{n-t}{n}\mathcal{D^{*}}\Big(\frac{nY-tx}{n-t}\Big) and study this function. We have: \left\{\begin{aligned} &g_{t}(Y)=\mathcal{D^{*}}(Y)\,,\\ &\nabla g_{t}(Y)=0\,,\\ &g_{t}\quad\hbox{strictly convex}\,,\\ &g_{t+1}>g_{t}\quad\hbox{except in point }\,Y\,.\\ \end{aligned}\right. Evaluation of g_{t} in Y is obvious, for the gradient we get: \nabla g_{t}(x)=\frac{t}{n}\Big(\nabla\mathcal{D^{*}}(x)-\nabla\mathcal{D^{*}}\Big(\frac{nY-tx}{n-t}\Big)\Big)\,, and then \nabla g_{t}(Y)=0 . Moreover, function g_{t} is strictly convex: \nabla^{2}g_{t}(x)=\frac{t}{n}\nabla^{2}\mathcal{D^{*}}(x)+\frac{t^{2}}{n(n-t)}\nabla^{2}\mathcal{D^{*}}\Big(\frac{nZ-tx}{n-t}\Big) ; its Hessian is definite positive since the Hessian of \mathcal{D^{*}} is. We prove g_{t+1}>g_{t} considering t as a continuous variable. We define h_{x}(t)=g_{t}(x) and we have: \nabla h_{x}(t)=\frac{1}{n}\mathcal{D^{*}}(x)-\frac{1}{n}\mathcal{D^{*}}\Big(\frac{nY-tx}{n-t}\Big)+\frac{Y-x}{n-t}\cdot\nabla\mathcal{D^{*}}\Big(\frac{nY-tx}{n-t}\Big)\,. However, by a characterisation of the strict convexity of \mathcal{D^{*}} we have for x\neq Y : \mathcal{D^{*}}(x)>\mathcal{D^{*}}\Big(\frac{nY-tx}{n-t}\Big)+n\frac{Y-x}{n-t}\cdot\nabla\mathcal{D^{*}}\Big(\frac{nY-tx}{n-t}\Big)\,, as n\frac{Y-x}{n-t}=x-\frac{nY-tx}{n-t} . This leads obviously to \nabla h_{x}(t)>0 and consequently to h_{x}(t+1)-h_{x}(t)>0 or with the g notation: g_{t+1}(x)>g_{t}(x) for all t and all x\neq Y . Now, with \Omega_{t} the convex domain of g_{t} , if \Omega_{0}=\cap_{t=1}^{n-1}\Omega_{t} is not empty, we can choose Y in \Omega_{0} . We also choose \beta such that \sup_{x\in\Omega_{0}\,,\,x\leq Y}\{g_{1}(x)\}>\frac{\beta}{n}+\mathcal{D^{*}}(Y) . By continuity of g_{t} we can find x=s_{1} solving E(1) . Using the fact that g_{2}>g_{1} and \min_{x\in\Omega_{0}}g_{2}(x)=\mathcal{D}^{*}(Y) we can now find x=s_{2}>s_{1} solving E(2) . Step by step, we build the sequence (s_{t}) corresponding to an increasing sequence of means \overline{y}_{0t} . From this point, it is easy to extract the increasing time series (y_{t}) , which concludes the proof. ∎ Notice that the multiple independent Poisson model leads to the expression ( 27 ) written as: \frac{t}{n}x\log(x)-Y\log(Y)+\Big(Y-\frac{t}{n}x\Big)\log\Big(\frac{Y-\frac{t}{n}x}{1-\frac{t}{n}}\Big)=\frac{\beta}{n}\,, where x\in\Omega_{0}=\Big(0,\frac{n}{n-1}Y\Big)=\Big(0,\frac{n}{n-1}Y_{1}\Big)\times\cdots\times\Big(0,\frac{n}{n-1}Y_{d}\Big)\subset\mathbb{R}^{d} . The set \Omega_{0} is not empty and the limit of g_{1} in zero leads to the condition for beta: \beta\leq n\log\Big(\frac{n}{n-1}\Big)\Big(\sum_{i=1}^{d}Y_{i}\Big) . This bound is much lower than usual values chosen for penalty, bounded by a \log(n) term cleynen2017model . As the Poisson model needs integer data points, the solution we get has to be approximated by \tilde{y}_{t}=\lceil y_{t}\rceil and the resulting data and functional cost Q_{n}(\cdot) have some of their indices pruned as illustrated in Figure 9 . If Y is chosen very large, the approximation improves and the obtained time series converges to the Gaussian data with no pruning. Figure 9: Poisson functional cost Q_{20}(\cdot) obtained from 20 data points. We identify easily the 20 different inner functions from which the functional cost is built. We choose Y=30 and \beta=0.995Y\log(n/(n-1)) . Due to the integer approximation for \tilde{y}_{t} , only 14 inner functions are visible in the functional cost. In Table 4 we provide the expression for A , (\nabla A)^{-1} , and its domain \Omega for a few distributions of the natural exponential family. For instance, the exponential model leads to the expression ( 27 ) written as: \log(Y)-\frac{t}{n}\log(x)-\Big(1-\frac{t}{n}\Big)\log\Big(\frac{Y-\frac{t}{n}x}{1-\frac{t}{n}}\Big)=\frac{\beta}{n}\,, where x\in\Omega_{0}=\Big(0,\frac{n}{n-1}Y\Big) . For a multiple independent exponential model, the dual \mathcal{D^{*}} can be decomposed as the sum of dual functions, one for each dimension: \mathcal{D^{*}}(x)=\sum_{i=1}^{d}\mathcal{D}^{*}_{i}(x_{i}) , with x=(x_{1},\ldots,x_{d})^{T} , justifying the following rectangular form for \Omega_{0}=\Big(0,\frac{n}{n-1}Y_{1}\Big)\times\cdots\times\Big(0,\frac{n}{n-1}Y_{d}\Big)\subset\mathbb{R}^{d} . The set \Omega_{0} is not empty, and the limit of g_{1} is infinite; thus, there is no restriction on the \beta value. A more general result for the exponential family seems possible. Still, it requires solving Equation ( 27 ) for x=\frac{1}{t}\sum_{i=1}^{t}\mathbf{T}(y_{i}) and inverting \mathbf{T} to explicit the time series (y_{t}) . This step depends on the chosen distribution and requires additional effort, which is left for further work. Figure 10: Examples with 30 data points in worst case complexity (no pruning) with Gaussian model (middle curve in black) and two examples with exponential model with two different penalty values (beta). We chose Y=1 . Appendix C Proofs of Section 3 C.1 Proof of Proposition 4 The primal Lagrangian function is given for a non-negative multiplier \mu by the relation: \displaystyle\mathcal{L}(\boldsymbol{\theta},\mu) \displaystyle=q_{t}^{s}(\boldsymbol{\theta})+\mu(q_{t}^{s}(\boldsymbol{\theta})-q_{t}^{r}(\boldsymbol{\theta}))\,, \displaystyle=(t-s)A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\mathbf{S}_{st}+Q_{s}+\beta-\mu\Big((s-r)A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\mathbf{S}_{rs}+Q_{r}-Q_{s}\Big)\,, \displaystyle=\Big((t-s)-\mu(s-r)\Big)A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\Big(\mathbf{S}_{st}-\mu\mathbf{S}_{rs}\Big)+\beta+Q_{s}-\mu(Q_{r}-Q_{s})\,. We get the critical point solving \nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta},\mu)=0 : \boldsymbol{\theta}^{*}(\mu)=(\nabla A)^{-1}\Big(\frac{\mathbf{S}_{st}-\mu\mathbf{S}_{rs}}{(t-s)-\mu(s-r)}\Big)=(\nabla A)^{-1}\Big(\mathbf{m}(\mu)\Big)\,, which leads to the proposed expression: \mathcal{L}(\boldsymbol{\theta}^{*}(\mu),\mu)=\mathcal{D}(\mu)=-\Big((t-s)-\mu(s-r)\Big)\mathcal{D^{*}}(\mathbf{m}(\mu))+\beta+(1+\mu)Q_{s}-\mu Q_{r}\,, where \mathcal{D^{*}}(x)=x\cdot(\nabla A)^{-1}(x)-A((\nabla A)^{-1}(x)) . We have the constraint: \nabla A(\boldsymbol{\theta})=\frac{\mathbf{S}_{st}-\mu\mathbf{S}_{rs}}{(t-s)-\mu(s-r)}\in\mathcal{M}^{o}\,, where \mathcal{M}^{o} is an open convex set ( brown1986fundamentals ; wainwright2008graphical ) including the value \mathbf{S}_{st} and thus \mu=0 is in the definition domain and \mu=\frac{t-s}{s-r} is the maximum feasible value (but it can be a smaller value, depending on the shape of \mathcal{M}^{o} ). The result of proposition 4 is obtained after the simple change of variable \mu\to\mu\frac{t-s}{s-r} . C.2 Proof of Theorem 6 We consider the decision function ( 14 ) defined on segment [0,x_{max}) with univariate data: \mathbb{D}(x)=-\mathcal{D}^{*}\Big(\overline{S}_{st}+x\Delta\overline{S}_{rst}\Big)-\Big(\overline{Q}_{st}+x\Delta\overline{Q}_{rst}\Big)\,, where we assume \Delta\overline{S}_{rst}\neq 0 in order to rule out the trivial linear case. Differentiating \mathbb{D} with respect to x , we obtain: -\Delta\overline{S}_{rst}(\nabla A)^{-1}(\overline{S}_{st}+x\Delta\overline{S}_{rst})-\Delta\overline{Q}_{rst}=0\,. The critical point corresponds to a maximum, since the decision function is concave. We thus obtain: x^{\star}=\frac{1}{\Delta\overline{S}_{rst}}\Big(\nabla A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)-\overline{S}_{st}\Big)\,, and \displaystyle\mathbb{D}(x^{\star}) \displaystyle=-\mathcal{D}^{*}\Big(\nabla A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)\Big)-\Big(\overline{Q}_{st}+x^{*}\Delta\overline{Q}_{rst}\Big)\,, \displaystyle=-\nabla A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)+A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)-\Big(\overline{Q}_{st}+\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big(\nabla A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)-\overline{S}_{st}\Big)\Big)\,, \displaystyle=A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)-\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)\overline{S}_{st}-\overline{Q}_{st}\,. We notice that: (t-s)\mathbb{D}(x^{\star})=(t-s)A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)-\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)S_{st}-(Q_{t}-Q_{s}) and the pruning occurs when \mathbb{D}(x^{\star})>0 that is when: q_{t}^{s}\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)=(t-s)A\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)-\Big(-\frac{\Delta\overline{Q}_{rst}}{\Delta\overline{S}_{rst}}\Big)S_{st}+Q_{s}+\beta>Q_{t}+\beta\,. If x^{\star}<0 or x^{\star}>x_{max} , the decision function is evaluated in 0 or x_{max} , respectively. In case x^{\star}<0 , the test is exactly the PELT inequality pruning test: q_{t}^{s}\Big((\nabla A)^{-1}(\overline{S}_{st})\Big)>Q_{t}+\beta . C.3 Dual for the change-in-mean-and-variance problem We use the canonical form of the exponential family, for (\theta_{1},\theta_{2})\in\mathbb{R}\times\mathbb{R}^{-} : c(y_{st};[\theta_{1};\theta_{2}])=(t-s)A(\theta_{1},\theta_{2})-\theta_{1}\Big(\sum_{i=s+1}^{t}y_{i}\Big)-\theta_{2}\Big(\sum_{i=s+1}^{t}y_{i}^{2}\Big)\,, (28) where A(\theta_{1},\theta_{2})=-\frac{\theta_{1}^{2}}{4\theta_{2}}+\frac{1}{2}\log\Big(-\frac{1}{2\theta_{2}}\Big)\,. Its gradient is: \nabla A(\theta)=\Big(-\frac{\theta_{1}}{2\theta_{2}},\frac{\theta_{1}^{2}}{4\theta_{2}^{2}}-\frac{1}{2\theta_{2}}\Big)\,, and \nabla A(\theta)=(u,v)\iff(\theta_{1},\theta_{2})=\Big(-\frac{u}{u^{2}-v},\frac{1}{2(u^{2}-v)}\Big)\,. The minimum cost is then c(y_{st})=\frac{t-s}{2}\Big(1+\log(v-u^{2})\Big)\quad\hbox{with}\quad u=\overline{y}_{st}\quad v=\overline{y_{st}^{2}}\,. (29) We obtain the dual, considering the case r0 , which we write after simplification as: -(\Delta\overline{S}_{rst})^{2}x^{2}+(V(y_{st})-V(y_{rs})-(\Delta\overline{S}_{rst})^{2}))x+V(y_{st})>0\,. We have the following roots, between which the polynomial takes positive values: \displaystyle x_{\pm} \displaystyle=\frac{V(y_{st})-V(y_{rs})-(\Delta\overline{S}_{rst})^{2}}{2(\Delta\overline{S}_{rst})^{2}}\pm\sqrt{\frac{\Big(V(y_{st})-V(y_{rs})-(\Delta\overline{S}_{rst})^{2}\Big)^{2}+4(\Delta\overline{S}_{rst})^{2}V(y_{st})}{4(\Delta\overline{S}_{rst})^{4}}} \displaystyle=x_{0}+\sqrt{x_{0}^{2}+\frac{V(y_{st})}{(\Delta\overline{S}_{rst})^{2}}}\,, where x_{0}=\frac{1}{2}\Big(\frac{V(y_{st})-V(y_{rs})}{(\Delta\overline{S}_{rst})^{2}}-1\Big)\,. To get the argument of the maximum, we differentiate \mathbb{D} to search for the critical point, which yields: \frac{1}{2}\frac{\Delta\overline{S_{rst}^{2}}-2(\overline{S}_{st}+x\Delta\overline{S}_{rst})}{\overline{S^{2}_{st}}+x\Delta\overline{S_{rst}^{2}}-(\overline{S}_{st}+x\Delta\overline{S}_{rst})^{2}}-\Delta\overline{Q}_{rst}=0 or \Delta\overline{S_{rst}^{2}}-2(\overline{S}_{st}+x\Delta\overline{S}_{rst})-2\Delta\overline{Q}_{rst}(\overline{S^{2}_{st}}+x\Delta\overline{S_{rst}^{2}}-(\overline{S}_{st}+x\Delta\overline{S}_{rst})^{2})=0\,. After simple computations we get the desired result when \Delta\overline{Q}_{rst}\neq 0 . Appendix D Proofs of Section 4 D.1 Proof of Theorem 7 The proof is similar to the proof with a single constraint. We differentiate in \boldsymbol{\theta} the Lagrangian function \mathcal{L}(\boldsymbol{\theta},\overline{\mu})=q_{t}^{s}(\boldsymbol{\theta})+\sum_{r\neq s}\overline{\mu}_{r}(q_{t}^{s}(\boldsymbol{\theta})-q_{t}^{r}(\boldsymbol{\theta})) with q_{t}^{r}(\boldsymbol{\theta})=Q_{r}+(t-r)A(\boldsymbol{\theta})-\boldsymbol{\theta}\cdot\mathbf{S}_{rt}+\beta and inject its solution \boldsymbol{\theta}^{*}(\overline{\mu})=(\nabla A)^{-1}(\mathbf{m}(\overline{\mu})) to get \mathcal{D}_{st}(\overline{\mu})=\mathcal{L}(\boldsymbol{\theta}(\overline{\mu}),\overline{\mu}) . The final result comes after the change of variable \overline{\mu}_{r}=\mu_{r}\frac{t-s}{|s-r|} . The decision function is obtained by the simple change of variable x_{r}=\mu_{r}/l(\mu) . D.2 Proof of Theorem 8 For simplicity, we rename the indices as follows: s\to 0 , r_{i}\to i for i=1,\ldots,d , skip the t variable, and move the upper indices to a lower position. Therefore we solve: \min_{\boldsymbol{\theta}\in\Theta}q_{0}(\boldsymbol{\theta}) under constraints q_{0}(\boldsymbol{\theta})-q_{i}(\boldsymbol{\theta})\leq 0 for all indices i\in\{1,\ldots,d\} . We also use the vector function notation q=(q_{1},\ldots,q_{d}) . The proof for strong duality relies on the following three lemmas. Lemma 2 . We consider a function f:\mathbb{R}^{d}\to\mathbb{R} for which the evaluation at point c\in\mathbb{R}^{p} can only be done through an auxiliary bijection g:\mathbb{R}^{p}\to\mathbb{R}^{p} such that there exists \boldsymbol{\theta}_{c}\in\mathbb{R}^{p} with g(\boldsymbol{\theta}_{c})=c . Function f is convex if for any a,b in the convex domain \Omega of f there exists a parametric curve g_{ab} joining in a straight line the points a to b such that g_{ab}(\boldsymbol{\theta}_{(1-\alpha)a+\alpha b})=(1-\alpha)a+\alpha b and with notation h(\alpha)=\boldsymbol{\theta}_{(1-\alpha)a+\alpha b} ( h:(0,1)\to\mathbb{R}^{p} ) we have: \nabla(fg_{ab}h(0))\cdot(h^{\prime}(0))\leq fg_{ab}h(1)-fg_{ab}h(0)\,. It’s a generalisation of a well-known result. Function f:\mathbb{R}^{p}\to\mathbb{R} is convex if for all a,b in its domain: \nabla f(a)\cdot(b-a)\leq f(b)-f(a) . When g_{ab} is the identity, we return to this result. Proof. (of Lemma 2 ) The convexity of f is the same as the convexity of fgh by definition of fgh . Using the definition of convexity for fgh , we have for all \alpha\in(0,1) : fgh(\alpha)\leq(1-\alpha)fgh(0)+\alpha fgh(1)\quad\hbox{or}\quad fgh(\alpha)-fgh(0)\leq\alpha(fgh(1)-fgh(0))\,. Dividing by \alpha and taking the limit \alpha\to 0 : \nabla(fgh(0))\cdot(h^{\prime}(0))\leq fgh(1)-fgh(0) . ∎ Lemma 3 . Consider the d constraints. Let \boldsymbol{\theta}_{0} be in \mathbb{R}^{d} such that (q_{0}-q)(\boldsymbol{\theta}_{0})=c with c\in\mathbb{R}^{p} , then \boldsymbol{\theta}_{0}\in\{x^{+}u+w,x^{-}u+w\} with x^{+},x^{-}\in\mathbb{R} and u,w\in\mathbb{R}^{p} . They are the two intersection points between a straight line and a level curve (q_{0}-q_{1})=c_{1} . Proof. (of Lemma 3 ) We have for i=1,\ldots,p : (q_{0}-q_{i})(\boldsymbol{\theta}_{0})=(r_{i}-s)A(\boldsymbol{\theta}_{0})-\boldsymbol{\theta}_{0}\cdot\mathbf{S}_{r_{i}s}+Q_{s}-Q_{r_{i}}=c_{i}\,, or A(\boldsymbol{\theta}_{0})-\boldsymbol{\theta}_{0}\cdot\overline{\mathbf{S}}_{r_{i}s}=\frac{c_{i}}{r_{i}-s}+\frac{Q_{r_{i}}-Q_{s}}{r_{i}-s}\,. Combining equations with indices i and i+1 for i=1,\ldots,p-1 to remove A(\boldsymbol{\theta}_{0}) we get: \boldsymbol{\theta}_{0}\cdot(\overline{\mathbf{S}}_{r_{i+1}s}-\overline{\mathbf{S}}_{r_{i}s})=\frac{c_{i}}{r_{i}-s}-\frac{c_{i+1}}{r_{i+1}-s}+\frac{Q_{r_{i}}-Q_{s}}{r_{i}-s}-\frac{Q_{r_{i+1}}-Q_{s}}{r_{i+1}-s}\,. With the assumption that the points \overline{\mathbf{S}}_{r_{i}s} are in general position (no redundant equation or unsolvable system), we get \boldsymbol{\theta}_{0}(x)=xu+w for potential solutions where x\in\mathbb{R} is a parameter and u,w\in\mathbb{R}^{p} are fixed values. As we considered that a solution exists and as A is convex, this straight line intersects in two points the level curve (q_{0}-q_{1})=c_{1} (counted with their multiplicity). ∎ Remark 3 . Using relation (\overline{\mathbf{S}}_{r_{i+1}s}-\overline{\mathbf{S}}_{r_{i}s})\cdot u=0 , we easily get that for all indices i and a fixed intersection value \boldsymbol{\theta}_{0} we have expressions (\nabla A(\boldsymbol{\theta}_{0})-\overline{\mathbf{S}}_{r_{i}s})\cdot u is a constant. Lemma 4 . The orthogonal projection of \mathcal{O} on its last d variables ( \mathcal{O}\cdot(\emptyset,\mathbb{R}^{d}) ) is a convex object. Proof. (of Lemma 4 ) Let \boldsymbol{\theta}_{a} and \boldsymbol{\theta}_{b} be in \mathbb{R}^{d} such that (q_{0}-q)(\boldsymbol{\theta}_{a})=a and (q_{0}-q)(\boldsymbol{\theta}_{b})=b with a,b\in\mathbb{R}^{p} . We need to prove that for all \alpha\in(0,1) , there exists \boldsymbol{\theta}_{\alpha} such that (q_{0}-q)(\boldsymbol{\theta}_{\alpha})=(1-\alpha)a+\alpha b . Using Lemma 3 there are only two points for each \alpha (counting multiplicity) in \mathcal{O}\cdot(\emptyset,\mathbb{R}^{d}) solving the equations: x^{-}(\alpha)u+\alpha v+w and x^{+}(\alpha)u+\alpha v+w . They intersect in \alpha=0 and \alpha=1 the level curve (q_{0}-q_{1})=a and (q_{0}-q_{1})=b , respectively. We must show that the straight line also intersects (q_{0}-q_{1})=(1-\alpha)a+\alpha b . We increase by one the size of the problem, considering \alpha to be one of the variables. the plane xu+\alpha v+w intersect f(\boldsymbol{\theta},\alpha)=(q_{0}-q_{1})(\boldsymbol{\theta})-\alpha(b-a)-a in \alpha=0 and \alpha=1 . f(\boldsymbol{\theta},\alpha)\leq 0 or f(\boldsymbol{\theta},\alpha)\geq 0 is convex and bounded. Thus, the intersection also occurs for all \alpha in (0,1) . ∎ Proof of the Theorem : We need to prove the convexity of the epigraph, that is, for the lowest values of q_{0} for points on the projection \mathcal{O}\cdot(\emptyset,\mathbb{R}^{d}) . This is not equivalent to the convexity of q_{0} as the evaluation is done here on the initial parameter’s functions (the constraint values) instead of \boldsymbol{\theta} . Let \boldsymbol{\theta}_{a} and \boldsymbol{\theta}_{b} be in \mathbb{R}^{d} and a,b be in \mathcal{O}\cdot(\emptyset,\mathbb{R}^{d}) such that (q_{0}-q)(\boldsymbol{\theta}_{a})=a and (q_{0}-q)(\boldsymbol{\theta}_{b})=b . We have: h^{-}:\mathbb{R}\to\mathbb{R}^{p},\alpha\mapsto x^{-}(\alpha)u+\alpha v+w\,,\quad h^{+}:\mathbb{R}\to\mathbb{R}^{p},\alpha\mapsto x^{+}(\alpha)u+\alpha v+w\,. such that \boldsymbol{\theta}_{a}\in\{h^{-}(0),h^{+}(0)\} , \boldsymbol{\theta}_{b}\in\{h^{-}(1),h^{+}(1)\} and g(h^{-}(\alpha))=g(h^{+}(\alpha))=(1-\alpha)a+\alpha b . Function h^{-} corresponds to the solution for q_{0} returning the smallest value: q_{0}(g_{ab}(h^{-}(\alpha))\leq q_{0}(g_{ab}(h^{+}(\alpha))\,. h^{-} and h^{+} can be discontinuous, however h^{-} is differentiable in 0 (no jump in minimum value at 0 ). Applying Lemma 2 with h=h^{-} (and x=x^{-} ) we need to prove: \nabla(fg_{ab}h(0))\cdot(h^{\prime}(0))\leq fg_{ab}h(1)-fg_{ab}h(0)\,. That is: \Big(\nabla A(x(0)u+w)-\overline{\mathbf{S}}_{st}\Big)\cdot\Big(\frac{dx}{d\alpha}(0)u+v\Big)\leq\frac{q_{0}(\boldsymbol{\theta}_{b})-q_{0}(\boldsymbol{\theta}_{a})}{t-s} (30) Notice that we decide to choose u such that \Big(\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st}\Big)\cdot u\geq 0 (as u can be replaced by -u if we have the wrong sign). We can also derive two interesting equalities. We consider the intersection between the line and the level curve (see Lemma 3 ), which also intersects the curves q_{0}=q_{0}(\boldsymbol{\theta}_{a}) and q_{0}=q_{0}(\boldsymbol{\theta}_{b}) . For \alpha=0 and \alpha=1 we get four relations: \left\{\begin{aligned} &A(\boldsymbol{\theta}_{a})-\boldsymbol{\theta}_{a}\cdot\overline{\mathbf{S}}_{st}+\frac{Q_{s}+\beta}{t-s}=\frac{q_{0}(\boldsymbol{\theta}_{a})}{t-s}\,,\\ &A(\boldsymbol{\theta}_{b})-\boldsymbol{\theta}_{b}\cdot\overline{\mathbf{S}}_{st}+\frac{Q_{s}+\beta}{t-s}=\frac{q_{0}(\boldsymbol{\theta}_{b})}{t-s}\,,\\ &A(\boldsymbol{\theta}_{a})-\boldsymbol{\theta}_{a}\cdot\overline{\mathbf{S}}_{s_{1}s}-\frac{Q_{s_{1}}-Q_{s}}{s_{1}-s}=\frac{(q_{0}-q_{1})(\boldsymbol{\theta}_{a})}{s_{1}-s}\,,\\ &A(\boldsymbol{\theta}_{b})-\boldsymbol{\theta}_{b}\cdot\overline{\mathbf{S}}_{s_{1}s}-\frac{Q_{s_{1}}-Q_{s}}{s_{1}-s}=\frac{(q_{0}-q_{1})(\boldsymbol{\theta}_{b})}{s_{1}-s}\,,\end{aligned}\right. leading to relation: (\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st})\cdot(\boldsymbol{\theta}_{b}-\boldsymbol{\theta}_{a})=\frac{q_{0}(\boldsymbol{\theta}_{b})-q_{0}(\boldsymbol{\theta}_{a})}{s_{1}-s}-\frac{(q_{0}-q_{1})(\boldsymbol{\theta}_{b})-(q_{0}-q_{1})(\boldsymbol{\theta}_{a})}{s_{1}-s}\,. (31) The second relation is the dynamic equation for points x^{\pm}(\alpha)u+\alpha v+w . We use relations: (q_{0}-q_{1})(x(0)u+w)=(q_{0}-q_{1})(\boldsymbol{\theta}_{a}) and (q_{0}-q_{1})(x(\epsilon)u+\epsilon v+w)=(1-\epsilon)(q_{0}-q_{1})(\boldsymbol{\theta}_{a})+\epsilon(q_{0}-q_{1})(\boldsymbol{\theta}_{b}) We derive, taking the difference with \epsilon\to 0 : \Big(\nabla A(x(0)u+w)-\overline{\mathbf{S}}_{s_{1}s}\Big)\cdot(\frac{dx}{d\alpha}(0)u+v)=\frac{(q_{0}-q_{1})(\boldsymbol{\theta}_{b})-(q_{0}-q_{1})(\boldsymbol{\theta}_{a})}{s_{1}-s}\,. (32) Using ( 31 ) and ( 32 ) we can now reformulate ( 30 ) as: \Big(\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st}\Big)\cdot(\frac{dx}{d\alpha}(0)u+v)\leq(\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st})\cdot(\boldsymbol{\theta}_{b}-\boldsymbol{\theta}_{a})\,, or \frac{dx}{d\alpha}(0)\Big(\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st}\Big)\cdot u\leq(x(1)-x(0))(\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st})\cdot u\,. As we set \Big(\overline{\mathbf{S}}_{s_{1}s}-\overline{\mathbf{S}}_{st}\Big)\cdot u\geq 0 , this gives us the relation: \nabla x(0)\cdot(1-0)\leq x(1)-x(0)\,, to be proven. This is true if \alpha\mapsto x(\alpha) is convex. Generalising Equation ( 32 ) for all \alpha\in(0,1) we get: \Big(\nabla A(x(\alpha)u+\alpha v+w)-\overline{\mathbf{S}}_{s_{1}s}\Big)\cdot(\frac{dx}{d\alpha}(\alpha)u+v)=\frac{(q_{0}-q_{1})(\boldsymbol{\theta}_{b})-(q_{0}-q_{1})(\boldsymbol{\theta}_{a})}{s_{1}-s}\,, and differentiating in \alpha : h^{\prime}(\alpha)\cdot\Big(\nabla A^{2}(h(\alpha))\Big)\cdot h^{\prime}(\alpha)=-\frac{d^{2}x}{d\alpha^{2}}(\alpha)\Big(\nabla A(h(\alpha))-\overline{\mathbf{S}}_{s_{1}s}\Big)\cdot u\,. However, \Big(\nabla A(h(\alpha))-\overline{\mathbf{S}}_{s_{1}s}\Big)\cdot u<0 , knowing the choice of u we made and Remark 3 . We exclude the nullity case as it is possible only for a point on the boundary of \mathcal{O}\cdot(\emptyset,\mathbb{R}^{d}) . We can restrict points a and b to be in the interior and still prove the same result. Using the convexity of A , we obtain \frac{d^{2}x}{d\alpha^{2}}(\alpha)>0 and we find that \alpha\mapsto x(\alpha) is convex. D.3 Proof of Proposition 10 The gradient of \mathcal{D}^{*} is equal to (\nabla A)^{-1} which leads to relation: \nabla\mathcal{D}^{*}\Big(\overline{\mathbf{S}}_{st}+\sum_{r\neq s}x_{r}\Delta\overline{\mathbf{S}}_{rst}\Big)=(\Delta\overline{\mathbf{S}}_{\bullet st})^{T}\Big((\nabla A)^{-1}\Big(\overline{\mathbf{S}}_{st}+\sum_{r\neq s}x_{r}\Delta\overline{\mathbf{S}}_{rst}\Big)\Big)\,. We introduce notation \mathbf{y}=(\nabla A)^{-1}\Big(\overline{\mathbf{S}}_{st}+\sum_{r\neq s}x_{r}\Delta\overline{\mathbf{S}}_{rst}\Big) which leads to the first system of equations: (\Delta\overline{\mathbf{S}}_{\bullet st})\,\mathbf{x}=\nabla A(\mathbf{y})-\overline{\mathbf{S}}_{st} . With such notation, the critical point (the maximum, function \mathbb{D} being concave), is the solution of \nabla\mathbb{D}(\mathbf{x})=0 and gives: -(\Delta\overline{\mathbf{S}}_{\bullet st})^{T}\mathbf{y}-\Delta\overline{Q}_{\bullet st}=0\,. Appendix E Quadratic cost function E.1 The General case We consider the following functions of the type: q_{t}^{s}(\theta_{1},\theta_{2})=A_{st}\theta_{1}^{2}+2B_{st}\theta_{1}\theta_{2}+C_{st}\theta_{2}^{2}+2D_{st}\theta_{1}+2E_{st}\theta_{2}+F_{st}\,. A natural restriction is to study the case when all the cost functions have a unique finite minimum value and a unique argument for the minimum. Thus, we can define the cost of a segment and associate with it a non-ambiguous parameter value. For any function q_{t}^{k} it is equivalent to condition A_{kt}C_{kt}-B_{kt}^{2}>0 with A_{kt}>0 (such functions are then strictly convex). With the Lagrangian with one constraint given by inequality q_{t}^{s}-q_{t}^{r}\leq 0 (always considering that r0 and \omega_{2}^{2}>0 and we consider that \omega_{1}^{2}\neq\omega_{2}^{2} . The discriminant is also positive: 4(\Delta^{2}-\omega_{1}^{2}\omega_{2}^{2})>0 . The maximal value is then given by: \mu_{max}=\left\{\begin{aligned} &\frac{\Delta-\omega_{1}^{2}-\sqrt{\Delta^{2}-\omega_{1}^{2}\omega_{2}^{2}}}{\omega_{1}^{2}-2\Delta+\omega_{2}^{2}}\,,\quad&\hbox{if}\quad 2\Delta>\omega_{1}^{2}+\omega_{2}^{2}&\,,\\ &&\hbox{or}\quad 2\Delta<\omega_{1}^{2}+\omega_{2}^{2}\,,\,&\omega_{1}^{2}<\Delta\,,\\ &\frac{\omega_{1}^{2}}{\omega_{2}^{2}-\omega_{1}^{2}}\,,\quad&\hbox{if}\quad 2\Delta=\omega_{1}^{2}+\omega_{2}^{2}\,,\,&\omega_{1}^{2}<\Delta\,,\\ &+\infty\,,\quad&\hbox{if}\quad 2\Delta\leq\omega_{1}^{2}+\omega_{2}^{2}\,,&\,\omega_{1}^{2}>\Delta\,.\\ \end{aligned}\right. (34) Proof. First, we propose that the discriminant is positive. We can write: \Delta^{2}-\omega_{1}^{2}\omega_{2}^{2}=A_{st}C_{st}\Big(A_{st}C_{st}(d_{C}-d_{A})^{2}+4B^{2}_{st}d_{A}d_{C}\Big)\,, with d_{A}=\frac{B_{st}}{B_{rt}}-\frac{A_{st}}{A_{rt}}\quad\hbox{and}\quad d_{C}=\frac{B_{st}}{B_{rt}}-\frac{C_{st}}{C_{rt}}\,. As we have A_{st}C_{st}>B^{2}_{st} and (d_{C}-d_{A})^{2}>-4d_{A}d_{C} , multiplying these two inequalities give us a positive determinant. Second, we determine the smallest positive root by studying the sign of the product of the roots, which is equal to \omega_{1}^{2}(\omega_{1}^{2}-2\Delta+\omega_{2}^{2})^{-1} . With 2\Delta>\omega_{1}^{2}+\omega_{2}^{2} , the product is negative and the biggest root is the only one positive. If on the contrary 2\Delta<\omega_{1}^{2}+\omega_{2}^{2} , the roots have the same sign and the sign of \Delta-\omega_{1}^{2} determines whether both roots are positive (in that case the smallest root is the solution) or both negative (in that case \mu_{max} is infinite). The degenerated case with no quadratic term is obvious. ∎ It is also possible to consider the quadratic form in dimension p more than 2 . However, determining the boundary for \mu is challenging to determine explicitly: this is the first mu value such that \det(A-\mu B)=0 with A and B two p\times p matrices. E.2 Changes in simple regression A direct application of the previous result is the problem of detecting a change point in simple regression. In this setting, we gather two-dimensional (x_{t},y_{t}) points over time. At a change location, the linear bound linking x_{t} and y_{t} changes. To be specific, this corresponds to a model with data points (x_{t},y_{t}) generated by a succession of simple linear models (choosing x_{t} and then getting the response y_{t} through the regression) y_{t}=a_{i}x_{t}+b_{i}+\epsilon_{t}\,,\quad t=\tau_{i}+1,\dots,\tau_{i+1}\,,\quad i=0,\dots,K\,, with t\mapsto a_{t} and t\mapsto b_{t} piecewise constant time series and \epsilon_{t}\sim\mathcal{N}(0,\sigma^{2}) identically and independently distributed. The vector (\tau_{1},\ldots,\tau_{K}) of strictly increasing integers subdivides the time-series into K+1 consecutive segments with natural notations \tau_{0}=0 and \tau_{K+1}=n . Using the maximum likelihood approach, we see that this leads to considering the cost function q_{t}^{s}(\theta_{1},\theta_{2})=Q_{s}+c(y_{st};[\theta_{1};\theta_{2}])+\beta with \begin{split}c(y_{st};[\theta_{1};\theta_{2}])&=\sum_{j=s+1}^{t}(y_{j}-(\theta_{1}x_{j}+\theta_{2}))^{2}\,,\\ &=(t-s)\Big(\overline{x_{st}^{2}}\theta_{1}^{2}+2\overline{x}_{st}\theta_{1}\theta_{2}+\theta_{2}^{2}-2\overline{(xy)_{st}}\theta_{1}-2\overline{y}_{st}\theta_{2}+\overline{y_{st}^{2}}\Big)\,.\end{split} Identifying the coefficients term by term, we introduce the notations: q_{t}^{s}(\theta_{1},\theta_{2})=A_{st}\theta_{1}^{2}+2B_{st}\theta_{1}\theta_{2}+C_{st}\theta_{2}^{2}+2D_{st}\theta_{1}+2E_{st}\theta_{2}+F_{st}\,. Writing as previously A(\mu)=A_{st}+\mu(A_{st}-A_{rt}),\ldots we obtain the dual function in expression ( 33 ). Appendix F Examples of decision functions We consider the function q_{t}^{s} constrained by the function q_{t}^{r} . We recall the shape of the decision function: \mathbb{D}_{st}(\mathbf{x})=-\mathcal{D}^{*}\Big(\overline{\mathbf{S}}_{st}+\sum_{r\neq s}x_{r}\Delta\overline{\mathbf{S}}_{rst}\Big)-\Big(\overline{Q}_{st}+\sum_{r\neq s}x_{r}\Delta\overline{Q}_{rst}\Big)\,. Convex functions \mathcal{D^{*}} as well as their associated domain \Omega_{\mathbf{x}} are distribution-dependent. The domain is also data-dependent. We give their form on many examples from the exponential family in Table 3 . Function \mathcal{D^{*}} can be expressed through the log-partition function A as \mathcal{D^{*}}(x)=x(\nabla A)^{-1}(x)-A((\nabla A)^{-1}(x)) . We consider the single-constraint case with support [0,x_{max}) and notation \mathcal{D}^{*}(\overline{\mathbf{S}}_{st}+x\Delta\overline{\mathbf{S}}_{rst})=\mathcal{D}^{*}(\sigma_{1}+x(\sigma_{1}-\sigma_{2})) in Table 3 . Notice that we address here the case rs , the bound is always x_{max}=1 . Details for computing \mathcal{D^{*}} are given in Table 4 . More details on the properties of \mathcal{D^{*}} can be found in Chapter 3 of wainwright2008graphical . Table 3: Univariate case. Distribution, their corresponding \mathcal{D}^{\star} function and maximum x value in case r\sigma_{2} ) Gauss \frac{1}{2}x^{2} +\infty +\infty Exponential -\log x-1 -\frac{\sigma_{1}}{\sigma_{1}-\sigma_{2}} +\infty Poisson x(\log x-1) -\frac{\sigma_{1}}{\sigma_{1}-\sigma_{2}} +\infty Geometric (x-1)\log(x-1)-x\log x -\frac{\sigma_{1}-1}{\sigma_{1}-\sigma_{2}} +\infty Bernoulli/Binomial x\log x+(1-x)\log(1-x) -\frac{\sigma_{1}}{\sigma_{1}-\sigma_{2}} \frac{1-\sigma_{1}}{\sigma_{1}-\sigma_{2}} Negative Binomial x\log x-(1+x)\log(1+x) -\frac{\sigma_{1}}{\sigma_{1}-\sigma_{2}} +\infty Variance -\frac{1}{2}(\log x+1) -\frac{\sigma_{1}}{\sigma_{1}-\sigma_{2}} +\infty In the Gaussian case, data is standardised: divided by the estimated standard deviation. In binomial and negative binomial cases, data is divided by the estimated number of trials and successes (respectively) so that the logarithmic values can be computed. Remark 4 . From Table 3 we can easily write down the decision functions in an independent multivariate setting. In that case, we sum over all dimensions the function \mathcal{D}^{\star} obtained for each univariate time series. Table 4: Functions A and (\nabla A)^{-1} used to compute \mathcal{D^{*}}(x)=x(\nabla A)^{-1}(x)-A((\nabla A)^{-1}(x)) for some standard distributions in exponential family. Distribution y\mapsto A(y) x\mapsto(\nabla A)^{-1}(x) x\in\Omega Gauss \frac{1}{2}y^{2} x \Omega=\mathbb{R} Exponential -\log(-y) -\frac{1}{x} \Omega=(0,+\infty) Poisson \exp(y) \log(x) \Omega=(0,+\infty) Geometric -\log(e^{-y}-1) \log\Big(\frac{x-1}{x}\Big) \Omega=(1,+\infty) Bernoulli/Binomial \log(1+e^{y}) \log\Big(\frac{x}{1-x}\Big) \Omega=(0,1) Negative Binomial -\log(1-e^{y}) \log\Big(\frac{x}{1+x}\Big) \Omega=(0,+\infty) Variance -\frac{1}{2}\log(-2y) -\frac{1}{2x} \Omega=(0,+\infty) For the sake of completeness, we provide details about the limiting cases, defined by the limit values for \overline{\mathbf{S}}_{st} or \overline{\mathbf{S}}_{rs} , with \overline{\mathbf{S}}_{st}\neq\overline{\mathbf{S}}_{rs} , on the boundary of \Omega . These limit values are denoted \partial\Omega (equal to 0 or 1 with the given distributions in Table 4 ). If \overline{\mathbf{S}}_{st}=\partial\Omega , then x_{max}=0 for all distributions (except for Gauss). If \overline{\mathbf{S}}_{rs}=\partial\Omega , then x_{max}=+\infty except in the case Bernoulli/Binomial. Remark 5 . If \overline{\mathbf{S}}_{st}=\overline{\mathbf{S}}_{rs}=\mathbf{S}\in\Omega\cup\partial\Omega for all r indices used, the decision function is linear with maximum in x=0 or x=+\infty , depending on the sign of the slope. Appendix G Additional simulations To be determined. This section will be updated post-publication. Competing interests No competing interest is declared.