論文の概要: GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs

• arxiv url: http://arxiv.org/abs/2603.01306v1
• Date: Sun, 01 Mar 2026 22:26:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-03 19:50:56.62004
• Title: GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs
• Title（参考訳）: 最適$k$-sparse GLM認証のためのGPUフレンドリで線形収束一階法
• Authors: Jiachang Liu, Andrea Lodi, Soroosh Shafiee,
• Abstract要約: ブランチ・アンド・バウンド(BnB)フレームワークは、パースペクティブ・リラクゼーションを使って最適性を証明できる。 これらの緩和を解く既存の手法は計算集約的であり、スケーラビリティを制限している。 我々は線形収束性と計算効率の両立した近位フレームワークを開発する。
• 参考スコア（独自算出の注目度）: 7.079949618914198
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through a cardinality constraint. While Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations, existing methods for solving these relaxations are computationally intensive, limiting their scalability. To address this challenge, we reformulate the relaxations as composite optimization problems and develop a unified proximal framework that is both linearly convergent and computationally efficient. Under specific geometric regularity conditions, our analysis links primal quadratic growth to dual quadratic decay, yielding error bounds that make the Fenchel duality gap a sharp proxy for progress towards the solution set. This leads to a duality gap-based restart scheme that upgrades a broad class of sublinear proximal methods to provably linearly convergent methods, and applies beyond the sparse GLM setting. For the implicit perspective regularizer, we further derive specialized routines to evaluate the regularizer and its proximal operator exactly in log-linear time, avoiding costly generic conic solvers. The resulting iterations are dominated by matrix--vector multiplications, which enables GPU acceleration. Experiments on synthetic and real-world datasets show orders-of-magnitude faster dual-bound computations and substantially improved BnB scalability on large instances.
• Abstract（参考訳）: 本稿では, 疎一般化線形モデル (GLM) に対する最適性証明の問題について検討する。 ブランチ・アンド・バウンド(BnB)フレームワークはパースペクティブ・リラクゼーションを用いて最適性を証明できるが、これらのリラクゼーションを解決する既存の手法は計算集約的であり、スケーラビリティを制限している。 この課題に対処するため、リラクゼーションを複合最適化問題として再定義し、線形収束性と計算効率の両立した近位フレームワークを開発する。 特定の幾何学的正則性条件の下では、解析は原始二次成長と双対二次崩壊を関連付け、フェンシェル双対性ギャップを解集合への前進の鋭いプロキシとする誤差境界を与える。 これにより、双対性ギャップに基づく再起動スキームが実現可能な線形収束法に幅広いサブ線形近似法をアップグレードし、スパース GLM 設定を超えて適用する。 暗黙的なパースペクティブ・レギュラーライザに対しては、コストのかかる一般的な円錐解法を避けるために、正規化器とその近位演算子を正確にログ線形時間で評価するための特別なルーチンを導出する。 結果として生じるイテレーションは、GPUアクセラレーションを可能にするマトリックス-ベクター乗算によって支配される。 合成および実世界のデータセットの実験では、より高速なデュアルバウンド計算と、大規模インスタンスでのBnBスケーラビリティが大幅に向上した。

関連論文リスト

• Parallel Diffusion Solver via Residual Dirichlet Policy Optimization [88.7827307535107]
  拡散モデル(DM)は、最先端の生成性能を達成したが、シーケンシャルなデノナイジング特性のため、高いサンプリング遅延に悩まされている。 既存のソルバベースの加速度法では、低次元の予算で画像品質が著しく低下することが多い。 本研究では,各ステップに複数の勾配並列評価を組み込んだ新しいODE解法であるEnsemble Parallel Directionsolvr(EPD-EPr)を提案する。
  論文  参考訳（メタデータ） (2025-12-28T05:48:55Z)
• Optimal Transportation and Alignment Between Gaussian Measures [80.4634530260329]
  最適なトランスポート(OT)とGromov-Wasserstein(GW)アライメントは、データセットの解釈可能な幾何学的フレームワークを提供する。 これらのフレームワークは計算コストが高いため、大規模アプリケーションは2次コストでガウス分布の閉形式解に依存することが多い。 この研究は、ガウス的、二次的コスト OT と内部積 GW (IGW) のアライメントを包括的に扱い、文学におけるいくつかのギャップを埋めて適用性を広げる。
  論文  参考訳（メタデータ） (2025-12-03T09:01:48Z)
• Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
  この研究は、一階法のみを用いた線形制約付き双レベル最適化に対する最初の有限時間収束保証を提供する。 線形制約、雑音、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。
  論文  参考訳（メタデータ） (2025-11-13T00:59:20Z)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• $\ell_0$-Regularized Quadratic Surface Support Vector Machines [0.0]
  カーネルフリーの二次曲面支持ベクトルマシンは、カーネル関数に依存することなく非線形決定境界をモデル化する柔軟性により、近年注目を集めている。 本稿では,モデルパラメータに濃度制約を課すことにより,QSVMのスパース変種を提案する。 我々は,いくつかの実世界のデータセットに対するアプローチを検証し,高い分類性能を維持しながらオーバーフィッティングを低減できることを実証した。
  論文  参考訳（メタデータ） (2025-01-20T04:26:34Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)

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

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