論文の概要: Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms

• arxiv url: http://arxiv.org/abs/2410.02559v1
• Date: Thu, 3 Oct 2024 15:04:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 02:31:52.762637
• Title: Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms
• Title（参考訳）: 軽量ゼロ階近似勾配アルゴリズムによる低次クエリ複雑性の実現
• Authors: Bin Gu, Xiyuan Wei, Hualin Zhang, Yi Chang, Heng Huang,
• Abstract要約: 複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
• 参考スコア（独自算出の注目度）: 65.42376001308064
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zeroth-order (ZO) optimization is one key technique for machine learning problems where gradient calculation is expensive or impossible. Several variance reduced ZO proximal algorithms have been proposed to speed up ZO optimization for non-smooth problems, and all of them opted for the coordinated ZO estimator against the random ZO estimator when approximating the true gradient, since the former is more accurate. While the random ZO estimator introduces bigger error and makes convergence analysis more challenging compared to coordinated ZO estimator, it requires only $\mathcal{O}(1)$ computation, which is significantly less than $\mathcal{O}(d)$ computation of the coordinated ZO estimator, with $d$ being dimension of the problem space. To take advantage of the computationally efficient nature of the random ZO estimator, we first propose a ZO objective decrease (ZOOD) property which can incorporate two different types of errors in the upper bound of convergence rate. Next, we propose two generic reduction frameworks for ZO optimization which can automatically derive the convergence results for convex and non-convex problems respectively, as long as the convergence rate for the inner solver satisfies the ZOOD property. With the application of two reduction frameworks on our proposed ZOR-ProxSVRG and ZOR-ProxSAGA, two variance reduced ZO proximal algorithms with fully random ZO estimators, we improve the state-of-the-art function query complexities from $\mathcal{O}\left(\min\{\frac{dn^{1/2}}{\epsilon^2}, \frac{d}{\epsilon^3}\}\right)$ to $\tilde{\mathcal{O}}\left(\frac{n+d}{\epsilon^2}\right)$ under $d > n^{\frac{1}{2}}$ for non-convex problems, and from $\mathcal{O}\left(\frac{d}{\epsilon^2}\right)$ to $\tilde{\mathcal{O}}\left(n\log\frac{1}{\epsilon}+\frac{d}{\epsilon}\right)$ for convex problems.
• Abstract（参考訳）: Zeroth-order (ZO) 最適化は、勾配計算が高価または不可能な機械学習問題の鍵となる手法である。 非滑らかな問題に対するZO最適化を高速化するために、いくつかの分散低減ZO近似アルゴリズムが提案されており、これらは全て、真の勾配を近似する際にランダムなZO推定器に対して座標ZO推定器を選択した。 ランダムZO推定器は、座標ZO推定器よりも大きい誤差を導入し、収束解析をより困難にするが、問題空間の次元が$d$であるような、座標ZO推定器の$\mathcal{O}(d)$よりもはるかに小さい$\mathcal{O}(1)$計算しか必要としない。 ランダムZO推定器の計算効率の良い性質を生かし、まず2種類の誤差を収束速度の上界に組み込むZO目標減少(ZOOD)特性を提案する。 次に, 内部解法がZOOD特性を満たす限り, 凸問題と非凸問題に対する収束結果を自動的に導出できるZO最適化のための2つの一般還元フレームワークを提案する。 提案した ZOR-ProxSVRG と ZOR-ProxSAGA に対する2つの還元フレームワークの適用により、完全ランダムな ZO 推定器によるZO 近似アルゴリズムを2つの分散化することにより、非凸問題に対して $\mathcal{O}\left(\min\{\frac{dn^{1/2}}{\epsilon^2}, \frac{d}{\epsilon^3}\right)$ から $\tilde{\mathcal{O}}\left(\frac{n+d}{\epsilon^2}\right)$ と $d > n^{\frac{1}{2}}$ から $\mathcal{O}\left(\frac{d}{\epsilon^2}\right)$ から $\tilde{\mathcal{O}}\left(\frac{n+d}{\epsilon^2}\right)$ へ、そして $\mathcal{O}\left(\frac{d}{\epsilon^2}})$ から $\tilde{\mathcal{O}\left(\tilde{\frac{O}}\right)$ へと改善する。

関連論文リスト

• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem [2.1485350418225244]
  線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。 PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
  論文  参考訳（メタデータ） (2022-03-02T01:16:10Z)
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method [3.860616339202303]
  本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。 エージェントは問題を解くためにzo座標法を近似する。
  論文  参考訳（メタデータ） (2021-03-24T03:07:46Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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