論文の概要: Never Go Full Batch (in Stochastic Convex Optimization)
- arxiv url: http://arxiv.org/abs/2107.00469v1
- Date: Tue, 29 Jun 2021 16:07:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-02 13:32:29.755712
- Title: Never Go Full Batch (in Stochastic Convex Optimization)
- Title（参考訳）: Never Go Full Batch (確率凸最適化における)
- Authors: Idan Amir, Yair Carmon, Tomer Koren, Roi Livni
- Abstract要約: 凸最適化のための$textfull-batch$最適化アルゴリズムの一般化性能について検討する。
我々は、勾配降下のようなアルゴリズムが人口リスクを$O(1/epsilon2)$の後に$epsilon$に一般化し、最適化する一方で、フルバッチ法は少なくとも$Omega(1/epsilon4)$の反復を必要とするか、あるいは次元依存的なサンプル複雑性を示すことを示した。
- 参考スコア（独自算出の注目度）: 42.46711831860667
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the generalization performance of $\text{full-batch}$ optimization
algorithms for stochastic convex optimization: these are first-order methods
that only access the exact gradient of the empirical risk (rather than
gradients with respect to individual data points), that include a wide range of
algorithms such as gradient descent, mirror descent, and their regularized
and/or accelerated variants. We provide a new separation result showing that,
while algorithms such as stochastic gradient descent can generalize and
optimize the population risk to within $\epsilon$ after $O(1/\epsilon^2)$
iterations, full-batch methods either need at least $\Omega(1/\epsilon^4)$
iterations or exhibit a dimension-dependent sample complexity.
- Abstract（参考訳）: 確率凸最適化のための$\text{full-batch}$最適化アルゴリズムの一般化性能について検討する:これらは経験的リスク(個々のデータ点に対する勾配ではなく)の正確な勾配にのみアクセスする一階法であり、勾配降下、ミラー降下、正規化および/または加速された変種を含む。
確率的勾配降下のようなアルゴリズムは、人口リスクをo(1/\epsilon^2)$の後に$\epsilon$に一般化し、最適化することができるが、フルバッチ法は少なくとも$\omega(1/\epsilon^4)$の反復を必要とするか、次元依存のサンプル複雑性を示す。
関連論文リスト
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。
その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
論文 参考訳（メタデータ） (2024-08-19T11:07:05Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳（メタデータ） (2020-08-24T15:57:50Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳（メタデータ） (2020-03-30T10:43:56Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。