論文の概要: On Stochastic Variance Reduced Gradient Method for Semidefinite
Optimization
- arxiv url: http://arxiv.org/abs/2101.00236v1
- Date: Fri, 1 Jan 2021 13:55:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-16 11:06:46.085847
- Title: On Stochastic Variance Reduced Gradient Method for Semidefinite
Optimization
- Title（参考訳）: 半定値最適化のための確率分散低減勾配法について
- Authors: Jinshan Zeng and Yixuan Zha and Ke Ma and Yuan Yao
- Abstract要約: SVRG法は最も有効な方法の1つと考えられている。
半定型プログラミング(SDP)に適応する場合、理論と実践の間には大きなギャップがある
本稿では,このギャップを,半定値最適化に適応したオプションIを用いて,元のSVRGの新たな変種を利用して埋める。
- 参考スコア（独自算出の注目度）: 14.519696724619074
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The low-rank stochastic semidefinite optimization has attracted rising
attention due to its wide range of applications. The nonconvex reformulation
based on the low-rank factorization, significantly improves the computational
efficiency but brings some new challenge to the analysis. The stochastic
variance reduced gradient (SVRG) method has been regarded as one of the most
effective methods. SVRG in general consists of two loops, where a reference
full gradient is first evaluated in the outer loop and then used to yield a
variance reduced estimate of the current gradient in the inner loop. Two
options have been suggested to yield the output of the inner loop, where Option
I sets the output as its last iterate, and Option II yields the output via
random sampling from all the iterates in the inner loop. However, there is a
significant gap between the theory and practice of SVRG when adapted to the
stochastic semidefinite programming (SDP). SVRG practically works better with
Option I, while most of existing theoretical results focus on Option II. In
this paper, we fill this gap via exploiting a new semi-stochastic variant of
the original SVRG with Option I adapted to the semidefinite optimization.
Equipped with this, we establish the global linear submanifold convergence
(i.e., converging exponentially fast to a submanifold of a global minimum under
the orthogonal group action) of the proposed SVRG method, given a provable
initialization scheme and under certain smoothness and restricted strongly
convex assumptions. Our analysis includes the effects of the mini-batch size
and update frequency in the inner loop as well as two practical step size
strategies, the fixed and stabilized Barzilai-Borwein step sizes. Some
numerical results in matrix sensing demonstrate the efficiency of proposed SVRG
method outperforming Option II counterpart as well as others.
- Abstract（参考訳）: 低ランク確率半定最適化は幅広い応用のために注目を集めている。
低ランク因子化に基づく非凸改質は計算効率を大幅に改善するが、解析に新たな課題をもたらす。
The stochastic variance reduced gradient (SVRG) method is been considered one of the most effective method。
一般に、SVRGは2つのループから構成されており、そこでは、まず外側のループで基準フル勾配を評価し、その後、内側のループで電流勾配のばらつきを低減した推定値を得る。
内部ループの出力は2つの選択肢が提案されており、オプションIは出力を最後の繰り返しとして設定し、オプションIIは内部ループの全ての繰り返しからランダムサンプリングによって出力を得る。
しかし、確率半定プログラミング(SDP)に適応する場合、SVRGの理論と実践の間には大きなギャップがある。
SVRGは実際にOption Iでうまく機能し、既存の理論結果はOption IIにフォーカスしている。
本稿では,このギャップを,半定値最適化に適応したオプションIを用いて,元のSVRGの半確率的変種を利用して埋める。
これと合わせて、提案したSVRG法の大域線型部分多様体収束(すなわち、直交群作用の下で大域的極小の部分多様体に指数関数的に高速に収束する)を確立し、証明可能な初期化スキームと一定の滑らかさと強い凸仮定を与えられた。
本分析は, 内ループにおけるミニバッチサイズと更新周波数の影響に加えて, 固定および安定化されたバルジライ・ボルワインステップサイズという2つの実用的なステップサイズ戦略を含む。
行列センシングにおける数値的な結果は,提案したSVRG法がOption II法よりも優れていることを示すものである。
関連論文リスト
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence
and Variance Reduction [26.9632099249085]
AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。
我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
論文 参考訳（メタデータ） (2023-08-11T10:17:29Z) - Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions [9.518010235273785]
両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。
我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
論文 参考訳（メタデータ） (2023-06-21T07:32:29Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳（メタデータ） (2022-09-01T11:05:26Z) - 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) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。