論文の概要: Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

• arxiv url: http://arxiv.org/abs/2610.14893v1
• Date: Sat, 10 Oct 2026 13:14:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 11:11:23.199049
• Title: Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
• Title（参考訳）: リプシッツ関数の解析近似のための記述複雑性境界
• Abstract要約: 式は、変数と有理定数を持つ基底 $+,-,times,exp$ 上の有限木である。 我々は、$le 1/36$ および every $L>0$ some $L$-Lipschitz 関数が少なくとも $tfrac116(L/+lg(1/+2)$ ビットを必要とすることを証明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 \emph{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.
• Abstract（参考訳）: リプシッツ関数を均一に近似する基本解析式を書くのに必要なビット数について検討する。 式は変数と有理定数を持つ基底上の有限木で、そのサイズは$\dc(f)$であり、固定二項記述言語における$f$の最短記述の長さは$\dc(f)$である。 1つの変数の関数に対して、すべての$L$-Lipschitz $F:[0,1]\to[0,1]$が、すべての$L,Δ>0$に対して$\dc(f)\le C\,(L/Δ+\lg(1/Δ+2))$の至る所で定義された精度の近似を持つことを証明している。 例えば、$Δ\le 1/36$とすべての$L>0$に対して、少なくとも$\tfrac1{16}(L/Δ+\lg(1/Δ+2))$ bitsが必要である。 したがって、最悪のケース記述の複雑さは$(L/Δ+\lg(1/Δ+2))$である。 同じ方法である$[0,1]^d$ 上の函数に対して、係数が第2の差分を混合し、それぞれ$O(d)$ビットをコストするテンソル積スプライン(英語版)(tensor-product spline)を使用すると、$(L/Δ)^d+\lg(1/Δ+2)\bigr)$ が与えられる。 繰り返し構造がなければ、上界は追加の対数係数を持ち、平易な表現木の必要性は未開のままである。 参照エンコーダ、デコーダ、評価器が数値的に構成を確認し、数値と表がチェックを報告する。

関連論文リスト

• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck、Li、Nagarajは、一般的なデータでは、ノイズラベルに適合する$m$のニューロンを持つ任意の2層ニューラルネットワークは、リプシッツ定数を持つ必要があると推測した。 予想法則を1つの対数係数まで証明し、特にReLUネットワークにおいて連続的な片方向線形活性化を行う。
  論文  参考訳（メタデータ） (2026-07-08T17:44:15Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• ReLU Network Approximation in Terms of Intrinsic Parameters [5.37133760455631]
  固有パラメータ数の観点からReLUネットワークの近似誤差について検討する。 我々は、3つの固有パラメータしか持たないReLUネットワークを設計し、任意の誤差でH"古い連続関数を近似する。
  論文  参考訳（メタデータ） (2021-11-15T18:20:38Z)
• Ridgeless Interpolation with Shallow ReLU Networks in $1D$ is Nearest Neighbor Curvature Extrapolation and Provably Generalizes on Lipschitz Functions [16.75218291152252]
  一層のReLUネットワークの正確な幾何学的記述を1つの線形単位を持つ$z(x;theta)$で証明する。 我々はこれらをリッジレスReLU補間剤と呼ぶ。 この結果から,リッジレスReLU補間器は1d$リプシッツ関数の学習に最適な一般化を実現することがわかった。
  論文  参考訳（メタデータ） (2021-09-27T11:32:24Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。