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 も提案されている。

関連論文リスト

Revisiting Frank-Wolfe for Structured Nonconvex Optimization [33.44652927142219]
2つの凸関数の差分として表される構造的非函数を最適化する新しい射影法(フランク・ウルフ法)を導入する。提案手法は$O-(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O -)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O -)$(O-)$(O-)$(O-)$
論文参考訳（メタデータ） (2025-03-11T22:09:44Z)
On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文参考訳（メタデータ） (2024-11-21T22:06:25Z)
Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文参考訳（メタデータ） (2023-11-18T23:06:33Z)
Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文参考訳（メタデータ） (2023-04-23T20:05:09Z)
Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.667453772837954]
強い凸関数制約を受ける凸関数を最小化する方法を示す。有限個の結果に独立な意味を持つような空間パターンを同定する。
論文参考訳（メタデータ） (2022-12-21T16:04:53Z)
Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文参考訳（メタデータ） (2022-11-22T23:53:06Z)
On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文参考訳（メタデータ） (2021-07-17T11:45:13Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文参考訳（メタデータ） (2021-06-02T22:03:36Z)
Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文参考訳（メタデータ） (2021-01-19T04:24:23Z)
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)

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