論文の概要: Derivative-Free Optimization via Finite Difference Approximation: An Experimental Study

• arxiv url: http://arxiv.org/abs/2411.00112v1
• Date: Thu, 31 Oct 2024 18:07:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 21:27:52.616921
• Title: Derivative-Free Optimization via Finite Difference Approximation: An Experimental Study
• Title（参考訳）: 差分近似による微分自由最適化の実験的検討
• Authors: Wang Du-Yi, Liang Guo, Liu Guangwu, Zhang Kun,
• Abstract要約: 微分自由最適化(DFO)は、関数評価のみをオラクルで利用できるような複雑な最適化問題の解決に不可欠である。 2つの古典的なイテレーションアプローチは、Kiefer-Wolfowitz (KW) と同時摂動近似 (SPSA) アルゴリズムである。 本稿では,これらの手法の総合的な比較実験を行う。
• 参考スコア（独自算出の注目度）: 1.3886390523644807
• License:
• Abstract: Derivative-free optimization (DFO) is vital in solving complex optimization problems where only noisy function evaluations are available through an oracle. Within this domain, DFO via finite difference (FD) approximation has emerged as a powerful method. Two classical approaches are the Kiefer-Wolfowitz (KW) and simultaneous perturbation stochastic approximation (SPSA) algorithms, which estimate gradients using just two samples in each iteration to conserve samples. However, this approach yields imprecise gradient estimators, necessitating diminishing step sizes to ensure convergence, often resulting in slow optimization progress. In contrast, FD estimators constructed from batch samples approximate gradients more accurately. While gradient descent algorithms using batch-based FD estimators achieve more precise results in each iteration, they require more samples and permit fewer iterations. This raises a fundamental question: which approach is more effective -- KW-style methods or DFO with batch-based FD estimators? This paper conducts a comprehensive experimental comparison among these approaches, examining the fundamental trade-off between gradient estimation accuracy and iteration steps. Through extensive experiments in both low-dimensional and high-dimensional settings, we demonstrate a surprising finding: when an efficient batch-based FD estimator is applied, its corresponding gradient descent algorithm generally shows better performance compared to classical KW and SPSA algorithms in our tested scenarios.
• Abstract（参考訳）: 微分自由最適化(DFO)は、関数評価のみをオラクルで利用できるような複雑な最適化問題の解決に不可欠である。 この領域内では、有限差分(FD)近似によるDFOが強力な方法として現れている。 古典的なアプローチとしては、Kiefer-Wolfowitz (KW) と同時摂動確率近似 (SPSA) アルゴリズムがある。 しかし、このアプローチは不正確な勾配推定器をもたらし、収束を保証するためにステップサイズを小さくする必要があるため、しばしば最適化の進行が遅くなる。 対照的に、バッチサンプルから構築したFD推定器はより正確に近似勾配を推定する。 バッチベースのFD推定器を用いた勾配降下アルゴリズムは、各イテレーションにおいてより正確な結果を得るが、より多くのサンプルを必要とし、より少ないイテレーションを許可する。 KWスタイルのメソッドやバッチベースのFD推定器を使ったDFOなど、どのアプローチがより効果的か、という根本的な疑問が浮かび上がっています。 本稿では,これらの手法の総合的な比較実験を行い,勾配推定精度と繰り返しステップの基本的なトレードオフについて検討する。 低次元および高次元の両方で広範な実験を行い、効率的なバッチベースのFD推定器を適用した場合、その対応する勾配勾配アルゴリズムは、テストシナリオにおける古典的KWアルゴリズムやSPSAアルゴリズムと比較して、一般的に優れた性能を示す。

関連論文リスト

• A Correlation-induced Finite Difference Estimator [6.054123928890574]
  まず, 最適な摂動を推定するためにブートストラップ法を用いて試料駆動法を提案し, そして, 推定された最適摂動の相関値に基づく効率的なFD推定器を提案する。 数値計算により, 推定器の効率性を確認し, 提案理論, 特にサンプルサイズが小さい場合とよく一致した。
  論文  参考訳（メタデータ） (2024-05-09T09:27:18Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
  論文  参考訳（メタデータ） (2022-09-01T11:05:26Z)
• Accelerating Stochastic Probabilistic Inference [1.599072005190786]
  変分推論(SVI)は確率モデルの良好な後部近似を求める能力により、ますます魅力的になっている。 最先端のSVIアルゴリズムのほとんど全てが一階最適化に基づいており、しばしば収束率の低下に悩まされている。 我々は二階法と変分推論のギャップを二階法に基づく変分推論手法によって埋める。
  論文  参考訳（メタデータ） (2022-03-15T01:19:12Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
  本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。 本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
  論文  参考訳（メタデータ） (2020-06-06T21:04:21Z)

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

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