論文の概要: Combinatorial optimization of the coefficient of determination

• arxiv url: http://arxiv.org/abs/2410.09316v1
• Date: Sat, 12 Oct 2024 00:53:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 15:13:33.219631
• Title: Combinatorial optimization of the coefficient of determination
• Title（参考訳）: 決定係数の組合せ最適化
• Authors: Marc Harary,
• Abstract要約: 決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。 誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Robust correlation analysis is among the most critical challenges in statistics. Herein, we develop an efficient algorithm for selecting the $k$- subset of $n$ points in the plane with the highest coefficient of determination $\left( R^2 \right)$. Drawing from combinatorial geometry, we propose a method called the \textit{quadratic sweep} that consists of two steps: (i) projectively lifting the data points into $\mathbb R^5$ and then (ii) iterating over each linearly separable $k$-subset. Its basis is that the optimal set of outliers is separable from its complement in $\mathbb R^2$ by a conic section, which, in $\mathbb R^5$, can be found by a topological sweep in $\Theta \left( n^5 \log n \right)$ time. Although key proofs of quadratic separability remain underway, we develop strong mathematical intuitions for our conjectures, then experimentally demonstrate our method's optimality over several million trials up to $n=30$ without error. Implementations in Julia and fully seeded, reproducible experiments are available at https://github.com/marc-harary/QuadraticSweep.
• Abstract（参考訳）: 統計学において、ロバスト相関分析は最も重要な課題の一つである。 ここでは、決定係数が$\left(R^2 \right)$の最も高い平面上の$n$点の$k$-部分集合を選択する効率的なアルゴリズムを開発する。 組合せ幾何学から,2つのステップからなる「textit{quadratic sweep}」という手法を提案する。 i) データポイントを$\mathbb R^5$に投影し、それから (ii) 線形分離可能な各$k$-subset を反復する。 その根拠は、最適値の集合が、円錐部分によって$\mathbb R^2$ の補集合から分離可能であり、$\mathbb R^5$ のとき、$\Theta \left(n^5 \log n \right)$ の位相スイープによって見つけることができることである。 二次分離性の鍵となる証明はまだ進行中であるが、予想に対する強い数学的直観を発達させ、数万回の試行において、誤りなく$n=30$までメソッドの最適性を実験的に実証する。 Juliaの実装と完全にシードされた再現可能な実験はhttps://github.com/marc-harary/QuadraticSweep.comで公開されている。

関連論文リスト

• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。 結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [8.0153031008486]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
  階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。 我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
  論文  参考訳（メタデータ） (2021-01-15T18:52:02Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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