論文の概要: Clustering with Iterated Linear Optimization

• arxiv url: http://arxiv.org/abs/2012.09202v1
• Date: Wed, 16 Dec 2020 19:01:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-03 08:29:51.326202
• Title: Clustering with Iterated Linear Optimization
• Title（参考訳）: 反復線形最適化によるクラスタリング
• Authors: Pedro Felzenszwalb, Caroline Klivans, Alice Paul
• Abstract要約: 本稿では,Max k-Cut問題の半定プログラム緩和を用いたクラスタリング手法を提案する。 このアプローチは、反復線形最適化を用いてSDPの解を丸める新しい手法に基づいている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a novel method for clustering using a semidefinite programming (SDP) relaxation of the Max k-Cut problem. The approach is based on a new methodology for rounding the solution of an SDP using iterated linear optimization. We show the vertices of the Max k-Cut SDP relaxation correspond to partitions of the data into at most k sets. We also show the vertices are attractive fixed points of iterated linear optimization. We interpret the process of fixed point iteration with linear optimization as repeated relaxations of the closest vertex problem. Our experiments show that using fixed point iteration for rounding the Max k-Cut SDP relaxation leads to significantly better results when compared to randomized rounding.
• Abstract（参考訳）: 我々は、Max k-Cut問題の半定値プログラミング(SDP)緩和を用いたクラスタリングの新しい手法を提案する。 このアプローチは、反復線形最適化を用いてSDPの解を丸める新しい手法に基づいている。 我々は、Max k-Cut SDP緩和の頂点がデータの分割に対応していることを示す。 また、頂点は反復線形最適化の魅力的な固定点であることを示す。 直近の頂点問題の繰り返し緩和として線形最適化を用いて固定点反復の過程を解釈する。 実験の結果, Max k-Cut SDP の緩和に固定点反復を用いると, ランダム化ラウンドリングに比べて有意に良好な結果が得られた。

関連論文リスト

• $A^*$ for Graphs of Convex Sets [7.9756690088226145]
  本稿では,既存の凸プログラミングに基づくアプローチを情報と融合して最適性を保証する新しいアルゴリズムを提案する。 我々の方法は$A*$にインスパイアされ、指定された頂点の部分集合から最優先的な手順を開始し、さらなる成長が不可能かつ有益になるまで反復的に拡張する。
  論文  参考訳（メタデータ） (2024-07-24T16:48:32Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
  パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。 滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-16T05:26:03Z)
• A Combinatorial Perspective on the Optimization of Shallow ReLU Networks [35.329916555349214]
  浅いReLUネットワークを最適化するNPハード問題は、各トレーニング例のアクティベーションパターンの探索として特徴付けられる。 ゾノトープを用いて自然にモデル化できることを示し、その集合は実現可能な活性化パターンの集合であることを示す。
  論文  参考訳（メタデータ） (2022-10-01T03:09:02Z)
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [14.719077076351377]
  本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。 Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
  論文  参考訳（メタデータ） (2022-08-11T16:55:26Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  内部最適化問題が凸であるが非滑らかである場合の一階法を研究する。 本研究では, ヤコビアンの近位勾配降下と近位座標降下収率列の前方モード微分が, 正確なヤコビアンに向かって収束していることを示す。
  論文  参考訳（メタデータ） (2021-05-04T17:31:28Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。