論文の概要: "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection
- arxiv url: http://arxiv.org/abs/2402.02196v3
- Date: Tue, 17 Dec 2024 14:02:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-18 13:54:23.286942
- Title: "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection
- Title(参考訳): クラスタリングとコンカヤ」による大規模ランキングと選抜の並列化
- Authors: Zishi Zhang, Yijie Peng,
- Abstract要約: 並列コンピューティングにおいてよく使われる「分割と征服」フレームワークを,相関に基づくクラスタリングのステップを追加して修正する。
この一見単純な修正は、$mathcalO(p)$サンプルの複雑さの減少率を達成することができる。
ニューラルネットワーク探索のような大規模AIアプリケーションでは,本手法は優れた性能を示す。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: This work breaks the sample efficiency bottleneck in parallel large-scale ranking and selection (R&S) problem by leveraging correlation information. We modify the commonly used "divide and conquer" framework in parallel computing by adding a correlation-based clustering step, transforming it into "clustering and conquer". This seemingly simple modification can achieve an $\mathcal{O}(p)$ sample complexity reduction rate, which represents the maximum attainable reduction for the class of sample-optimal R&S methods. Our approach enjoys two key advantages: 1) it does not require highly accurate correlation estimation or precise clustering, and 2) it allows for seamless integration with various existing R&S method, while achieving optimal sample complexity. Theoretically, we develop a novel gradient analysis framework to analyze sample efficiency and guide the design of large-scale R&S procedures. Building upon this framework, we propose a gradient-based budget allocation policy. We also introduce a new clustering algorithm, selection policy, and precision criterion tailored for large-scale scenarios. Finally, in large-scale AI applications such as neural architecture search, our methods demonstrate superior performance.
- Abstract(参考訳): この研究は、相関情報を活用することで、並列大規模ランキングと選択(R&S)問題におけるサンプル効率のボトルネックを破る。
我々は、相関に基づくクラスタリングのステップを追加して、並列コンピューティングでよく使われる「分割と征服」のフレームワークを変更し、それを「クラスタリングと征服」に変換する。
この一見単純な修正は$\mathcal{O}(p)$サンプル複雑性低減率を達成でき、これはサンプル最適化R&S法のクラスで達成可能な最大還元率を示す。
私たちのアプローチには2つの大きな利点があります。
1)高精度な相関推定や正確なクラスタリングは必要とせず、
2) 様々な既存R&S手法とシームレスに統合でき, 最適なサンプル複雑性を実現することができる。
理論的には、サンプル効率を解析し、大規模R&S手順の設計を導くための新しい勾配解析フレームワークを開発する。
この枠組みに基づいて、勾配に基づく予算配分政策を提案する。
また、大規模シナリオに適した新しいクラスタリングアルゴリズム、選択ポリシー、精度基準も導入する。
最後に,ニューラルネットワーク探索などの大規模AIアプリケーションにおいて,本手法は優れた性能を示す。
関連論文リスト
- Fast and Scalable Semi-Supervised Learning for Multi-View Subspace Clustering [13.638434337947302]
FSSMSCは、既存のアプローチで一般的に見られる高い計算複雑性に対する新しいソリューションである。
この手法は、各データポイントを選択されたランドマークの疎線型結合として表現し、すべてのビューにまたがるコンセンサスアンカーグラフを生成する。
FSSMSCの有効性と効率は、様々なスケールの複数のベンチマークデータセットに対する広範な実験を通して検証される。
論文 参考訳(メタデータ) (2024-08-11T06:54:00Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳(メタデータ) (2024-02-02T13:31:24Z) - Sparse Variational Student-t Processes [8.46450148172407]
学生Tプロセスは、重い尾の分布とデータセットをアウトリーチでモデル化するために使用される。
本研究では,学生プロセスが現実のデータセットに対してより柔軟になるためのスパース表現フレームワークを提案する。
UCIとKaggleの様々な合成および実世界のデータセットに対する2つの提案手法の評価を行った。
論文 参考訳(メタデータ) (2023-12-09T12:55:20Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳(メタデータ) (2023-07-26T16:19:19Z) - Global Optimization for Cardinality-constrained Minimum Sum-of-Squares
Clustering via Semidefinite Programming [1.3053649021965603]
最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。
本稿では,分枝切断法に基づく大域的最適化手法を提案する。
上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
論文 参考訳(メタデータ) (2022-09-19T10:19:06Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳(メタデータ) (2022-08-02T01:49:31Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - DyCo3D: Robust Instance Segmentation of 3D Point Clouds through Dynamic
Convolution [136.7261709896713]
本稿では,インスタンスの性質に応じて適切な畳み込みカーネルを生成するデータ駆動型アプローチを提案する。
提案手法はScanetNetV2とS3DISの両方で有望な結果が得られる。
また、現在の最先端よりも推論速度を25%以上向上させる。
論文 参考訳(メタデータ) (2020-11-26T14:56:57Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Optimizing generalization on the train set: a novel gradient-based
framework to train parameters and hyperparameters simultaneously [0.0]
一般化は機械学習における中心的な問題である。
本稿では,新たなリスク尺度に基づく新しい手法を提案する。
論文 参考訳(メタデータ) (2020-06-11T18:04:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。