論文の概要: Nearly Linear Row Sampling Algorithm for Quantile Regression

• arxiv url: http://arxiv.org/abs/2006.08397v1
• Date: Mon, 15 Jun 2020 13:40:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 05:12:23.856780
• Title: Nearly Linear Row Sampling Algorithm for Quantile Regression
• Title（参考訳）: 分位回帰のための近似線形列サンプリングアルゴリズム
• Authors: Yi Li, Ruosong Wang, Lin Yang, Hanrui Zhang
• Abstract要約: データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。 行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 54.75919082407094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm whose sampling complexity has at least cubic dependence on the dimensionality. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs. Our main technical contribution is to show that Lewis weights sampling, which has been used in row sampling algorithms for $\ell_p$ norms, can also be applied in row sampling algorithms for a variety of loss functions. We complement our theoretical results by experiments to demonstrate the practicality of our approach.
• Abstract（参考訳）: データの次元にほぼ線形なサンプリング複雑性を持つ量子損失関数の行サンプリングアルゴリズムを提案し、サンプリング複雑性が少なくとも次元に3乗依存する以前の最良のアルゴリズムを改善した。 行サンプリングアルゴリズムに基づいて,分位回帰のための最速の既知のアルゴリズムと,平衡有向グラフに対するグラフスパーシフィケーションアルゴリズムを与える。 我々の主要な技術的貢献は、$\ell_p$ノルムの行サンプリングアルゴリズムで使用されているlewis weights samplingが、様々な損失関数の行サンプリングアルゴリズムにも適用可能であることを示すことです。 本手法の実用性を示すために実験により理論的結果を補完する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。 本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-10T06:16:24Z)
• Efficient Numerical Algorithm for Large-Scale Damped Natural Gradient Descent [7.368877979221163]
  本研究では,パラメータ数が利用可能なサンプル数を大幅に上回る大規模シナリオにおいて,減衰したフィッシャー行列を効率的に解くアルゴリズムを提案する。 アルゴリズムはColesky分解に基づいており、一般に適用可能である。ベンチマークの結果、既存の手法よりもかなり高速であることが示されている。
  論文  参考訳（メタデータ） (2023-10-26T16:46:13Z)
• Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models [98.95988351420334]
  本稿では,事前学習した潜在拡散モデルを利用した線形逆問題の解法を初めて提案する。 線形モデル設定において,証明可能なサンプル回復を示すアルゴリズムを理論的に解析する。
  論文  参考訳（メタデータ） (2023-07-02T17:21:30Z)
• Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
  我々は、完全に学習率の低い制約付き領域をサンプリングするための新しい粒子ベースのアルゴリズム一式を導入する。 我々は,本アルゴリズムの性能を,単純度に基づくターゲットからのサンプリングを含む,様々な数値的な例で示す。
  論文  参考訳（メタデータ） (2023-05-24T09:31:18Z)
• Quantum Algorithm for Path-Edge Sampling [0.9990687944474739]
  隣接行列として与えられる無向グラフにおいて、2つのノード s と t の間の経路上のエッジをサンプリングする量子アルゴリズムを提案する。 我々は,この経路サンプリングアルゴリズムを,特定のケースにおいてst-path検索およびst-cut-set発見アルゴリズムのサブルーチンとして利用する。
  論文  参考訳（メタデータ） (2023-03-06T17:45:12Z)
• Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling [0.0]
  本稿では、ReLUアクティベーションを用いたトレーニングニューラルネットワークを最適化する、スケーラブルでサンプリングベースのアルゴリズムを提案する。 本稿ではまず,ReLUニューラルネットワークのピースワイズ線形構造を利用した反復アルゴリズムを提案する。 次に、各反復で計算されたLPソリューションの近傍を探索することで、このアプローチを拡張します。
  論文  参考訳（メタデータ） (2022-05-27T18:35:48Z)
• Classical simulation of boson sampling based on graph structure [2.5496329090462626]
  線形光回路のグラフ構造を利用する単一光子およびガウス入力状態に対する古典的なサンプリングアルゴリズムを提案する。 回路深さが格子間隔の二次よりも小さい場合、指数的に小さな誤差で効率的なシミュレーションが可能であることを示す。 近年の数値的なガウスボソンサンプリング実験により,木幅に制限のある木幅アルゴリズムが実験データよりも大きな可能性を示す可能性が示された。
  論文  参考訳（メタデータ） (2021-10-04T17:02:35Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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