論文の概要: When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation
- arxiv url: http://arxiv.org/abs/2312.11425v1
- Date: Mon, 18 Dec 2023 18:29:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 18:54:16.002565
- Title: When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation
- Title(参考訳): 機能の選択をいつ信頼できますか?
--I:LASSOの条件に基づく解析と近似の一般化硬度
- Authors: Alexander Bastounis, Felipe Cucker, Anders C. Hansen
- Abstract要約: 近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
- 参考スコア(独自算出の注目度): 49.1574468325115
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The arrival of AI techniques in computations, with the potential for
hallucinations and non-robustness, has made trustworthiness of algorithms a
focal point. However, trustworthiness of the many classical approaches are not
well understood. This is the case for feature selection, a classical problem in
the sciences, statistics, machine learning etc. Here, the LASSO optimisation
problem is standard. Despite its widespread use, it has not been established
when the output of algorithms attempting to compute support sets of minimisers
of LASSO in order to do feature selection can be trusted. In this paper we
establish how no (randomised) algorithm that works on all inputs can determine
the correct support sets (with probability $> 1/2$) of minimisers of LASSO when
reading approximate input, regardless of precision and computing power.
However, we define a LASSO condition number and design an efficient algorithm
for computing these support sets provided the input data is well-posed (has
finite condition number) in time polynomial in the dimensions and logarithm of
the condition number. For ill-posed inputs the algorithm runs forever, hence,
it will never produce a wrong answer. Furthermore, the algorithm computes an
upper bound for the condition number when this is finite. Finally, for any
algorithm defined on an open set containing a point with infinite condition
number, there is an input for which the algorithm will either run forever or
produce a wrong answer. Our impossibility results stem from generalised
hardness of approximation -- within the Solvability Complexity Index (SCI)
hierarchy framework -- that generalises the classical phenomenon of hardness of
approximation.
- Abstract(参考訳): 幻覚と非ロマンス性の可能性を持つ計算におけるAI技術の到来は、アルゴリズムの信頼性を焦点にしている。
しかし、多くの古典的アプローチの信頼性はよく分かっていない。
これは、科学、統計、機械学習などにおける古典的な問題である特徴選択のケースである。
ここでは、LASSO最適化問題は標準である。
広く利用されているにもかかわらず、機能選択を行うためにLASSOのミニミサのサポートセットを計算しようとするアルゴリズムの出力が信頼されるのは定かではない。
本稿では,全ての入力に作用する(ランダム化された)アルゴリズムが,精度や計算能力に関わらず,近似入力を読み取る際に,LASSOのミニミサの正しいサポートセット(確率$>1/2$)を決定する方法を確立する。
しかし、入力データが条件番号の次元と対数における時間多項式において十分(有限条件数)であるならば、LASSO条件数を定義し、これらのサポートセットを計算するための効率的なアルゴリズムを設計する。
不正な入力の場合、アルゴリズムは永久に実行されるため、間違った答えを生成することはない。
さらに、このアルゴリズムは、条件数に対する上限を有限であるときに計算する。
最後に、無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか間違った解を生成するような入力が存在する。
我々の不合理性は、近似の硬さの古典的な現象を一般化する一般化された硬さ(Solvability Complexity Index (SCI) 階層フレームワーク)から生じる。
関連論文リスト
- Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文 参考訳(メタデータ) (2024-02-01T09:18:34Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with
quantum algorithms [0.0]
ハミルトン時間進化に基づく量子アルゴリズムにおける近似硬さの直感的なメカニズムはよく理解されていない。
これらの問題に支障を来さない新しいスペクトル畳み込み最適化法を提案する。
エネルギーを$E = N_unsat-N_sat$と定義すれば、スペクトル的に折り畳まれた量子最適化はエネルギー$E leq Aを持つ状態を返す。
論文 参考訳(メタデータ) (2023-12-11T04:15:55Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳(メタデータ) (2023-06-29T14:57:56Z) - Accelerated Nonnegative Tensor Completion via Integer Programming [7.3149416054553065]
整数計画法に基づく非負のテンソル完備化へのアプローチを提案する。
我々はアルゴリズムと同じ理論的な保証を維持できるいくつかの変種を探索するが、潜在的に高速な計算を提供する。
論文 参考訳(メタデータ) (2022-11-28T21:00:25Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Applying the Quantum Alternating Operator Ansatz to the Graph Matching
Problem [0.5584060970507505]
グラフの最大マッチングに関するいくつかの問題に対処するための導出手法を設計する。
入力として空の状態が与えられたとき、可能なすべてのマッチングに対する重ね合わせと、入力としてW-状態が与えられたとき、すべての最大マッチングに対する重ね合わせを得る。
本研究の主な成果は,QAOA+アルゴリズムの2正規グラフ上での実行時の出力状態に対応するマッチングの期待サイズが,全てのマッチングの均一分布から得られるマッチングサイズよりも大きいことである。
論文 参考訳(メタデータ) (2020-11-24T06:36:11Z) - Computing solutions of Schr\"odinger equations on unbounded domains- On
the brink of numerical algorithms [0.0]
我々は、一般にアルゴリズムが存在しないことを実証し、計算可能な量子力学における問題の実質的な分類理論を導出する。
我々は、非有界領域上の離散NLS方程式の解は、アルゴリズムのランタイム上の一様境界で常に計算可能であることを示す。
我々の結果は、計算量子力学以上の意味を持ち、Solvability Complexity Index(SCI)階層とSmaleの計算数学の基礎に関するプログラムの一部である。
論文 参考訳(メタデータ) (2020-10-30T16:08:32Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳(メタデータ) (2020-09-23T08:33:18Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳(メタデータ) (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。