論文の概要: Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions

• arxiv url: http://arxiv.org/abs/2611.00334v1
• Date: Fri, 30 Oct 2026 20:07:44 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 20:02:10.788564
• Title: Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
• Title（参考訳）: 複合包摂性に対するランダム化座標と可変化戦略を用いた最適勾配アルゴリズム
• Abstract要約: 分散削減とランダム化されたブロック座標更新を組み合わせた2つの楽観的勾配フレームワークを開発する。 重要度に基づくブロックサンプリングにおいて,対応するオラクル複雑度を導出する。 特に、高度に異質な状態において、L-SVRG と JacSketch の変種は $mathcalObig(n + n2/3-2big)$ および $mathcalObig(n + n2/3-1big)$ オラクル複素量に達する。
• 参考スコア（独自算出の注目度）: 4.094815321148208
• License:
• Abstract: In this paper, we consider a class of possibly nonmonotone finite-sum composite inclusions in which evaluating all components or updating all coordinates at every iteration can be computationally expensive. We develop two optimistic gradient frameworks that combine variance reduction with randomized block-coordinate updates. The first framework applies under a blockwise average Lipschitz continuity condition and the existence of a weak-Minty solution. It achieves an $\mathcal{O}(1/k)$ convergence rate for the expected squared residual, and its iterates converge almost surely under mild additional conditions. The second framework relies on a backward-forward reformulation under average co-coercivity and co-hypomonotonicity. It achieves faster $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ rates for the expected squared residual, as well as $o(1/k^2)$ almost-sure rates. For both frameworks, we provide a generic condition on the stochastic estimator that covers mini-batch, loopless SVRG, and a generalized JacSketch-type estimator, and we derive the corresponding oracle complexities under importance-based block sampling. In particular, in highly heterogeneous regimes, the L-SVRG and JacSketch variants attain $\mathcal{O}\big(n + n^{2/3}ε^{-2}\big)$ and $\mathcal{O}\big(n + n^{2/3}ε^{-1}\big)$ oracle complexities for the nonaccelerated and accelerated methods, respectively. Numerical experiments illustrate the effects of variance reduction and block-coordinate sampling, and compare the proposed methods with existing baselines.
• Abstract（参考訳）: 本稿では、全てのコンポーネントを評価したり、各イテレーションで全ての座標を更新したりする非単調な有限サム合成包含のクラスを計算的にコストがかかることを考察する。 分散削減とランダム化されたブロック座標更新を組み合わせた2つの楽観的勾配フレームワークを開発する。 第1の枠組みはブロックワイド平均リプシッツ連続性条件と弱ミンティ解の存在の下で適用される。 期待される平方残差に対して$\mathcal{O}(1/k)$収束率を達成し、その反復は軽度追加条件下でほぼ確実に収束する。 第2の枠組みは、平均的なコ保磁力とコ・ヒロモノニクスの下での後方修正に依存している。 より高速な$\mathcal{O}(1/k^2)$と$o(1/k^2)$の2乗残差と$o(1/k^2)$の2乗残差を達成する。 どちらのフレームワークに対しても,ミニバッチ,ループレスSVRG,一般化された JacSketch 型推定器をカバーする確率的推定器の一般的な条件を提供し,重要なブロックサンプリングの下で対応するオラクルの複雑さを導出する。 特に、高度にヘテロジニアスな状態において、L-SVRG と JacSketch の変種は、非加速的および加速的手法に対してそれぞれ$\mathcal{O}\big(n + n^{2/3}ε^{-2}\big)$および$\mathcal{O}\big(n + n^{2/3}ε^{-1}\big)$ oracle complexities を得る。 数値実験では, 分散低減とブロック座標サンプリングの効果を実証し, 提案手法を既存のベースラインと比較した。

関連論文リスト

• A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization [66.48718943929202]
  非強凸二値問題の場合、既存の一階法はネストループに依存するのが一般的である。 2つの相補成分を組み合わせたSingle-loop Constant-1次ペナルティ法(ICOS)を提案する。
  論文  参考訳（メタデータ） (2026-10-05T19:26:20Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions [3.6997773420183866]
  本研究では,フォワード反射逆スプリッティング法(FRBS)のための新しい分散還元法を開発した。 ミニバッチのような偏見のない推定器とは異なり、偏見のある変種の開発は基本的な技術的課題に直面している。 ループレスSVRGやSAGAを利用する場合,$mathcalO(n2/3-2)$と$mathcalO(-10/3)$が最良であることを示す。
  論文  参考訳（メタデータ） (2026-03-16T17:39:25Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Variance-Reduced Fast Operator Splitting Methods for Generalized Equations [8.0153031008486]
  一般化方程式のクラスの解を近似する2つの分散還元高速演算子分割法を開発した。 提案手法は, 加速演算子分割法, 固定点法, 共高調波性, 分散低減の最近の進歩を取り入れたものである。
  論文  参考訳（メタデータ） (2025-04-17T16:02:20Z)
• 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)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)

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

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