論文の概要: Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance
- arxiv url: http://arxiv.org/abs/2202.11632v1
- Date: Wed, 23 Feb 2022 17:08:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-24 15:01:28.646863
- Title: Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance
- Title（参考訳）: 鏡像が再び揺らぐ:無限雑音下での最適確率凸最適化
- Authors: Nuri Mert Vural, Lu Yu, Krishnakumar Balasubramanian, Stanislav
Volgushev, Murat A. Erdogdu
- Abstract要約: 我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
- 参考スコア（独自算出の注目度）: 17.199063087458907
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic convex optimization under infinite noise variance.
Specifically, when the stochastic gradient is unbiased and has uniformly
bounded $(1+\kappa)$-th moment, for some $\kappa \in (0,1]$, we quantify the
convergence rate of the Stochastic Mirror Descent algorithm with a particular
class of uniformly convex mirror maps, in terms of the number of iterations,
dimensionality and related geometric parameters of the optimization problem.
Interestingly this algorithm does not require any explicit gradient clipping or
normalization, which have been extensively used in several recent empirical and
theoretical works. We complement our convergence results with
information-theoretic lower bounds showing that no other algorithm using only
stochastic first-order oracles can achieve improved rates. Our results have
several interesting consequences for devising online/streaming stochastic
approximation algorithms for problems arising in robust statistics and machine
learning.
- Abstract（参考訳）: 無限雑音分散下での確率凸最適化について検討する。
具体的には、確率的勾配が偏りなく、ある$\kappa \in (0,1]$ に対して一様に有界な$(1+\kappa)$-th モーメントを持つとき、最適化問題の反復数、次元、および関連する幾何学的パラメータの観点から、一様凸ミラー写像の特定のクラスに対する確率的ミラー降下アルゴリズムの収束率を定量化する。
興味深いことに、このアルゴリズムは、いくつかの最近の経験的および理論的研究で広く使われている明示的な勾配クリッピングや正規化を必要としない。
収束結果と情報理論的下界を補完し、確率的一階オラクルのみを用いた他のアルゴリズムは改善率を達成できないことを示す。
その結果,ロバストな統計処理や機械学習による問題に対するオンライン/ストリーミング確率近似アルゴリズムの開発に,いくつかの興味深い結果が得られた。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - 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) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-05-27T11:23:57Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。
アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。
アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文 参考訳（メタデータ） (2022-04-12T16:27:49Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。