論文の概要: Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization

• arxiv url: http://arxiv.org/abs/2010.08766v2
• Date: Sun, 19 Jun 2022 16:44:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-06 11:38:23.554897
• Title: Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
• Title（参考訳）: 強凸有限和最適化のための低次複素境界
• Authors: Min Zhang, Yao Shu, Kun He
• Abstract要約: SAG, SAGA, SVRG, SARAHを含むランダム化漸進勾配法では, 有限和最適化の典型的な2つの場合において, 厳密に低い複雑性境界を導出する。 結果は,各成分関数が強凸で滑らかな場合のKatyushaやVRADAの上部複雑性と密に一致し,有限サム関数が強凸で成分関数が平均滑らかな場合のKatyushaXとSDCAの上部複雑性と密に一致した。
• 参考スコア（独自算出の注目度）: 21.435973899949285
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finite-sum optimization plays an important role in the area of machine learning, and hence has triggered a surge of interest in recent years. To address this optimization problem, various randomized incremental gradient methods have been proposed with guaranteed upper and lower complexity bounds for their convergence. Nonetheless, these lower bounds rely on certain conditions: deterministic optimization algorithm, or fixed probability distribution for the selection of component functions. Meanwhile, some lower bounds even do not match the upper bounds of the best known methods in certain cases. To break these limitations, we derive tight lower complexity bounds of randomized incremental gradient methods, including SAG, SAGA, SVRG, and SARAH, for two typical cases of finite-sum optimization. Specifically, our results tightly match the upper complexity of Katyusha or VRADA when each component function is strongly convex and smooth, and tightly match the upper complexity of SDCA without duality and of KatyushaX when the finite-sum function is strongly convex and the component functions are average smooth.
• Abstract（参考訳）: 有限サム最適化は機械学習の分野で重要な役割を担い、近年は関心の高まりを招いている。 この最適化問題に対処するために、様々なランダム化漸進勾配法が提案され、それらの収束のために上層と下層の複雑性境界が保証されている。 それにもかかわらず、これらの下限は特定の条件に依存する:決定論的最適化アルゴリズム、または成分関数の選択のための固定確率分布。 一方、いくつかの下限は、特定の場合において最もよく知られた方法の上限にさえ一致しない。 これらの制限を断ち切るために、有限サム最適化の典型的な2つのケースに対して、SAG、SAGA、SVRG、SARAHを含むランダム化インクリメンタル勾配法の厳密なより低い複雑性境界を導出する。 具体的には,各成分関数が強凸かつ滑らかである場合,また,有限和関数が強凸で成分関数が平均滑らかである場合,sdcaやkatyushaxの高次複雑性と密に一致する場合,katyushaやvradaの高次複雑度と密に一致した。

関連論文リスト

• Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization [34.628967272528044]
  本稿では,制約付きマルチレベル最適化関数に対するプロジェクションフリーアルゴリズムについて検討する。 段階的適応を用いて凸関数と強凸関数の複素数を求める。
  論文  参考訳（メタデータ） (2024-06-06T06:56:56Z)
• Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective [17.5796206457693]
  局所的な局所次変分の下での非滑らかな最適化問題について検討する。 得られた目的のクラスは、定義されたクラスに基づいて目的のクラスをカプセル化する。
  論文  参考訳（メタデータ） (2024-03-24T22:42:40Z)
• First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
  合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。 本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
  論文  参考訳（メタデータ） (2023-07-14T19:59:18Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.667453772837954]
  強い凸関数制約を受ける凸関数を最小化する方法を示す。 有限個の結果に独立な意味を持つような空間パターンを同定する。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
  論文  参考訳（メタデータ） (2020-06-12T05:00:44Z)

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

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