論文の概要: Max-Linear Regression by Scalable and Guaranteed Convex Programming
- arxiv url: http://arxiv.org/abs/2103.07020v1
- Date: Fri, 12 Mar 2021 00:55:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-15 13:27:40.836376
- Title: Max-Linear Regression by Scalable and Guaranteed Convex Programming
- Title（参考訳）: スケーラブルで保証された凸プログラミングによる最大線形回帰
- Authors: Seonho Kim, Sohail Bahmani, and Kiryung Lee
- Abstract要約: 最大線形モデルは、従来の線形モデルを大幅に一般化する。
凸プログラミングに基づく推定器は文献では知られていない。
コンベックスプログラムが高い確率でパラメータを回復することを示す非漸近的性能保証を示す。
- 参考スコア（独自算出の注目度）: 13.980924073019963
- 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 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 that a sufficient
number of observations scales as $k^{2}p$ up to a logarithmic factor. This
significantly improves on the analogous prior result based on alternating
minimization (Ghosh et al., 2019). Finally, through a set of Monte Carlo
simulations, we illustrate that our theoretical result is consistent with
empirical behavior, and the convex estimator for max-linear regression is as
competitive as the alternating minimization algorithm in practice.
- Abstract（参考訳）: モデルパラメータ $\boldsymbol{\beta}_{1},\dotsc,\boldsymbol{\beta}_{k}\in\mathbb{R}^{p}$ が (ノイズの多い)観測 $y = \max_{1\leq j \leq k} \boldsymbol{\beta}_{j}^{\mathsf{T}} \boldsymbol{x} + \mathrm{noise}$ の独立したサンプルから推定される必要がある。
最大線形モデルは、従来の線形モデルを大幅に一般化し、線型モデルが十分に大きい場合、任意の凸関数を任意の精度に近似することができる。
しかし、マックス・リニアモデルの固有非線形性は計算上難しい回帰パラメータの推定を導出する。
特に、凸プログラミングに基づく推定器は文献で知られていない。
最大線形回帰問題の推定器としてスケーラブル凸プログラムを定式化し,解析する。
標準ガウス観測条件では、凸プログラムが高い確率でパラメータを回復することを示す非漸近的な性能保証を示す。
線形成分 $k$ が等しく最大値に達する可能性が高い場合、その結果、十分な数の観測が対数係数まで $k^{2}p$ としてスケールすることを示しています。
これは交代最小化(ghosh et al., 2019)に基づく類似の先行結果を大幅に改善する。
最後に,モンテカルロシミュレーションにより,理論結果が経験的挙動と一致していることを示し,最大線形回帰の凸推定器は,実際には交互最小化アルゴリズムと同等の競合性を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。