論文の概要: Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm
- arxiv url: http://arxiv.org/abs/2306.02159v1
- Date: Sat, 3 Jun 2023 17:05:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-06 19:45:43.033480
- Title: Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm
- Title（参考訳）: 高滑らか関数の勾配なし最適化:改良解析と新しいアルゴリズム
- Authors: Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil, and Alexandre B.
Tsybakov
- Abstract要約: この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
- 参考スコア（独自算出の注目度）: 87.22224691317766
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: This work studies minimization problems with zero-order noisy oracle
information under the assumption that the objective function is highly smooth
and possibly satisfies additional properties. We consider two kinds of
zero-order projected gradient descent algorithms, which differ in the form of
the gradient estimator. The first algorithm uses a gradient estimator based on
randomization over the $\ell_2$ sphere due to Bach and Perchet (2016). We
present an improved analysis of this algorithm on the class of highly smooth
and strongly convex functions studied in the prior work, and we derive rates of
convergence for two more general classes of non-convex functions. Namely, we
consider highly smooth functions satisfying the Polyak-{\L}ojasiewicz condition
and the class of highly smooth functions with no additional property. The
second algorithm is based on randomization over the $\ell_1$ sphere, and it
extends to the highly smooth setting the algorithm that was recently proposed
for Lipschitz convex functions in Akhavan et al. (2022). We show that, in the
case of noiseless oracle, this novel algorithm enjoys better bounds on bias and
variance than the $\ell_2$ randomization and the commonly used Gaussian
randomization algorithms, while in the noisy case both $\ell_1$ and $\ell_2$
algorithms benefit from similar improved theoretical guarantees. The
improvements are achieved thanks to a new proof techniques based on Poincar\'e
type inequalities for uniform distributions on the $\ell_1$ or $\ell_2$
spheres. The results are established under weak (almost adversarial)
assumptions on the noise. Moreover, we provide minimax lower bounds proving
optimality or near optimality of the obtained upper bounds in several cases.
- Abstract（参考訳）: この研究は、目的関数が非常に滑らかで、追加特性を満たす可能性があるという仮定の下で、ゼロ次ノイズオラクル情報による最小化問題を研究する。
我々は、勾配推定器の形式が異なる2種類のゼロ次射影勾配降下アルゴリズムを考察する。
最初のアルゴリズムは、bach and perchet (2016) による$\ell_2$ sphere 上のランダム化に基づく勾配推定器を用いる。
先行研究で研究した高滑らかかつ強凸関数のクラスについて,このアルゴリズムを改良した解析を行い,非凸関数のより一般的な2つのクラスに対する収束率を導出する。
すなわち、Polyak-{\L}ojasiewicz条件を満たす高滑らかな函数と、追加的な性質を持たない高滑らかな函数のクラスを考える。
第二のアルゴリズムは$\ell_1$球面上のランダム化に基づいており、最近アハバンら (2022) のリプシッツ凸関数に対して提案されたアルゴリズムを非常に滑らかに設定する。
ノイズのないオラクルの場合、このアルゴリズムは$\ell_2$ランダム化やよく使われるガウス確率化アルゴリズムよりもバイアスと分散のバウンダリが良いが、ノイズの多い場合、$\ell_1$と$\ell_2$アルゴリズムは同様に改善された理論的保証の恩恵を受ける。
この改善は、$\ell_1$ または $\ell_2$ 球面上の均一分布に対する Poincar\'e 型不等式に基づく新しい証明手法によって達成される。
結果は、ノイズに対する弱い(ほぼ敵対的な)仮定の下で確立される。
さらに,いくつかのケースで得られた上界の最適性または至近性を示す最小下界を提供する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。
我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
論文 参考訳（メタデータ） (2024-03-29T21:12:25Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-05-27T11:23:57Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。