論文の概要: A theoretical guarantee for SyncRank
- arxiv url: http://arxiv.org/abs/2509.22766v1
- Date: Fri, 26 Sep 2025 16:45:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-30 22:32:18.866292
- Title: A theoretical guarantee for SyncRank
- Title（参考訳）: SyncRankの理論的保証
- Authors: Yang Rao,
- Abstract要約: 雑音のペア比較からグローバルランキングを復元する SyncRank アルゴリズムの理論的,実証的な解析を行う。
我々の主定理は臨界雑音閾値(sigma = O(sqrt(n / log n))を特徴付け、SyncRankは高い確率で正確なランク回復を達成する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a theoretical and empirical analysis of the SyncRank algorithm for recovering a global ranking from noisy pairwise comparisons. By adopting a complex-valued data model where the true ranking is encoded in the phases of a unit-modulus vector, we establish a sharp non-asymptotic recovery guarantee for the associated semidefinite programming (SDP) relaxation. Our main theorem characterizes a critical noise threshold - scaling as sigma = O(sqrt(n / log n)) - below which SyncRank achieves exact ranking recovery with high probability. Extensive experiments under this model confirm the theoretical predictions and demonstrate the algorithm's robustness across varying problem sizes and noise regimes.
- Abstract（参考訳）: 雑音のペア比較からグローバルランキングを復元する SyncRank アルゴリズムの理論的,実証的な解析を行う。
単位モジュラーベクトルの位相に真のランクが符号化された複素数値データモデルを採用することにより、関連する半定値プログラミング(SDP)緩和のための急激な非漸近回復保証を確立する。
我々の主定理は臨界雑音閾値(sigma = O(sqrt(n / log n))を特徴付け、SyncRankは高い確率で正確なランク回復を達成する。
このモデルの下での広範囲な実験は、理論的な予測を確認し、様々な問題サイズとノイズレシエーションにまたがるアルゴリズムの頑健さを実証する。
関連論文リスト
- Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Stochastic Gradient Descent Revisited [0.0]
勾配降下(SGD)は、機械学習における非勾配収束問題のアルゴリズムである。
本稿では、全範囲収束理論を示し、速度と複雑さを提供する。
論文 参考訳（メタデータ） (2024-12-08T21:15:08Z) - Regression with Label Differential Privacy [64.21020761920322]
与えられた回帰損失関数の下で最適なラベルDPランダム化機構を導出する。
我々は、最適メカニズムが「ビンのランダム化応答」の形をとることを証明した。
論文 参考訳（メタデータ） (2022-12-12T17:41:32Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Label Ranking through Nonparametric Regression [5.994412766684843]
ラベルランキング(英: Label Ranking)とは、有限個のラベルの上のランクに特徴をマップする仮説を学習する問題である。
雑音のない非パラメトリック回帰設定において,ラベルランク付けのための生成モデルを導入する。
我々は,入力回帰雑音が観測された出力にどのように影響するかを理解することを目的として,実験による理論的貢献を補完する。
論文 参考訳（メタデータ） (2021-11-04T10:59:46Z) - Optimizing Information-theoretical Generalization Bounds via Anisotropic
Noise in SGLD [73.55632827932101]
SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。
低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
論文 参考訳（メタデータ） (2021-10-26T15:02:27Z) - On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。
本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。
理論的にも経験的にも二重降下現象を観察する。
論文 参考訳（メタデータ） (2021-10-13T17:47:39Z) - Statistical optimality and stability of tangent transform algorithms in
logit models [6.9827388859232045]
我々は,データ生成過程の条件として,ロジカルオプティマによって引き起こされるリスクに対して,非漸近上界を導出する。
特に,データ生成過程の仮定なしにアルゴリズムの局所的変動を確立する。
我々は,大域収束が得られる半直交設計を含む特別な場合について検討する。
論文 参考訳（メタデータ） (2020-10-25T05:15:13Z) - Consistency of Anchor-based Spectral Clustering [0.0]
アンカーベースの手法は、スペクトルクラスタリングアルゴリズムの計算複雑性を低減する。
厳密な分析が可能であり,実践に有効であることを示す。
我々はChenとCaiの最先端のLCC法と競合することが判明した。
論文 参考訳（メタデータ） (2020-06-24T18:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。