論文の概要: Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional
Optimization: Sharp Analysis and Lower Bounds
- arxiv url: http://arxiv.org/abs/2012.07054v1
- Date: Sun, 13 Dec 2020 13:02:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-09 12:37:41.464292
- Title: Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional
Optimization: Sharp Analysis and Lower Bounds
- Title（参考訳）: 高次元最適化のための適応的無作為部分空間法:シャープ解析と下限
- Authors: Jonathan Lacotte, Mert Pilanci
- Abstract要約: 2次統計が入力データを反映する相関ランダム行列をサンプリングすることにより、適切な適応部分空間を生成することができる。
ランダム化された近似の相対誤差は、データ行列のスペクトルの観点から厳密に特徴付けることができることを示した。
実験の結果,提案手法は様々な機械学習および最適化問題において,大幅な高速化を可能にすることがわかった。
- 参考スコア（独自算出の注目度）: 37.03247707259297
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose novel randomized optimization methods for high-dimensional convex
problems based on restrictions of variables to random subspaces. We consider
oblivious and data-adaptive subspaces and study their approximation properties
via convex duality and Fenchel conjugates. A suitable adaptive subspace can be
generated by sampling a correlated random matrix whose second order statistics
mirror the input data. We illustrate that the adaptive strategy can
significantly outperform the standard oblivious sampling method, which is
widely used in the recent literature. We show that the relative error of the
randomized approximations can be tightly characterized in terms of the spectrum
of the data matrix and Gaussian width of the dual tangent cone at optimum. We
develop lower bounds for both optimization and statistical error measures based
on concentration of measure and Fano's inequality. We then present the
consequences of our theory with data matrices of varying spectral decay
profiles. Experimental results show that the proposed approach enables
significant speed ups in a wide variety of machine learning and optimization
problems including logistic regression, kernel classification with random
convolution layers and shallow neural networks with rectified linear units.
- Abstract（参考訳）: 本稿では,変数のランダム部分空間への制約に基づく高次元凸問題に対する新しいランダム化最適化法を提案する。
我々は、可観測部分空間とデータ適応部分空間を考察し、凸双対性とフェンシェル共役を通して近似特性を研究する。
2階統計が入力データを反映した相関ランダム行列をサンプリングすることにより、適切な適応部分空間を生成することができる。
本稿では,近年の文献で広く用いられている標準不完全サンプリング法を,適応戦略が大幅に上回ることを示す。
ランダム化近似の相対誤差は、データ行列のスペクトルと2つの接円錐のガウス幅を最適に表現することで、厳密に特徴付けられることを示す。
測定値の集中とファノの不等式に基づく最適化と統計誤差尺度の双方に対する下限を開発する。
次に、スペクトル減衰プロファイルの異なるデータ行列を用いて、我々の理論の結果を示す。
実験結果から,提案手法は,ロジスティック回帰,ランダム畳み込み層を用いたカーネル分類,修正線形ユニットによる浅層ニューラルネットワークなど,幅広い機械学習および最適化問題において,大幅な高速化を実現することが示唆された。
関連論文リスト
- A Bayesian Approach Toward Robust Multidimensional Ellipsoid-Specific Fitting [0.0]
本研究は, ノイズおよび外周波の汚染における散乱データに多次元楕円体を適合させる, 新規で効果的な方法を提案する。
楕円体領域内でのプリミティブパラメータの探索を制約するために、均一な事前分布を組み込む。
本研究では, 顕微鏡細胞計数, 3次元再構成, 幾何学的形状近似, 磁力計の校正タスクなど, 幅広い応用に応用する。
論文 参考訳（メタデータ） (2024-07-27T14:31:51Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Multistage Stochastic Optimization via Kernels [3.7565501074323224]
我々は,多段階最適化問題に対する非パラメトリック,データ駆動,トラクタブルアプローチを開発した。
本稿では,提案手法が最適に近い平均性能で決定ルールを生成することを示す。
論文 参考訳（メタデータ） (2023-03-11T23:19:32Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳（メタデータ） (2022-10-23T23:23:23Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳（メタデータ） (2022-03-18T05:49:13Z) - A similarity-based Bayesian mixture-of-experts model [0.5156484100374058]
多変量回帰問題に対する新しい非パラメトリック混合実験モデルを提案する。
条件付きモデルを用いて、サンプル外入力の予測は、観測された各データポイントと類似性に基づいて行われる。
混合物のパラメータと距離測定値に基づいて後部推論を行う。
論文 参考訳（メタデータ） (2020-12-03T18:08:30Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
論文 参考訳（メタデータ） (2020-07-13T17:39:35Z) - To Each Optimizer a Norm, To Each Norm its Generalization [31.682969645989512]
過度なパラメータ化と過度なパラメータ化の条件下でのトレーニングデータを補間する線形モデルに対する最適化手法の暗黙的な正規化について検討する。
我々は、標準最大値 l2-margin への収束解析は任意であり、データによって誘導されるノルムの最小化がより良い一般化をもたらすことを示す。
論文 参考訳（メタデータ） (2020-06-11T21:07:38Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
[1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。
我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。
また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
論文 参考訳（メタデータ） (2020-04-17T12:47:04Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。
我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。
また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
論文 参考訳（メタデータ） (2020-02-16T09:01:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。