論文の概要: Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions

• arxiv url: http://arxiv.org/abs/2605.06959v1
• Date: Thu, 07 May 2026 21:23:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.63092
• Title: Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions
• Title（参考訳）: 最大アフィン関数の差による高次元の局所的最適方向線形回帰
• Authors: Haitham Kanj, Kiryung Lee,
• Abstract要約: 本稿では,Adaptive Block Gradient Descent (ABGD) アルゴリズムによる線形回帰の解を提案する。 この方法の心臓は、極大ファイン関数の差分として片方向線型関数のパラメトリゼーションである。 我々は,実世界のデータセットにおける最先端手法と比較して,競争性能を観察する。
• 参考スコア（独自算出の注目度）: 4.297070083645049
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a parametric solution to piecewise linear regression through the Adaptive Block Gradient Descent (ABGD) algorithm. The heart of the method is the parametrization of piecewise linear functions as the difference of max-affine (DoMA) functions. A non-asymptotic local convergence analysis for ABGD is provided under sub-Gaussian covariate and noise distributions. To initialize ABGD, we adapt a prior algorithm originally developed for the simpler setting of max-affine functions. When suitably initialized, ABGD converges linearly to an $ε$-accurate estimate given $\tilde{\mathcal{O}}(d\max(σ_z/ε,1)^2)$ observations where $σ_z^2$ denotes the noise variance. This implies exact recovery given $\tilde{\mathcal{O}}(d)$ samples in the noiseless case. Also, such a rate is shown to be minimax optimal up to logarithmic factors. Synthetic numerical results corroborate the theoretical guarantees for ABGD. We also observe competitive performance compared to the state-of-the-art methods on real-world datasets.
• Abstract（参考訳）: 本稿では,Adaptive Block Gradient Descent (ABGD)アルゴリズムを用いて,一方向線形回帰のパラメトリック解を提案する。 この手法の心臓は、最大アフィン関数(DoMA)の差分として、片方向線形関数のパラメトリゼーションである。 ABGDの非漸近局所収束解析は、準ガウス的共変量および雑音分布の下で提供される。 ABGD を初期化するために,より単純な最大アフィン関数設定のために開発された先行アルゴリズムを適応する。 適切に初期化されると、ABGD は $\tilde{\mathcal{O}}(d\max(σ_z/ε,1)^2)$ で与えられる$ε$-正確な推定値に線形収束する。 これは、ノイズレスケースで$\tilde{\mathcal{O}}(d)$サンプルが与えられた正確なリカバリを意味する。 また、この比率は対数係数まで最小限の値であることが示される。 合成数値結果は、ABGDの理論的保証を裏付ける。 また、実世界のデータセットの最先端手法と比較して、競合性能も観察する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Fundamental limits of Non-Linear Low-Rank Matrix Estimation [18.455890316339595]
  ベイズ最適性能は、有効前のガウスモデルによって特徴づけられる。 信号を正確に再構成するためには、Nfrac 12 (1-1/k_F)$として増加する信号対雑音比が必要であり、$k_F$は関数の最初のゼロでないフィッシャー情報係数である。
  論文  参考訳（メタデータ） (2024-03-07T05:26:52Z)
• Max-affine regression via first-order methods [7.12511675782289]
  最大アフィンモデルは信号処理と統計学の応用においてユビキタスに現れる。 最大アフィン回帰に対する勾配降下(GD)とミニバッチ勾配降下(SGD)の非漸近収束解析を行った。
  論文  参考訳（メタデータ） (2023-08-15T23:46:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs [16.96562173221624]
  有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。 特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。 崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
  論文  参考訳（メタデータ） (2020-05-15T21:14:22Z)

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

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