論文の概要: Second-order Conditional Gradient Sliding
- arxiv url: http://arxiv.org/abs/2002.08907v3
- Date: Mon, 28 Aug 2023 21:10:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-30 19:37:45.686568
- Title: Second-order Conditional Gradient Sliding
- Title（参考訳）: 2次条件勾配スライディング
- Authors: Alejandro Carderera and Sebastian Pokutta
- Abstract要約: 本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
- 参考スコア（独自算出の注目度）: 79.66739383117232
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constrained second-order convex optimization algorithms are the method of
choice when a high accuracy solution to a problem is needed, due to their local
quadratic convergence. These algorithms require the solution of a constrained
quadratic subproblem at every iteration. We present the \emph{Second-Order
Conditional Gradient Sliding} (SOCGS) algorithm, which uses a projection-free
algorithm to solve the constrained quadratic subproblems inexactly. When the
feasible region is a polytope the algorithm converges quadratically in primal
gap after a finite number of linearly convergent iterations. Once in the
quadratic regime the SOCGS algorithm requires $\mathcal{O}(\log(\log
1/\varepsilon))$ first-order and Hessian oracle calls and $\mathcal{O}(\log
(1/\varepsilon) \log(\log1/\varepsilon))$ linear minimization oracle calls to
achieve an $\varepsilon$-optimal solution. This algorithm is useful when the
feasible region can only be accessed efficiently through a linear optimization
oracle, and computing first-order information of the function, although
possible, is costly.
- Abstract（参考訳）: 制約付き第二次凸最適化アルゴリズムは、局所二次収束のため、問題に対する高精度解が必要な場合に選択する手法である。
これらのアルゴリズムは、反復ごとに制限された二次部分プロブレムの解を必要とする。
本稿では,制約付き二次部分問題を解くのに投影不要なアルゴリズムを用いた,二階条件勾配スライディング (socgs) アルゴリズムを提案する。
実現可能な領域がポリトープであるとき、アルゴリズムは有限個の線形収束反復の後に原始ギャップで二次的に収束する。
二次状態において、socgsアルゴリズムは$\mathcal{o}(\log(\log 1/\varepsilon))$ first-order and hessian oracle calls and $\mathcal{o}(\log (1/\varepsilon) \log(\log1/\varepsilon))$ linear minimization oracle は $\varepsilon$-optimal ソリューションを達成するために$\varepsilon$-optimal を呼び出す。
このアルゴリズムは、実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有効であり、可能ではあるが関数の1次情報を計算することはコストがかかる。
関連論文リスト
- 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) - A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。
また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。
我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
論文 参考訳（メタデータ） (2024-07-04T01:46:07Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully
First-Order Oracles [14.697733592222658]
1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。
さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。