論文の概要: Optimal Rates for Random Order Online Optimization
- arxiv url: http://arxiv.org/abs/2106.15207v1
- Date: Tue, 29 Jun 2021 09:48:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-30 15:34:24.015051
- Title: Optimal Rates for Random Order Online Optimization
- Title(参考訳): ランダム順序オンライン最適化のための最適レート
- Authors: Uri Sherman, Tomer Koren, Yishay Mansour
- Abstract要約: 敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
- 参考スコア(独自算出の注目度): 60.011653053877126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online convex optimization in the random order model, recently
proposed by \citet{garber2020online}, where the loss functions may be chosen by
an adversary, but are then presented to the online algorithm in a uniformly
random order. Focusing on the scenario where the cumulative loss function is
(strongly) convex, yet individual loss functions are smooth but might be
non-convex, we give algorithms that achieve the optimal bounds and
significantly outperform the results of \citet{garber2020online}, completely
removing the dimension dependence and improving their scaling with respect to
the strong convexity parameter. Our analysis relies on novel connections
between algorithmic stability and generalization for sampling
without-replacement analogous to those studied in the with-replacement
i.i.d.~setting, as well as on a refined average stability analysis of
stochastic gradient descent.
- Abstract(参考訳): ランダム順序モデルのオンライン凸最適化について研究し、最近 \citet{garber2020online} によって提案され、損失関数は敵によって選択されるが、一様ランダム順序でオンラインアルゴリズムに提示される。
累積損失関数が(強く)凸であるが、個々の損失関数は滑らかであるが、凸でないかもしれないというシナリオに注目して、最適境界を満たし、<citet{garber2020online} の結果を著しく上回るアルゴリズムを与え、次元依存を完全に取り除き、強い凸パラメータに対するスケーリングを改善する。
本分析は, アルゴリズムの安定性と, 再置換を伴わないサンプリングの一般化との新たな関係と, 確率勾配勾配の洗練された平均安定性解析に依存する。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳(メタデータ) (2024-08-17T02:22:08Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Random Scaling and Momentum for Non-smooth Non-convex Optimization [38.443430569753026]
ニューラルネットワークのトレーニングには、非常に不規則な、特に凸や滑らかな損失関数が必要である。
一般的なトレーニングアルゴリズムは運動量による勾配降下(SGDM)に基づいており、損失が凸あるいは滑らかである場合にのみ解析が適用される。
論文 参考訳(メタデータ) (2024-05-16T00:52:03Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳(メタデータ) (2022-11-29T05:52:17Z) - Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
ゼロ階エントロピー合成目的のためのアルゴリズムを解析し,次元依存性に着目した。
これは、ミラー降下法と推定類似関数を用いて、決定セットの低次元構造を利用して達成される。
勾配を改善するため、Rademacherに基づく古典的なサンプリング法を置き換え、ミニバッチ法が非ユークリ幾何学に対処することを示す。
論文 参考訳(メタデータ) (2022-08-09T07:36:25Z) - A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random
Perturbations for Stochastic Optimization [10.820943271350442]
本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。
また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
論文 参考訳(メタデータ) (2022-07-30T18:50:36Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - 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) - Non-asymptotic bounds for stochastic optimization with biased noisy
gradient oracles [8.655294504286635]
関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。
提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
論文 参考訳(メタデータ) (2020-02-26T12:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。