Function Approximation

Follow this topic Ask about this topic

Latest papers

32 papers5 papers in the last four weeks, up 67% on the four weeks before. 0.0% of all new papers.

Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
Oct 10, 2026Artem VozmishchevFunction Approximation
Faculty of Applied Informatics, ITMO University, St. Petersburg, 197101, Russia
Bellman Error Minimization Via Linear Programming Normalization
Oct 2, 2026Haining YuFunction Approximation in RL Dynamic Programming
Independent Consultant
Kolmogorov-Arnold Classifier Systems as Universal Approximators
Sep 29, 2026Hiroki Shiraishi, Hisao Ishibuchi, Masaya NakataUniversal Approximation Function Approximation
Graduate School of Engineering Science, Yokohama National University, Yokohama 240-8501, Japan · Digital Healthcare Research Department, Hitachi, Ltd., Tokyo 185-8601, Japan · Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China +1
A Weighted Kernel Method for Approximation that Adapts to Learned Multivariable Structure
Sep 15, 2026John E. Darges, Laura WeidensagerKernel Regression Kernel Methods
Department of Mathematics, Emory University · Department of Mathematics, Simon Fraser University
Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation
Sep 14, 2026Aleksander TankmanFunction Approximation Neural Network Approximation Theory
Fivestar Europe OÜ, Tallinn, Estonia
Shallow neural network approximation in mixed Sobolev spaces
Sep 4, 2026Yuwen Li, Guozhi ZhangNeural Network Approximation Theory Function Approximation
School of Mathematical Sciences, Zhejiang University, 866 Yuhangtang Road, Hangzhou 310058, Zhejiang, China
SW-KAN: Kolmogorov-Arnold Networks with Stieltjes-Wigert q-Orthogonal Polynomials
Sep 3, 2026Amirhosein Azarpour, Seyyed Moein KazemiFunction Approximation Kolmogorov-Arnold Networks
Faculty of Mathematical Sciences, Department of Computer Science, Shahid Beheshti University, Tehran · Faculty of Mathematical Sciences, Shahid Beheshti University, Tehran
Resolution-Consistent Greedy Neural Approximation on Infinite-Dimensional Spaces
Aug 21, 2026Pablo M. Berná, Antonio Falcó, Diego MondéjarNeural Network Approximation Theory Function Approximation
Universidad Tecnol´ogica Atl´antico Mediterr´aneo – UTAMED, Facultad de Empresa Digital, Tecnolog´ıa y Derecho, M´alaga, Espa˜na · Departamento de Matem´aticas, F´ısica y Ciencias Tecnol´ogicas, Universidad Cardenal Herrera-CEU, CEU Universities, San Bartolom´e 55, Alfara del Patriarca (Valencia), 46115, Spain · Departamento de Matem´aticas, CUNEF Universidad, 28040, Espa˜na
Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization
Aug 11, 2026Sohaib AfifiDempster-Shafer Theory Combinatorial Optimization
Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), Béthune, France
Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View
Aug 2, 2026Tong Mao, Jinchao XuCurse of Dimensionality Neural Network Approximation Theory
King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia
All you need is SAMPAT
Jul 10, 2026Jayadeva, Madhur AswaniShallow Neural Networks Interpretable ML
Department of Electrical Engineering, Indian Institute of Technology, Delhi
Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation
Jun 25, 2026Anastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim +2Universal Approximation Neural Network Approximation Theory
McMaster University & Vector Institute, Toronto, ON, Canada · Concordia University, Montréal, QC, Canada · University of Tokyo, Tokyo, Japan +2
EML Trees Are Universal Approximators
Jun 22, 2026Joe Germany, Elie Abdo, Joseph BakarjiUniversal Approximation Neural Network Approximation Theory
Department of Mathematics American University of Beirut Beirut, Lebanon · Department of Mechanical Engineering American University of Beirut Beirut, Lebanon
Recurrent neural networks approximate continuous functions
Jun 18, 2026Valentin Abadie, Clemens Hutter, Helmut BölcskeiReLU Neural Networks Recurrent Neural Networks
A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise
Jun 16, 2026M. Forzo, E. Monzio Compagnoni, A. Russo +1Stochastic Differential Equations Temporal-Difference Learning
Technical University of Munich (TUM), Munich, Germany · University of Basel, Basel, Switzerland · Boston University, Boston, USA.
Compositional Approximation Can Strictly Outperform Superpositional Approximation
Jun 7, 2026Dennis Elbrächter, Philipp PetersenNeural Network Approximation Theory Function Approximation
Faculty of Mathematics, University of Vienna, Austria
Fitting scattered data with optional monotonicity constraints on GPU: LipFit package
Jun 3, 2026Gleb BeliakovFunction Approximation
School of Information Technology, Deakin University, Burwood 3125, Australia
Approximation Theory for Neural Networks: Old and New
May 20, 2026Soumendu Sundar Mukherjee, Himasish TalukdarUniversal Approximation Neural Network Approximation Theory
Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata
Adaptive RBF-KAN: A Comparative Evaluation of Dynamic Shape Parameters in Kolmogorov-Arnold Networks
May 20, 2026Roberto Cavoretto, Alessandra De Rossi, Adeeba Haider +1Kolmogorov-Arnold Networks Kernel Methods
Department of Mathematics “Giuseppe Peano”, University of Torino, via Carlo Alberto 10, 10123 Torino, Italy · Member of the INdAM Research Group GNCS · Department of Mathematics, Hong Kong Baptist University, Hong Kong SAR, China
Thermodynamic Networks: Harnessing Non-Equilibrium Steady States for Computation
May 15, 2026Patryk Lipka-Bartosik, Gianmichele Blasi, Javier Lalueza Puértolas +3Thermodynamic Computing Function Approximation
Center for Theoretical Physics, Polish Academy of Sciences, Warsaw, Poland · Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), E-07122 Palma de Mallorca, Spain · Física Teòrica: Informació i Fenòmens Quàntics, Department de Física, Universitat Autònoma de Barcelona, 08193 Bellaterra (Barcelona), Spain +1
Transformer Approximations from ReLUs
Apr 27, 2026Jerry Yao-Chieh Hu, Mingcheng Lu, Yi-Chen Lee +1Softmax Attention Neural Network Approximation Theory
Center for Foundation Models and Generative AI, Northwestern University, Evanston, IL 60208, USA · Department of Computer Science, Northwestern University, Evanston, IL 60208, USA · Department of Physics, National Taiwan University, Taipei 10617, Taiwan +1
Universal Approximation Constraints of Narrow ResNets: The Tunnel Effect
Mar 30, 2026Christian Kuehn, Sara-Viola Kuntz, Tobias WöhrerUniversal Approximation Neural Network Approximation Theory
Technical University of Munich, School of Computation, Information and Technology, Department of Mathematics, Boltzmannstraße 3, 85748 Garching, Germany · Munich Data Science Institute (MDSI), Garching, Germany · Munich Center for Machine Learning (MCML), München, Germany +1
CFNN: Continued Fraction Neural Network
Mar 21, 2026Chao Wang, Xuancheng Zhou, Ruilin Hou +2Function Approximation Scientific ML
School of Future Technology, Shanghai University, Shanghai, 200444, China. · Institute of Artificial Intelligence, Shanghai University, Shanghai, 200444, China. · School of Computer Science and Technology, Shanghai University, Shanghai, 200444, China. +2
Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation
Mar 17, 2026Yiming Zong, Jiashuo JiangFunction Approximation Linear Programming
Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology
Deep learning and the rate of approximation by flows
Mar 16, 2026Jingpu Cheng, Qianxiao Li, Ting Lin +1Neural Network Approximation Theory Function Approximation
Department of Mathematics, National University of Singapore, 117543, Singapore · Department of Mathematics and Institute for Functional Intelligent Materials, National University of Singapore, 117543, Singapore · School of Mathematical Sciences, Peking University, 100871, China
Global universality via discrete-time signatures
Mar 10, 2026Mihriban Ceylan, David J. PrömelPath Signatures Universal Approximation
DualFlexKAN: Dual-stage Kolmogorov-Arnold Networks with Independent Function Control
Mar 9, 2026Andrés Ortiz, Nicolás J. Gallego-Molina, Carmen Jiménez-Mesa +2Function Approximation Kolmogorov-Arnold Networks
Department of Communications Engineering University of Malaga Malaga, Spain · DaSCI Andalusian Institute of Data Science and Computational Intelligence University of Granada Granada, Spain · Department of signal Theory, Communications and Telematics University of Granada Granada, Spain
Learning Without Training
Feb 20, 2026Ryan O'DowdFunction Approximation Supervised Learning
Claremont Graduate University
FEKAN: Feature-Enriched Kolmogorov-Arnold Networks
Feb 18, 2026Sidharth S. Menon, Ameya D. JagtapFunction Approximation Kolmogorov-Arnold Networks
Aerospace Engineering Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA.
Global universal approximation with Brownian signatures
Dec 18, 2025Mihriban Ceylan, David J. PrömelUniversal Approximation Path Signatures

Oct 10, 2026J/K move · Enter open · S save

Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

Artem Vozmishchev

Faculty of Applied Informatics, ITMO University, St. Petersburg, 197101, Russia

Function Approximation

Open paper AskPDF arXiv

We study how many bits are needed to write down an elementary analytic expression that uniformly approximates a Lipschitz function. Expressions are finite trees over the basis

\{+,-,\times,÷,\exp\}

with the variables and rational constants, and their size is

\dc(f)

, the length of the shortest description of

f

in a fixed binary description language. For functions of one variable we prove that every

L

-Lipschitz

F:[0,1]\to[0,1]

has an everywhere-defined approximant of accuracy

Δ

with

\dc(f)\le C\,(L/Δ+\lg(1/Δ+2))

for all

L,Δ>0

, by a linear spline smoothed with logistic ramps in a description language with one repetition construct. We prove a matching lower bound valid for every description language: for

Δ\le 1/36

and every

L>0

some

L

-Lipschitz function needs at least

\tfrac1{16}(L/Δ+\lg(1/Δ+2))

bits. Hence the worst-case description complexity is

Θ(L/Δ+\lg(1/Δ+2))

. For functions on

[0,1]^d

the same method gives

Θ_d\bigl((L/Δ)^d+\lg(1/Δ+2)\bigr)

, using a tensor-product spline whose coefficients are mixed second differences and cost

O(d)

bits each. Without the repetition construct the upper bounds carry an additional logarithmic factor, whose necessity for plain expression trees is left open. A reference encoder, decoder and evaluator confirm the constructions numerically, and figures and tables report the checks.