論文の概要: From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs

• arxiv url: http://arxiv.org/abs/2605.22188v1
• Date: Thu, 21 May 2026 08:56:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 16:35:42.175055
• Title: From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs
• Title（参考訳）: 逐次ノードからGPUバッチ: 最適な$k$-sparse GLMのための並列ブランチとバウンド
• Authors: Jiachang Liu, Andrea Lodi,
• Abstract要約: 分岐およびバウンド(BnB)における異種ノードを処理する汎用的なモジュラーフレームワークを提案する。 このフレームワークはGPU効率の小さなルーチンを中心に構築されており、パディングと軽量のカスタムカーネルを使って不規則なノードデータ構造を処理する。 実験では、挑戦するインスタンスに対して1から2桁のスピードアップと最適性ギャップがゼロであることが示されている。
• 参考スコア（独自算出の注目度）: 6.381561491422844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: GPUs have significantly accelerated first-order methods for large-scale optimization, especially in continuous optimization. However, this success has not transferred cleanly to problems with discrete variables, combinatorial structure, and nonlinear objectives, such as certifying optimal solutions for cardinality-constrained generalized linear models. Major challenges include the sequential processing of heterogeneous nodes in branch and bound (BnB) and frequent data movement between the CPU and GPU. We propose a simple, generic, and modular CPU--GPU framework that processes multiple BnB nodes in batches on GPUs. The framework is built around a small set of GPU-efficient routines and uses padding together with lightweight custom kernels to handle irregular node data structures. Experiments show one to two orders of magnitude speedups and zero optimality gap on challenging instances. The framework can also be extended to collect the entire Rashomon set, enabling downstream statistical analysis such as variable-importance analysis and model selection under secondary user-specific measures (e.g., AUC in classification).
• Abstract（参考訳）: GPUは、特に連続最適化において、大規模最適化のための一階法を大幅に高速化した。 しかし、この成功は、離散変数、組合せ構造、非線形目的に関する問題、例えば濃度制約付き一般化線形モデルに対する最適解の証明にきれいに移行していない。 主な課題は、ブランチとバウンド(BnB)における異種ノードのシーケンシャルな処理と、CPUとGPU間の頻繁なデータ移動である。 我々は,複数のBnBノードをGPU上でバッチ処理する,シンプルで汎用的でモジュール化されたCPU-GPUフレームワークを提案する。 このフレームワークはGPU効率の小さなルーチンを中心に構築されており、パディングと軽量のカスタムカーネルを使って不規則なノードデータ構造を処理する。 実験では、挑戦するインスタンスに対して1から2桁のスピードアップと最適性ギャップがゼロであることが示されている。 フレームワークを拡張してRashomonセット全体の収集も可能で、変数重要度分析やモデル選択といった下流の統計分析を、二次的なユーザ固有測度(例えば、分類におけるAUC)で行うことができる。

関連論文リスト

• Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly [0.42970700836450487]
  ゲノム組立問題に対する短期量子最適化手法を開発した。 固定された線形ランプQAOAスケジュールと反復的ウォームスタートバイアス更新を組み合わせたIterative-QAOAフレームワークを使用する。 カスタム回路コンパイル戦略は、標準ツールと比較してハードウェアゲートのオーバーヘッドを最大67%削減する。
  論文  参考訳（メタデータ） (2026-04-07T17:17:34Z)
• Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
  本稿では,連続凸プログラミングと乗算器のコンセンサスに基づく交互方向法を組み合わせた,フルGPUネイティブなトラジェクトリ最適化フレームワークを提案する。 本研究は,有人エッジコンピューティングプラットフォームを用いて,四重項アジャイル飛行タスクと火星搭載降下問題の解法を検証した。 ベンチマークでは、高度に最適化された12コアのCPUベースラインよりも、持続的な4倍のスループットのスピードアップとエネルギー消費の51%削減が明らかにされている。
  論文  参考訳（メタデータ） (2026-03-11T12:39:14Z)
• NGPU-LM: GPU-Accelerated N-Gram Language Model for Context-Biasing in Greedy ASR Decoding [54.88765757043535]
  この研究は、統計的なn-gram言語モデルのデータ構造を再考し、GPU最適化推論の高速かつ並列な操作を可能にする。 我々のアプローチは NGPU-LM と呼ばれ、7% 未満の計算オーバーヘッドを持つ全ての主要な ASR モデルに対して、カスタマイズ可能なgreedy decoding を導入している。 提案手法は,ビーム探索による顕著な遅延を回避しつつ,greedy と beam search の精度ギャップの50%以上を排除できる。
  論文  参考訳（メタデータ） (2025-05-28T20:43:10Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers [65.60007071024629]
  本稿では,Adaptive SGDが4つの最先端ソリューションよりも精度が高いことを示す。 本稿では,Adaptive SGDが時間と精度で4つの最先端ソリューションより優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-13T20:58:15Z)
• Kernel Clustering with Sigmoid-based Regularization for Efficient Segmentation of Sequential Data [3.8326963933937885]
  セグメント化は、データシーケンスを非線形で複雑な構造を持つ複数の重複しないセグメントに分割することを目的としている。 この問題を最適に解決するための一般的なカーネルは動的プログラミング(DP)である。 最適セグメンテーションを近似するために多くのアルゴリズムが提案されているが、それらの解の品質は保証されていない。
  論文  参考訳（メタデータ） (2021-06-22T04:32:21Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
  ヘテロジニアスCPU+GPUアーキテクチャの深層学習のためのトレーニングアルゴリズムについて検討する。 私たちの2倍の目標 -- 収束率と資源利用を同時に最大化する -- は、この問題を難しくします。 これらのアルゴリズムの実装は,複数の実データセットよりも高速な収束と資源利用の両立を実現していることを示す。
  論文  参考訳（メタデータ） (2020-04-19T05:21:20Z)

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

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