論文の概要: First-Order Sparse Convex Optimization: Better Rates with Sparse Updates

• arxiv url: http://arxiv.org/abs/2506.19075v1
• Date: Mon, 23 Jun 2025 19:44:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-25 19:48:23.36407
• Title: First-Order Sparse Convex Optimization: Better Rates with Sparse Updates
• Title（参考訳）: 1次スパース凸最適化:スパース更新によるより良いレート
• Authors: Dan Garber,
• Abstract要約: Inは、疎最適解を用いた凸最適化問題に対して線形収束率を持つことが最近確立された。 改良された混合ノルム条件数に依存する線形収束速度はスパース更新のみを用いて得られることを示す。
• 参考スコア（独自算出の注目度）: 18.035791732015802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In was recently established that for convex optimization problems with a sparse optimal solution (may it be entry-wise sparsity or matrix rank-wise sparsity) it is possible to have linear convergence rates which depend on an improved mixed-norm condition number of the form $\frac{\beta_1{}s}{\alpha_2}$, where $\beta_1$ is the $\ell_1$-Lipchitz continuity constant of the gradient, $\alpha_2$ is the $\ell_2$-quadratic growth constant, and $s$ is the sparsity of the optimal solution. However, beyond the improved convergence rate, these methods are unable to leverage the sparsity of optimal solutions towards improving also the runtime of each iteration, which may still be prohibitively high for high-dimensional problems. In this work, we establish that linear convergence rates which depend on this improved condition number can be obtained using only sparse updates, which may result in overall significantly improved running times. Moreover, our methods are considerably easier to implement.
• Abstract（参考訳）: In が最近確立されたのは、スパース最適解の凸最適化問題(エントリーワイドの空間性や行列ランクの空間性)に対して、$\frac{\beta_1{}s}{\alpha_2}$, $\beta_1$ は勾配の $\ell_1$-Lipchitz 連続性定数、$\alpha_2$ は $\ell_2$-二乗成長定数、$s$ は最適解の空間性に依存する線形収束率を持つことである。 しかし、収束率の改善を超えて、これらの手法は各イテレーションのランタイムの改善にも最適な解の空間性を利用することができない。 本研究では, この改良された条件数に依存する線形収束率を, スパース更新のみで得られることを確認した。 さらに,本手法の実装は極めて容易である。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)

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

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