論文の概要: Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees

• arxiv url: http://arxiv.org/abs/2311.01806v1
• Date: Fri, 3 Nov 2023 09:35:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-06 14:34:20.053490
• Title: Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees
• Title（参考訳）: シャープ保証付き凸および非凸正規化最小方形に対するスケッチング
• Authors: Yingzhen Yang, Ping Li
• Abstract要約: 本稿では,非正規化関数によって正規化あるいは凸化される最小二乗問題に対する高速近似を提案する。 スケッチされた凸や非近似問題を解くことにより、推定のための最小値率を初めて示す。
• 参考スコア（独自算出の注目度）: 23.614074988517864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized algorithms are important for solving large-scale optimization problems. In this paper, we propose a fast sketching algorithm for least square problems regularized by convex or nonconvex regularization functions, Sketching for Regularized Optimization (SRO). Our SRO algorithm first generates a sketch of the original data matrix, then solves the sketched problem. Different from existing randomized algorithms, our algorithm handles general Frechet subdifferentiable regularization functions in an unified framework. We present general theoretical result for the approximation error between the optimization results of the original problem and the sketched problem for regularized least square problems which can be convex or nonconvex. For arbitrary convex regularizer, relative-error bound is proved for the approximation error. Importantly, minimax rates for sparse signal estimation by solving the sketched sparse convex or nonconvex learning problems are also obtained using our general theoretical result under mild conditions. To the best of our knowledge, our results are among the first to demonstrate minimax rates for convex or nonconvex sparse learning problem by sketching under a unified theoretical framework. We further propose an iterative sketching algorithm which reduces the approximation error exponentially by iteratively invoking the sketching algorithm. Experimental results demonstrate the effectiveness of the proposed SRO and Iterative SRO algorithms.
• Abstract（参考訳）: ランダム化アルゴリズムは大規模な最適化問題の解決に重要である。 本稿では、凸正規化関数や非凸正規化関数によって正規化される最小二乗問題に対する高速スケッチアルゴリズム、Sketching for Regularized Optimization (SRO)を提案する。 我々のSROアルゴリズムは最初に元のデータ行列のスケッチを生成し、それからスケッチされた問題を解く。 既存のランダム化アルゴリズムと異なり、我々のアルゴリズムは統一されたフレームワークで一般的なFrechet subdifferentiable regularization関数を処理する。 本稿では,元の問題の最適化結果と,凸あるいは凸のない正則化最小二乗問題のスケッチ問題との近似誤差に関する一般的な理論的結果を示す。 任意の凸正規化器の場合、近似誤差に対して相対誤差境界が証明される。 さらに, 弱条件下での一般理論結果を用いて, スケッチされたスパース凸あるいは非凸学習問題を解くことにより, スパース信号推定のためのミニマックス率を求める。 私たちの知識を最大限に活用するために、我々の結果は、統一理論の枠組みでスケッチすることで凸または非凸スパース学習問題のミニマックス率を最初に示すものの一つです。 さらに,スケッチアルゴリズムを反復的に呼び出すことで近似誤差を指数関数的に低減する反復スケッチアルゴリズムを提案する。 実験により提案したSROアルゴリズムと反復SROアルゴリズムの有効性が示された。

関連論文リスト

• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。 本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-10T06:16:24Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• A Parameter-free Algorithm for Convex-concave Min-max Problems [33.39558541452866]
  洞窟なし最適化アルゴリズムは、学習速度を調整せずに初期点に対して収束率が最適であるアルゴリズムを指す。 副産物として,パラメータフリーなアルゴリズムを用いて,成長条件付きmin-max問題の高速速度を求める新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-02-27T18:10:06Z)
• Train simultaneously, generalize better: Stability of gradient-based minimax learners [12.691047660244331]
  コンベックス・コンベブと非コンベックス・ミニマックス・セッティングの両方において,訓練されたミニマックスモデルの性能において重要な役割を担っている。 学習したミニマックスモデルの一般化における最適化アルゴリズムの役割を示す数値的な結果について議論する。
  論文  参考訳（メタデータ） (2020-10-23T17:44:43Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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