論文の概要: Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations

• arxiv url: http://arxiv.org/abs/2511.21890v2
• Date: Tue, 02 Dec 2025 04:05:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-03 14:50:32.050101
• Title: Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations
• Title（参考訳）: Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations
• Authors: Dimitris Bertsimas, Caio de Prospero Iglesias, Nicholas A. G. Johnson,
• Abstract要約: ベクトル二項分類を支援するために,事前に規定されたカーネルのスパース組み合わせを選択することの問題点を考察する。 最良の応答によって返されるソリューションを認証し、開始を温めるために使用できる予測の階層を導出します。
• 参考スコア（独自算出の注目度）: 4.86840788259762
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing l1 regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an l2 penalty for robustness. We solve the resulting non-convex minimax problem via an alternating best response algorithm with two subproblems: the alpha subproblem is a standard kernel SVM dual solved via LIBSVM, while the beta subproblem admits an efficient solution via the Greedy Selector and Simplex Projector algorithm. We reformulate SMKL as a mixed integer semidefinite optimization problem and derive a hierarchy of semidefinite convex relaxations which can be used to certify near-optimality of the solutions returned by our best response algorithm and also to warm start it. On ten UCI benchmarks, our method with random initialization outperforms state-of-the-art MKL approaches in out-of-sample prediction accuracy on average by 3.34 percentage points (relative to the best performing benchmark) while selecting a small number of candidate kernels in comparable runtime. With warm starting, our method outperforms the best performing benchmark's out-of-sample prediction accuracy on average by 4.05 percentage points. Our convex relaxations provide a certificate that in several cases, the solution returned by our best response algorithm is the globally optimal solution.
• Abstract（参考訳）: 本研究では,ベクトル二分法をサポートするために,あらかじめ規定されたカーネルのスパース凸結合を選択する問題であるスパース多重カーネル学習(SMKL)について検討する。 スパース化ペナルティを近似する一般的な l1 正規化アプローチとは異なり、カーネル重みに明示的な濃度制約を課し、ロバスト性に l2 ペナルティを加えることで問題を定式化する。 アルファサブプロブレムは標準カーネルSVMであり、ベータサブプロブレムはGreedy Selector と Simplex Projector のアルゴリズムによる効率的な解を認めている。 SMKLを混合整数半定値最適化問題として再構成し、最適応答アルゴリズムによって返される解のほぼ最適性を証明し、その解を温められる半定凸緩和の階層を導出する。 10のUCIベンチマークにおいて, ランダム初期化手法は, 平均3.34ポイント(最高の性能ベンチマーク)で, 最先端のMKL手法よりも高い精度で, 少数の候補カーネルを選択しながら, 平均3.34ポイントの精度で予測精度を向上する。 ウォームスタートでは,ベンチマークのアウトオブサンプル予測精度を平均4.05ポイント向上させる。 凸緩和は、いくつかのケースにおいて、最良の応答アルゴリズムによって返される解が、大域的に最適な解であることを示す。

関連論文リスト

• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Compressed Sensing: A Discrete Optimization Approach [5.877778007271621]
  本稿では, 2次円錐緩和を強化し, 独自の分岐結合アルゴリズムを開発する半定緩和法を提案する。 マルチラベル分類アルゴリズムの構成要素として用いられる場合,提案手法は,ベンチマーク圧縮センシング法よりも高い分類精度を実現する。
  論文  参考訳（メタデータ） (2023-06-05T01:29:24Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。