RAYEN: Imposition of Hard Convex Constraints on Neural Networks

• URL: http://arxiv.org/abs/2307.08336v1
• Date: Mon, 17 Jul 2023 09:12:05 GMT
• Title: RAYEN: Imposition of Hard Convex Constraints on Neural Networks
• Abstract summary: RAYEN is a framework to impose hard convex constraints on a neural network. It achieves times between 20 and 7468 times faster than state-of-the-art algorithms.
• Score: 47.494620411594624
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents RAYEN, a framework to impose hard convex constraints on the output or latent variable of a neural network. RAYEN guarantees that, for any input or any weights of the network, the constraints are satisfied at all times. Compared to other approaches, RAYEN does not perform a computationally-expensive orthogonal projection step onto the feasible set, does not rely on soft constraints (which do not guarantee the satisfaction of the constraints at test time), does not use conservative approximations of the feasible set, and does not perform a potentially slow inner gradient descent correction to enforce the constraints. RAYEN supports any combination of linear, convex quadratic, second-order cone (SOC), and linear matrix inequality (LMI) constraints, achieving a very small computational overhead compared to unconstrained networks. For example, it is able to impose 1K quadratic constraints on a 1K-dimensional variable with an overhead of less than 8 ms, and an LMI constraint with 300x300 dense matrices on a 10K-dimensional variable in less than 12 ms. When used in neural networks that approximate the solution of constrained optimization problems, RAYEN achieves computation times between 20 and 7468 times faster than state-of-the-art algorithms, while guaranteeing the satisfaction of the constraints at all times and obtaining a cost very close to the optimal one.

Related papers

• The Edge-based Contiguous p-median Problem with Connections to Logistics Districting [0.0]
  This paper introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories.<n>Two binary programming models are introduced, both of which incorporate a network distance.<n>The respective solution approaches are tested on road networks with over 2,700 nodes and close to 3,400 edges.
  arXiv  Detail & Related papers  (2026-07-30T03:49:03Z)
• A Scalable Global Optimization Algorithm For Constrained Clustering [2.3915781021862332]
  Constrained clustering uses pairwise must-link and cannot-link constraints to improve clustering performance and interpretability.<n>Existing mixed-integer optimization methods are confined to small-scale datasets, limiting their utility.<n>We propose a decomposable branch-and-bound framework that collapses must-linked samples into centroid-based pseudo-samples and prunes cannot-link through geometric rules.
  arXiv  Detail & Related papers  (2025-10-26T04:01:07Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) pruning methods operate layer-wise, minimizing the per-layer pruning error on a small dataset to avoid full retraining.<n>Existing methods hence rely on greedy convexs that ignore the weight interactions in the pruning objective.<n>Our method drastically reduces the per-layer pruning error, outperforms strong baselines on state-of-the-art GPT architectures, and remains memory-efficient.
  arXiv  Detail & Related papers  (2025-10-15T16:13:44Z)
• Virtual Arc Consistency for Linear Constraints in Cost Function Networks [2.8675177318965037]
  We adapt an existing SAC algorithm to handle linear constraints.<n>We show that our algorithm significantly improves the lower bounds compared to the original algorithm on several benchmarks.
  arXiv  Detail & Related papers  (2025-09-22T12:44:52Z)
• Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees [34.164821598251315]
  In sparse optimization, enforcing hard constraints using the $ell_$ pseudo-norm offers advantages like controlled sparsity.<n>Many real-world applications demand not only sparsity constraints but also some extra constraints.<n>We present a new variant of hard-preserving iterative algorithm equipped with a two-step projection operator customized for these mixed constraints.
  arXiv  Detail & Related papers  (2025-06-10T08:27:01Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs. We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  Traditional mathematical programming solvers require long computational times to solve constrained minimization problems. We propose a penalty-based guardrail algorithm (PGA) to efficiently solve them.
  arXiv  Detail & Related papers  (2024-05-03T10:37:34Z)
• A New Computationally Simple Approach for Implementing Neural Networks with Output Hard Constraints [5.482532589225552]
  A new method of imposing hard convex constraints on the neural network output values is proposed. The mapping is implemented by the additional neural network layer with constraints for output. The proposed method is simply extended to the case when constraints are imposed not only on the output vectors, but also on joint constraints depending on inputs.
  arXiv  Detail & Related papers  (2023-07-19T21:06:43Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Reachability Analysis of Neural Feedback Loops [34.94930611635459]
  This work focuses on estimating the forward reachable set of textitneural feedback loops (closed-loop systems with NN controllers) Recent work provides bounds on these reachable sets, but the computationally tractable approaches yield overly conservative bounds. This work bridges the gap by formulating a convex optimization problem for the reachability analysis of closed-loop systems with NN controllers.
  arXiv  Detail & Related papers  (2021-08-09T16:11:57Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  This paper considers online convex optimization with long term constraints, where constraints can be violated in intermediate rounds, but need to be satisfied in the long run. A novel algorithm is first proposed and it achieves an $mathcalO(Tmaxc,1-c)$ bound for static regret and an $mathcalO(T(1-c)/2)$ bound for cumulative constraint violation.
  arXiv  Detail & Related papers  (2021-06-09T15:18:06Z)
• Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
  We present two novel dual algorithms for tight and efficient neural network bounding. Both methods recover the strengths of the new relaxation: tightness and a linear separation oracle. We can obtain better bounds than off-the-shelf solvers in only a fraction of their running time.
  arXiv  Detail & Related papers  (2021-01-14T19:45:17Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.