論文の概要: Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis

• arxiv url: http://arxiv.org/abs/2609.25576v2
• Date: Fri, 25 Sep 2026 01:06:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.033608
• Title: Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis
• Title（参考訳）: 非漸近解析による拡張性最小体積単純度推定
• Abstract要約: 既存の推定器は、サンプルごとの立方体処理か、または$O(NK)$ストレージを必要とする。 DeepMVSAは神経暗黙の形で最小限の原理を再表現する。 最大$N=108$の合成観測実験は、予測された精度とスケーリングと一致している。
• 参考スコア（独自算出の注目度）: 3.008906408145323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the estimation of a $K$-dimensional simplex from $N$ i.i.d.\ points sampled uniformly from its interior; the observations are convex combinations of $K+1$ unknown prototypes. Existing polynomial-time estimators need cubic per-sample work or $O(NK)$ storage and are impractical at $N\sim 10^6$--$10^8$. We propose DeepMVSA, which re-expresses the minimum-volume principle in neural implicit form: a lightweight coordinate network generates the mixing weights and a triangular LU-type parameterization the dual simplex matrix, reducing the trainable-state memory to $O(K^2)$, independent of $N$, and the cost per data pass to $O(NK^2)$. We prove a non-asymptotic sample-complexity bound of the polynomial-time benchmark order for a localized surrogate estimator; an oracle inequality for every global minimizer of the neural objective, with volume-inflation control and an explicit shrinkage bias; a conditional end-to-end error budget separating statistical, approximation, optimization, and enclosure-residual terms on an explicit envelope event; and two-point lower bounds: at any noise level $σ>0$ fixed independently of $N$, the $N^{-1/2}$ scaling is unimprovable in its $N$-exponent. Experiments with up to $N=10^8$ synthetic observations are consistent with the predicted accuracy and scaling, and feasibility on real scenes of $\sim 10^7$ pixels is demonstrated.
• Abstract（参考訳）: 我々は、内部から一様にサンプリングされた$N$ i.i.d.\点から$K$次元の単純点を推定し、その観測は、$K+1$未知のプロトタイプの凸結合である。 既存の多項式時間推定器は、サンプル当たりの立方的作業またはO(NK)$ストレージを必要とし、N\sim 10^6$-$10^8$で非現実的である。 軽量座標ネットワークは混合重みと三角LU型パラメータ化を二重単純行列に生成し、トレーニング可能な状態メモリを$O(K^2)$、$N$とは独立に$O(NK^2)$に還元し、データ当たりのコストを$O(NK^2)$とする。 局所的なサロゲート推定器に対する多項式時間ベンチマークオーダーの非漸近的なサンプル-複雑性境界、体積インフレーション制御と明示的収縮バイアスを持つ神経目的のすべての大域的最小化器に対するオラクル不等式、明示的エンベロープイベントにおける統計的、近似、最適化、および囲い込み残差項を分離する条件付きエラー予算、および2点下限:任意のノイズレベル$σ>0$$$N$とは独立に固定された場合、$N$-1/2$スケールは$N$-exponentでは不可能である。 N=10^8$の合成観測実験は、予測精度とスケーリングと一致し、$\sim 10^7$ピクセルの実シーンで実現可能性を示す。

関連論文リスト

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization [0.6015898117103067]
  我々は,条件付き予測を共同で推定し,外的目的を最適化する同時学習最適化アルゴリズムを解析する。 我々は,この手法が次数$mathcalObig (1/sqrtNbig)$の収束率を達成することを証明した。
  論文  参考訳（メタデータ） (2026-03-13T14:53:35Z)
• Interplay between depth and width for interpolation in neural ODEs [0.0]
  それらの幅$p$と層遷移数$L$の相互作用について検討する。 高次元設定では、$p=O(N)$ニューロンが正確な制御を達成するのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-01-18T11:32:50Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。 本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
  論文  参考訳（メタデータ） (2023-06-26T17:13:31Z)
• A note on $L^1$-Convergence of the Empiric Minimizer for unbounded functions with fast growth [0.0]
  V : mathbbRd to mathbbR$ coercive に対して、経験的最小値の$L1$-distance の収束率について検討する。 一般に、高速な成長を持つ非有界函数に対しては、収束率は上述の$a_n n-1/q$で制限され、$q$は潜在確率変数の次元である。
  論文  参考訳（メタデータ） (2023-03-08T08:46:13Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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