論文の概要: Fast Spawn\&Prune (FS\&P): Global convergence of stochastic conic particle gradient descent via birth/death process

• arxiv url: http://arxiv.org/abs/2605.19784v1
• Date: Tue, 19 May 2026 12:50:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.337764
• Title: Fast Spawn\&Prune (FS\&P): Global convergence of stochastic conic particle gradient descent via birth/death process
• Title（参考訳）: Fast Spawn\&Prune (FS\&P): 誕生・死過程による確率円錐粒子勾配のグローバル収束
• Authors: Yohann De Castro, Sébastien Gadat, Clément Marteau,
• Abstract要約: 連続回帰における大域的目的改善関数について検討する。 このクラスのアルゴリズムに対する最初の理論的保証を提供する。 我々は、事前知識を必要としない先行知識を必要としない先行知識を、事前知識を必要としない先行知識を、事前知識を必要としない先行知識を、事前知識を必要としない先行知識を必要としない先行知識を、事前知識を必要としない先行知識を必要としない先行知識を、事前知識を必要としない先行知識を提案する。
• 参考スコア（独自算出の注目度）: 3.377298662011438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the global optimization of the objective function arising in continuous sparse regression, specifically the Beurling LASSO (BLASSO), over the space of measures. While Conic Particle Gradient Descent (CPGD) methods are computationally efficient, they may become trapped in local minima due to the non-convexity of the parameterization. To overcome this limitation, we introduce Fast Spawn\&Prune (FS\&P), a stochastic algorithm that extends FastPart introduced in De Castro et al. (2025) and combines CPGD with a birth-death process. The birth mechanism ensures asymptotic global exploration by introducing particles in regions where first-order optimality conditions are violated, while the death process preserves computational efficiency by pruning non-informative particles. We provide the first theoretical guarantee of global convergence for this class of discrete-time stochastic algorithms, without requiring exponentially large initializations. Furthermore, we derive explicit convergence rates for the excess risk, which scale as $\mathcal{O}\big(\left(\log K / K\right)^{\frac{1}{2(2+d)}}\big)$, where $K$ denotes the number of iterations and d the dimension of the domain, thereby quantifying the trade-off between global exploration and local refinement. Moreover, the sample complexity is $\mathcal{O}\big(N^{-\frac{1}{4(2+d)}}\big)$ (up to logarithmic factors). We also propose a horizon-free variant that does not require prior knowledge of the iteration budget.
• Abstract（参考訳）: 本研究では,連続スパース回帰における目的関数,特にBLASSO(Beurling LASSO)の測度空間における大域的最適化について検討する。 Conic Particle Gradient Descent (CPGD) 法は計算効率が良いが、パラメータ化の非凸性により局所最小値に閉じ込められることがある。 この制限を克服するために、De Castro et al (2025)で導入されたFastPartを拡張した確率的アルゴリズムであるFast Spawn\&Prune (FS\&P)を導入し、CPGDと生死過程を組み合わせた。 誕生メカニズムは、一階最適条件に反する領域に粒子を導入することで漸近的グローバルな探索を保証し、死過程は非情報的粒子を刈り取ることによって計算効率を保っている。 我々は、指数関数的に大きな初期化を必要とせず、このタイプの離散時間確率的アルゴリズムに対して、最初の大域収束の理論的保証を提供する。 さらに、過剰リスクに対する明示的な収束率を導出し、$\mathcal{O}\big(\left(\log K / K\right)^{\frac{1}{2(2+d)}}\big)$、$K$は反復数、dは領域の次元を表し、大域的な探索と局所的な洗練の間のトレードオフを定量化する。 さらに、サンプルの複雑さは$\mathcal{O}\big(N^{-\frac{1}{4(2+d)}}\big)$(対数因子まで)である。 また、イテレーション予算に関する事前の知識を必要としない地平線のない変種も提案する。

関連論文リスト

• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。 実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
  論文  参考訳（メタデータ） (2026-05-09T15:47:20Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties [8.294148737585543]
  本稿では,非二次絶対および非平滑収束ペナルティの存在下での凹凸および切断された量子レグレッションについて検討する。 本稿では,スパース回帰に特化してSIADと呼ばれるペナルティ乗算器が増加する新しいループADMアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-04T21:48:51Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
  コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。 数値実験では, 既存の再起動バージョンよりも改善が見られた。
  論文  参考訳（メタデータ） (2021-08-10T07:15:07Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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