論文の概要: Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements

• arxiv url: http://arxiv.org/abs/2604.11584v2
• Date: Tue, 14 Apr 2026 14:29:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 14:01:13.513099
• Title: Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements
• Title（参考訳）: ラストトリミング正方形の計算:超平面配置強化による分岐境界フレームワーク
• Authors: Xiang Meng, Andrés Gómez, Rahul Mazumder,
• Abstract要約: 最小トリミング正方形(LTS)回帰問題(英語版)は、大きめの残差を捕獲することによってデータにおける外れ値の影響を緩和する頑健な推定器である。 既存のMIO(mixed-integer Optimization)の定式化は、弱い緩和と観測数における指数的な最悪ケースの複雑さのために、不十分にスケールする。 我々は,超平面配置論理を視点再構成に組み込んだMIOの新たな定式化を提案し,最適解の構造的特性を明示する。
• 参考スコア（独自算出の注目度）: 21.28320211178358
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study computational aspects of a key problem in robust statistics -- the penalized least trimmed squares (LTS) regression problem, a robust estimator that mitigates the influence of outliers in data by capping residuals with large magnitudes. Although statistically attractive, penalized LTS is NP-hard, and existing mixed-integer optimization (MIO) formulations scale poorly due to weak relaxations and exponential worst-case complexity in the number of observations. We propose a new MIO formulation that embeds hyperplane arrangement logic into a perspective reformulation, explicitly enforcing structural properties of optimal solutions. We show that, if the number of features is fixed, the resulting branch-and-bound tree is of polynomial size in the sample size. Moreover, we develop a tailored branch-and-bound algorithm that uses first-order methods with dual bounds to solve node relaxations efficiently. Computational experiments on synthetic and real datasets demonstrate substantial improvements over existing MIO approaches: on synthetic instances with 5000 samples and 20 features, our tailored solver reaches a 1% gap in 1 minute while competing approaches fail to do so within one hour. These gains enable exact robust regression at significantly larger sample sizes in low-dimensional settings.
• Abstract（参考訳）: 本研究では,大容量の残差をカプセル化することにより,データにおける外れ値の影響を緩和するロバスト推定器である,正則化最小トリミング正方形回帰問題(LTS)について,重要な問題の計算的側面について検討する。 統計学的には魅力的だが、ペナル化LTSはNPハードであり、既存の混合整数最適化(MIO)の定式化は、観測数において弱い緩和と極端な最悪のケースの複雑さのために不十分にスケールする。 我々は,超平面配置論理を視点再構成に組み込んだMIOの新たな定式化を提案し,最適解の構造的特性を明示する。 特徴数が固定された場合、結果として得られる分岐とバウンドツリーは、サンプルサイズにおいて多項式サイズであることが示される。 さらに,ノードの緩和を効率的に解くために,二元境界を持つ一階法を用いるアルゴリズムを開発した。 5000のサンプルと20の特徴を持つ合成インスタンスでは、我々の調整されたソルバは1分で1%のギャップに達し、競合するアプローチは1時間以内にそれを行うことができない。 これらの利得は、低次元の設定において、かなり大きなサンプルサイズで正確に頑健な回帰を可能にする。

関連論文リスト

• Nearly Optimal Best Arm Identification for Semiparametric Bandits [2.538209532048867]
  半パラメトリックバンディットにおける固定信頼ベストアーム識別(BAI)について検討した。 トランスダクティブ・セッティングのために、シフトした特徴に対する対応する線形帯域複雑性を特徴とする、達成可能なインスタンス依存下界を確立する。 我々の分析は、最大ログ係数と追加の$d2$項を含む、ほぼ最適に高確率のサンプル複雑度上限を得る。
  論文  参考訳（メタデータ） (2026-04-05T05:13:02Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
  アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。 アルゴリズムは任意の外れ値の小さな部分に対して頑健であり、外れ値の小さな部分の関数として最適誤差率を達成する。
  論文  参考訳（メタデータ） (2025-03-31T17:08:12Z)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  MIDX-Samplerは、逆多重インデックスアプローチに基づく新しい適応型サンプリング戦略である。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。
  論文  参考訳（メタデータ） (2025-01-15T04:09:21Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)

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

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