論文の概要: Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

• arxiv url: http://arxiv.org/abs/2610.05038v1
• Date: Sun, 04 Oct 2026 08:14:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-11 06:50:53.572972
• Title: Optimal Oracle Complexity for Finite-Sum Monotone Inclusions
• Title（参考訳）: 有限サムモノトン包有物に対するOracleの最適複雑度
• Abstract要約: 提案手法は,$$y$,$$gin G(y)$ with $(mathbbE|F(y)+g|2)1/2levarepsilon$ using $mathcalO(n+sqrtnLR/varepsilon)$ expected component evaluations and resolvent evaluations。 A matching $(n+sqrtnLR/varepsilon)$ lower bound Hold for randomized linear-span component-oracle algorithm with adapt Stop and expected query budgets
• 参考スコア（独自算出の注目度）: 1.6921396880325779
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point $y$ and a certificate $g\in G(y)$ with $(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon$ using $\mathcal{O}(n+\sqrt{n}LR/\varepsilon)$ expected component evaluations and resolvent evaluations. It removes the additive $n\log n$ cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength $L/\sqrt{n}$. Carrying an operator estimate between the remaining stages limits their total cost to $\mathcal{O}(n)$. A matching $Ω(n+\sqrt{n}LR/\varepsilon)$ lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for $0<\varepsilon\le LR/2$, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.
• Abstract（参考訳）: 平均二乗リプシッツ連続性の下での有限サム単調包含に対するオラクル最適化法を提案する。 我々のスイッチング正規化法は、$$y$ と $g\in G(y)$ と $(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon$ と $\mathcal{O}(n+\sqrt{n}LR/\varepsilon)$ とすると、期待されるコンポーネント評価とリゾルペント評価を行う。 正則化の強さ$L/\sqrt{n}$で中心確率的近位反復に切り替えることで、正則化の各段階で分散還元解法を再開する追加の$n\log n$コストを除去する。 演算子の推定を残りの段階間で行うと、その総コストは$\mathcal{O}(n)$に制限される。 一致した$Ω(n+\sqrt{n}LR/\varepsilon)$ lower bound hold for randomized linear-span component-oracle algorithm with adapt stop and expected query budgets。 したがって、$0<\varepsilon\le LR/2$の場合、このメソッドは、このオラクルモデルにおいて、最大で最悪のケースで期待されるコンポーネントの複雑さを、普遍定数まで達成する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
  コンパクト凸集合の一般ノルム $|cdot|$ と自己写像 $T$ に対して、小さな固定点残差 $|T(x)-x| leq $ を持つ点を計算するオラクル複雑性について検討する。 弱ラデマッハ型$q > 1$の任意のノルムに対して、高い確率でそのような問題を解くアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2026-09-08T23:09:39Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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