Near-optimal Linear Predictive Clustering in Non-separable Spaces via Mixed Integer Programming and Quadratic Pseudo-Boolean Reductions

• URL: http://arxiv.org/abs/2511.10809v2
• Date: Mon, 17 Nov 2025 02:13:44 GMT
• Title: Near-optimal Linear Predictive Clustering in Non-separable Spaces via Mixed Integer Programming and Quadratic Pseudo-Boolean Reductions
• Authors: Jiazhou Liang, Hassan Khurram, Scott Sanner,
• Abstract summary: Linear Predictive Clustering (LPC) partitions samples based on shared linear relationships between feature and target variables.<n>Greedy optimization methods, commonly used for LPC, alternate between clustering and linear regression but lack global optimality.<n>This work builds on the constrained optimization paradigm to introduce two novel approaches that improve the efficiency of global optimization for LPC.
• Score: 21.80447518126464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Linear Predictive Clustering (LPC) partitions samples based on shared linear relationships between feature and target variables, with numerous applications including marketing, medicine, and education. Greedy optimization methods, commonly used for LPC, alternate between clustering and linear regression but lack global optimality. While effective for separable clusters, they struggle in non-separable settings where clusters overlap in feature space. In an alternative constrained optimization paradigm, Bertsimas and Shioda (2007) formulated LPC as a Mixed-Integer Program (MIP), ensuring global optimality regardless of separability but suffering from poor scalability. This work builds on the constrained optimization paradigm to introduce two novel approaches that improve the efficiency of global optimization for LPC. By leveraging key theoretical properties of separability, we derive near-optimal approximations with provable error bounds, significantly reducing the MIP formulation's complexity and improving scalability. Additionally, we can further approximate LPC as a Quadratic Pseudo-Boolean Optimization (QPBO) problem, achieving substantial computational improvements in some settings. Comparative analyses on synthetic and real-world datasets demonstrate that our methods consistently achieve near-optimal solutions with substantially lower regression errors than greedy optimization while exhibiting superior scalability over existing MIP formulations.

Related papers

• GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
  Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations.<n>Existing methods for solving these relaxations are computationally intensive, limiting their scalability.<n>We develop a unified proximal framework that is both linearly convergent and computationally efficient.
  arXiv  Detail & Related papers  (2026-03-01T22:26:09Z)
• Towards Robust Scaling Laws for Optimizers [89.21160945066737]
  Empirical scaling laws are widely used to predict loss as model size and training data grow.<n>We show that Chinchilla-style scaling laws emerge naturally as a result of loss decomposition into irreducible, approximation, and optimization errors.
  arXiv  Detail & Related papers  (2026-02-07T21:40:33Z)
• Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach [17.725629133949955]
  Mixed-integer programming (MIP) offers a high degree of modeling flexibility.<n>We propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics.<n>We evaluate the proposed approach on 50 benchmark datasets.
  arXiv  Detail & Related papers  (2026-02-02T14:46:01Z)
• Multi-Objective Reward and Preference Optimization: Theory and Algorithms [3.316593788543852]
  This thesis develops theoretical frameworks and algorithms that advance constrained reinforcement learning (RL) across control, preference learning, and alignment of large language models.<n>ACPO, e-COP, warmPref-PS, PSPL, and MOPO advance RL across average-cost, episodic, and preference-driven paradigms.<n> Collectively, the thesis unifies RL across average-cost, episodic, and preference-driven paradigms, delivering theoretical advances and practical tools for safe and aligned decision-making.
  arXiv  Detail & Related papers  (2025-12-11T12:51:21Z)
• Pareto Multi-Objective Alignment for Language Models [7.9051473654430655]
  Large language models (LLMs) are increasingly deployed in real-world applications that require careful balancing of multiple, often conflicting, objectives.<n>We propose a principled and computationally efficient algorithm designed explicitly for multi-objective alignment (MOA) in LLMs.<n>PAMA transforms multi-objective RLHF into a convex optimization with a closed-form solution, significantly enhancing scalability.
  arXiv  Detail & Related papers  (2025-08-11T08:54:14Z)
• Leveraging Robust Optimization for LLM Alignment under Distribution Shifts [51.74394601039711]
  Preference alignment methods are increasingly critical for steering large language models to generate outputs consistent with human values.<n>We propose a novel distribution-aware optimization framework that improves preference alignment despite such shifts.
  arXiv  Detail & Related papers  (2025-04-08T09:14:38Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  We propose a smooth variant of the min-max problem based on the augmented Lagrangian.<n>The proposed algorithm scales better with the number of objectives than subgradient-based strategies.
  arXiv  Detail & Related papers  (2025-03-16T11:05:51Z)
• Preference-Optimized Pareto Set Learning for Blackbox Optimization [1.9628841617148691]
  No single solution exists that can optimize all the objectives simultaneously. In a typical MOO problem, the goal is to find a set of optimum solutions (Pareto set) that trades off the preferences among objectives. Our formulation leads to a bilevel optimization problem that can be solved by e.g. differentiable cross-entropy methods.
  arXiv  Detail & Related papers  (2024-08-19T13:23:07Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences.<n>To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model.<n>Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Global Optimization: A Machine Learning Approach [7.052596485478637]
  Bertsimas and Ozturk (2023) proposed OCTHaGOn as a way of solving black-box global optimization problems. We provide extensions to this approach by approximating the original problem using other MIO-representable ML models. We show improvements in solution feasibility and optimality in the majority of instances.
  arXiv  Detail & Related papers  (2023-11-03T06:33:38Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  We propose a reduced-space formulation with trained Gaussian processes trained on few data points. The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding. In total, we reduce time convergence by orders of orders of the proposed method.
  arXiv  Detail & Related papers  (2020-05-21T20:59:11Z)

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.