Fugu-MT 論文翻訳(概要): Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization

論文の概要: 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))$であり、我々の知る限りでは、単一のパスオーバデータ未満で最適な一般化を達成することができる。広範な数値計算結果から,従来のアルゴリズムよりも計算効率が優れていることを示す。

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

関連論文リスト