論文の概要: Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

• arxiv url: http://arxiv.org/abs/2607.25785v1
• Date: Tue, 28 Jul 2026 14:37:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-29 20:50:42.870525
• Title: Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization
• Title（参考訳）: 非凸合成最適化のためのマルコフサンプリング条件付き条件勾配法
• Abstract要約: 我々は,1つのエルゴード連鎖に対する非制約モンテカルロ最適化を新たに提案する。 特に、一般化されたCarlo-Wolfevious gradient $MC-ALFCFCを用いてプロジェクションフリー設定に対処する。 本手法は,期待されるサンプルの複雑さを$widetildeO(_mathrmmix2G_+_mathrmmix5G_2)varepsilon-3+_mathrmmix5varepsilon-2で実現することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias $O(τ_{\mathrm{mix}}/T)$ uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under $σ^2\mapsto 2ΛG_σ^2$ and $L^2\mapsto 2ΛL^2$, where $Λ=O(τ_{\mathrm{mix}}\log T)$. For positive centered noise, the tuned method achieves expected sample complexity $\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})$. The exactly noiseless specialization achieves $\widetilde{O}(\varepsilon^{-2})$ with mixing-time-free constants, while a mixing-time-oblivious variant achieves $\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})$. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.
• Abstract（参考訳）: 固定エルゴード型マルコフ連鎖の単一軌道に沿って勾配サンプルが到着したとき, コンパクト凸集合上の確率的合成非凸最適化について検討した。 既存の単軌道分散還元理論は、滑らかな制約のない目的をカバーし、一般化されたフランク=ウルフギャップを用いた射影のない合成設定に対処する。 そこで, MC-ALFCGを提案する。これは, モーメント条件勾配法と, キャップ付きマルチレベルモンテカルロ推定と, 点当たりのクリッピングを組み合わせたものである。 最も深いネスト平均は、同じ軌道から連続した状態を使い、条件バイアス$O(τ_{\mathrm{mix}}/T)$を開始状態上で均一に生成し、カップリングは繰り返し変位を介して勾配差第2モーメントを制御する。 クリッピングは適応解析に必要な経路境界を強制する。 我々は、Markovian Recursionを、$σ^2\mapsto 2\G_σ^2$ と $L^2\mapsto 2\L^2$ で独立サンプリング(independent-sampling)に還元する。 正中心雑音に対して、チューナー法は期待されるサンプル複雑性$\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})$を達成する。 正確なノイズのない特殊化は$\widetilde{O}(\varepsilon^{-2})$を混合時間自由定数で達成し、混合時間自由変種は$\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})$を得る。 すべての保証は固定されたトランジションカーネルの下で期待されている。 制御された数値計算では、非凸複合インスタンスの依存性感度とクリッピング挙動について検討する。

関連論文リスト

• High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence [41.64418624570687]
  マルコフ連鎖によって試料が生成された場合,ポリアク・オジャシエヴィチ(PL)条件を満たす目的の1次法について検討した。 ライトテール設定では、標準成長エンベロープスケールの通常のグラディエントD(SGD)に対して、以前の均一時間高確率境界を$widetildeO(t_mix/k)$とする。 我々は、この混合時間に対する線形依存が、持続的2で駆動される二次目的物上の一致する$(2 t_mix/k)$下界によって最適であることを示す。
  論文  参考訳（メタデータ） (2026-06-24T19:00:56Z)
• Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
  我々は,Blum-Gladyshev(mathsfBG$-0)ノイズモデルの下での非線形最適化について検討した。 モーメント付き正規化勾配降下は、勾配毎のパラメータを1つだけ使い、複雑さが$O(varepsilon-6)$で$mathsfBG$-0ノイズの下に収束することを示す。
  論文  参考訳（メタデータ） (2026-05-14T18:27:49Z)
• Tikhonov-regularised projected gradient flow for equality-constrained bilinear quantum control [0.0]
  本研究では,$mathcalH=L(0,T;mathbbR)$に対する等式制約制御対象に対する投影型勾配流について検討する。 i) $(_varepsilon)=(_min2+varepsilon2)$; (ii) Objective monotonicity $mathrmdJ/
  論文  参考訳（メタデータ） (2026-04-29T12:53:58Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
  本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。 標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。 対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
  論文  参考訳（メタデータ） (2026-02-14T13:09:29Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
  目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。 ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。 PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
  論文  参考訳（メタデータ） (2022-11-29T18:43:22Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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