論文の概要: Fast and Exact Least Absolute Deviations Line Fitting via Piecewise Affine Lower-Bounding

• arxiv url: http://arxiv.org/abs/2512.20682v1
• Date: Mon, 22 Dec 2025 10:18:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-25 19:43:21.562404
• Title: Fast and Exact Least Absolute Deviations Line Fitting via Piecewise Affine Lower-Bounding
• Title（参考訳）: ピスワイドアフィン下界を経由した高速かつ高精度な絶対偏差線フィッティング
• Authors: Stefan Volz, Martin Storath, Andreas Weinmann,
• Abstract要約: Laast-absolute-deviations (LAD) ラインフィッティングは、外れ値に対して堅牢であるが、最小二乗回帰よりも計算的により複雑である。 LADラインフィッティングの正確なアルゴリズムであるPiecewise Affine Lower-Bounding (PALB)法を提案する。 LPベースの実装やIRLSベースの解決器よりも一貫して高速である。
• 参考スコア（独自算出の注目度）: 0.509780930114934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Least-absolute-deviations (LAD) line fitting is robust to outliers but computationally more involved than least squares regression. Although the literature includes linear and near-linear time algorithms for the LAD line fitting problem, these methods are difficult to implement and, to our knowledge, lack maintained public implementations. As a result, practitioners often resort to linear programming (LP) based methods such as the simplex-based Barrodale-Roberts method and interior-point methods, or on iteratively reweighted least squares (IRLS) approximation which does not guarantee exact solutions. To close this gap, we propose the Piecewise Affine Lower-Bounding (PALB) method, an exact algorithm for LAD line fitting. PALB uses supporting lines derived from subgradients to build piecewise-affine lower bounds, and employs a subdivision scheme involving minima of these lower bounds. We prove correctness and provide bounds on the number of iterations. On synthetic datasets with varied signal types and noise including heavy-tailed outliers as well as a real dataset from the NOAA's Integrated Surface Database, PALB exhibits empirical log-linear scaling. It is consistently faster than publicly available implementations of LP based and IRLS based solvers. We provide a reference implementation written in Rust with a Python API.
• Abstract（参考訳）: Laast-absolute-deviations (LAD) ラインフィッティングは、外れ値に対して堅牢であるが、最小二乗回帰よりも計算的により複雑である。 文献にはLADラインフィッティング問題に対する線形およびニア線形時間アルゴリズムが含まれているが、これらの手法は実装が困難であり、我々の知る限り、維持された公開実装が欠如している。 結果として、実践者はリニアプログラミング(LP)に基づく手法、例えば、単純型Barrodale-Roberts法やインテリアポイント法、あるいは正確な解を保証しない反復再重み付き最小二乗法(IRLS)の近似を利用することが多い。 このギャップを埋めるために,LADラインフィッティングの正確なアルゴリズムであるPiecewise Affine Lower-Bounding (PALB)法を提案する。 PALBは、下階から派生した支持線を用いて、下層境界を断片的に配置し、これらの下層境界のミニマを含む部分分割スキームを用いる。 正確さを証明し、イテレーションの数に限界を与えます。 NOAAのIntegrated Surface Databaseの実際のデータセットと同様に、重い尾の外れ値を含む様々な信号タイプとノイズを持つ合成データセットでは、PALBは経験的なログ線形スケーリングを示す。 LPベースの実装やIRLSベースの解決器よりも一貫して高速である。 Python APIでRustで記述されたリファレンス実装を提供しています。

関連論文リスト

• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  ペナルティに基づく手法は、双レベル最適化(BLO)問題を解くのに人気がある。 それらはしばしば、大きなペナルティ項によって引き起こされる滑らかさの増加に対応するために、低レベル(LL)問題と小さな外ループステップサイズを解決するためにインナーループ反復を必要とする。 この研究は、結合制約(CC)を伴う一般的なBLO問題を考察し、上位変数と下位変数を分離する新しいペナルティ改革を活用する。
  論文  参考訳（メタデータ） (2025-11-20T20:48:14Z)
• Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
  オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。 本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
  論文  参考訳（メタデータ） (2022-12-28T15:28:12Z)
• On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation [80.86358123230757]
  本稿では,Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) というアルゴリズムを提案する。 部分的なデータカバレッジの仮定の下で、BCP-VI は最適な Q-値関数に正のギャップがあるときに、オフライン RL に対して $tildemathcalO(frac1K)$ の高速レートを得る。 これらは、アダプティブデータからの線形関数近似を持つオフラインRLに対してそれぞれ、最初の$tildemathcalO(frac1K)$boundと絶対零部分最適境界である。
  論文  参考訳（メタデータ） (2022-11-23T18:50:44Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting [60.98700344526674]
  線形関数表現のような低複雑度モデルがサンプル効率のよい強化学習を可能にする上で重要な役割を果たしている。 本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することができる新しいサンプリングプロトコルについて検討する。 この設定に合わせたアルゴリズムを開発し、特徴次元、地平線、逆の準最適ギャップと実際にスケールするサンプル複雑性を実現するが、状態/作用空間のサイズではない。
  論文  参考訳（メタデータ） (2021-05-17T17:22:07Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。 既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
  論文  参考訳（メタデータ） (2020-11-27T16:42:12Z)
• Low-Rank Robust Online Distance/Similarity Learning based on the Rescaled Hinge Loss [0.34376560669160383]
  既存のオンライン手法では、トレーニング三つ子やペアの制約が事前に存在すると仮定することが多い。 オンライン距離相似学習問題を,ロバストな再スケールヒンジ損失関数を用いて定式化する。 提案モデルは比較的汎用的で,任意のPAベースのオンラインディスタンス・シミュラリティアルゴリズムに適用可能である。
  論文  参考訳（メタデータ） (2020-10-07T08:38:34Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)

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

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