論文の概要: From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces
- arxiv url: http://arxiv.org/abs/2507.13263v3
- Date: Thu, 25 Sep 2025 02:43:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-26 14:16:55.954484
- Title: From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces
- Title（参考訳）: ソルティングアルゴリズムからスケーラブルカーネルへ:高次元置換空間におけるベイズ最適化
- Authors: Zikai Xie, Linjiang Chen,
- Abstract要約: 本稿では,ソートアルゴリズムから派生したカーネル関数を用いて,効率的な置換表現を生成する新しいフレームワークを提案する。
このフレームワーク内では、Mallowsカーネルはソートから派生した特別なインスタンスと見なすことができる。
我々の中心的な主張は、マージカーネルが低次元設定でMallowsカーネルと競合するということである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bayesian Optimization (BO) is a powerful tool for black-box optimization, but its application to high-dimensional permutation spaces is severely limited by the challenge of defining scalable representations. The current state-of-the-art BO approach for permutation spaces relies on an exhaustive $\Omega(n^2)$ pairwise comparison, inducing a dense representation that is impractical for large-scale permutations. To break this barrier, we introduce a novel framework for generating efficient permutation representations via kernel functions derived from sorting algorithms. Within this framework, the Mallows kernel can be viewed as a special instance derived from enumeration sort. Further, we introduce the \textbf{Merge Kernel} , which leverages the divide-and-conquer structure of merge sort to produce a compact, $\Theta(n\log n)$ to achieve the lowest possible complexity with no information loss and effectively capture permutation structure. Our central thesis is that the Merge Kernel performs competitively with the Mallows kernel in low-dimensional settings, but significantly outperforms it in both optimization performance and computational efficiency as the dimension $n$ grows. Extensive evaluations on various permutation optimization benchmarks confirm our hypothesis, demonstrating that the Merge Kernel provides a scalable and more effective solution for Bayesian optimization in high-dimensional permutation spaces, thereby unlocking the potential for tackling previously intractable problems such as large-scale feature ordering and combinatorial neural architecture search.
- Abstract（参考訳）: ベイズ最適化(BO)はブラックボックス最適化のための強力なツールであるが、その高次元置換空間への応用はスケーラブルな表現を定義することの難しさによって著しく制限されている。
置換空間に対する現在の最先端の BO アプローチは、大規模置換には実用的でない密度表現を誘導する、徹底した$\Omega(n^2)$対比較に依存する。
この障壁を断ち切るために、ソートアルゴリズムから派生したカーネル関数を介して効率的な置換表現を生成する新しいフレームワークを導入する。
このフレームワーク内では、Mallowsカーネルは列挙ソートから派生した特別なインスタンスと見なすことができる。
さらに,情報損失を伴わない最小の複雑性を実現するために,マージソートの分母構造を利用して$\Theta(n\log n)$を生成する。
マージカーネルは低次元設定でMallowsカーネルと競合するが、次元$n$が大きくなるにつれて最適化性能と計算効率の両方で大幅に向上する。
様々な置換最適化ベンチマークの広範囲な評価により、マージカーネルは高次元の置換空間におけるベイズ最適化のためのスケーラブルで効率的なソリューションを提供することを示した。
関連論文リスト
- Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳（メタデータ） (2023-12-19T01:52:13Z) - Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳（メタデータ） (2023-09-04T19:47:04Z) - Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-15T04:57:37Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Local Sample-weighted Multiple Kernel Clustering with Consensus
Discriminative Graph [73.68184322526338]
マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。
本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。
実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2022-07-05T05:00:38Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳（メタデータ） (2022-07-02T16:59:37Z) - Scalable First-Order Bayesian Optimization via Structured Automatic
Differentiation [4.061135251278187]
広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。
提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
論文 参考訳（メタデータ） (2022-06-16T17:59:48Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Kernel Clustering with Sigmoid-based Regularization for Efficient
Segmentation of Sequential Data [3.8326963933937885]
セグメント化は、データシーケンスを非線形で複雑な構造を持つ複数の重複しないセグメントに分割することを目的としている。
この問題を最適に解決するための一般的なカーネルは動的プログラミング(DP)である。
最適セグメンテーションを近似するために多くのアルゴリズムが提案されているが、それらの解の品質は保証されていない。
論文 参考訳（メタデータ） (2021-06-22T04:32:21Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization [8.386501595252]
BMM(Block Majorization-minimativeization)は、制約付き非負のサロゲートに対する単純な反復アルゴリズムである。
BMMは,様々なアルゴリズムに対して,新しい一階最適度尺度を生成する。
また, BMM の収束率を向上させるために, 減衰半径の付加的利用が有効であることを示す。
論文 参考訳（メタデータ） (2020-12-07T07:53:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。