論文の概要: Scalable First-order Method for Certifying Optimal k-Sparse GLMs

• arxiv url: http://arxiv.org/abs/2502.09502v1
• Date: Thu, 13 Feb 2025 17:14:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:47:22.863731
• Title: Scalable First-order Method for Certifying Optimal k-Sparse GLMs
• Title（参考訳）: 最適k-スパースGLMの証明のためのスケーラブルな1次法
• Authors: Jiachang Liu, Soroosh Shafiee, Andrea Lodi,
• Abstract要約: そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
• 参考スコア（独自算出の注目度）: 9.613635592922174
• License:
• Abstract: This paper investigates the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through an $\ell_0$ cardinality constraint. While branch-and-bound (BnB) frameworks can certify optimality by pruning nodes using dual bounds, existing methods for computing these bounds are either computationally intensive or exhibit slow convergence, limiting their scalability to large-scale problems. To address this challenge, we propose a first-order proximal gradient algorithm designed to solve the perspective relaxation of the problem within a BnB framework. Specifically, we formulate the relaxed problem as a composite optimization problem and demonstrate that the proximal operator of the non-smooth component can be computed exactly in log-linear time complexity, eliminating the need to solve a computationally expensive second-order cone program. Furthermore, we introduce a simple restart strategy that enhances convergence speed while maintaining low per-iteration complexity. Extensive experiments on synthetic and real-world datasets show that our approach significantly accelerates dual bound computations and is highly effective in providing optimality certificates for large-scale problems.
• Abstract（参考訳）: 本稿では,スパース一般化線形モデル (GLM) の最適性を証明する問題について検討する。 分岐とバウンド(BnB)フレームワークは、ノードを2つのバウンドでプルーニングすることで最適性を証明できるが、これらのバウンドを計算する既存の手法は計算集約的であるか、あるいは緩やかな収束を示し、スケーラビリティを大規模問題に制限している。 この課題に対処するために,BnB フレームワーク内の問題に対する視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 具体的には、この緩和問題を合成最適化問題として定式化し、非平滑成分の近作用素をログ線形時間複雑性で正確に計算できることを示し、計算コストのかかる2次コーンプログラムを解く必要がなくなる。 さらに,コンバージェンス速度を低く抑えつつ,コンバージェンス速度を向上する簡単な再起動戦略を導入する。 合成および実世界のデータセットに対する大規模な実験により、我々の手法は双有界計算を著しく加速し、大規模問題に対する最適性証明を提供するのに非常に効果的であることが示された。

関連論文リスト

• qNBO: quasi-Newton Meets Bilevel Optimization [26.0555315825777]
  階層的な学習タスクにおける課題に対処するバイレベル最適化は、機械学習に大きな関心を集めている。 我々はこれらの計算課題に協調的に対処するための一般的な枠組みを導入する。 具体的には、準ニュートンアルゴリズムを利用して、逆ヘッセンベクトル積を効率的に近似しながら、下層問題の解法を高速化する。
  論文  参考訳（メタデータ） (2025-02-03T05:36:45Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
  論文  参考訳（メタデータ） (2022-09-01T11:05:26Z)
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
  直交制約付き分散最適化のための新しいアルゴリズムを提案する。 VRSGTは、サンプリングと通信の複雑さを同時に低減する直交制約付き分散最適化のための最初のアルゴリズムである。 数値実験では、VRGTSは現実の自律的なサンプルにおいて有望な性能を持つ。
  論文  参考訳（メタデータ） (2022-08-29T14:46:44Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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