論文の概要: Non-convex online learning via algorithmic equivalence
- arxiv url: http://arxiv.org/abs/2205.15235v1
- Date: Mon, 30 May 2022 16:50:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 19:05:19.759857
- Title: Non-convex online learning via algorithmic equivalence
- Title（参考訳）: アルゴリズム等価性による非凸オンライン学習
- Authors: Udaya Ghai, Zhou Lu, Elad Hazan
- Abstract要約: アルゴリズム同値法 非勾配降下凸ミラー降下理論を示す。
我々の分析は、新しい単純なアルゴリズム法に基づいて、$frac23$を証明している。
- 参考スコア（独自算出の注目度）: 30.038975353298117
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study an algorithmic equivalence technique between nonconvex gradient
descent and convex mirror descent. We start by looking at a harder problem of
regret minimization in online non-convex optimization. We show that under
certain geometric and smoothness conditions, online gradient descent applied to
non-convex functions is an approximation of online mirror descent applied to
convex functions under reparameterization. In continuous time, the gradient
flow with this reparameterization was shown to be exactly equivalent to
continuous-time mirror descent by Amid and Warmuth 2020, but theory for the
analogous discrete time algorithms is left as an open problem. We prove an
$O(T^{\frac{2}{3}})$ regret bound for non-convex online gradient descent in
this setting, answering this open problem. Our analysis is based on a new and
simple algorithmic equivalence method.
- Abstract（参考訳）: 非凸勾配降下と凸ミラー降下のアルゴリズム等価性について検討した。
まず、オンラインの非凸最適化における後悔の最小化という難しい問題に目を向ける。
幾何および滑らか性条件下では、非凸関数に適用されたオンライン勾配降下は、再パラメータ化下の凸関数に適用されるオンラインミラー降下の近似である。
連続時間では、この再パラメータ化による勾配流は、Amid と Warmuth 2020 による連続時間ミラー降下と完全に等しいことが示されているが、類似の離散時間アルゴリズムの理論はオープン問題として残されている。
この設定において、非凸なオンライン勾配降下に対して、$O(T^{\frac{2}{3}})$ regret bound を証明し、この開問題に答える。
我々の分析は、新しい単純アルゴリズム同値法に基づいている。
関連論文リスト
- An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。
本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
論文 参考訳（メタデータ） (2024-07-05T08:53:06Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-05-27T11:23:57Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via
Early-Stopped Mirror Descent [29.206451882562867]
本稿では,雑音の位相探索に応用した早期停止ミラー降下法について検討する。
単純なアルゴリズムは、スパーシティを促進するために明示的な正規化やしきい値ステップに依存しない。
論文 参考訳（メタデータ） (2021-05-08T11:22:19Z) - A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval [24.17778927729799]
スパース位相探索に適用した連続時間ミラーを解析する。
これは、測定のみの集合からスパース信号を復元する問題である。
この問題に対して収束解析アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-20T10:03:44Z) - 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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z) - Geometry, Computation, and Optimality in Stochastic Optimization [24.154336772159745]
問題幾何学の計算および統計的結果とオンライン最適化について検討する。
制約集合と勾配幾何学に焦点をあてて、どの次法と適応次法が最適(minimax)であるかという問題族を特徴づける。
論文 参考訳（メタデータ） (2019-09-23T16:14:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。