論文の概要: Continuous Submodular Maximization: Boosting via Non-oblivious Function
- arxiv url: http://arxiv.org/abs/2201.00703v1
- Date: Mon, 3 Jan 2022 15:10:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-04 15:32:23.686156
- Title: Continuous Submodular Maximization: Boosting via Non-oblivious Function
- Title（参考訳）: 連続部分モジュラ最大化:非公開関数によるブースティング
- Authors: Qixin Zhang, Zengde Deng, Zaiyi Chen, Yu Yang
- Abstract要約: 本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。
係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。
オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
- 参考スコア（独自算出の注目度）: 12.755674710719616
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we revisit the constrained and stochastic continuous
submodular maximization in both offline and online settings. For each
$\gamma$-weakly DR-submodular function $f$, we use the factor-revealing
optimization equation to derive an optimal auxiliary function $F$, whose
stationary points provide a $(1-e^{-\gamma})$-approximation to the global
maximum value (denoted as $OPT$) of problem
$\max_{\boldsymbol{x}\in\mathcal{C}}f(\boldsymbol{x})$. Naturally, the
projected (mirror) gradient ascent relied on this non-oblivious function
achieves $(1-e^{-\gamma}-\epsilon^{2})OPT-\epsilon$ after $O(1/\epsilon^{2})$
iterations, beating the traditional
$(\frac{\gamma^{2}}{1+\gamma^{2}})$-approximation gradient ascent
\citep{hassani2017gradient} for submodular maximization. Similarly, based on
$F$, the classical Frank-Wolfe algorithm equipped with variance reduction
technique \citep{mokhtari2018conditional} also returns a solution with
objective value larger than $(1-e^{-\gamma}-\epsilon^{2})OPT-\epsilon$ after
$O(1/\epsilon^{3})$ iterations. In the online setting, we first consider the
adversarial delays for stochastic gradient feedback, under which we propose a
boosting online gradient algorithm with the same non-oblivious search,
achieving a regret of $\sqrt{D}$ (where $D$ is the sum of delays of gradient
feedback) against a $(1-e^{-\gamma})$-approximation to the best feasible
solution in hindsight. Finally, extensive numerical experiments demonstrate the
efficiency of our boosting methods.
- Abstract（参考訳）: 本稿では、オフラインとオンラインの両方の設定における制約付きおよび確率的連続部分モジュラー最大化について再検討する。
各々の$\gamma$-weakly dr-submodular function $f$ に対して、係数回帰最適化方程式を用いて最適な補助関数 $f$ を導出し、その定常点が大域的最大値 ($opt$) に近似する$(1-e^{-\gamma}) を問題 $\max_{\boldsymbol{x}\in\mathcal{c}}f(\boldsymbol{x})$ に導出する。
当然、予想された(鏡面)勾配の上昇は、この非公理関数に依存して 1-e^{-\gamma}-\epsilon^{2})OPT-\epsilon$ after $O(1/\epsilon^{2})$ iterations を達成し、部分モジュラー最大化に対して $(\frac{\gamma^{2}}{1+\gamma^{2}})$-approximation gradient ascent \citep{hassani2017gradient} を破る。
同様に、古典的フランク=ウルフのアルゴリズムは、分散還元法を組み込んだ$F$に基づいて、$(1-e^{-\gamma}-\epsilon^{2})OPT-\epsilon$ after $O(1/\epsilon^{3})$ iterations よりも大きい目的値の解を返す。
オンライン設定では、まず確率的勾配フィードバックの逆方向遅延について検討し、直近の最も有効な解に対する$-approximationに対する$1-e^{-\gamma}に対する$\sqrt{D}$(D$は勾配フィードバックの遅延の和である)の後悔を生かして、同じ非公開な探索を伴うオンライン勾配アルゴリズムを提案する。
最後に,提案手法の有効性を示す数値実験を行った。
関連論文リスト
- Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Communication-Efficient Decentralized Online Continuous DR-Submodular
Maximization [11.889570525184801]
単調連続DR-submodular-Frank問題に対する2つの分散オンラインアルゴリズムを提案する。
1つはOne-shot Decentralized Meta-Wolfe (Mono-DMFW)で、1-1/e)$regret bound $O(T4/5)$を達成している。
次に,非公開ブースティング関数citepzhang2022 に着想を得て,分散オンラインブースティング・グラディエント・アセンジ(DOBGA)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-18T07:32:28Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳（メタデータ） (2021-03-17T18:18:57Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z) - Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond [25.845034951660544]
我々は,一階述語法では改善できないことを示した。
我々は、$$quasar のアログ関数を計算する変種加速降下を開発する。
ファーストオーダーの方法では改善できません。
論文 参考訳（メタデータ） (2019-06-27T22:39:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。