論文の概要: Max-Linear Regression by Convex Programming
- arxiv url: http://arxiv.org/abs/2103.07020v2
- Date: Sat, 24 Feb 2024 01:28:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 19:53:59.545907
- Title: Max-Linear Regression by Convex Programming
- Title（参考訳）: 凸プログラミングによる最大線形回帰
- Authors: Seonho Kim, Sohail Bahmani, and Kiryung Lee
- Abstract要約: 我々は、最大線形回帰問題の推定器として、アンカーレグレッション(AR)によって与えられるスケーラブルな凸プログラムを定式化し、解析する。
以上の結果から, 対数係数まで, 正確な回復スケールについて, 十分な数のノイズのない観測結果が得られた。
- 参考スコア（独自算出の注目度）: 5.366354612549172
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the multivariate max-linear regression problem where the model
parameters
$\boldsymbol{\beta}_{1},\dotsc,\boldsymbol{\beta}_{k}\in\mathbb{R}^{p}$ need to
be estimated from $n$ independent samples of the (noisy) observations $y =
\max_{1\leq j \leq k} \boldsymbol{\beta}_{j}^{\mathsf{T}} \boldsymbol{x} +
\mathrm{noise}$. The max-linear model vastly generalizes the conventional
linear model, and it can approximate any convex function to an arbitrary
accuracy when the number of linear models $k$ is large enough. However, the
inherent nonlinearity of the max-linear model renders the estimation of the
regression parameters computationally challenging. Particularly, no estimator
based on convex programming is known in the literature. We formulate and
analyze a scalable convex program given by anchored regression (AR) as the
estimator for the max-linear regression problem. Under the standard Gaussian
observation setting, we present a non-asymptotic performance guarantee showing
that the convex program recovers the parameters with high probability. When the
$k$ linear components are equally likely to achieve the maximum, our result
shows a sufficient number of noise-free observations for exact recovery scales
as {$k^{4}p$} up to a logarithmic factor. { This sample complexity coincides
with that by alternating minimization (Ghosh et al., {2021}). Moreover, the
same sample complexity applies when the observations are corrupted with
arbitrary deterministic noise. We provide empirical results that show that our
method performs as our theoretical result predicts, and is competitive with the
alternating minimization algorithm particularly in presence of multiplicative
Bernoulli noise. Furthermore, we also show empirically that a recursive
application of AR can significantly improve the estimation accuracy.}
- Abstract（参考訳）: モデルパラメータ $\boldsymbol{\beta}_{1},\dotsc,\boldsymbol{\beta}_{k}\in\mathbb{R}^{p}$ を、(ノイズ)観測の独立サンプル$n$$$y = \max_{1\leq j \leq k} \boldsymbol{\beta}_{j}^{\mathsf{T}} \boldsymbol{x} + \mathrm{noise}$ から推定する必要がある。
最大線形モデルは、従来の線形モデルを大幅に一般化し、線型モデルが十分に大きい場合、任意の凸関数を任意の精度に近似することができる。
しかし、マックス・リニアモデルの固有非線形性は計算上難しい回帰パラメータの推定を導出する。
特に、凸プログラミングに基づく推定器は文献では知られていない。
我々は,最大線形回帰問題の推定子としてアンカー回帰 (ar) によって与えられるスケーラブルな凸プログラムを定式化し,解析する。
標準ガウス観測条件では、凸プログラムが高い確率でパラメータを回復することを示す非漸近的な性能保証を示す。
k$ の線形成分が等しく最大値に達する可能性がある場合、この結果は {$k^{4}p$} から対数係数までの正確な回復スケールに対して十分なノイズのない観測結果を示す。
このサンプルの複雑性は、最小化の交互化(Ghosh et al., {2021})と一致する。
さらに同じサンプル複雑性は、観測が任意の決定論的ノイズで崩壊した場合にも適用される。
本稿では,提案手法が理論結果として有効であることを示す実験結果を示し,特にベルヌーイ雑音の存在下での交互最小化アルゴリズムとの競合性を示す。
さらに,ARの再帰的応用により推定精度が大幅に向上することを示す。
}
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Max-affine regression via first-order methods [7.12511675782289]
最大アフィンモデルは信号処理と統計学の応用においてユビキタスに現れる。
最大アフィン回帰に対する勾配降下(GD)とミニバッチ勾配降下(SGD)の非漸近収束解析を行った。
論文 参考訳（メタデータ） (2023-08-15T23:46:44Z) - Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood
Estimation for Latent Gaussian Models [69.22568644711113]
我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。
理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。
シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
論文 参考訳（メタデータ） (2023-06-05T21:08:34Z) - Mixed Regression via Approximate Message Passing [16.91276351457051]
複数の信号と潜伏変数を持つ一般化線形モデル(GLM)における回帰問題について検討する。
混合線形回帰では、それぞれの観測は$L$信号ベクトル(回帰器)の1つから来るが、どれがどれであるかはわからない。
最大アフィン回帰では、各観測は最大で$L$アフィン関数から成り、それぞれ異なる信号ベクトルによって定義される。
論文 参考訳（メタデータ） (2023-04-05T04:59:59Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
我々は,n$の線形測定に応用したハードおよびソフトサポートベクター回帰法について検討した。
得られた結果は、ハードおよびソフトサポートベクトル回帰アルゴリズムの設計に介入するパラメータを最適に調整するために使用される。
論文 参考訳（メタデータ） (2021-05-21T14:26:28Z) - Robust High Dimensional Expectation Maximization Algorithm via Trimmed
Hard Thresholding [24.184520829631587]
本研究では,高次元空間における任意の劣化サンプルを用いた潜在変数モデルの推定問題について検討する。
本稿では,トリミング勾配ステップを付加したトリミング予測最大化法を提案する。
アルゴリズムは汚損防止であり、幾何学的に(ほぼ)最適統計率に収束することを示す。
論文 参考訳（メタデータ） (2020-10-19T15:00:35Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳（メタデータ） (2020-10-19T07:15:38Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。