Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

Artem Vozmishchev

math.CAOct 10, 2026

Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

Authors: Artem Vozmishchev

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

Abstract

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.

Figures & tables

$d$	$\Delta$	$L$	$N$	$q$	bits (block)	bits (plain)	round trip	$\max\|f_{\rm dec}-f\|$	$\\|F-f\\|_{\infty}/\Delta$
1	0.2	3	30	10	328	3 917	yes	$4.4e-16$	0.185
1	0.05	1	40	40	390	5 657	yes	$4.4e-16$	0.228
1	0.01	2	400	200	1 878	70 343	yes	$4.4e-16$	0.246
2	0.3	1.5	21	14	4 162	171 553	yes	$8.7e-14$	0.181
2	0.4	1	10	10	1 569	37 436	yes	$2.1e-14$	0.136
2	0.45	2	18	9	3 301	125 654	yes	$2.2e-13$	0.143

Table 1: Round trip encode

\to

decode

\to

evaluate. “Bits (block)” is the length of the encoded string in the language with loops, “bits (plain)” the length of the same formula written without loops.

Figure 1: The construction of Theorem 8 for

L=3

\Delta=0.2

(

N=30

). (a) The function

F

and the approximant

f

. (b) The uniform error stays inside

[-\Delta,\Delta]

. (c) The integer coefficients

e_{i}

(second differences) take values in

\{-4,\dots,4\}

and cost

O(1)

bits each.

Figure 2: Distribution of

\|F-f\|_{\infty}/\Delta

over random instances. The dotted line is the proved worst-case ratio (

2/3

for

d=1

5/8

for

d\geq 2

), the dashed line is

1

Figure 3: Description length of the construction for

d=1

(four values of

L

, thirteen values of

\Delta

each). (a) Log–log plot against

L/\Delta

with the proved bounds. (b) Bits per unit of

L/\Delta

: flat with the loop block, growing without it.

Panel of Figure 4 — Figure 4: (a) Largest observed integer coefficient against the bound $3\cdot 4^{d}$ . (b) Measured description length against $A=(L/\Delta)^{d}$ for $d=1,2,3$ .

$d$	$L$	$\Delta$	$m$	$\lg\|\mathcal{G}\|=m^{d}$	$\eta$	$2\Delta$	min. distance	max. Lip. ratio
1	6	0.1	14	14	0.214	0.200	0.214	6.000
1	20	0.2	24	24	0.417	0.400	0.417	20.000
2	5	0.2	6	36	0.417	0.400	0.417	5.000
2	8	0.3	6	36	0.667	0.600	0.667	8.000
3	6	0.3	4	64	0.750	0.600	0.750	6.000

Table 2: Check of the packing family of Lemma 19 :

m^{d}

bits are forced because the members are more than

2\Delta

apart.

Figure 5: The hard family of Lemma 19 . (a) Three members for $d=1$ . (b) One member for $d=2$ . (c) The number $m^{d}$ of independent bits against $L/\Delta$ .

Figure 6: (a) The function

\varphi

of Lemma 7 and its maximum. (b) The smooth ramp

R_{\gamma}

against

\max\{0,z\}

Function Approximation

See all 32 papers

Efficient Approximation to Analytic and $L^p$ functions by Height-Augmented ReLU Networks
Mar 11, 2026ZeYu Li, FengLei Fan, TieYong ZengNeural Network Approximation Theory ReLU Neural Networks
Chinese University of Hong Kong, Department of Mathematics, Hong Kong, 999077, NT, Hong Kong SAR, China · City University of Hong Kong, Department of Data Science, Hong Kong, 999077, Kowloon, Hong Kong SAR, China · Guangzhou Nanfang College, School of Mathematics and Statistics, Guangzhou, 510970, Guangdong, China +1
Demystifying Lipschitz verification: positive matrices, negative results
Mar 30, 2026Simon Kuang, Yuezhu Xu, S. Sivaranjani +1Neural Network Verification Lipschitz Neural Networks
Department of Mechanical and Aerospace Engineering University of California, Davis · Edwardson School of Industrial Engineering Purdue University
Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions
Apr 29, 2026Aleksander TankmanKolmogorov-Arnold Networks Neural Network Approximation Theory
Fivestar Europe OÜ, Tallinn, Estonia

Mar 11, 2026J/K move · Enter open · S save

Efficient Approximation to Analytic and $L^p$ functions by Height-Augmented ReLU Networks

ZeYu Li, FengLei Fan, TieYong Zeng

Chinese University of Hong Kong, Department of Mathematics, Hong Kong, 999077, NT, Hong Kong SAR, China · City University of Hong Kong, Department of Data Science, Hong Kong, 999077, Kowloon, Hong Kong SAR, China · Guangzhou Nanfang College, School of Mathematics and Statistics, Guangzhou, 510970, Guangdong, China+1

Neural Network Approximation Theory ReLU Neural Networks

Open paper AskPDF arXiv

This work addresses two fundamental limitations in neural network approximation theory. We demonstrate that a three-dimensional network architecture enables a significantly more efficient representation of sawtooth functions, which serves as the cornerstone in the approximation of analytic and

L^p

functions. First, we establish substantially improved exponential approximation rates for several important classes of analytic functions and offer a parameter-efficient network design. Second, for the first time, we derive a quantitative and non-asymptotic approximation of high orders for general

L^p

functions. Our techniques advance the theoretical understanding of the neural network approximation in fundamental function spaces and offer a theoretically grounded pathway for designing more parameter-efficient networks.

Abstract

Function Approximation

Explore similar work

Efficient Approximation to Analytic and LpL^pLp functions by Height-Augmented ReLU Networks

Demystifying Lipschitz verification: positive matrices, negative results

Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions

Efficient Approximation to Analytic and $L^p$ functions by Height-Augmented ReLU Networks