論文の概要: Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method
- arxiv url: http://arxiv.org/abs/2010.01848v1
- Date: Mon, 5 Oct 2020 08:16:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-10 21:04:25.804818
- Title: Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method
- Title（参考訳）: 射影効率向上法と最適非平滑フランクウルフ法
- Authors: Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong
Oh
- Abstract要約: 実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
- 参考スコア（独自算出の注目度）: 54.93433440034386
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the classical setting of optimizing a nonsmooth Lipschitz
continuous convex function over a convex constraint set, when having access to
a (stochastic) first-order oracle (FO) for the function and a projection oracle
(PO) for the constraint set. It is well known that to achieve
$\epsilon$-suboptimality in high-dimensions, $\Theta(\epsilon^{-2})$ FO calls
are necessary. This is achieved by the projected subgradient method (PGD).
However, PGD also entails $O(\epsilon^{-2})$ PO calls, which may be
computationally costlier than FO calls (e.g. nuclear norm constraints).
Improving this PO calls complexity of PGD is largely unexplored, despite the
fundamental nature of this problem and extensive literature. We present first
such improvement. This only requires a mild assumption that the objective
function, when extended to a slightly larger neighborhood of the constraint
set, still remains Lipschitz and accessible via FO. In particular, we introduce
MOPES method, which carefully combines Moreau-Yosida smoothing and accelerated
first-order schemes. This is guaranteed to find a feasible
$\epsilon$-suboptimal solution using only $O(\epsilon^{-1})$ PO calls and
optimal $O(\epsilon^{-2})$ FO calls. Further, instead of a PO if we only have a
linear minimization oracle (LMO, a la Frank-Wolfe) to access the constraint
set, an extension of our method, MOLES, finds a feasible $\epsilon$-suboptimal
solution using $O(\epsilon^{-2})$ LMO calls and FO calls---both match known
lower bounds, resolving a question left open since White (1993). Our
experiments confirm that these methods achieve significant speedups over the
state-of-the-art, for a problem with costly PO and LMO calls.
- Abstract（参考訳）: 非滑らかなリプシッツ連続凸関数を凸制約集合上で最適化する古典的な設定は、函数の(確率的な)一階オラクル(FO)と制約集合の射影オラクル(PO)にアクセスできるときに考慮する。
高次元での$\epsilon$-suboptimalityを達成するには$\theta(\epsilon^{-2})$ foコールが必要であることはよく知られている。
これは projected subgradient method (pgd) によって達成される。
しかし、pgdには$o(\epsilon^{-2})$ poコールも含まれており、fo呼び出しよりも計算コストが高い可能性がある(核規範制約など)。
PGDの複雑性は、この問題の基本的な性質と広範な文献にもかかわらず、ほとんど解明されていない。
私たちはそのような改善を最初に提示する。
これは、対象函数が制約集合の少し大きな近傍に拡張されたとき、まだリプシッツのままで FO を介してアクセス可能であるという穏やかな仮定のみを必要とする。
特に,Moreau-Yosida平滑化と高速化された1次スキームを慎重に組み合わせたMOPS法を提案する。
これは、$O(\epsilon^{-1})$ PO コールと$O(\epsilon^{-2})$ FO コールのみを使用して実現可能な $\epsilon$-suboptimal ソリューションを見つけることが保証されている。
さらに、制約集合にアクセスするための線形最小化オラクル (LMO, a la Frank-Wolfe) しか持たない PO の代わりに、我々の方法であるMOLES は、$O(\epsilon^{-2})$ LMO コールと FO コールの両方が既知の下界と一致し、White (1993) 以降に残された質問を解決し、実現可能な $\epsilon$-suboptimal ソリューションを見つける。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現する。
関連論文リスト
- First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。
線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
論文 参考訳（メタデータ） (2024-06-18T16:41:21Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳（メタデータ） (2022-05-06T13:29:14Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳（メタデータ） (2022-02-19T20:31:05Z) - 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) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。
非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文 参考訳（メタデータ） (2021-05-04T21:49:15Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。
このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。
我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
論文 参考訳（メタデータ） (2020-06-23T20:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。