論文の概要: 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) 階層フレームワーク)から生じる。
関連論文リスト
- Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。
理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals [10.850101961203752]
正方形損失目標を持つガウスの辺縁部における任意のバイアスのReLU活性化(あるいはニューロン)を学習する問題を考察する。
我々の主な成果は時間統計クエリ(SQ)アルゴリズムであり、任意のバイアスに対して最初の定数係数近似を与える。
我々のアルゴリズムは、勾配降下に基づく既存のアルゴリズムから興味深い逸脱を示す。
論文 参考訳（メタデータ） (2024-11-21T17:43:51Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文 参考訳（メタデータ） (2024-02-01T09:18:34Z) - 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) - 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) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。