論文の概要: Dynamic Ranking and Translation Synchronization
- arxiv url: http://arxiv.org/abs/2207.01455v4
- Date: Wed, 5 Jun 2024 09:16:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 04:58:43.592012
- Title: Dynamic Ranking and Translation Synchronization
- Title（参考訳）: 動的ランク付けと翻訳同期
- Authors: Ernesto Araya, Eglantine Karlé, Hemant Tyagi,
- Abstract要約: 本研究では, エン翻訳同期問題の動的設定への拡張について検討する。
そこで我々は,2つの推定器を提案し,その1つはスムーズネスの最小二乗法に基づくものであり,もう1つは適切な滑らかさ演算子の低周波固有空間への射影に基づくものである。
- 参考スコア（独自算出の注目度）: 3.946250592943285
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In many applications, such as sport tournaments or recommendation systems, we have at our disposal data consisting of pairwise comparisons between a set of $n$ items (or players). The objective is to use this data to infer the latent strength of each item and/or their ranking. Existing results for this problem predominantly focus on the setting consisting of a single comparison graph $G$. However, there exist scenarios (e.g., sports tournaments) where the the pairwise comparison data evolves with time. Theoretical results for this dynamic setting are relatively limited and is the focus of this paper. We study an extension of the \emph{translation synchronization} problem, to the dynamic setting. In this setup, we are given a sequence of comparison graphs $(G_t)_{t\in \mathcal{T}}$, where $\mathcal{T} \subset [0,1]$ is a grid representing the time domain, and for each item $i$ and time $t\in \mathcal{T}$ there is an associated unknown strength parameter $z^*_{t,i}\in \mathbb{R}$. We aim to recover, for $t\in\mathcal{T}$, the strength vector $z^*_t=(z^*_{t,1},\dots,z^*_{t,n})$ from noisy measurements of $z^*_{t,i}-z^*_{t,j}$, where $\{i,j\}$ is an edge in $G_t$. Assuming that $z^*_t$ evolves smoothly in $t$, we propose two estimators -- one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator. For both estimators, we provide finite sample bounds for the $\ell_2$ estimation error under the assumption that $G_t$ is connected for all $t\in \mathcal{T}$, thus proving the consistency of the proposed methods in terms of the grid size $|\mathcal{T}|$. We complement our theoretical findings with experiments on synthetic and real data.
- Abstract（参考訳）: スポーツトーナメントやレコメンデーションシステムなど,多くのアプリケーションにおいて,1組の$n$アイテム(またはプレイヤー)のペア比較からなる廃棄データがある。
目的は、このデータを使って各項目の潜在強度と/またはランキングを推測することである。
この問題の既存の結果は、主に単一の比較グラフ$G$からなる設定に焦点を当てている。
しかし、ペア比較データが時間とともに進化するシナリオ(例えばスポーツトーナメント)が存在する。
この動的設定の理論的結果は比較的限定的であり,本論文の焦点となっている。
本研究では, 動的セッティングに対する \emph{translation synchro} 問題の拡張について検討する。
ここで $\mathcal{T} \subset [0,1]$ は時間領域を表す格子であり、各項目 $i$ と time $t\in \mathcal{T}$ に対して、関連する未知の強度パラメータ $z^*_{t,i}\in \mathbb{R}$ が存在する。
我々は、$t\in\mathcal{T}$ に対して、強度ベクトル $z^*_t=(z^*_{t,1},\dots,z^*_{t,n})$ を $z^*_{t,i}-z^*_{t,j}$ のノイズ測定から回復することを目指している。
例えば、$z^*_t$が$t$で滑らかに進化すると仮定すると、スムーズネスの最小二乗法に基づく2つの推定器と、適切な滑らかさ作用素の低周波固有空間への射影に基づく2つの推定器を提案する。
両方の推定器に対して、$G_t$がすべての$t\in \mathcal{T}$に対して連結であるという仮定の下で$\ell_2$推定誤差に対して有限サンプル境界を与えるので、グリッドサイズ$|\mathcal{T}|$という観点から提案された手法の整合性を証明することができる。
我々は、理論的な結果と、合成および実データに関する実験を補完する。
関連論文リスト
- Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。
制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文 参考訳（メタデータ） (2024-10-30T17:01:00Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。
我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文 参考訳（メタデータ） (2024-05-25T08:34:49Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank
Centrality Method [5.025654873456756]
静的設定から動的設定への古典的BTL(Bradley-Terry-Luce)モデルの拡張について検討する。
我々は mathbbRn$ のアイテム $w_t* の潜在強度をいつでも回復することを目指している。
また、実データおよび合成データに関する実験で理論解析を補完する。
論文 参考訳（メタデータ） (2021-09-28T14:01:40Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳（メタデータ） (2021-01-11T17:23:24Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。