論文の概要: Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization

• arxiv url: http://arxiv.org/abs/2207.08540v1
• Date: Mon, 18 Jul 2022 12:03:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-19 19:16:56.729048
• Title: Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization
• Title（参考訳）: 結合構成最適化のためのマルチブロック・シングル・プロベ分散最小推定器
• Authors: Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang, Tianbao Yang
• Abstract要約: 構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
• 参考スコア（独自算出の注目度）: 49.58290066287418
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variance reduction techniques such as SPIDER/SARAH/STORM have been extensively studied to improve the convergence rates of stochastic non-convex optimization, which usually maintain and update a sequence of estimators for a single function across iterations. {\it What if we need to track multiple functional mappings across iterations but only with access to stochastic samples of $\mathcal{O}(1)$ functional mappings at each iteration?} There is an important application in solving an emerging family of coupled compositional optimization problems in the form of $\sum_{i=1}^m f_i(g_i(\mathbf{w}))$, where $g_i$ is accessible through a stochastic oracle. The key issue is to track and estimate a sequence of $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ across iterations, where $\mathbf g(\mathbf{w})$ has $m$ blocks and it is only allowed to probe $\mathcal{O}(1)$ blocks to attain their stochastic values and Jacobians. To improve the complexity for solving these problems, we propose a novel stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator to track the sequence of $\mathbf g(\mathbf{w})$. It is inspired by STORM but introduces a customized error correction term to alleviate the noise not only in stochastic samples for the selected blocks but also in those blocks that are not sampled. With the help of the MSVR estimator, we develop several algorithms for solving the aforementioned compositional problems with improved complexities across a spectrum of settings with non-convex/convex/strongly convex objectives. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on the strong convexity parameter. Empirical studies on multi-task deep AUC maximization demonstrate the better performance of using the new estimator.
• Abstract（参考訳）: SPIDER/SARAH/STORMのようなばらつき低減技術は、確率的非凸最適化の収束率を改善するために広く研究されている。 イテレーションをまたいで複数の関数マッピングを追跡する必要があるが、各イテレーションで$\mathcal{o}(1)$関数マッピングの確率的サンプルにアクセスするだけでよいとしたらどうだろう? 関連スポンサーコンテンツ } $\sum_{i=1}^m f_i(g_i(\mathbf{w}))$ という形式で、結合構成最適化問題の新たなファミリーを解決する上で重要な応用がある。 主要な問題は、$\mathbf g(\mathbf{w})=(g_1(\mathbf{w})) \ldots, g_m(\mathbf{w})$の列を反復して追跡して推定することであり、$\mathbf g(\mathbf{w})$は$m$ブロックを持ち、$\mathcal{O}(1)$ブロックを探索するだけで確率値とヤコビアンが得られる。 これらの問題を解決するための複雑さを改善するために、$\mathbf g(\mathbf{w})$をトラックするMulti-block-Single-probe Variance Reduced (MSVR)推定器を提案する。 STORMにインスパイアされているが、選択されたブロックの確率的なサンプルだけでなく、サンプリングされていないブロックのノイズを軽減するために、カスタマイズされたエラー訂正項を導入する。 提案手法は,MSVR推定器の助けを借りて,上述した合成問題を,非凸・凸・凸・強凸を対象とする多種多様な条件で解くアルゴリズムを開発した。 サンプル複素数の順序や強い凸パラメータへの依存性など,いくつかの点で先行する結果が改善される。 マルチタスク・ディープaucの最大化に関する実証研究は、新しい推定器の使用により優れた性能を示す。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
  目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。 また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
  論文  参考訳（メタデータ） (2022-02-15T16:02:32Z)
• 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)
• DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity [25.775517797956237]
  本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。 我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-01T07:27:34Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。 citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。 これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-08-24T15:57:50Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)

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

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