論文の概要: On Newton Screening

• arxiv url: http://arxiv.org/abs/2001.10616v2
• Date: Fri, 7 Feb 2020 16:09:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-06 08:08:51.857795
• Title: On Newton Screening
• Title（参考訳）: ニュートンスクリーニングについて
• Authors: Jian Huang, Yuling Jiao, Lican Kang, Jin Liu, Yanyan Liu, Xiliang Lu, and Yuanyuan Yang
• Abstract要約: 我々はNewton Screening (NS) と呼ばれる新しいスクリーニング手法を開発した。 NSは、一段階局所収束を達成するという意味で、最適収束特性を有することを示す。
• 参考スコア（独自算出の注目度）: 14.040371216692645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Screening and working set techniques are important approaches to reducing the size of an optimization problem. They have been widely used in accelerating first-order methods for solving large-scale sparse learning problems. In this paper, we develop a new screening method called Newton screening (NS) which is a generalized Newton method with a built-in screening mechanism. We derive an equivalent KKT system for the Lasso and utilize a generalized Newton method to solve the KKT equations. Based on this KKT system, a built-in working set with a relatively small size is first determined using the sum of primal and dual variables generated from the previous iteration, then the primal variable is updated by solving a least-squares problem on the working set and the dual variable updated based on a closed-form expression. Moreover, we consider a sequential version of Newton screening (SNS) with a warm-start strategy. We show that NS possesses an optimal convergence property in the sense that it achieves one-step local convergence. Under certain regularity conditions on the feature matrix, we show that SNS hits a solution with the same signs as the underlying true target and achieves a sharp estimation error bound with high probability. Simulation studies and real data analysis support our theoretical results and demonstrate that SNS is faster and more accurate than several state-of-the-art methods in our comparative studies.
• Abstract（参考訳）: 最適化問題のサイズを減らすため、スクリーニングと作業セット技術は重要なアプローチである。 大規模なスパース学習問題を解決する一階法の高速化に広く用いられている。 本稿では,ニュートンスクリーニング機構を内蔵した一般化ニュートン法であるNewton Screening (NS) という新しいスクリーニング手法を提案する。 我々は、lasso の等価な kkt 系を導出し、一般化ニュートン法を用いて kkt 方程式を解く。 このKKTシステムに基づいて、前回の繰り返しから生成された原始変数と双対変数の和を用いて、比較的小さな組込み作業セットをまず決定し、次いで、作業セットと閉形式式に基づいて更新された双対変数の最小二乗問題を解くことにより、一次変数を更新する。 さらに,ウォームスタート戦略によるニュートンスクリーニング(sns)の逐次バージョンについて検討する。 NSは1ステップの局所収束を達成するという意味で最適収束特性を有することを示す。 特徴行列上の一定の規則性条件下では、SNSが真ターゲットと同じ符号の解に到達し、高い確率で有界な推定誤差が得られることを示す。 シミュレーション研究と実データ解析は理論的な結果をサポートし、比較研究においてsnsがいくつかの最先端手法よりも高速かつ正確であることを実証する。

関連論文リスト

• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning [0.0]
  深部記憶ネットワークのための準ニュートン学習アルゴリズムの動作について検討する。 準ニュートンは効率が良く、よく知られたAdamの1次実行よりも性能が優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-18T20:53:58Z)
• SCORE: Approximating Curvature Information under Self-Concordant Regularization [0.0]
  本稿では,新たな入力を受信するたびに最小化速度を更新する自己調和正規化アルゴリズム(GGN-SCORE)を提案する。 提案アルゴリズムはヘッセン行列の2階情報構造を利用して計算オーバーヘッドを削減する。
  論文  参考訳（メタデータ） (2021-12-14T13:03:04Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach [33.21301562890201]
  準ニュートン法の超線形収束を利用する適応型サンプルサイズスキームを, 学習過程を通じて, 全世界的に活用する。 初期サンプルサイズが十分に大きく、準ニュートン法を用いて各サブプロブレムを解くと、サブプロブレムは超直線的に高速に解けることを示す。
  論文  参考訳（メタデータ） (2021-06-10T01:08:51Z)
• Distributed Second Order Methods with Fast Rates and Compressed Communication [6.069611493148631]
  分散最適化のための通信効率の高い第2次手法を複数開発する。 我々は大域的な部分線型および線形収束率と高速超線形速度を証明した。 結果は実データセットでの実験結果と共にサポートされます。
  論文  参考訳（メタデータ） (2021-02-14T14:06:45Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Disentangling the Gauss-Newton Method and Approximate Inference for Neural Networks [96.87076679064499]
  我々は一般化されたガウスニュートンを解き、ベイズ深層学習の近似推論を行う。 ガウス・ニュートン法は基礎となる確率モデルを大幅に単純化する。 ガウス過程への接続は、新しい関数空間推論アルゴリズムを可能にする。
  論文  参考訳（メタデータ） (2020-07-21T17:42:58Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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