論文の概要: History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities
- arxiv url: http://arxiv.org/abs/2606.24465v1
- Date: Tue, 23 Jun 2026 11:58:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-24 22:16:48.934417
- Title: History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities
- Title（参考訳）: ランダム再帰木における履歴推定:反復ジョルダン中心性によるポイントワイズアプローチ
- Authors: Johannes Bäumler, Simon Briend, Joost Jorritsma,
- Abstract要約: 本研究は,木の大きさと境界に一様である相対推定誤差と導出テールの分布を解析する。
ジョーダン中心性によって誘導されるランクについて、推定値が真の到着時刻を超える確率は、1/S$の順序で$S$崩壊する。
過大な推定テールが$(log S)/S2$の順序で減衰する洗練された中央度尺度を、より低いテールオーダー1/S2$のコストで導入する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of estimating the arrival times of vertices in a uniform random recursive tree from its unlabeled structure. We adopt a pointwise perspective and analyze the distribution of the relative estimation error, and derive tail bounds that are uniform in both the vertex and the tree size. For the ranking induced by Jordan centrality, the probability that the estimate exceeds the true arrival time by a factor $S$ decays on the order of $1/S$, while the probability of underestimating the arrival time by a factor $1/S$ decays exponentially in $S$. We introduce a refined centrality measure whose overestimation tail decays on the order of $(\log S)/S^{2}$, at the cost of a heavier lower tail of order $1/S^{2}$. These results reveal a tradeoff between upper- and lower-tail performance in arrival-time estimation that is invisible to the previously studied risk functional. Nevertheless, the refined centrality measure attains the optimal order of the risk for all its parameter values.
- Abstract（参考訳）: 非ラベル構造から一様無作為再帰木における頂点の到達時刻を推定する問題について検討する。
我々は,頂点と木の大きさの双方で一様である尾の境界を導出し,相対的な推定誤差の分布を分析し,ポイントワイズな視点を採用する。
ジョーダン中心性によって引き起こされたランキングでは、推定値が真の到着時刻を超える確率は1/S$の次数で$S$崩壊するが、到着時刻を1/S$の次数で指数関数的に$S$の次数で過小評価する確率は$S$の次数で$S$崩壊する。
過大推定テールが$(\log S)/S^{2}$の順序で減衰する洗練された中央性測度を導入する。
これらの結果から, 従来検討されていたリスク関数には見えない, 到着時推定における上尾と下尾のトレードオフが明らかとなった。
それでも、洗練された集中度尺度は、全てのパラメータ値に対するリスクの最適順序に達する。
関連論文リスト
- Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization [62.48819955422706]
大規模偏差理論のレンズによるSGD法における長期のテール崩壊について検討する。
我々は、テールが以前よりもはるかに早く崩壊する体制を発見し、個々のランニングに対してより強力な長期保証を提供する。
論文 参考訳（メタデータ） (2026-02-05T13:41:13Z) - Approximating $f$-Divergences with Rank Statistics [0.3222802562733787]
ランクの分布を直接扱うことで、明示的な密度比推定を避けるために、$f$-divergencesのランク統計近似を導入する。
発散の結果として生じる推定量は、K$の単調であり、常に真$f$-発散の下位境界であることを示す。
ニューラルベースラインに対するベンチマークによるアプローチを実証的に検証し,生成モデル実験における学習目的としての利用を例証する。
論文 参考訳（メタデータ） (2026-01-30T10:05:33Z) - SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
勾配降下 (SGD) は, 広範囲の段階的スケジュールと探索率スキームの下で, 独立情報と依存情報の両方に対応できることが示されている。
SGDは統計的に最適な推定誤差と後悔を同時に達成し,既存の結果を拡張し,改善することを示す。
オンラインのスパースレグレッションのために、我々はSGDベースの新しいアルゴリズムを開発し、ストレージの$d$のみを使用し、1イテレーションあたり$O(d)$フロップを必要とする。
論文 参考訳（メタデータ） (2026-01-04T04:52:11Z) - Learning the score under shape constraints [7.005582630391827]
正方形の$L2(P_0)$-lossに対するスコア推定の最小リスクについて検討する。
推定問題の2つの基本的な側面を捉えた対数凹密度のサブクラスを定義する。
後者のクラスに対するミニマックスリスクは、次数$L2/(2+1)n-/(2+1)$からpoly-logarithmic factorまでである。
論文 参考訳（メタデータ） (2025-12-16T17:39:54Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Unbiased least squares regression via averaged stochastic gradient descent [0.0]
最適解 $theta*$ および Hessian matrix H を用いたオンライン最小二乗回帰問題を考える。
kge2$の場合、時間平均推定器の修正である$theta*$の偏りのない推定器を提供する。
論文 参考訳（メタデータ） (2024-06-26T11:39:22Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Super fast rates in structured prediction [88.99819200562784]
連続的な問題が連続的な値を予測しているときに、離散的な問題が本質的に離散的なアウトプットを予測しているという事実を活用する方法を示す。
まず、近接する隣人に基づく予測器について説明し、二項分類で知られている確率を、構造的予測の枠組み内の任意の離散問題に一般化する。
次に、カーネルリッジの回帰について検討し、問題の硬さを特徴付けるパラメータによって、n-1/4$の既知のレートを任意に高速化する。
論文 参考訳（メタデータ） (2021-02-01T10:50:04Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳（メタデータ） (2021-01-31T16:17:56Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。