Fugu-MT 論文翻訳(概要): Partial Optimality in Cubic Correlation Clustering

論文の概要: Partial Optimality in Cubic Correlation Clustering

arxiv url: http://arxiv.org/abs/2302.04694v2
Date: Fri, 31 Mar 2023 14:50:55 GMT
ステータス: 処理完了
システム内更新日: 2023-04-03 16:52:57.826905
Title: Partial Optimality in Cubic Correlation Clustering
Title（参考訳）: 立方相関クラスタリングにおける部分最適性
Authors: David Stein, Silvia Di Gregorio, Bjoern Andres
Abstract要約: 最適性の証明はNPハードであり、問題文の複雑さによって事実上妨げられている。ここでは、完備グラフと立方体目的関数の特殊ケースに対する部分最適条件の確立に焦点をあてる。さらに、これらの条件をテストするアルゴリズムを定義し、その効果を2つのデータセット上で数値的に検証する。
参考スコア（独自算出の注目度）: 6.372499127940625
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.
Abstract（参考訳）: 高次相関クラスタリング問題は表現モデルであり,近年,いくつかの応用において局所探索ヒューリスティックスが提案されている。しかし、最適性の証明はNPハードであり、すでに問題文の複雑さによって妨げられている。本稿では,完全グラフと立方体目的関数の特別な場合に対する部分最適条件の確立に着目する。さらに、これらの条件をテストするアルゴリズムを定義し、その効果を2つのデータセット上で数値的に検証する。

関連論文リスト

Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization [34.628967272528044]
本稿では,制約付きマルチレベル最適化関数に対するプロジェクションフリーアルゴリズムについて検討する。段階的適応を用いて凸関数と強凸関数の複素数を求める。
論文参考訳（メタデータ） (2024-06-06T06:56:56Z)
Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
論文参考訳（メタデータ） (2024-02-14T10:48:00Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文参考訳（メタデータ） (2022-07-02T16:59:37Z)
On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。バイマックス性能問題を解くための優れた外挿が得られることが示されている。
論文参考訳（メタデータ） (2022-01-19T16:14:27Z)
Trilevel and Multilevel Optimization using Monotone Operator Theory [5.927983571004003]
そこで我々は,2つの下位層の目的が滑らかな項と非滑らかな項の和からなる三段階最適化問題を考える。自然一階法アルゴリズムを提案し,その収束率と収束率をいくつかのパラメーターで解析する。
論文参考訳（メタデータ） (2021-05-19T21:31:18Z)
Joint Continuous and Discrete Model Selection via Submodularity [1.332560004325655]
機械学習のモデル選択問題では、意味のある構造を持つ優れたモデルに対する欲求は、典型的には正規化された最適化問題によって表される。しかし、多くのシナリオでは、数値的に意味のある構造が離散空間において特定され、難しい非最適化問題を引き起こす。我々は、ロバスト最適化によって動機づけられた特定の問題クラスに対して、単純な連続的あるいは離散的な制約をいかに扱うかを示す。
論文参考訳（メタデータ） (2021-02-17T21:14:47Z)
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文参考訳（メタデータ） (2020-10-31T21:35:42Z)
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)
Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文参考訳（メタデータ） (2020-02-26T16:19:09Z)

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