Fugu-MT 論文翻訳(概要): Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions

論文の概要: Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions

arxiv url: http://arxiv.org/abs/2006.08167v2
Date: Wed, 26 Jan 2022 19:49:59 GMT
ステータス: 処理完了
システム内更新日: 2022-11-21 03:41:05.433766
Title: Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
Title（参考訳）: 補間的条件下での確率的条件勾配法の複雑さの改善
Authors: Tesi Xiao, Krishnakumar Balasubramanian, Saeed Ghadimi
Abstract要約: 条件付き勾配法では, 勾配オラクルへの$mathcalO(epsilon-1.5)$呼び出しが必要であり, 最適解を求める。勾配のスライディングステップを含めると、呼び出しの数は$mathcalO(epsilon-1.5)$に減少する。
参考スコア（独自算出の注目度）: 12.096252285460814
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We analyze stochastic conditional gradient methods for constrained optimization problems arising in over-parametrized machine learning. We show that one could leverage the interpolation-like conditions satisfied by such models to obtain improved oracle complexities. Specifically, when the objective function is convex, we show that the conditional gradient method requires $\mathcal{O}(\epsilon^{-2})$ calls to the stochastic gradient oracle to find an $\epsilon$-optimal solution. Furthermore, by including a gradient sliding step, we show that the number of calls reduces to $\mathcal{O}(\epsilon^{-1.5})$.
Abstract（参考訳）: 過パラメータ機械学習における制約付き最適化問題に対する確率的条件勾配法の解析を行った。このようなモデルによって満たされた補間的な条件を活用してオラクルの複雑さを改善することができることを示す。具体的には、目的関数が凸である場合、条件付き勾配法で$\mathcal{o}(\epsilon^{-2})$ を確率的勾配オラクルに呼び出して$\epsilon$-optimal の解を求める必要があることを示す。さらに、勾配スライディングステップを含めることで、呼び出し数を$\mathcal{o}(\epsilon^{-1.5})$にすることを示す。

関連論文リスト

Gradient Methods with Online Scaling [19.218484733179356]
オンライン学習による勾配に基づく手法の収束を加速する枠組みを提案する。広範に使用される過勾配降下は勾配降下の収束により改善されることを示す。
論文参考訳（メタデータ） (2024-11-04T05:04:18Z)
Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文参考訳（メタデータ） (2024-09-23T13:11:37Z)
Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文参考訳（メタデータ） (2023-05-23T15:26:36Z)
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文参考訳（メタデータ） (2023-01-10T12:18:47Z)
Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文参考訳（メタデータ） (2022-06-17T06:10:20Z)
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)
Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文参考訳（メタデータ） (2022-03-30T11:39:00Z)
Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文参考訳（メタデータ） (2022-03-29T17:59:10Z)
A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文参考訳（メタデータ） (2022-02-09T06:05:38Z)
Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start [39.13249645102326]
目的関数の反復が上層問題であり、下層問題は滑らかな写像の固定点を見つけることである。いくつかの最近の研究で、下層の問題を温めるアルゴリズムが提案されている。ウォームスタートなしでは、オーダーワイズ最適サンプルの複雑さを達成できることが示される。
論文参考訳（メタデータ） (2022-02-07T18:35:46Z)
Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文参考訳（メタデータ） (2019-12-26T22:10:10Z)

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