Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
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 {+,−,×,÷,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]→[0,1] has an everywhere-defined approximant of accuracy Δ with dc(f)≤ 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 \emph{every} description language: for Δ≤ 1/36 and every L>0 some L-Lipschitz function needs at least 1/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((L/Δ)d+lg(1/Δ+2)), 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.
Related
- A note on the convergence analysis of Laguerre approximations for analytic functions
- Analytic description of the phase transition of inhomogeneous multigraphs
- Simple and accurate approximations to Dirichlet L-functions
- The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
- Variationally correct loss functions for nonlinear parametric problems and their neural approximations
BibTeX
@misc{vozmishchev2026description,
title = {{Description Complexity Bounds for Analytic Approximations of Lipschitz Functions}},
author = {Artem Vozmishchev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14893},
eprint = {2610.14893},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14893},
}
RIS
TY - UNPB
TI - Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
AU - Artem Vozmishchev
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14893
UR - https://arxiv.org/abs/2610.14893
AB - 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 {+,−,×,÷,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]→[0,1] has an everywhere-defined approximant of accuracy Δ with dc(f)≤ 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 \emph{every} description language: for Δ≤ 1/36 and every L>0 some L-Lipschitz function needs at least 1/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((L/Δ)^d+lg(1/Δ+2)), 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.
ER -