論文の概要: Efficient Algorithms for Multidimensional Segmented Regression

• arxiv url: http://arxiv.org/abs/2003.11086v1
• Date: Tue, 24 Mar 2020 19:39:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-20 08:59:24.514553
• Title: Efficient Algorithms for Multidimensional Segmented Regression
• Title（参考訳）: 多次元分割回帰のための効率的なアルゴリズム
• Authors: Ilias Diakonikolas and Jerry Li and Anastasia Voloshinov
• Abstract要約: 多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
• 参考スコア（独自算出の注目度）: 42.046881924063044
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fundamental problem of fixed design {\em multidimensional segmented regression}: Given noisy samples from a function $f$, promised to be piecewise linear on an unknown set of $k$ rectangles, we want to recover $f$ up to a desired accuracy in mean-squared error. We provide the first sample and computationally efficient algorithm for this problem in any fixed dimension. Our algorithm relies on a simple iterative merging approach, which is novel in the multidimensional setting. Our experimental evaluation on both synthetic and real datasets shows that our algorithm is competitive and in some cases outperforms state-of-the-art heuristics. Code of our implementation is available at \url{https://github.com/avoloshinov/multidimensional-segmented-regression}.
• Abstract（参考訳）: 関数 $f$ のノイズサンプルが未知の $k$ 矩形集合上で一意に線形であることを約束するならば、平均二乗誤差において所望の精度で$f$ を回復したい。 任意の次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元設定において新しい単純な反復的マージ手法に依存する。 合成データと実データの両方を実験的に評価したところ、アルゴリズムは競争力があり、場合によっては最先端のヒューリスティックスよりも優れていた。 実装のコードは \url{https://github.com/avoloshinov/multidimensional-segmented-regression} で利用可能です。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
  本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。 解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
  論文  参考訳（メタデータ） (2024-04-27T10:20:41Z)
• Noise misleads rotation invariant algorithms on sparse targets [0.0]
  回転不変アルゴリズムのクラスは疎線形問題を学習するのに最適であることを示す。 回転対称問題に対してベイズ最適アルゴリズムの下位境界を用いてこれを証明する。 次に、単純な非回転不変アルゴリズムに対して、同じ問題に対してより低い上限を証明した。
  論文  参考訳（メタデータ） (2024-03-05T06:25:19Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。 また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
  論文  参考訳（メタデータ） (2023-03-03T18:03:49Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• A Data-Driven Line Search Rule for Support Recovery in High-dimensional Data Analysis [5.180648702293017]
  適切なステップサイズを適応的に決定する新しい,効率的なデータ駆動行探索法を提案する。 線形回帰問題とロジスティック回帰問題における最先端アルゴリズムとの比較は,提案アルゴリズムの安定性,有効性,優越性を示す。
  論文  参考訳（メタデータ） (2021-11-21T12:18:18Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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