論文の概要: Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization

• arxiv url: http://arxiv.org/abs/2009.09835v1
• Date: Fri, 18 Sep 2020 02:18:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 02:50:44.708053
• Title: Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization
• Title（参考訳）: ハイブリッド確率的決定論的ミニバッチ近位勾配:ほぼ最適一般化によるシングルパス最適化
• Authors: Pan Zhou, Xiaotong Yuan
• Abstract要約: HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
• 参考スコア（独自算出の注目度）: 83.80460802169999
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic variance-reduced gradient (SVRG) algorithms have been shown to work favorably in solving large-scale learning problems. Despite the remarkable success, the stochastic gradient complexity of SVRG-type algorithms usually scales linearly with data size and thus could still be expensive for huge data. To address this deficiency, we propose a hybrid stochastic-deterministic minibatch proximal gradient (HSDMPG) algorithm for strongly-convex problems that enjoys provably improved data-size-independent complexity guarantees. More precisely, for quadratic loss $F(\theta)$ of $n$ components, we prove that HSDMPG can attain an $\epsilon$-optimization-error $\mathbb{E}[F(\theta)-F(\theta^*)]\leq\epsilon$ within $\mathcal{O}\Big(\frac{\kappa^{1.5}\epsilon^{0.75}\log^{1.5}(\frac{1}{\epsilon})+1}{\epsilon}\wedge\Big(\kappa \sqrt{n}\log^{1.5}\big(\frac{1}{\epsilon}\big)+n\log\big(\frac{1}{\epsilon}\big)\Big)\Big)$ stochastic gradient evaluations, where $\kappa$ is condition number. For generic strongly convex loss functions, we prove a nearly identical complexity bound though at the cost of slightly increased logarithmic factors. For large-scale learning problems, our complexity bounds are superior to those of the prior state-of-the-art SVRG algorithms with or without dependence on data size. Particularly, in the case of $\epsilon=\mathcal{O}\big(1/\sqrt{n}\big)$ which is at the order of intrinsic excess error bound of a learning model and thus sufficient for generalization, the stochastic gradient complexity bounds of HSDMPG for quadratic and generic loss functions are respectively $\mathcal{O} (n^{0.875}\log^{1.5}(n))$ and $\mathcal{O} (n^{0.875}\log^{2.25}(n))$, which to our best knowledge, for the first time achieve optimal generalization in less than a single pass over data. Extensive numerical results demonstrate the computational advantages of our algorithm over the prior ones.
• Abstract（参考訳）: 確率分散還元勾配 (svrg) アルゴリズムは, 大規模学習問題の解法として有効であることが示されている。 顕著な成功にもかかわらず、svrg型アルゴリズムの確率的勾配複雑性は通常、データサイズと線形にスケールするので、巨大なデータにはコストがかかる可能性がある。 この欠陥に対処するために,データサイズに依存しない複雑性保証を確実に改善した強凸問題に対して,Hybrid stochastic-Deterministic Minibatch proximal gradient (HSDMPG)アルゴリズムを提案する。 より正確には、$F(\theta)$ of $n$コンポーネントに対して、HSDMPGが$\epsilon$-optimization-error $\mathbb{E}[F(\theta)-F(\theta^*)]\leq\epsilon$ in $\mathcal{O}\Big(\frac{\kappa^{1.5}\epsilon^{0.75}\log^{1.5}(\frac{1}{\epsilon})+1}{\epsilon}\wedge\Big(\kappa \sqrt{n}\log^{1.5}\big(\frac{1}{\epsilon}\big)+n\log(\frac{1}{\epsilon)\big) +n\log(\frac{1}{\epsilon)\big)\big) を満たすことを証明している。 一般の強凸損失関数に対しては、対数係数がわずかに増加するコストで、ほぼ同一の複雑性を証明できる。 大規模学習問題では,従来のSVRGアルゴリズムよりも,データサイズに依存するか否かに関わらず,複雑性境界が優れている。 特に、学習モデルの本質的な過大誤差境界の順であり、一般化に十分である$\epsilon=\mathcal{o}\big(1/\sqrt{n}\big)$の場合、二次損失関数に対するhsdmpgの確率的勾配複雑性境界は、それぞれ$\mathcal{o} (n^{0.875}\log^{1.5}(n))$ と$\mathcal{o} (n^{0.875}\log^{2.25}(n))$であり、我々の知る限りでは、単一のパスオーバデータ未満で最適な一般化を達成することができる。 広範な数値計算結果から,従来のアルゴリズムよりも計算効率が優れていることを示す。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。 以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
  論文  参考訳（メタデータ） (2023-02-20T05:16:18Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [77.8485863487028]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [39.29885444997579]
  この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。 損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
  論文  参考訳（メタデータ） (2020-11-04T20:10:31Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits [3.9919781077062497]
  アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。 この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
  論文  参考訳（メタデータ） (2020-02-17T21:32:04Z)

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

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