PolyKAN: A Polyhedral Analysis Framework for Provable and Approximately Optimal KAN Compression

• URL: http://arxiv.org/abs/2510.04205v2
• Date: Wed, 08 Oct 2025 03:27:57 GMT
• Title: PolyKAN: A Polyhedral Analysis Framework for Provable and Approximately Optimal KAN Compression
• Abstract summary: Kolmogorov-Arnold Networks (KANs) have emerged as a promising alternative to traditional Multi-Layer Perceptrons (MLPs)<n>This paper introduces PolyKAN, a novel theoretical framework for KAN compression that provides formal guarantees on both model size reduction and approximation error.
• Score: 8.201374511929538
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kolmogorov-Arnold Networks (KANs) have emerged as a promising alternative to traditional Multi-Layer Perceptrons (MLPs), offering enhanced interpretability and a solid mathematical foundation. However, their parameter efficiency remains a significant challenge for practical deployment. This paper introduces PolyKAN, a novel theoretical framework for KAN compression that provides formal guarantees on both model size reduction and approximation error. By leveraging the inherent piecewise polynomial structure of KANs, we formulate the compression problem as a polyhedral region merging task. We establish a rigorous polyhedral characterization of KANs, develop a complete theory of $\epsilon$-equivalent compression, and design a dynamic programming algorithm that achieves approximately optimal compression under specified error bounds. Our theoretical analysis demonstrates that PolyKAN achieves provably near-optimal compression while maintaining strict error control, with guaranteed global optimality for univariate spline functions. This framework provides the first formal foundation for KAN compression with mathematical guarantees, opening new directions for the efficient deployment of interpretable neural architectures.

Related papers

• Sharper Analysis of Single-Loop Methods for Bilevel Optimization [81.36947969465848]
  We establish sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods.<n>We prove that the error is $mathcalO(2)$, exactly matching the known lower bound and improving upon the previous $mathcalO(3)$ guarantee.
  arXiv  Detail & Related papers  (2026-07-11T11:41:42Z)
• Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs [20.54731804867887]
  We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs)<n>By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample complexity and computational complexities in $N$.
  arXiv  Detail & Related papers  (2026-06-12T04:19:53Z)
• Tree-Preconditioned Differentiable Optimization and Axioms as Layers [0.0]
  "Axioms-as-Layers" paradigm embeds axiomatic structure of Random Utility Models directly into deep neural networks.<n>"Axioms-as-Layers" paradigm eliminates the structural overfitting inherent in penalty-based methods.
  arXiv  Detail & Related papers  (2025-12-03T04:47:37Z)
• DeePoly: A High-Order Accuracy Scientific Machine Learning Framework for Function Approximation and Solving PDEs [5.483488375189695]
  This work introduces a novel framework that transforms the Dee solution to a two-stage approach.<n>The strategic combination leverages the strengths of both methods.<n>This approach also serves as the open-source project also serves as the paper.
  arXiv  Detail & Related papers  (2025-06-05T04:10:52Z)
• Input convex neural networks: universal approximation theorem and implementation for isotropic polyconvex hyperelastic energies [0.0]
  This paper presents a novel framework that enforces necessary physical and mathematical constraints while simultaneously satisfying the universal mathematical constraints.<n>A universal theorem for the proposed approach is proven.<n>The proposed network can any frame-in, isotropic poly energy (provided the network is large)<n>Existing approaches identify the advantages of the proposed method.
  arXiv  Detail & Related papers  (2025-02-12T16:15:03Z)
• HKAN: Hierarchical Kolmogorov-Arnold Network without Backpropagation [1.3812010983144802]
  The Hierarchical Kolmogorov-Arnold Network (HKAN) is a novel network architecture that offers a competitive alternative to the recently proposed Kolmogorov-Arnold Network (KAN)<n>HKAN adopts a randomized learning approach, where the parameters of its basis functions are fixed, and linear aggregations are optimized using least-squares regression.<n> Empirical results show that HKAN delivers comparable, if not superior, accuracy and stability relative to KAN across various regression tasks, while also providing insights into variable importance.
  arXiv  Detail & Related papers  (2025-01-30T08:44:54Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm called ALEXR.<n>We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions.<n> Experimental results on GDRO and partial Area Under the ROC Curve for cFCCO demonstrate the promising performance of our algorithm.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
  We derive new complexity bounds for the set of Coupled CP-Decomposition (CCP) and Nested Coupled CP-decomposition (NCP) models of Polynomial Nets. We propose a principled regularization scheme that we evaluate experimentally in six datasets and show that it improves the accuracy as well as the robustness of the models to adversarial perturbations.
  arXiv  Detail & Related papers  (2022-02-10T14:54:29Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Efficient Micro-Structured Weight Unification and Pruning for Neural Network Compression [56.83861738731913]
  Deep Neural Network (DNN) models are essential for practical applications, especially for resource limited devices. Previous unstructured or structured weight pruning methods can hardly truly accelerate inference. We propose a generalized weight unification framework at a hardware compatible micro-structured level to achieve high amount of compression and acceleration.
  arXiv  Detail & Related papers  (2021-06-15T17:22:59Z)
• A Deep Learning approach to Reduced Order Modelling of Parameter Dependent Partial Differential Equations [0.2148535041822524]
  We develop a constructive approach based on Deep Neural Networks for the efficient approximation of the parameter-to-solution map. In particular, we consider parametrized advection-diffusion PDEs, and we test the methodology in the presence of strong transport fields.
  arXiv  Detail & Related papers  (2021-03-10T17:01:42Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  Existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms. Motivated by primal-dual algorithms, this paper proposes first underlineLinunderlineEAr convergent. underlineDecentralized with compression, LEAD.
  arXiv  Detail & Related papers  (2020-07-01T04:35:00Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Structured Sparsification with Joint Optimization of Group Convolution and Channel Shuffle [117.95823660228537]
  We propose a novel structured sparsification method for efficient network compression. The proposed method automatically induces structured sparsity on the convolutional weights. We also address the problem of inter-group communication with a learnable channel shuffle mechanism.
  arXiv  Detail & Related papers  (2020-02-19T12:03: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.