論文の概要: Large-Scale Methods for Distributionally Robust Optimization

• arxiv url: http://arxiv.org/abs/2010.05893v2
• Date: Fri, 11 Dec 2020 03:05:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-08 06:22:26.565127
• Title: Large-Scale Methods for Distributionally Robust Optimization
• Title（参考訳）: 分散ロバスト最適化のための大規模手法
• Authors: Daniel Levy, Yair Carmon, John C. Duchi and Aaron Sidford
• Abstract要約: 我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
• 参考スコア（独自算出の注目度）: 53.98643772533416
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and $\chi^2$ divergence uncertainty sets. We prove that our algorithms require a number of gradient evaluations independent of training set size and number of parameters, making them suitable for large-scale applications. For $\chi^2$ uncertainty sets these are the first such guarantees in the literature, and for CVaR our guarantees scale linearly in the uncertainty level rather than quadratically as in previous work. We also provide lower bounds proving the worst-case optimality of our algorithms for CVaR and a penalized version of the $\chi^2$ problem. Our primary technical contributions are novel bounds on the bias of batch robust risk estimation and the variance of a multilevel Monte Carlo gradient estimator due to [Blanchet & Glynn, 2015]. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
• Abstract（参考訳）: 本稿では,危険条件値(CVaR)と分散不確実性集合($\chi^2$)による凸損失の分布的ロバストな最適化アルゴリズムを提案する。 提案アルゴリズムは,トレーニングセットのサイズやパラメータの数によらず,多数の勾配評価を必要とすることを証明し,大規模アプリケーションに適合する。 $\chi^2$不確実集合の場合、これらは文献において最初のそのような保証であり、CVaRの場合、我々の保証は以前の研究のように二次的にではなく不確実度レベルで線形にスケールする。 また,CVaRに対するアルゴリズムの最悪の最適性を証明し,$\chi^2$問題のペナル化版も提供する。 私たちの主な技術的貢献は、バッチロバストなリスク推定のバイアスと[blanchet & glynn, 2015]によるマルチレベルモンテカルロ勾配推定器の分散に関する新しい境界です。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。

関連論文リスト

• SOREL: A Stochastic Algorithm for Spectral Risks Minimization [1.6574413179773761]
  スペクトルリスクは機械学習、特に現実世界の意思決定において幅広い応用がある。 異なるサンプルポイントの損失に異なる重みを割り当てることで、平均的なパフォーマンスと最悪のパフォーマンスの間にモデルのパフォーマンスを配置することができる。 SORELはスペクトルリスク最小化のための収束保証をもつ最初の勾配に基づくアルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-19T18:20:53Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• On Private Online Convex Optimization: Optimal Algorithms in $\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
  本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。 また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。 提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
  論文  参考訳（メタデータ） (2022-06-16T12:09:47Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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