Mixed-Integer Programming for Change-point Detection

• URL: http://arxiv.org/abs/2602.11947v1
• Date: Thu, 12 Feb 2026 13:43:56 GMT
• Title: Mixed-Integer Programming for Change-point Detection
• Authors: Apoorva Narula, Santanu S. Dey, Yao Xie,
• Abstract summary: We present a new mixed-integer programming (MIP) approach for offline multiple change-point detection.<n>We extend the framework to two settings of active research interest: (i) multidimensional PWL models with shared change-points, and (ii) sparse change-point detection.
• Score: 8.644610122423993
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a new mixed-integer programming (MIP) approach for offline multiple change-point detection by casting the problem as a globally optimal piecewise linear (PWL) fitting problem. Our main contribution is a family of strengthened MIP formulations whose linear programming (LP) relaxations admit integral projections onto the segment assignment variables, which encode the segment membership of each data point. This property yields provably tighter relaxations than existing formulations for offline multiple change-point detection. We further extend the framework to two settings of active research interest: (i) multidimensional PWL models with shared change-points, and (ii) sparse change-point detection, where only a subset of dimensions undergo structural change. Extensive computational experiments on benchmark real-world datasets demonstrate that the proposed formulations achieve reductions in solution times under both $\ell_1$ and $\ell_2$ loss functions in comparison to the state-of-the-art.

Related papers

• Towards a Unified Analysis of Neural Networks in Nonparametric Instrumental Variable Regression: Optimization and Generalization [66.08522228989634]
  We establish the first global convergence result of neural networks for two stage least squares (2SLS) approach in nonparametric instrumental variable regression (NPIV)<n>This is achieved by adopting a lifted perspective through mean-field Langevin dynamics (MFLD)
  arXiv  Detail & Related papers  (2025-11-18T17:51:17Z)
• Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions [4.566850249315913]
  This paper addresses the mixed-integer programming (MILP) formulation for continuous piecewise linear (CPWL) approximations of data sets in arbitrary dimensions.
  arXiv  Detail & Related papers  (2025-08-13T00:00:09Z)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  We introduce a novel global optimization method for align partially overlapping point sets.<n>Our method exhibits superior robustness to non-rigid deformations, positional noise and outliers.<n> Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to outliers.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Inferring Change Points in High-Dimensional Regression via Approximate Message Passing [13.296007624690974]
  We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations.<n>We rigorously characterize its performance in the high-dimensional limit where the number of parameters $p$ is proportional to the number of samples $n$.<n>We show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit.
  arXiv  Detail & Related papers  (2024-04-11T15:57:12Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  Contextual decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. CMDPs serve as an important framework to model many real-world applications with time-varying environments. We study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights.
  arXiv  Detail & Related papers  (2024-02-05T03:25:04Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
  This paper proposes a novel surrogate-based global optimization algorithm to solve linearly constrained mixed-variable problems.<n>The proposed approach is based on constructing a piecewise affine surrogate of the objective function over feasible samples.<n>The two algorithms are evaluated on several unconstrained and constrained mixed-variable benchmark problems.
  arXiv  Detail & Related papers  (2023-02-09T15:04:35Z)
• Robust Multi-view Registration of Point Sets with Laplacian Mixture Model [25.865100974015412]
  We propose a novel probabilistic generative method to align multiple point sets based on the heavy-tailed Laplacian distribution. We demonstrate the advantages of our method by comparing it with representative state-of-the-art approaches on benchmark challenging data sets.
  arXiv  Detail & Related papers  (2021-10-26T14:49:09Z)
• Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees [1.0660480034605242]
  This article provides a new analytically tractable and fully frequentist framework to characterize and implement regression trees. The connection to regression trees is made by a high dimensional model with dynamic mean vectors over multi-dimensional change axes. Results are obtained under a high dimensional scaling $slog2 p=o(T_wT_h), where $p$ is the response dimension, $s$ is a sparsity parameter, and $T_w,T_h$ are sampling periods along change axes.
  arXiv  Detail & Related papers  (2021-05-20T20:29:48Z)
• InverseForm: A Loss Function for Structured Boundary-Aware Segmentation [80.39674800972182]
  We present a novel boundary-aware loss term for semantic segmentation using an inverse-transformation network. This plug-in loss term complements the cross-entropy loss in capturing boundary transformations. We analyze the quantitative and qualitative effects of our loss function on three indoor and outdoor segmentation benchmarks.
  arXiv  Detail & Related papers  (2021-04-06T18:52:45Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Compositional ADAM: An Adaptive Compositional Solver [69.31447856853833]
  C-ADAM is the first adaptive solver for compositional problems involving a non-linear functional nesting of expected values. We prove that C-ADAM converges to a stationary point in $mathcalO(delta-2.25)$ with $delta$ being a precision parameter.
  arXiv  Detail & Related papers  (2020-02-10T14:00:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.