Fugu-MT 論文翻訳(概要): Complexity of Linear Minimization and Projection on Some Sets

論文の概要: Complexity of Linear Minimization and Projection on Some Sets

arxiv url: http://arxiv.org/abs/2101.10040v1
Date: Mon, 25 Jan 2021 12:14:34 GMT
ステータス: 処理完了
システム内更新日: 2021-03-14 18:54:27.298185
Title: Complexity of Linear Minimization and Projection on Some Sets
Title（参考訳）: ある集合上の線形最小化と射影の複雑さ
Authors: Cyrille W. Combettes and Sebastian Pokutta
Abstract要約: Frank-Wolfeアルゴリズムは、プロジェクションではなく線形最小化に依存する制約付き最適化の手法である。本稿では、最適化によく用いられる複数の集合上の両タスクの複雑性境界について検討する。
参考スコア（独自算出の注目度）: 33.53609344219565
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Frank-Wolfe algorithm is a method for constrained optimization that relies on linear minimizations, as opposed to projections. Therefore, a motivation put forward in a large body of work on the Frank-Wolfe algorithm is the computational advantage of solving linear minimizations instead of projections. However, the discussions supporting this advantage are often too succinct or incomplete. In this paper, we review the complexity bounds for both tasks on several sets commonly used in optimization. Projection methods onto the $\ell_p$-ball, $p\in\left]1,2\right[\cup\left]2,+\infty\right[$, and the Birkhoff polytope are also proposed.
Abstract（参考訳）: Frank-Wolfeアルゴリズムは、プロジェクションではなく線形最小化に依存する制約付き最適化の手法である。したがって、Frank-Wolfeアルゴリズムの大規模な作業の動機は、プロジェクションの代わりに線形最小化を解くことの計算上の利点である。しかし、この利点を支持する議論は、しばしば簡潔すぎるか不完全です。本稿では,最適化によく用いられる複数の集合上の両タスクの複雑性境界について検討する。 $\ell_p$-ball, $p\in\left]1,2\right[\cup\left]2,+\infty\right[$, and the Birkhoff polytope も提案されている。

関連論文リスト

Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文参考訳（メタデータ） (2023-02-03T03:19:14Z)
Accelerated First-Order Optimization under Nonlinear Constraints [97.16266088683061]
制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。これらのアルゴリズムの重要な性質は制約の数である。我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
論文参考訳（メタデータ） (2023-02-01T08:50:48Z)
Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文参考訳（メタデータ） (2022-11-22T23:53:06Z)
Convex integer optimization with Frank-Wolfe methods [15.599296461516982]
混合整数非線形最適化は、構造や非線形性を特徴とする幅広い種類の問題である。本稿では,Frank-Wolfeアルゴリズムに基づく誤り適応型一階法の特性と利点について検討する。この新しいアプローチは、多面体制約の1つの表現に取り組んでいる間、実現可能な解を計算する。
論文参考訳（メタデータ） (2022-08-23T14:46:54Z)
Efficient Projection-Free Online Convex Optimization with Membership Oracle [11.745866777357566]
ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
論文参考訳（メタデータ） (2021-11-10T17:22:29Z)
On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文参考訳（メタデータ） (2021-07-17T11:45:13Z)
Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文参考訳（メタデータ） (2021-07-09T16:04:24Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文参考訳（メタデータ） (2021-06-02T22:03:36Z)
Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文参考訳（メタデータ） (2021-03-15T11:20:31Z)
A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文参考訳（メタデータ） (2020-07-10T05:20:02Z)
Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文参考訳（メタデータ） (2020-01-30T21:18:39Z)

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