論文の概要: Minimax Rates for Hyperbolic Hierarchical Learning

• arxiv url: http://arxiv.org/abs/2601.20047v1
• Date: Tue, 27 Jan 2026 20:50:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.657907
• Title: Minimax Rates for Hyperbolic Hierarchical Learning
• Title（参考訳）: 双曲型階層学習のためのミニマックスレート
• Authors: Divit Rawal, Sriram Vishwanath,
• Abstract要約: 階層データから学習するためのユークリッド表現と双曲表現の指数関数的分離を証明した。 任意のランク-$k$予測空間は、O(k)$標準階層的コントラストのみをキャプチャする。
• 参考スコア（独自算出の注目度）: 3.3192479135000426
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove an exponential separation in sample complexity between Euclidean and hyperbolic representations for learning on hierarchical data under standard Lipschitz regularization. For depth-$R$ hierarchies with branching factor $m$, we first establish a geometric obstruction for Euclidean space: any bounded-radius embedding forces volumetric collapse, mapping exponentially many tree-distant points to nearby locations. This necessitates Lipschitz constants scaling as $\exp(Ω(R))$ to realize even simple hierarchical targets, yielding exponential sample complexity under capacity control. We then show this obstruction vanishes in hyperbolic space: constant-distortion hyperbolic embeddings admit $O(1)$-Lipschitz realizability, enabling learning with $n = O(mR \log m)$ samples. A matching $Ω(mR \log m)$ lower bound via Fano's inequality establishes that hyperbolic representations achieve the information-theoretic optimum. We also show a geometry-independent bottleneck: any rank-$k$ prediction space captures only $O(k)$ canonical hierarchical contrasts.
• Abstract（参考訳）: 標準リプシッツ正則化の下で階層データから学習するためのユークリッド表現と双曲表現の間のサンプル複雑性の指数関数的分離を証明した。 深さ-$R$ 分岐係数 $m$ の階層に対して、まずユークリッド空間の幾何学的障害物を確立する:任意の有界半径埋め込みは体積的崩壊を強制し、指数関数的に多くの木距離点を近傍にマッピングする。 これによりリプシッツ定数は$\exp(Ω(R))$としてスケールし、単純な階層的目標さえも達成し、キャパシティコントロールの下で指数的なサンプル複雑性をもたらす。 定数歪み双曲埋め込みは$O(1)$-Lipschitz実現可能性を認め、$n = O(mR \log m)$サンプルで学習することができる。 ファノの不等式による一致する$Ω(mR \log m)$下界は、双曲表現が情報理論最適化を達成することを証明している。 任意のランク-$k$予測空間は、O(k)$標準階層的コントラストのみをキャプチャする。

関連論文リスト

• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  量子ビット効率の最適化を幾何学的問題として再検討する。 局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
  論文  参考訳（メタデータ） (2025-11-11T15:38:57Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Generalization and Stability of Interpolating Neural Networks with Minimal Width [37.908159361149835]
  補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。 トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。 m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
  論文  参考訳（メタデータ） (2023-02-18T05:06:15Z)
• Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure [9.759209713196718]
  我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。 より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
  論文  参考訳（メタデータ） (2022-06-07T20:39:51Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。 ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
  論文  参考訳（メタデータ） (2020-12-21T03:10:21Z)

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

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