論文の概要: A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback
- arxiv url: http://arxiv.org/abs/2205.13910v1
- Date: Fri, 27 May 2022 11:23:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-30 23:57:46.977229
- Title: A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback
- Title（参考訳）: 2点フィードバックによるオンラインゼロオーダー最適化のためのL1ランダム化による勾配推定器
- Authors: Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil, Alexandre B.
Tsybakov
- Abstract要約: 2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 93.57603470949266
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: This work studies online zero-order optimization of convex and Lipschitz
functions. We present a novel gradient estimator based on two function
evaluation and randomization on the $\ell_1$-sphere. Considering different
geometries of feasible sets and Lipschitz assumptions we analyse online mirror
descent algorithm with our estimator in place of the usual gradient. We
consider two types of assumptions on the noise of the zero-order oracle:
canceling noise and adversarial noise. We provide an anytime and completely
data-driven algorithm, which is adaptive to all parameters of the problem. In
the case of canceling noise that was previously studied in the literature, our
guarantees are either comparable or better than state-of-the-art bounds
obtained by~\citet{duchi2015} and \citet{Shamir17} for non-adaptive algorithms.
Our analysis is based on deriving a new Poincar\'e type inequality for the
uniform measure on the $\ell_1$-sphere with explicit constants, which may be of
independent interest.
- Abstract（参考訳）: 本研究は凸関数とリプシッツ関数のオンラインゼロ次最適化を研究する。
2つの関数評価と$\ell_1$-sphereのランダム化に基づく新しい勾配推定器を提案する。
実現可能な集合の異なる測度とリプシッツの仮定を考えると、通常の勾配に代えてオンラインミラー降下アルゴリズムを推定器で解析する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類を考慮する。
問題の全パラメータに適応した,任意の時間かつデータ駆動型アルゴリズムを提供する。
これまで文献で研究されていたノイズキャンセリングの場合、この保証は--\citet{duchi2015} と \citet{shamir17} によって得られた非適応アルゴリズムの最先端境界と同等かそれ以上である。
我々の分析は、明示定数を持つ$\ell_1$-球面上の一様測度に対する新しいポアンカー型不等式を導出することに基づいている。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens [11.98212766542468]
我々は,$widetildemathcalO (1/varepsilon)$関数評価において,$varepsilon$-optimalityを達成する最初のアルゴリズムを提供する。
この結果は,2点勾配推定の領域外において,既存の文献を著しく改善する。
論文 参考訳（メタデータ） (2024-04-16T18:54:57Z) - Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。
我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
論文 参考訳（メタデータ） (2024-03-29T21:12:25Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48: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) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。