論文の概要: 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} で利用可能です。
関連論文リスト
- Noise misleads rotation invariant algorithms on sparse targets [0.0]
回転不変アルゴリズムのクラスは疎線形問題を学習するのに最適であることを示す。
回転対称問題に対してベイズ最適アルゴリズムの下位境界を用いてこれを証明する。
次に、単純な非回転不変アルゴリズムに対して、同じ問題に対してより低い上限を証明した。
論文 参考訳(メタデータ) (2024-03-05T06:25:19Z) - Learning the Positions in CountSketch [56.22648269865784]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-11T07:28:35Z) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳(メタデータ) (2023-03-03T18:03:49Z) - Near Optimal Private and Robust Linear Regression [47.2888113094367]
本稿では,2つのアルゴリズムを改良したDP-SGDアルゴリズムを提案する。
ラベル破壊の下では、これは$(varepsilon,delta)$-DPとロバスト性の両方を保証する最初の効率的な線形回帰アルゴリズムである。
論文 参考訳(メタデータ) (2023-01-30T20:33:26Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳(メタデータ) (2022-06-29T01:40:38Z) - 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) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳(メタデータ) (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。