論文の概要: Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms
- arxiv url: http://arxiv.org/abs/2111.15426v1
- Date: Tue, 30 Nov 2021 14:16:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-01 19:37:59.211552
- Title: Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms
- Title（参考訳）: 非線形素数-双対ハイブリッド勾配アルゴリズムによる効率的でロジスティック回帰
- Authors: J\'er\^ome Darbon and Gabriel P. Langlois
- Abstract要約: 弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Logistic regression is a widely used statistical model to describe the
relationship between a binary response variable and predictor variables in data
sets. It is often used in machine learning to identify important predictor
variables. This task, variable selection, typically amounts to fitting a
logistic regression model regularized by a convex combination of $\ell_1$ and
$\ell_{2}^{2}$ penalties. Since modern big data sets can contain hundreds of
thousands to billions of predictor variables, variable selection methods depend
on efficient and robust optimization algorithms to perform well.
State-of-the-art algorithms for variable selection, however, were not
traditionally designed to handle big data sets; they either scale poorly in
size or are prone to produce unreliable numerical results. It therefore remains
challenging to perform variable selection on big data sets without access to
adequate and costly computational resources. In this paper, we propose a
nonlinear primal-dual algorithm that addresses these shortcomings.
Specifically, we propose an iterative algorithm that provably computes a
solution to a logistic regression problem regularized by an elastic net penalty
in $O(T(m,n)\log(1/\epsilon))$ operations, where $\epsilon \in (0,1)$ denotes
the tolerance and $T(m,n)$ denotes the number of arithmetic operations required
to perform matrix-vector multiplication on a data set with $m$ samples each
comprising $n$ features. This result improves on the known complexity bound of
$O(\min(m^2n,mn^2)\log(1/\epsilon))$ for first-order optimization methods such
as the classic primal-dual hybrid gradient or forward-backward splitting
methods.
- Abstract（参考訳）: ロジスティック回帰は、データセットのバイナリ応答変数と予測変数の関係を記述するために広く用いられる統計モデルである。
機械学習で重要な予測変数を特定するためによく使われる。
このタスク、変数の選択は、通常、$\ell_1$と$\ell_{2}^{2}$ペナルティの凸結合によって正規化されたロジスティック回帰モデルに適合する。
現代のビッグデータは数十万から数十億の予測変数を含むことができるため、変数選択法は効率的で堅牢な最適化アルゴリズムに依存している。
しかし、変数選択のための最先端のアルゴリズムは、従来、ビッグデータの集合を扱うように設計されていなかった。
したがって、十分な計算資源にアクセスすることなく、データセット上で変数の選択を実行することは依然として困難である。
本稿では,これらの欠点に対処する非線形原始双対アルゴリズムを提案する。
具体的には,$o(t(m,n)\log(1/\epsilon))$演算において弾性ネットペナルティによって正規化されたロジスティック回帰問題に対する解を証明可能な反復アルゴリズムを提案し,ここで$\epsilon \in (0,1)$ は許容値を示し,$t(m,n)$ は$n$特徴を含むデータ集合上で行列ベクトル乗算を行うのに必要な演算演算数を表す。
この結果は、古典的原始双対ハイブリッド勾配や前方後方分割法のような一階最適化法に対して$O(\min(m^2n,mn^2)\log(1/\epsilon))$の既知の複雑性境界を改善する。
関連論文リスト
- Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data [17.657917523817243]
この問題を条件付き最適化問題とみなして,器用変分回帰のためのアルゴリズムを開発し,解析する。
最小二乗変数回帰の文脈では、我々のアルゴリズムは行列逆転やミニバッチを必要としない。
任意の$iota>0$に対して$mathcalO(log T/T)$と$mathcalO(1/T1-iota)$の順の収束率を導出する。
論文 参考訳（メタデータ） (2024-05-29T19:21:55Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Conformalization of Sparse Generalized Linear Models [2.1485350418225244]
等角予測法は、任意の有限サンプルサイズに対して有効である$y_n+1$の信頼セットを推定する。
魅力的ではあるが、そのような集合の計算は多くの回帰問題において計算不可能である。
経路追従アルゴリズムが共形予測集合を正確に近似する方法を示す。
論文 参考訳（メタデータ） (2023-07-11T08:36:12Z) - Easy Differentially Private Linear Regression [16.325734286930764]
本研究では,指数関数機構を用いて,非プライベート回帰モデルの集合からタキー深度の高いモデルを選択するアルゴリズムについて検討する。
このアルゴリズムは、データリッチな設定において、強い経験的性能を得る。
論文 参考訳（メタデータ） (2022-08-15T17:42:27Z) - Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。
結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文 参考訳（メタデータ） (2021-10-08T08:22:05Z) - Linear Regression by Quantum Amplitude Estimation and its Extension to
Convex Optimization [0.0]
線形回帰のための新しい量子アルゴリズムを提案し,その複雑性は$O(epsilon-1)$であり,データ点数に対する対数依存性は$N_D$である。
この方法では,データ点の和の形で計算のボトルネックを克服し,その複雑性を$N_D$に比例する。
論文 参考訳（メタデータ） (2021-05-28T00:04:11Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。