Fugu-MT 論文翻訳(概要): Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

論文の概要: Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

arxiv url: http://arxiv.org/abs/2505.11259v1
Date: Fri, 16 May 2025 13:50:55 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-19 14:36:15.17811
Title: Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes
Title（参考訳）: 製品ポリトープ上のFrank-Wolfeアルゴリズムの線形収束
Authors: Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Wirth, Sebastian Pokutta,
Abstract要約: 積ポリトープ上のFrank-Wolfeアルゴリズムの線形収束について検討する。約$mu$-Polyak-Lojasiewicz の凸対象に対しては、結果の条件数で定量化される線形収束率を示す。
参考スコア（独自算出の注目度）: 20.7580525897407
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the \emph{pyramidal width} and the \emph{vertex-facet distance}, based on the condition numbers of individual polytope components. As a result, for convex objectives that are $\mu$-Polyak-{\L}ojasiewicz, we show linear convergence rates quantified in terms of the resulting condition numbers. We apply our results to the problem of approximately finding a feasible point in a polytope intersection in high-dimensions, and demonstrate the practical efficiency of our algorithms through empirical results.
Abstract（参考訳）: 積ポリトープ上のFrank-Wolfeアルゴリズムの線形収束について検討する。本研究では,各ポリトープ成分の条件数に基づいて,積ポリトープの条件数,すなわち \emph{pyramidal width} と \emph{vertex-facet distance} を解析した。結果として、$\mu$-Polyak-{\L}ojasiewicz となる凸対象に対しては、結果の条件数で定量化される線形収束率を示す。本研究では, 高次元のポリトープ交差点において, ほぼ可能な点を求める問題に適用し, 経験的結果を通じて, アルゴリズムの実用的効率を実証する。

関連論文リスト

Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
本稿では,線形系を解くためにエントロピックミラー降下を適用することに焦点を当てる。収束解析の主な課題は、領域の非有界性に起因する。制限的な仮定を課さずにこれを克服するために、Polyak型階段の変種を導入する。
論文参考訳（メタデータ） (2025-05-05T12:33:18Z)
Flows on convex polytopes [0.0]
実次元ポリトープが単位球に同型であることを示し、我々のアプローチは球上で定義された流れを利用し、元のポリトープにマッピングする。本実験は, メタボリックフラックス解析の応用から着想を得て, 競合密度推定, サンプリング精度, 高速トレーニング, 推論時間の実現を実証した。
論文参考訳（メタデータ） (2025-03-13T10:15:40Z)
Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
本稿では,ポリトープ内の格子数に近似する新しいフレームワークを提案する。我々のアルゴリズムは、数十次元のポリトープを解くことができ、最先端のカウンタを著しく上回る。
論文参考訳（メタデータ） (2023-12-14T09:53:54Z)
Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文参考訳（メタデータ） (2023-11-18T04:41:07Z)
Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文参考訳（メタデータ） (2023-02-02T08:33:36Z)
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文参考訳（メタデータ） (2023-01-10T12:18:47Z)
Enumeration of max-pooling responses with generalized permutohedra [39.58317527488534]
最大プーリング層(英: Max-pooling layer)は、入力座標のシフトしたウィンドウの最大値を取ることで入力アレイをサンプリングする関数である。このようなポリトープの面を特徴付け、1次元最大プーリング層における頂点数と面数の生成関数と閉式を得る。
論文参考訳（メタデータ） (2022-09-29T17:45:54Z)
Reconstruction of Convex Polytope Compositions from 3D Point-clouds [3.04585143845864]
対応する入力ポイントクラウドに完全に適合する凸ポリトープの組成(結合)を再構築することは、難しい最適化の問題です。本稿ではまず,まず平面の集合を抽出し,次に入力点雲を弱凸クラスタに分割し,各分割に適合する平面の交点として凸多面体の集合を生成するパイプラインを提案する。最良充填凸ポリトープの探索は、適応面の集合上の最適化問題として定式化し、進化的アルゴリズムを用いて解く。
論文参考訳（メタデータ） (2021-04-27T00:14:55Z)
Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文参考訳（メタデータ） (2021-01-19T04:24:23Z)
Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity [19.24470467199451]
フランク=ウルフのアルゴリズムは最適面の次元にのみ依存する速度で線形に収束することを示す。ノイズに対する最適解の疎結合性を示すことを証明して、厳密な相補性を動機づける。
論文参考訳（メタデータ） (2020-05-31T16:48:10Z)

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