論文の概要: Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
- arxiv url: http://arxiv.org/abs/2606.07931v1
- Date: Sat, 06 Jun 2026 01:50:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-09 14:42:05.54252
- Title: Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
- Title（参考訳）: ガウス場のポイントワイド複素性:上エンベロープ、アルゴリズム下界、分離
- Authors: Yunbei Xu,
- Abstract要約: 中心ガウス過程に対する分散対応点ワイド・メジャー化測度定理を証明した。
この定理は古典的なジェネリックチェインのフィールドレベルの再利用可能な洗練を提供する。
アルゴリズム的下界は固定推定器の点次複雑性の局所幾何学的証明を提供することを示す。
- 参考スコア（独自算出の注目度）: 5.082462420126421
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes. Classical generic chaining characterizes the scalar quantity $\mathbb E\sup_{x\in T}X_x$; the theorem here gives a simultaneous high-probability envelope for the entire field. For an ambient prior $μ$, the envelope at $x$ is governed by a pointwise Fernique-Talagrand functional \[Φ_μ(x):=\int_0^{4σ(x)}\sqrt{\log\frac{1}{μ(B_d(x,\varepsilon))}}\,d\varepsilon,\] together with the corresponding Gaussian tail term. The theorem provides a reusable field-level refinement of classical generic chaining and a Gaussian-process counterpart of pointwise empirical-process bounds for deep neural networks. We also record a Bayesian algorithmic lower envelope from the interactive Fano/data-processing principle. For a known prior $π$, an observation channel, and a concrete estimator $\widehat t(Y)$, the lower bound is expressed through the exact ghost small-ball mass $\mathbb E_{Y\sim Q}π(B_d(\widehat t(Y),Δ))$, rather than a worst-case covering number. In Gaussian location experiments, comparison decoders convert Bayes location error into lower bounds on decision-aligned Gaussian ranges. We then construct an elementary weighted-basis example separating the usual Fano relaxation for a fixed prior, the Bayesian algorithmic lower envelope, the pointwise Gaussian envelope on the selected subatlas, and the full-class minimax risk/global Gaussian scale. Together, these results show that algorithmic lower bounds provide local-geometric certificates of pointwise complexity for fixed estimators in overparameterized ambient classes, precisely in regimes where classical minimax theory becomes either too coarse or oracle-dependent.
- Abstract（参考訳）: 中心ガウス過程に対する分散対応点ワイド・メジャー化測度定理を証明した。
古典的なジェネリック連鎖はスカラー量 $\mathbb E\sup_{x\in T}X_x$ を特徴づける。
周囲の$μ$に対して、$x$のエンベロープは、対応するガウス尾項と共にフェルニク=タラグランド汎函数 \[*_μ(x):=\int_0^{4σ(x)}\sqrt{\log\frac{1}{μ(B_d(x,\varepsilon))}}\,d\varepsilon,\] によって支配される。
この定理は、古典的なジェネリックチェインのフィールドレベルの再利用可能な洗練と、ディープニューラルネットワークに対するポイントワイドな経験的プロセス境界のガウス過程を提供する。
また、対話型ファノ/データ処理原理からベイズアルゴリズムの下位エンベロープを記録する。
既知の事前の$π$、観測チャネルおよび具体的な推定器$\widehat t(Y)$に対して、下界は最悪のケース被覆数ではなく、正確なゴースト小球質量$\mathbb E_{Y\sim Q}π(B_d(\widehat t(Y,Δ))$で表される。
ガウスの位置実験において、比較復号器はベイズの位置誤差を決定整列ガウス範囲の下位境界に変換する。
次に, 固定前のファノ緩和, ベイジアンアルゴリズムの下層エンベロープ, 選択したサブアトラス上のガウス的エンベロープ, フルクラスのミニマックスリスク/グロバルガウス的スケールを分離する基本重み付き基底例を構築した。
これらの結果から、アルゴリズム的下界は、古典的ミニマックス理論が大きすぎるか、あるいはオラクルに依存している状態において、過度にパラメータ化された環境クラスにおける固定推定器に対して、局所幾何学的複雑性の証明を提供することを示した。
関連論文リスト
- Local and Global Contraction Principles for MCMC Mixing [2.889268075288957]
我々はモンテカルロアルゴリズムの混合時間境界を証明するための収縮に基づくフレームワークを開発する。
ランゲヴィン・ランゲヴィンのコンパクト凸領域に対して、明示的な大域的収縮係数を示す。
有限モーメントが存在しない場合、 somep 条件に対して $mathbb E_q[wp]infty$ が $p1$ であるときに、鋭いモーメントベースの収束率を回復する。
論文 参考訳（メタデータ） (2026-06-02T02:16:52Z) - Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
Scoreベースの生成モデルは高次元空間で訓練されていることを示す。
有限固有アンカーとガウス・ニュートンによる最も近い射影座標のReLU実装を用いる。
論文 参考訳（メタデータ） (2026-05-15T10:20:05Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs [8.162867143465382]
我々はこの手法を利用して、平均ケースの複雑さにおいて広く信じられている予想の下で、いくつかの正準高次元統計モデルに対して、還元に基づく計算下界を確立する。
ガウス雑音を持つスパイクテンソルPCAの計算下界は、クラス内の他のガウス雑音分布にまで拡張可能であることを示す。
論文 参考訳（メタデータ） (2025-10-08T17:16:36Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians [2.311583680973075]
楕円分布の共分散/散乱行列の計算効率の良いロバスト推定問題について検討する。
ガウスのケースを超えて拡張される、計算可能で、ほぼ最適な、ほぼ最適な共分散推定器を初めて得る。
論文 参考訳（メタデータ） (2025-02-10T15:31:57Z) - Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。
多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
論文 参考訳（メタデータ） (2024-09-08T13:08:45Z) - Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach [18.009376840944284]
本稿では,ヘッセン損失行列を効果的に正規化できるアルゴリズムを提案する。
提案手法は,CLIPとチェーン・オブ・ファインチューニングデータセットの事前学習における一般化の改善に有効である。
論文 参考訳（メタデータ） (2023-06-14T14:58:36Z) - Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。
ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
論文 参考訳（メタデータ） (2022-02-22T01:49:41Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。