論文の概要: Lazy Queries Can Reduce Variance in Zeroth-order Optimization

• arxiv url: http://arxiv.org/abs/2206.07126v1
• Date: Tue, 14 Jun 2022 19:38:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-16 13:19:55.257440
• Title: Lazy Queries Can Reduce Variance in Zeroth-order Optimization
• Title（参考訳）: 遅延クエリはゼロ階最適化におけるばらつきを低減できる
• Authors: Quan Xiao, Qing Ling and Tianyi Chen
• Abstract要約: LAZOと呼ばれる適応遅延クエリに基づくゼロ階法(ZO)の勾配推定手法を提案する。 LAZOは、古いクエリを司法的に再利用することで、勾配推定のばらつきを減らすことができることを厳格に証明する。
• 参考スコア（独自算出の注目度）: 34.29567699904557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major challenge of applying zeroth-order (ZO) methods is the high query complexity, especially when queries are costly. We propose a novel gradient estimation technique for ZO methods based on adaptive lazy queries that we term as LAZO. Different from the classic one-point or two-point gradient estimation methods, LAZO develops two alternative ways to check the usefulness of old queries from previous iterations, and then adaptively reuses them to construct the low-variance gradient estimates. We rigorously establish that through judiciously reusing the old queries, LAZO can reduce the variance of stochastic gradient estimates so that it not only saves queries per iteration but also achieves the regret bound for the symmetric two-point method. We evaluate the numerical performance of LAZO, and demonstrate the low-variance property and the performance gain of LAZO in both regret and query complexity relative to several existing ZO methods. The idea of LAZO is general, and can be applied to other variants of ZO methods.
• Abstract（参考訳）: ゼロオーダー(ZO)メソッドを適用する際の大きな課題は、特にクエリが高価である場合、高いクエリ複雑性である。 LAZOと呼ばれる適応型遅延クエリに基づくZO法のための新しい勾配推定手法を提案する。 従来の1点または2点勾配推定法とは異なり、lazoは以前のイテレーションから古いクエリの有用性をチェックするための2つの代替手法を開発し、それらを適応的に再利用して低分散勾配推定を構築する。 LAZOは,従来のクエリを巧みに再利用することにより,確率勾配推定のばらつきを低減し,反復毎にクエリを節約するだけでなく,対称二点法に対する後悔のバウンダリを達成できることを確認した。 我々は,LAZOの数値性能を評価し,LAZOの低分散特性と性能向上を,既存のZO法と比較して,後悔と問合せの複雑さの両方において示す。 LAZOの考え方は一般であり、ZO法の他の変種にも適用することができる。

関連論文リスト

• 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)
• Improving Diffusion Models for Inverse Problems Using Optimal Posterior Covariance [52.093434664236014]
  近年の拡散モデルは、特定の逆問題に対して再訓練することなく、ノイズの多い線形逆問題に対する有望なゼロショット解を提供する。 この発見に触発されて、我々は、最大推定値から決定されるより原理化された共分散を用いて、最近の手法を改善することを提案する。
  論文  参考訳（メタデータ） (2024-02-03T13:35:39Z)
• Improving Diffusion Models for Inverse Problems using Manifold Constraints [55.91148172752894]
  我々は,現在の解法がデータ多様体からサンプルパスを逸脱し,エラーが蓄積することを示す。 この問題に対処するため、多様体の制約に着想を得た追加の補正項を提案する。 本手法は理論上も経験上も従来の方法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-02T09:06:10Z)
• Stochastic Gradient Methods with Preconditioned Updates [47.23741709751474]
  このような問題に対するアルゴリズムはいくつかあるが、既存の手法は、スケールが悪く、あるいは条件が悪ければ、しばしばうまく機能しない。 ここではハッチンソンの対角ヘッセン近似のアプローチに基づく前提条件を含む。 我々は滑らかさとPL条件が仮定されるときの収束性を証明する。
  論文  参考訳（メタデータ） (2022-06-01T07:38:08Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Scalable Gaussian-process regression and variable selection using Vecchia approximations [3.4163060063961255]
  ヴェッキアをベースとしたミニバッチサブサンプリングは、偏りのない勾配推定器を提供する。 偏りのない勾配推定器を提供するVecchiaベースのミニバッチサブサンプリングを提案する。
  論文  参考訳（メタデータ） (2022-02-25T21:22:38Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
  我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。 問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。 また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
  論文  参考訳（メタデータ） (2021-09-07T17:21:09Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach [80.59047515124198]
  機械学習やオペレーションの応用によって動機づけられた私たちは、オンラインで制約された問題を最小化するために、一階のオラクルフィードバックを後悔しています。 我々は、近位複雑性低減技術を保証する新しいプロキシグレードを開発する。
  論文  参考訳（メタデータ） (2020-10-13T09:22:21Z)
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control [28.679167097106813]
  本稿では,各反復で関数値を1回クエリし,2つの連続点間の残差を用いて勾配を推定する新しい一点フィードバック方式を提案する。 提案アルゴリズムは,制御不能なデータサンプルを持つ2点スキームと同じ収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-06-18T19:31:13Z)

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

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