論文の概要: 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 14:01:15.251401
• 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:
• 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}$で向上し、類似またはより良い精度が得られることが示された。

関連論文リスト

• 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)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• 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)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• 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)

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

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