論文の概要: Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles

• arxiv url: http://arxiv.org/abs/2408.11084v1
• Date: Tue, 20 Aug 2024 17:56:16 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-22 21:26:55.689070
• Title: Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles
• Title（参考訳）: バイアスオラクルを用いた確率最適化のためのマルチレベルモンテカルロ勾配法
• Authors: Yifan Hu, Jie Wang, Xin Chen, Niao He,
• Abstract要約: バイアスのあるオラクルにアクセスし、低いバイアスで目的を得る必要がある場合、最適化を検討する。 偏り勾配法は,非分散状態のばらつきを低減できることを示す。 また、条件最適化手法は、条件最適化とリスク最適化の文献における最もよく知られた複雑さを著しく改善することを示した。
• 参考スコア（独自算出の注目度）: 23.648702140754967
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider stochastic optimization when one only has access to biased stochastic oracles of the objective and the gradient, and obtaining stochastic gradients with low biases comes at high costs. This setting captures various optimization paradigms, such as conditional stochastic optimization, distributionally robust optimization, shortfall risk optimization, and machine learning paradigms, such as contrastive learning. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate tradeoff among bias, variance, and oracle cost. We systematically study their total sample and computational complexities for strongly convex, convex, and nonconvex objectives and demonstrate their superiority over the widely used biased stochastic gradient method. When combined with the variance reduction techniques like SPIDER, these MLMC gradient methods can further reduce the complexity in the nonconvex regime. Our results imply that a series of stochastic optimization problems with biased oracles, previously considered to be more challenging, is fundamentally no harder than the classical stochastic optimization with unbiased oracles. We also delineate the boundary conditions under which these problems become more difficult. Moreover, MLMC gradient methods significantly improve the best-known complexities in the literature for conditional stochastic optimization and shortfall risk optimization. Our extensive numerical experiments on distributionally robust optimization, pricing and staffing scheduling problems, and contrastive learning demonstrate the superior performance of MLMC gradient methods.
• Abstract（参考訳）: 確率的最適化は、目的と勾配の偏りのある確率的オラクルにのみアクセスでき、バイアスの低い確率的勾配を得るには、高いコストがかかる。 この設定は、条件付き確率最適化、分布的に堅牢な最適化、短命リスク最適化、コントラスト学習のような機械学習パラダイムなど、様々な最適化パラダイムを捉えている。 本稿では, 偏差, 分散, オラクルコストの微妙なトレードオフを利用したマルチレベルモンテカルロ勾配法について検討する。 本研究では, 強凸, 凸, 非凸の目的に対して, それらの全試料および計算複雑性を体系的に検討し, 広く使用されている偏りの確率勾配法に対するそれらの優位性を実証する。 SPIDERのような分散還元技術と組み合わせることで、これらのMLMC勾配法は非凸状態の複雑さをさらに減らすことができる。 以上の結果から,従来より難易度が高いと考えられていたバイアス付きオラクルによる確率的最適化問題は,非バイアス付きオラクルによる古典的確率的最適化よりも根本的には難しいことが示唆された。 また、これらの問題がより困難になる境界条件についても述べる。 さらに,MLMC勾配法は,条件付き確率最適化やショートフォールリスク最適化の文献でよく知られた複雑さを著しく改善する。 分散的ロバストな最適化,価格設定,スタッフスケジューリングの問題,および対照的な学習に関する広範な数値実験により,MLMC勾配法の性能が向上したことを示す。

関連論文リスト

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• SDEs for Minimax Optimization [11.290653315174382]
  本稿では,微分方程式(SDE)を用いてミニマックス収束の解析と比較を行う。 グラディエント・ディキセント、エクストラグラディエント、ハミルトニアン・ディキセントのSDEモデルはアルゴリズムの近似である。 この観点はまた、伊藤計算の原理に基づく統一的で単純化された分析戦略を可能にする。
  論文  参考訳（メタデータ） (2024-02-19T20:18:29Z)
• On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization [10.36447258513813]
  我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。 特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon$-stationaryポイントに含めることが示されている。 分析の結果,サンプルの複雑さは,追加条件下では$O(epsilon-4)$から$O(epsilon-3)$に改善できることがわかった。
  論文  参考訳（メタデータ） (2024-01-23T06:01:29Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。 メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
  論文  参考訳（メタデータ） (2023-10-27T23:24:37Z)
• Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization [55.115992622028685]
  以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。 最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
  論文  参考訳（メタデータ） (2023-10-26T19:56:52Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• Backward error analysis and the qualitative behaviour of stochastic optimization algorithms: Application to stochastic coordinate descent [1.534667887016089]
  一般最適化法の力学を近似した微分方程式のクラスを提案する。 座標降下の場合の修正方程式の安定性について検討する。
  論文  参考訳（メタデータ） (2023-09-05T09:39:56Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• An adaptive stochastic gradient-free approach for high-dimensional blackbox optimization [0.0]
  本研究では,高次元非平滑化問題に対する適応勾配フリー (ASGF) アプローチを提案する。 本稿では,グローバルな問題と学習タスクのベンチマークにおいて,本手法の性能について述べる。
  論文  参考訳（メタデータ） (2020-06-18T22:47:58Z)

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

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