Optimal Abstractions for Verifying Properties of Kolmogorov-Arnold Networks (KANs)

• URL: http://arxiv.org/abs/2602.06737v1
• Date: Fri, 06 Feb 2026 14:33:41 GMT
• Title: Optimal Abstractions for Verifying Properties of Kolmogorov-Arnold Networks (KANs)
• Authors: Noah Schwartz, Chandra Kanth Nagesh, Sriram Sankaranarayanan, Ramneet Kaur, Tuhin Sahai, Susmit Jha,
• Abstract summary: We present a novel approach for verifying properties of Kolmogorov-Arnold Networks (KANs)<n>Our key contribution is a systematic framework that exploits KAN structure to find optimal abstractions.<n>This approach determines the optimal approximation strategy for each unit while maintaining overall accuracy requirements.
• Score: 8.114307305249929
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel approach for verifying properties of Kolmogorov-Arnold Networks (KANs), a class of neural networks characterized by nonlinear, univariate activation functions typically implemented as piecewise polynomial splines or Gaussian processes. Our method creates mathematical ``abstractions'' by replacing each KAN unit with a piecewise affine (PWA) function, providing both local and global error estimates between the original network and its approximation. These abstractions enable property verification by encoding the problem as a Mixed Integer Linear Program (MILP), determining whether outputs satisfy specified properties when inputs belong to a given set. A critical challenge lies in balancing the number of pieces in the PWA approximation: too many pieces add binary variables that make verification computationally intractable, while too few pieces create excessive error margins that yield uninformative bounds. Our key contribution is a systematic framework that exploits KAN structure to find optimal abstractions. By combining dynamic programming at the unit level with a knapsack optimization across the network, we minimize the total number of pieces while guaranteeing specified error bounds. This approach determines the optimal approximation strategy for each unit while maintaining overall accuracy requirements. Empirical evaluation across multiple KAN benchmarks demonstrates that the upfront analysis costs of our method are justified by superior verification results.

Related papers

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Fast Bayesian Optimization of Function Networks with Partial Evaluations [7.688686113950605]
  We propose an accelerated p-KGFN algorithm that reduces computational overhead with only a modest loss in query efficiency.<n>Key to our approach is generation of node-specific candidate inputs for each node in the network via one inexpensive global Monte Carlo simulation.<n> Numerical experiments show that our method maintains competitive query efficiency while achieving up to a 16x speedup over the original p-KGFN algorithm.
  arXiv  Detail & Related papers  (2025-06-13T04:20:36Z)
• Degree-Optimized Cumulative Polynomial Kolmogorov-Arnold Networks [0.0]
  Kolmogorov-Arnold networks (CP-KAN) is a neural architecture combining Chebyshev basis functions and quadratic unconstrained binary optimization (QUBO)<n>Our contribution involves reformulating the degree selection problem as a QUBO task, reducing the complexity from $O($N) to a single optimization step per layer.<n>The architecture performs well in regression tasks with limited data, showing good robustness to input scales and natural regularization properties from its basis.
  arXiv  Detail & Related papers  (2025-05-21T07:59:12Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  We propose an iterative-based algorithm that jointly updates the decision and the IS distribution without requiring time-scale separation between the two.<n>Our method achieves the lowest possible variable variance and guarantees global convergence under convexity of the objective and mild assumptions on the IS distribution family.
  arXiv  Detail & Related papers  (2025-04-04T16:10:18Z)
• Complexity-Aware Training of Deep Neural Networks for Optimal Structure Discovery [0.0]
  We propose a novel algorithm for combined unit and layer pruning of deep neural networks that functions during training and without requiring a pre-trained network to apply.<n>Our algorithm optimally trades-off learning accuracy and pruning levels while balancing layer vs. unit pruning and computational vs. parameter complexity.<n>We show that the proposed algorithm converges to solutions of the optimization problem corresponding to networks.
  arXiv  Detail & Related papers  (2024-11-14T02:00:22Z)
• Multilevel CNNs for Parametric PDEs based on Adaptive Finite Elements [0.0]
  A neural network architecture is presented that exploits the multilevel properties of high-dimensional parameter-dependent partial differential equations. The network is trained with data on adaptively refined finite element meshes. A complete convergence and complexity analysis is carried out for the adaptive multilevel scheme.
  arXiv  Detail & Related papers  (2024-08-20T13:32:11Z)
• 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)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  Facility location problems (FLPs) are a typical class of NP-hard optimization problems, which are widely seen in the supply chain and logistics. In this paper, we consider the multi-objective facility location problem (MO-FLP) that simultaneously minimizes the overall cost and maximizes the system reliability. Two graph neural networks are constructed to learn the implicit graph representation on nodes and edges.
  arXiv  Detail & Related papers  (2022-10-27T07:15:55Z)
• Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
  Inspired by sum-of-infeasibilities methods in convex optimization, we propose a novel procedure for analyzing verification queries on networks with extensive branching functions. An extension to a canonical case-analysis-based complete search procedure can be achieved by replacing the convex procedure executed at each search state with DeepSoI.
  arXiv  Detail & Related papers  (2022-03-19T15:05:09Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  Non-smooth finite-sum minimization is a fundamental problem in machine learning. This paper develops a distributed proximal-gradient algorithm with random reshuffling to solve the problem.
  arXiv  Detail & Related papers  (2021-11-06T07:29:55Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts. Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures. We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
  arXiv  Detail & Related papers  (2020-10-07T08:19:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.