Fugu-MT 論文翻訳(概要): Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator

論文の概要: Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator

arxiv url: http://arxiv.org/abs/2609.15723v1
Date: Mon, 14 Sep 2026 15:21:32 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-16 07:15:06.469358
Title: Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
Title（参考訳）: 多ブロックシングルプローブ推定器による有限サム結合合成最適化の解法
Abstract要約: そこで,新しいMSVR推定器は,複雑さを$mathcalO(1)$ブロックに効率的にトレースすることを示した。また、外関数勾配が勾配であるときの$m$への依存も改善する。マルチタスク深度AUCに関する実証研究は,提案した線形推定器の優れた性能を示す。
参考スコア（独自算出の注目度）: 41.84305838914204
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Traditional variance reduction methods (e.g., SPIDER, SARAH, STORM) have been extensively investigated for improving the convergence rates of stochastic optimization. These techniques typically maintain a sequence of estimators for a single function (or gradient) across iterations. However, what if we need to track multiple functions, but can only access stochastic samples of $\mathcal{O}(1)$ functions at each iteration? This scenario arises in an important emerging family of finite-sum coupled compositional optimization (FCCO) problems of the form $\frac{1}{m}\sum_{i=1}^m f_i(g_i(\mathbf{w}))$, where each $g_i$ is accessible only through a stochastic oracle. The key challenge is to track $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ over time, where $\mathbf g(\mathbf{w})$ has $m$ blocks but only $\mathcal{O}(1)$ blocks can be probed for their stochastic values at each step. To address this challenge, we propose a novel Multi-block-Single-probe Variance Reduction (MSVR) estimator to efficiently trace $\mathbf g(\mathbf{w})$ under partial block sampling. Building on the MSVR estimator, we develop several algorithms for FCCO problems, achieving improved sample complexities for non-convex, convex, strongly convex, and Polyak-Łojasiewicz (PL) objectives. We further obtain an improved dependence on $m$ when the outer function gradients $\nabla f_i$ are linear. Empirical studies on multi-task deep AUC maximization further demonstrate the superior performance of the proposed estimators.
Abstract（参考訳）: 従来の分散還元法(SPIDER, SARAH, STORM)は確率最適化の収束率を改善するために広く研究されている。これらのテクニックは典型的には、イテレーション間で単一の関数(または勾配)に対する推定器のシーケンスを保持する。しかし、もし複数の関数を追跡する必要があるとしても、各イテレーションで$\mathcal{O}(1)$関数の確率的なサンプルにしかアクセスできないとしたらどうでしょう? このシナリオは、$\frac{1}{m}\sum_{i=1}^m f_i(g_i(\mathbf{w}))$という形の有限サム結合合成最適化(FCCO)問題で、各$g_i$は確率的オラクルを通してのみアクセス可能である。鍵となる課題は、$\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ over time, where $\mathbf g(\mathbf{w})$ has $m$ blocks だが、各ステップにおける確率値に対して、$ $mathcal{O}(1)$ blocksのみを探索することができる。この課題に対処するため、我々は、部分的ブロックサンプリングの下で$\mathbf g(\mathbf{w})$を効率的にトレースする、新しいマルチブロック・シングルプローブ可変化(MSVR)推定器を提案する。提案手法は,MSVR推定器上に構築され,非凸,凸,強凸,ポリアック・オジャシエヴィチ(PL)の目的に対して改良されたサンプル複素量を実現するために,FCCO問題に対するいくつかのアルゴリズムを開発した。さらに、外函数勾配 $\nabla f_i$ が線型であるとき、$m$ に対する改善された依存を得る。マルチタスク深度AUCの最大化に関する実証研究は、提案した推定器の性能をさらに向上させる。

関連論文リスト

SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。我々は悲観的な収束分析を避ける分析を提供する。我々の成果は、既存の最先端の体制を改善した。
論文参考訳（メタデータ） (2026-06-14T14:11:07Z)
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)
MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文参考訳（メタデータ） (2024-05-29T18:36:59Z)
Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文参考訳（メタデータ） (2023-06-30T08:34:29Z)
On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
論文参考訳（メタデータ） (2022-10-25T11:37:11Z)
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文参考訳（メタデータ） (2022-08-07T20:53:42Z)
Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文参考訳（メタデータ） (2022-07-18T12:03:26Z)
Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
論文参考訳（メタデータ） (2022-02-15T16:02:32Z)
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)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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