論文の概要: Efficient Strongly Polynomial Algorithms for Quantile Regression
- arxiv url: http://arxiv.org/abs/2307.08706v1
- Date: Fri, 14 Jul 2023 03:07:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 17:57:20.470298
- Title: Efficient Strongly Polynomial Algorithms for Quantile Regression
- Title（参考訳）: 量子回帰のための高効率多項アルゴリズム
- Authors: Suraj Shetiya, Shohedul Hasan, Abolfazl Asudeh, and Gautam Das
- Abstract要約: 量子回帰(QR)の古典的手法を再考する
本稿では,様々な設定に対して,QRに対して高効率な古典的アルゴリズムを提案する。
2次元QRでは、$k$-setという幾何学的概念に結びつくため、$mathcalO(n4/3 polylog(n))$の最悪の時間複雑性を持つアルゴリズムを提案する。
2次元に対して$mathcalO(nlog2(n))$の期待時間複雑性を持つランダム化QRも提案する。
- 参考スコア（独自算出の注目度）: 12.772027028644041
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear Regression is a seminal technique in statistics and machine learning,
where the objective is to build linear predictive models between a response
(i.e., dependent) variable and one or more predictor (i.e., independent)
variables. In this paper, we revisit the classical technique of Quantile
Regression (QR), which is statistically a more robust alternative to the other
classical technique of Ordinary Least Square Regression (OLS). However, while
there exist efficient algorithms for OLS, almost all of the known results for
QR are only weakly polynomial. Towards filling this gap, this paper proposes
several efficient strongly polynomial algorithms for QR for various settings.
For two dimensional QR, making a connection to the geometric concept of
$k$-set, we propose an algorithm with a deterministic worst-case time
complexity of $\mathcal{O}(n^{4/3} polylog(n))$ and an expected time complexity
of $\mathcal{O}(n^{4/3})$ for the randomized version. We also propose a
randomized divide-and-conquer algorithm -- RandomizedQR with an expected time
complexity of $\mathcal{O}(n\log^2{(n)})$ for two dimensional QR problem. For
the general case with more than two dimensions, our RandomizedQR algorithm has
an expected time complexity of $\mathcal{O}(n^{d-1}\log^2{(n)})$.
- Abstract（参考訳）: リニア回帰(英: Linear Regression)とは、統計学と機械学習において、応答(従属)変数と1つ以上の予測(独立)変数の間に線形予測モデルを構築することを目的とする基礎的な手法である。
本稿では,通常の最小二乗回帰 (ols) の他の古典的手法よりも統計的にロバストな手法である量子量回帰 (qr) の古典的手法を再検討する。
しかし、OLSの効率的なアルゴリズムは存在するが、QRの既知の結果のほとんどすべてが弱多項式である。
このギャップを埋めるため,本論文ではqrの高効率な強多項式アルゴリズムを提案する。
2次元 qr に対して、k$-set の幾何学的概念と接続し、決定論的に最悪の場合の時間複雑性を $\mathcal{o}(n^{4/3} polylog(n))$ とし、ランダム化バージョンに対して $\mathcal{o}(n^{4/3})$ を期待するアルゴリズムを提案する。
また、2次元QR問題に対して$\mathcal{O}(n\log^2{(n)})$の期待時間複雑性を持つランダム化QRを提案する。
2次元以上の一般の場合、ランダム化qrアルゴリズムは、$\mathcal{o}(n^{d-1}\log^2{(n)})$という予測時間複雑性を持つ。
関連論文リスト
- 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) - 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) - Feature Adaptation for Sparse Linear Regression [20.923321050404827]
スパース線形回帰は高次元統計学における中心的な問題である。
少数の近似依存を許容するアルゴリズムを提供する。
我々のフレームワークは、疎線形回帰のためのより広範な機能適応のフレームワークに適合する。
論文 参考訳（メタデータ） (2023-05-26T12:53:13Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - Subgradient Regularized Multivariate Convex Regression at Scale [21.55988846648753]
次数正規化凸回帰関数を$d$次元で$n$のサンプルに適合させる新しい大規模アルゴリズムを提案する。
本研究のフレームワークは,n=105$と$d=10$で,段階的な正規化凸回帰問題のインスタンスを数分で解くことができることを示す。
論文 参考訳（メタデータ） (2020-05-23T19:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。