論文の概要: Robust estimation via generalized quasi-gradients

• arxiv url: http://arxiv.org/abs/2005.14073v1
• Date: Thu, 28 May 2020 15:14:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-27 05:00:47.560650
• Title: Robust estimation via generalized quasi-gradients
• Title（参考訳）: 一般化準次数によるロバスト推定
• Authors: Banghua Zhu, Jiantao Jiao and Jacob Steinhardt
• Abstract要約: 最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。 我々は「一般化された準次数」の存在を識別する 一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
• 参考スコア（独自算出の注目度）: 28.292300073453877
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore why many recently proposed robust estimation problems are efficiently solvable, even though the underlying optimization problems are non-convex. We study the loss landscape of these robust estimation problems, and identify the existence of "generalized quasi-gradients". Whenever these quasi-gradients exist, a large family of low-regret algorithms are guaranteed to approximate the global minimum; this includes the commonly-used filtering algorithm. For robust mean estimation of distributions under bounded covariance, we show that any first-order stationary point of the associated optimization problem is an {approximate global minimum} if and only if the corruption level $\epsilon < 1/3$. Consequently, any optimization algorithm that aproaches a stationary point yields an efficient robust estimator with breakdown point $1/3$. With careful initialization and step size, we improve this to $1/2$, which is optimal. For other tasks, including linear regression and joint mean and covariance estimation, the loss landscape is more rugged: there are stationary points arbitrarily far from the global minimum. Nevertheless, we show that generalized quasi-gradients exist and construct efficient algorithms. These algorithms are simpler than previous ones in the literature, and for linear regression we improve the estimation error from $O(\sqrt{\epsilon})$ to the optimal rate of $O(\epsilon)$ for small $\epsilon$ assuming certified hypercontractivity. For mean estimation with near-identity covariance, we show that a simple gradient descent algorithm achieves breakdown point $1/3$ and iteration complexity $\tilde{O}(d/\epsilon^2)$.
• Abstract（参考訳）: 最近提案された多くのロバストな推定問題が、基礎となる最適化問題は凸ではないにもかかわらず、効率的に解ける理由を考察する。 本研究では、これらのロバストな推定問題の損失状況を調査し、「一般化された準次数」の存在を同定する。 これらの準勾配が存在する場合、大域的な最小値に近似することが保証され、一般に使用されるフィルタリングアルゴリズムを含む。 有界共分散の下での分布のロバストな平均推定について、関連する最適化問題の1次定常点が {approximate global minimum} であることは、汚職レベル $\epsilon < 1/3$ であることと同値である。 その結果、定常点を推定する最適化アルゴリズムは、破壊点$1/3$を持つ効率的なロバスト推定器が得られる。 注意深い初期化とステップサイズによって、これを1/2$に改善します。 線形回帰、結合平均および共分散推定を含む他のタスクでは、損失のランドスケープはより頑丈である。 それでも、一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。 これらのアルゴリズムは、文献の以前のアルゴリズムよりも単純であり、線形回帰では、推定誤差を$o(\sqrt{\epsilon})$から$o(\epsilon)$の最適レートに改善する。 近似共分散による平均推定では、単純な勾配降下アルゴリズムが分解点$1/3$ と反復複雑性 $\tilde{o}(d/\epsilon^2)$ を達成することを示す。

関連論文リスト

• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Noise misleads rotation invariant algorithms on sparse targets [0.0]
  回転不変アルゴリズムのクラスは疎線形問題を学習するのに最適であることを示す。 回転対称問題に対してベイズ最適アルゴリズムの下位境界を用いてこれを証明する。 次に、単純な非回転不変アルゴリズムに対して、同じ問題に対してより低い上限を証明した。
  論文  参考訳（メタデータ） (2024-03-05T06:25:19Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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