Fugu-MT 論文翻訳(概要): The computational complexity of some explainable clustering problems

論文の概要: The computational complexity of some explainable clustering problems

arxiv url: http://arxiv.org/abs/2208.09643v1
Date: Sat, 20 Aug 2022 09:13:23 GMT
ステータス: 処理完了
システム内更新日: 2022-08-23 14:21:29.850270
Title: The computational complexity of some explainable clustering problems
Title（参考訳）: いくつかの説明可能なクラスタリング問題の計算複雑性
Authors: Eduardo Sany Laber
Abstract要約: 我々は[Dasgupta et al., ICML 2020]によって提案されたフレームワークにおけるいくつかの説明可能なクラスタリング問題の計算複雑性について検討する。我々は、$k$-means、$k$-medians、$k$-centers、そしてコスト分散関数を考える。最初の3つは最適化が難しいが、後者は時間内に最適化できる。
参考スコア（独自算出の注目度）: 10.330512795438889
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the computational complexity of some explainable clustering problems in the framework proposed by [Dasgupta et al., ICML 2020], where explainability is achieved via axis-aligned decision trees. We consider the $k$-means, $k$-medians, $k$-centers and the spacing cost functions. We prove that the first three are hard to optimize while the latter can be optimized in polynomial time.
Abstract（参考訳）: 我々は, [dasgupta et al., icml 2020] によって提案された枠組みにおける説明可能なクラスタリング問題の計算複雑性について検討した。我々は、k$-means, $k$-medians, $k$-centers and the spacing cost functionを考える。最初の3つは最適化が困難であり、後者は多項式時間で最適化可能であることが証明される。

関連論文リスト

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文参考訳（メタデータ） (2024-05-20T02:24:58Z)
Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
論文参考訳（メタデータ） (2024-01-23T07:16:32Z)
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)
On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文参考訳（メタデータ） (2022-06-22T23:57:40Z)
Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文参考訳（メタデータ） (2022-06-14T08:14:14Z)
Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
論文参考訳（メタデータ） (2021-07-25T11:21:59Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-05-05T18:28:42Z)
Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文参考訳（メタデータ） (2021-04-14T19:21:59Z)
Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。提案アルゴリズムは,過度な通信を実現することができることを示す。提案アルゴリズムの有効性を示す実験を行った。
論文参考訳（メタデータ） (2020-11-10T13:12:21Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)

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