論文の概要: The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network

• arxiv url: http://arxiv.org/abs/2602.07219v1
• Date: Fri, 06 Feb 2026 22:00:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.514746
• Title: The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
• Title（参考訳）: メディアは見た目より簡単:定数深度線形幅ReLUネットワークによる近似
• Authors: Abhigyan Dutta, Itay Safran, Paul Valiant,
• Abstract要約: 本稿では、ReLUニューラルネットワークを用いて、中央値の$d$入力の近似について検討する。 単位ハイパーキューブ上の均一分布に対して指数関数的に小さな近似誤差を実現する定数深さ線形幅構成を提案する。
• 参考スコア（独自算出の注目度）: 4.88752466747693
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the approximation of the median of $d$ inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-width construction that achieves exponentially small approximation error with respect to the uniform distribution over the unit hypercube. By further establishing a general reduction from the maximum to the median, our results break a barrier suggested by prior work on the maximum function, which indicated that linear width should require depth growing at least as $\log\log d$ to achieve comparable accuracy. Our construction relies on a multi-stage procedure that iteratively eliminates non-central elements while preserving a candidate set around the median. We overcome obstacles that do not arise for the maximum to yield approximation results that are strictly stronger than those previously known for the maximum itself.
• Abstract（参考訳）: 本稿では、ReLUニューラルネットワークを用いて、中央値の$d$入力の近似について検討する。 単位ハイパーキューブ上の一様分布に対して指数関数的に小さな近似誤差を実現する定数深度線形幅構成において、いくつかの条件下で深度幅のトレードオフを提示する。 さらに,最大値から中央値への一般還元を確立させることで,線形幅が少なくとも$\log\log d$の深さ成長を必要とすることが示唆された。 我々の構成は、中央値に設定された候補を保存しながら、非中央値要素を反復的に除去する多段階的な手順に依存している。 我々は、これまで最大値で知られていたものよりも厳密な近似結果を得るために、最大値に対して発生しない障害を克服する。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks [2.7195102129095003]
  以下の2つの問題について検討する。 1つ目は、$mathbbRd+1$の任意のソノイドがハウスドルフ距離で$n$の線分で近似できる誤差を決定することである。 2つ目は、変動空間上の浅いReLU$k$ニューラルネットワークの均一ノルムにおける最適近似率を決定することである。
  論文  参考訳（メタデータ） (2023-07-28T03:43:17Z)
• How Many Neurons Does it Take to Approximate the Maximum? [10.995895410470279]
  我々は、$d$入力以上の最大関数を近似するために必要なニューラルネットワークのサイズについて検討する。 様々な深さにまたがる近似に必要な幅について, 新たな下限と上限を提供する。
  論文  参考訳（メタデータ） (2023-07-18T12:47:35Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  本研究では,2次損失を持つ1層多変量ReLUネットワークをトレーニングする際に,勾配勾配勾配が収束する解のタイプについて検討する。 我々は、浅いReLUネットワークが普遍近似器であるにもかかわらず、安定した浅層ネットワークは存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-06-30T09:17:39Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  Nystr"om法に基づく効率的な近似手法を提案する。 サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。 本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
  論文  参考訳（メタデータ） (2022-01-31T08:26:06Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  ランダムに選択されたデータバッチの分類出力行列の構造について検討し,予測可能性と多様性について検討した。 本稿では,目標出力行列上で核ノルムを行い,目標予測能力を向上するBatch Nuclear-norm Maximization and Minimizationを提案する。 実験により,本手法は3つの典型的なドメイン適応シナリオにおいて適応精度とロバスト性を高めることができることが示された。
  論文  参考訳（メタデータ） (2021-07-13T15:08:32Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)

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

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