論文の概要: Unraveling Zeroth-Order Optimization through the Lens of Low-Dimensional Structured Perturbations

• arxiv url: http://arxiv.org/abs/2501.19099v1
• Date: Fri, 31 Jan 2025 12:46:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-03 22:46:13.019559
• Title: Unraveling Zeroth-Order Optimization through the Lens of Low-Dimensional Structured Perturbations
• Title（参考訳）: 低次元構造摂動レンズによるゼロ階最適化
• Authors: Sihwan Park, Jihun Yun, SungYub Kim, Souvik Kundu, Eunho Yang,
• Abstract要約: Zeroth-order (ZO) 最適化は、勾配ベースのバックプロパゲーション法に代わる有望な代替手段として登場した。 我々は高次元性が主要なボトルネックであることを示し、構造的摂動が勾配雑音を減らし収束を加速する方法を説明するために、テクティットとテクティット有効摂動の概念を導入する。
• 参考スコア（独自算出の注目度）: 33.38543010618118
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Zeroth-order (ZO) optimization has emerged as a promising alternative to gradient-based backpropagation methods, particularly for black-box optimization and large language model (LLM) fine-tuning. However, ZO methods suffer from slow convergence due to high-variance stochastic gradient estimators. While structured perturbations, such as sparsity and low-rank constraints, have been explored to mitigate these issues, their effectiveness remains highly under-explored. In this work, we develop a unified theoretical framework that analyzes both the convergence and generalization properties of ZO optimization under structured perturbations. We show that high dimensionality is the primary bottleneck and introduce the notions of \textit{stable rank} and \textit{effective overlap} to explain how structured perturbations reduce gradient noise and accelerate convergence. Using the uniform stability under our framework, we then provide the first theoretical justification for why these perturbations enhance generalization. Additionally, through empirical analysis, we identify that \textbf{block coordinate descent} (BCD) to be an effective structured perturbation method. Extensive experiments show that, compared to existing alternatives, memory-efficient ZO (MeZO) with BCD (\textit{MeZO-BCD}) can provide improved converge with a faster wall-clock time/iteration by up to $\times\textbf{2.09}$ while yielding similar or better accuracy.
• Abstract（参考訳）: Zeroth-order (ZO) 最適化は、特にブラックボックス最適化や大規模言語モデル(LLM)の微調整において、勾配ベースのバックプロパゲーション法に代わる有望な代替手段として登場した。 しかし、ZO法は高分散確率勾配推定器によって緩やかに収束する。 疎度や低ランク制約といった構造的摂動はこれらの問題を緩和するために研究されてきたが、その効果は未解明のままである。 本研究では、構造化摂動下でのZO最適化の収束特性と一般化特性の両方を解析する統一的理論フレームワークを開発する。 高次元性が主要なボトルネックであることを示し、構造的摂動が勾配雑音を減らし収束を加速させる方法を説明するために、 \textit{stable rank} と \textit{ Effective overlap} の概念を導入する。 この枠組みの下での均一な安定性を用いて、これらの摂動が一般化を促進する理由を初めて理論的に正当化する。 さらに, 経験的解析により, BCD (textbf{block coordinate descent}) が効果的な構造摂動法であることが確認された。 大規模な実験により、メモリ効率のよいZO (MeZO) とBCD (\textit{MeZO-BCD}) は、より高速なウォールクロック時間/イテレーションを最大$\times\textbf{2.09}$で向上し、類似またはより良い精度が得られることが示された。

関連論文リスト

• SUMO: Subspace-Aware Moment-Orthogonalization for Accelerating Memory-Efficient LLM Training [13.180761892449736]
  低ランク勾配に基づく最適化手法は、大規模言語モデル(LLM)の訓練において、メモリ効率を大幅に改善した。 これらの手法は主にメモリの節約を強調し、しばしば収束の潜在的な加速を見落としている。 本稿では,SUMO(Subspace-Aware Moment-Orthogonalization)を提案する。 我々は,SUMOがコンバージェンスを加速し,安定性を向上し,性能を向上し,最先端手法と比較してメモリ要求を最大20%削減することを示した。
  論文  参考訳（メタデータ） (2025-05-30T16:08:40Z)
• More Optimal Fractional-Order Stochastic Gradient Descent for Non-Convex Optimization Problems [2.5971517743176915]
  本稿では,FOSGDとFOSGDを統合した2FOSGD法を提案する。 感度と有効次元性を追跡することにより、2SEDFOSGDは指数を動的に変調し、スラグ振動と急収束を緩和する。
  論文  参考訳（メタデータ） (2025-05-05T19:27:36Z)
• Iterate to Accelerate: A Unified Framework for Iterative Reasoning and Feedback Convergence [0.0]
  本稿では,Bregmanの発散による非ユークリッド幾何学,高次演算子平均化,適応フィードバック機構を利用した反復推論のための統一的フレームワークを提案する。 我々の分析は、軽度な滑らかさと収縮性仮定の下では、ミラー降下や動的プログラミングのような古典的手法を統一するだけでなく、大規模言語モデルにおける現代の連鎖推論過程も捉えることを証明している。
  論文  参考訳（メタデータ） (2025-02-06T05:24:35Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates [17.777466668123886]
  PROMISE ($textbfPr$econditioned $textbfO$ptimization $textbfM$ethods by $textbfI$ncorporating $textbfS$calable Curvature $textbfE$stimates)はスケッチベースの事前条件勾配アルゴリズムである。 PROMISEには、SVRG、SAGA、およびKatyushaのプレコンディション版が含まれている。
  論文  参考訳（メタデータ） (2023-09-05T07:49:10Z)
• Min-Max Optimization under Delays [26.830212508878162]
  大規模な機械学習問題では遅延と非同期は避けられない。 min-max最適化に類似した理論は存在しない。 たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
  論文  参考訳（メタデータ） (2023-07-13T16:39:01Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。 我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。 アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
  論文  参考訳（メタデータ） (2022-10-31T17:59:29Z)
• SCORE: Approximating Curvature Information under Self-Concordant Regularization [0.0]
  本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。 提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
  論文  参考訳（メタデータ） (2021-12-14T13:03:04Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。 我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
  論文  参考訳（メタデータ） (2021-07-23T13:43:34Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Transient growth of accelerated first-order methods for strongly convex optimization problems [1.6114012813668934]
  本稿では,高速化第一次最適化アルゴリズムの過渡挙動について検討する。 二次最適化問題に対しては、線形系理論のツールを用いて、非正規ダイナミクスの存在から過渡的成長が生じることを示す。 強凸滑らかな最適化問題に対して, 積分二次制約の理論を応用し, ネステロフ加速法の過渡応答の大きさの上限を定式化する。
  論文  参考訳（メタデータ） (2021-03-14T20:01:14Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• BAMSProd: A Step towards Generalizing the Adaptive Optimization Methods to Deep Binary Model [34.093978443640616]
  最近のBNN(Binary Neural Networks)の性能は大幅に低下している。 BNNの効果的かつ効率的なトレーニングを保証することは未解決の問題である。 そこで本研究では,BAMSProdアルゴリズムを用いて,深部二元モデルの収束特性が量子化誤差と強く関連していることを示す。
  論文  参考訳（メタデータ） (2020-09-29T06:12:32Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)

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

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