論文の概要: A Dimension-Insensitive Algorithm for Stochastic Zeroth-Order Optimization

• arxiv url: http://arxiv.org/abs/2104.11283v1
• Date: Thu, 22 Apr 2021 18:56:17 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-26 12:57:21.638836
• Title: A Dimension-Insensitive Algorithm for Stochastic Zeroth-Order Optimization
• Title（参考訳）: 確率零次最適化のための次元非感性アルゴリズム
• Authors: Hongcheng Liu and Yu Yang
• Abstract要約: そこで本研究では,SI-SGFアルゴリズムにより,ディメンション非感性クエリの複雑さを実現できることを示す。 結果は提案されたSI-SGFの既存の代わりと比較される強い潜在性を示します。
• 参考スコア（独自算出の注目度）: 6.447052211404121
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper concerns a convex, stochastic zeroth-order optimization (S-ZOO) problem, where the objective is to minimize the expectation of a cost function and its gradient is not accessible directly. To solve this problem, traditional optimization techniques mostly yield query complexities that grow polynomially with dimensionality, i.e., the number of function evaluations is a polynomial function of the number of decision variables. Consequently, these methods may not perform well in solving massive-dimensional problems arising in many modern applications. Although more recent methods can be provably dimension-insensitive, almost all of them work with arguably more stringent conditions such as everywhere sparse or compressible gradient. Thus, prior to this research, it was unknown whether dimension-insensitive S-ZOO is possible without such conditions. In this paper, we give an affirmative answer to this question by proposing a sparsity-inducing stochastic gradient-free (SI-SGF) algorithm. It is proved to achieve dimension-insensitive query complexity in both convex and strongly convex cases when neither gradient sparsity nor gradient compressibility is satisfied. Our numerical results demonstrate the strong potential of the proposed SI-SGF compared with existing alternatives.
• Abstract（参考訳）: 本稿では,コスト関数の期待を最小化し,その勾配が直接アクセスできないような,凸確率的ゼロ次最適化(s-zoo)問題について述べる。 この問題を解決するために、従来の最適化手法は、主に次元で多項式的に成長するクエリ複雑度、すなわち関数評価の数は、決定変数の数の多項式関数である。 したがって、これらの手法は、多くの近代的な応用で生じる大量次元問題の解決にうまく機能しない可能性がある。 より最近の手法は、証明可能な次元非感受性を持つことができるが、ほとんど全ての手法は、至る所のスパースや圧縮可能な勾配のようなより厳密な条件で機能する。 したがって, 本研究に先立ち, 次元非感応性S-ZOOがそのような条件なしに可能かどうかは不明である。 本稿では,スペーサ性誘導確率勾配自由(SI-SGF)アルゴリズムを提案することにより,この問題に対する肯定的な回答を与える。 勾配間隔や勾配圧縮性を満足しない場合, 凸面および強凸面の双方において, 次元不感なクエリ複雑性を実現することが証明された。 提案したSI-SGFは,既存の代替品と比較して強い可能性を示した。

関連論文リスト

• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization [34.628967272528044]
  本稿では,制約付きマルチレベル最適化関数に対するプロジェクションフリーアルゴリズムについて検討する。 段階的適応を用いて凸関数と強凸関数の複素数を求める。
  論文  参考訳（メタデータ） (2024-06-06T06:56:56Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples [1.0650780147044159]
  スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。 本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
  論文  参考訳（メタデータ） (2022-03-25T20:56:07Z)
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales [45.994415581007054]
  関数 $f : mathbbRd rightarrow mathbbR$ の最小化は、未知の非相互作用な滑らかで凸な函数の和として暗黙的に分解可能である。 そこで我々は,多種多様な条件の最適化問題を効率的に解くために,勾配に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-11-04T20:09:12Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Learning to Guide Random Search [111.71167792453473]
  我々は、潜在低次元多様体上の高次元関数の微分自由最適化を考える。 最適化を行いながらこの多様体を学習するオンライン学習手法を開発した。 本研究では,連続最適化ベンチマークと高次元連続制御問題について実験的に評価する。
  論文  参考訳（メタデータ） (2020-04-25T19:21:14Z)

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

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