論文の概要: Boosting One-Point Derivative-Free Online Optimization via Residual Feedback

• arxiv url: http://arxiv.org/abs/2010.07378v3
• Date: Thu, 3 Dec 2020 02:35:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 14:30:54.698792
• Title: Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
• Title（参考訳）: 残留フィードバックによる一点微分自由オンライン最適化の促進
• Authors: Yan Zhang, Yi Zhou, Kaiyi Ji, Michael M. Zavlanos
• Abstract要約: オンライン最適化のための新しい一点フィードバック手法を提案する。 残差フィードバックを用いることで,従来の一点フィードバック法に比べてはるかに小さな分散が得られることを示す。 私たちの後悔の限界は、従来の一点フィードバックのZOに対する既存の後悔の限界よりも厳格です。
• 参考スコア（独自算出の注目度）: 28.679167097106813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zeroth-order optimization (ZO) typically relies on two-point feedback to estimate the unknown gradient of the objective function. Nevertheless, two-point feedback can not be used for online optimization of time-varying objective functions, where only a single query of the function value is possible at each time step. In this work, we propose a new one-point feedback method for online optimization that estimates the objective function gradient using the residual between two feedback points at consecutive time instants. Moreover, we develop regret bounds for ZO with residual feedback for both convex and nonconvex online optimization problems. Specifically, for both deterministic and stochastic problems and for both Lipschitz and smooth objective functions, we show that using residual feedback can produce gradient estimates with much smaller variance compared to conventional one-point feedback methods. As a result, our regret bounds are much tighter compared to existing regret bounds for ZO with conventional one-point feedback, which suggests that ZO with residual feedback can better track the optimizer of online optimization problems. Additionally, our regret bounds rely on weaker assumptions than those used in conventional one-point feedback methods. Numerical experiments show that ZO with residual feedback significantly outperforms existing one-point feedback methods also in practice.
• Abstract（参考訳）: ゼロ階最適化(ZO)は通常、目的関数の未知の勾配を推定するために2点フィードバックに依存する。 それにもかかわらず、2点フィードバックは、各時間ステップで関数値の単一のクエリのみが可能な、時間変化対象関数のオンライン最適化には使用できない。 本研究では,2つのフィードバック点間の残差を連続する瞬間に推定するオンライン最適化のための新しい一点フィードバック手法を提案する。 さらに、凸および非凸のオンライン最適化問題に対する残差フィードバックを持つZOに対する後悔境界を開発する。 具体的には、決定論的および確率的問題とリプシッツ関数と滑らかな目的関数の両方について、残差フィードバックを用いることで、従来の一点フィードバック法に比べてより小さな分散で勾配推定ができることを示す。 その結果、従来の一点フィードバックによるZOに対する既存の後悔境界に比べて、我々の後悔境界ははるかに厳格であり、残差フィードバックによるZOは、オンライン最適化問題の最適化をより良く追跡できることを示している。 さらに、私たちの後悔の限界は、従来の一点フィードバック法よりも弱い仮定に依存している。 数値実験により, 残差フィードバックを持つZOは, 既存の一点フィードバック法よりも有意に優れていた。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Principled Preferential Bayesian Optimization [22.269732173306192]
  優先ベイズ最適化(BO)の問題について検討する。 一対の候補解よりも優先的なフィードバックしか持たないブラックボックス関数を最適化することを目指している。 この問題を解決するために,効率的な計算手法を用いた楽観的アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-08T02:57:47Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。 本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
  論文  参考訳（メタデータ） (2023-12-19T01:52:13Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。 我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。 遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
  論文  参考訳（メタデータ） (2023-10-29T06:12:43Z)
• Vanishing Point Estimation in Uncalibrated Images with Prior Gravity Direction [82.72686460985297]
  我々はマンハッタンのフレームを推定する問題に取り組む。 2つの新しい2行解法が導出され、そのうちの1つは既存の解法に影響を与える特異点に悩まされない。 また、局所最適化の性能を高めるために、任意の行で実行される新しい最小でないメソッドを設計する。
  論文  参考訳（メタデータ） (2023-08-21T13:03:25Z)
• Proximal Point Imitation Learning [48.50107891696562]
  我々は、無限地平線模倣学習のための厳密な効率保証を備えた新しいアルゴリズムを開発した。 我々は、最適化、特に近点法(PPM)と双対平滑化から古典的ツールを活用する。 線形関数とニューラルネットワーク関数の近似の双方に対して、説得力のある経験的性能を実現する。
  論文  参考訳（メタデータ） (2022-09-22T12:40:21Z)
• Bayesian Optimization under Stochastic Delayed Feedback [36.16843889404038]
  既存のBOメソッドは、関数評価(フィードバック)が学習者の即時または固定遅延後に利用可能であると仮定する。 本稿では,遅延フィードバックを待ちながら新しい関数クエリを選択するジレンマに効率よく対処する,線形後悔保証付きアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-19T07:34:08Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control [28.679167097106813]
  本稿では,各反復で関数値を1回クエリし,2つの連続点間の残差を用いて勾配を推定する新しい一点フィードバック方式を提案する。 提案アルゴリズムは,制御不能なデータサンプルを持つ2点スキームと同じ収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-06-18T19:31:13Z)

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

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