論文の概要: Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions

• arxiv url: http://arxiv.org/abs/2412.20330v1
• Date: Sun, 29 Dec 2024 03:05:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:04:15.597792
• Title: Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions
• Title（参考訳）: 決定依存分布をもつ非凸確率問題に対するゼロ階法
• Authors: Yuya Hikima, Akiko Takeda,
• Abstract要約: 決定変数に依存する不確実性のある最適化問題を考える。 この問題では、決定依存分布が未知であるため、目的関数の勾配は明示的には得られない。 いくつかのゼロ階法が提案され、繰り返しをサンプリングして更新することでノイズの多い目標値が得られる。
• 参考スコア（独自算出の注目度）: 8.90721241624138
• License:
• Abstract: In this study, we consider an optimization problem with uncertainty dependent on decision variables, which has recently attracted attention due to its importance in machine learning and pricing applications. In this problem, the gradient of the objective function cannot be obtained explicitly because the decision-dependent distribution is unknown. Therefore, several zeroth-order methods have been proposed, which obtain noisy objective values by sampling and update the iterates. Although these existing methods have theoretical convergence for optimization problems with decision-dependent uncertainty, they require strong assumptions about the function and distribution or exhibit large variances in their gradient estimators. To overcome these issues, we propose two zeroth-order methods under mild assumptions. First, we develop a zeroth-order method with a new one-point gradient estimator including a variance reduction parameter. The proposed method updates the decision variables while adjusting the variance reduction parameter. Second, we develop a zeroth-order method with a two-point gradient estimator. There are situations where only one-point estimators can be used, but if both one-point and two-point estimators are available, it is more practical to use the two-point estimator. As theoretical results, we show the convergence of our methods to stationary points and provide the worst-case iteration and sample complexity analysis. Our simulation experiments with real data on a retail service application show that our methods output solutions with lower objective values than the conventional zeroth-order methods.
• Abstract（参考訳）: 本研究では,決定変数に依存する不確実性を有する最適化問題について考察する。 この問題では、決定依存分布が未知であるため、目的関数の勾配は明示的には得られない。 そこで,複数のゼロ階法が提案され,繰り返しのサンプリングと更新によってノイズの多い目標値が得られた。 これらの既存手法は、決定依存の不確実性を伴う最適化問題に対する理論的収束性を持つが、関数と分布に関する強い仮定を必要としたり、勾配推定器に大きなばらつきを示す。 これらの問題を克服するために、軽度の仮定の下で2つのゼロ階法を提案する。 まず、分散還元パラメータを含む新しい1点勾配推定器を用いたゼロ階法を開発する。 提案手法は分散縮小パラメータを調整しながら決定変数を更新する。 第2に、2点勾配推定器を用いたゼロ階法を開発する。 一点推定器しか使用できない状況もあるが、一点推定器と二点推定器の両方が利用可能であれば、二点推定器の方が実用的である。 理論的な結果として,本手法の定常点への収束を示し,最悪の反復とサンプル複雑性解析を提供する。 小売サービスアプリケーションにおける実データを用いたシミュレーション実験により,従来のゼロオーダー法よりも低い目的値の解を出力できることが判明した。

関連論文リスト

• Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
  パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。 これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
  論文  参考訳（メタデータ） (2024-12-05T10:38:29Z)
• A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning [24.111048817721592]
  フェデレートラーニングは分散勾配降下技術に大きく依存している。 勾配情報が得られない状況では、勾配をゼロ次情報から推定する必要がある。 勾配推定法を改善するための非等方的サンプリング法を提案する。
  論文  参考訳（メタデータ） (2024-09-24T10:36:40Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Total Uncertainty Quantification in Inverse PDE Solutions Obtained with Reduced-Order Deep Learning Surrogate Models [50.90868087591973]
  機械学習サロゲートモデルを用いて得られた逆PDE解の総不確かさを近似したベイズ近似法を提案する。 非線型拡散方程式に対する反復的アンサンブルスムーズおよび深層アンサンブル法との比較により,提案手法を検証した。
  論文  参考訳（メタデータ） (2024-08-20T19:06:02Z)
• DF2: Distribution-Free Decision-Focused Learning [53.2476224456902]
  決定中心学習(DFL)は近年,予測最適化問題に対する強力なアプローチとして出現している。 既存のエンドツーエンドDFL法は、モデル誤差、サンプル平均近似誤差、予測対象の分布に基づくパラメータ化の3つの重大なボトルネックによって妨げられている。 DF2は,これら3つのボトルネックに明示的に対処するために設計された,初となるテキストフリーな意思決定型学習手法である。
  論文  参考訳（メタデータ） (2023-08-11T00:44:46Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [21.67411847762289]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAが$O(frac1T)$収束率を持つことを示す。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
  最適化問題の解法として,新しい2段階勾配法を提案する。 最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。 我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
  論文  参考訳（メタデータ） (2021-09-29T23:15:23Z)
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
  我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。 問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。 また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
  論文  参考訳（メタデータ） (2021-09-07T17:21:09Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)

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

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