論文の概要: KKT Conditions, First-Order and Second-Order Optimization, and
Distributed Optimization: Tutorial and Survey
- arxiv url: http://arxiv.org/abs/2110.01858v1
- Date: Tue, 5 Oct 2021 07:50:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-06 13:54:26.059454
- Title: KKT Conditions, First-Order and Second-Order Optimization, and
Distributed Optimization: Tutorial and Survey
- Title（参考訳）: KKT条件、一階と二階の最適化、分散最適化:チュートリアルとサーベイ
- Authors: Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, Mark Crowley
- Abstract要約: このチュートリアルでは、KKT条件、一階と二階の数値最適化、分散最適化に焦点を当てている。
- 参考スコア（独自算出の注目度）: 5.967999555890417
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This is a tutorial and survey paper on Karush-Kuhn-Tucker (KKT) conditions,
first-order and second-order numerical optimization, and distributed
optimization. After a brief review of history of optimization, we start with
some preliminaries on properties of sets, norms, functions, and concepts of
optimization. Then, we introduce the optimization problem, standard
optimization problems (including linear programming, quadratic programming, and
semidefinite programming), and convex problems. We also introduce some
techniques such as eliminating inequality, equality, and set constraints,
adding slack variables, and epigraph form. We introduce Lagrangian function,
dual variables, KKT conditions (including primal feasibility, dual feasibility,
weak and strong duality, complementary slackness, and stationarity condition),
and solving optimization by method of Lagrange multipliers. Then, we cover
first-order optimization including gradient descent, line-search, convergence
of gradient methods, momentum, steepest descent, and backpropagation. Other
first-order methods are explained, such as accelerated gradient method,
stochastic gradient descent, mini-batch gradient descent, stochastic average
gradient, stochastic variance reduced gradient, AdaGrad, RMSProp, and Adam
optimizer, proximal methods (including proximal mapping, proximal point
algorithm, and proximal gradient method), and constrained gradient methods
(including projected gradient method, projection onto convex sets, and
Frank-Wolfe method). We also cover non-smooth and $\ell_1$ optimization methods
including lasso regularization, convex conjugate, Huber function,
soft-thresholding, coordinate descent, and subgradient methods. Then, we
explain second-order methods including Newton's method for unconstrained,
equality constrained, and inequality constrained problems....
- Abstract（参考訳）: これはKKT条件、一階・二階数値最適化、分散最適化に関するチュートリアルおよび調査論文である。
最適化の歴史を概観した後、集合の性質、ノルム、関数、最適化の概念に関するいくつかの予備論から始める。
次に、最適化問題、標準最適化問題(線形計画、二次計画、半定値計画を含む)、凸問題を紹介する。
また,不平等,等式,制約の設定,slack変数の追加,エピグラフ形式などのテクニックも導入する。
我々は,ラグランジアン関数,双対変数,kkt条件(原始実現可能性,双対実現可能性,弱双対性,強双対性,相補的スラック性,定常性条件を含む)を導入し,ラグランジ乗算法による最適化を解く。
次に,勾配降下,直線探索,勾配法の収束,運動量,最急降下,逆伝播を含む一階最適化について述べる。
その他、加速度勾配法、確率勾配降下法、ミニバッチ勾配降下法、確率平均勾配法、確率分散還元勾配法、アダグラード法、rmsprop法、adamオプティマイザ法、近位法(近位写像法、近位点法、近位勾配法を含む)、制約勾配法(投影勾配法、凸集合への投影法、フランクウルフ法を含む)などが説明されている。
また,ラッソ正則化,凸共役,フーバー関数,ソフトスレッショルド法,座標降下法,準次数法を含む非スムースおよび$\ell_1$最適化法についても取り上げる。
そこで, ニュートン法を含む二階法を非制約, 等式制約, 不等式制約問題に適用する。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive
Step Size [29.15132344744801]
本研究では,行列逆変換などの問題に対して,適応的なステップサイズを持つ勾配勾配の局所収束性を確立する。
これらの一階最適化法は線形あるいは線形収束を実現することができることを示す。
論文 参考訳（メタデータ） (2021-12-30T00:50:30Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳（メタデータ） (2020-09-23T20:02:00Z) - Conditional Gradient Methods for Convex Optimization with General Affine
and Nonlinear Constraints [8.643249539674612]
本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。
まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。
さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
論文 参考訳（メタデータ） (2020-06-30T23:49:38Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z) - Geometry, Computation, and Optimality in Stochastic Optimization [24.154336772159745]
問題幾何学の計算および統計的結果とオンライン最適化について検討する。
制約集合と勾配幾何学に焦点をあてて、どの次法と適応次法が最適(minimax)であるかという問題族を特徴づける。
論文 参考訳（メタデータ） (2019-09-23T16:14:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。