Fugu-MT 論文翻訳(概要): Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets

論文の概要: Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets

arxiv url: http://arxiv.org/abs/2107.00472v1
Date: Tue, 29 Jun 2021 19:39:43 GMT
ステータス: 処理完了
システム内更新日: 2021-07-02 13:32:14.405272
Title: Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
Title（参考訳）: グラフ構造支援集合上の近似フランクウルフアルゴリズム
Authors: Baojian Zhou, Yifan Sun
Abstract要約: 2つの一般的な近似仮定(textitadditive と textitmultiplicative gap error)は、我々の問題には有効ではない。 DMO(textitapproximate dual Oracle)が提案され、ギャップではなく内部積を近似する。実験結果から,これらの改良された境界でさえ悲観的であり,グラフ構造を持つ実世界の画像に顕著な改善が認められたことが示唆された。
参考スコア（独自算出の注目度）: 27.913569257545554
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we propose approximate Frank-Wolfe (FW) algorithms to solve convex optimization problems over graph-structured support sets where the \textit{linear minimization oracle} (LMO) cannot be efficiently obtained in general. We first demonstrate that two popular approximation assumptions (\textit{additive} and \textit{multiplicative gap errors)}, are not valid for our problem, in that no cheap gap-approximate LMO oracle exists in general. Instead, a new \textit{approximate dual maximization oracle} (DMO) is proposed, which approximates the inner product rather than the gap. When the objective is $L$-smooth, we prove that the standard FW method using a $\delta$-approximate DMO converges as $\mathcal{O}(L / \delta t + (1-\delta)(\delta^{-1} + \delta^{-2}))$ in general, and as $\mathcal{O}(L/(\delta^2(t+2)))$ over a $\delta$-relaxation of the constraint set. Additionally, when the objective is $\mu$-strongly convex and the solution is unique, a variant of FW converges to $\mathcal{O}(L^2\log(t)/(\mu \delta^6 t^2))$ with the same per-iteration complexity. Our empirical results suggest that even these improved bounds are pessimistic, with significant improvement in recovering real-world images with graph-structured sparsity.
Abstract（参考訳）: 本稿では,グラフ構造化サポートセット上での凸最適化問題の解法として,LMO(textit{linear minimization oracle})を効率よく取得できないようなFW(Frank-Wolfe)アルゴリズムを提案する。まず、2つの一般的な近似仮定 (\textit{additive} と \textit{multiplicative gap error") が我々の問題に対して有効でないことを証明した。代わりに、ギャップではなく内積を近似する新しい \textit{approximate dual maximization oracle} (dmo) が提案されている。目的が$l$-smooth であれば、$\delta$-approximate dmo を用いた標準 fw 法は、一般に $\mathcal{o}(l / \delta t + (1-\delta)(\delta^{-1} + \delta^{-2})$ として収束し、$\mathcal{o}(l/(\delta^2(t+2))))$ が制約集合の $\delta$-relaxation 上で収束することを証明する。さらに、目的が$\mu$-strongly convexで解が一意であるとき、FWの変種は$\mathcal{O}(L^2\log(t)/(\mu \delta^6 t^2)$に収束する。実験結果から,これらの改良された境界でさえ悲観的であり,グラフ構造による空間像の復元が著しく向上したことが示唆された。

関連論文リスト

Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文参考訳（メタデータ） (2024-08-21T20:14:54Z)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文参考訳（メタデータ） (2023-06-30T08:34:29Z)
Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文参考訳（メタデータ） (2023-03-06T17:54:33Z)
An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文参考訳（メタデータ） (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)
Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文参考訳（メタデータ） (2022-05-30T14:28:02Z)
Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文参考訳（メタデータ） (2022-02-01T16:06:20Z)
Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文参考訳（メタデータ） (2022-01-19T05:56:19Z)
The Complexity of Dynamic Least-Squares Regression [11.815510373329337]
動的最小二乗回帰の複雑さ。ゴールは、$min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin に対する $epsilon-approximate ソリューションを維持することである。
論文参考訳（メタデータ） (2022-01-01T18:36:17Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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