論文の概要: Closing the Gaps: Optimality of Sample Average Approximation for Data-Driven Newsvendor Problems

• arxiv url: http://arxiv.org/abs/2407.04900v1
• Date: Sat, 6 Jul 2024 00:30:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-09 22:07:12.909628
• Title: Closing the Gaps: Optimality of Sample Average Approximation for Data-Driven Newsvendor Problems
• Title（参考訳）: ギャップの閉鎖:データ駆動ニューズベンダー問題に対するサンプル平均近似の最適性
• Authors: Jiameng Lyu, Shilin Yuan, Bingkun Zhou, Yuan Zhou,
• Abstract要約: 本研究では,一般的な凸在庫コストを伴うデータ駆動型ニュースベンダ問題に対して,SAA(Sample Average Approximation)の残念な性能について検討する。 局所的強い凸性条件の下では、SAA に対する Theta(log T/alpha + 1/ (alphabeta)) の最適後悔境界が証明される。 アルファ・グロバルの強い凸条件下では、任意のデータ駆動法における最悪の後悔は、Omega(log T/alpha)によって制限される。
• 参考スコア（独自算出の注目度）: 5.948933796081856
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the regret performance of Sample Average Approximation (SAA) for data-driven newsvendor problems with general convex inventory costs. In literature, the optimality of SAA has not been fully established under both \alpha-global strong convexity and (\alpha,\beta)-local strong convexity (\alpha-strongly convex within the \beta-neighborhood of the optimal quantity) conditions. This paper closes the gaps between regret upper and lower bounds for both conditions. Under the (\alpha,\beta)-local strong convexity condition, we prove the optimal regret bound of \Theta(\log T/\alpha + 1/ (\alpha\beta)) for SAA. This upper bound result demonstrates that the regret performance of SAA is only influenced by \alpha and not by \beta in the long run, enhancing our understanding about how local properties affect the long-term regret performance of decision-making strategies. Under the \alpha-global strong convexity condition, we demonstrate that the worst-case regret of any data-driven method is lower bounded by \Omega(\log T/\alpha), which is the first lower bound result that matches the existing upper bound with respect to both parameter \alpha and time horizon T. Along the way, we propose to analyze the SAA regret via a new gradient approximation technique, as well as a new class of smooth inverted-hat-shaped hard problem instances that might be of independent interest for the lower bounds of broader data-driven problems.
• Abstract（参考訳）: 本研究では,一般的な凸在庫コストを伴うデータ駆動型ニュースベンダ問題に対して,SAA(Sample Average Approximation)の残念な性能について検討する。 文学において、SAAの最適性は、(\alpha,\beta)局所強凸性(\alpha-strongly convex)と(\alpha-global strong convexity)の両方の条件の下で完全に確立されていない。 本論文は, 両条件とも, 後悔する上界と下界のギャップを埋めるものである。 SAA に対する (\alpha,\beta)-局所強凸条件の下では、 \Theta (\log T/\alpha + 1/ (\alpha\beta)) の最適後悔境界が証明される。 この上界的な結果から,SAAの後悔性能は,長期的には「アルファ」にのみ影響され,「ベタ」には影響されないことが示され,地域特性が意思決定戦略の長期後悔性能にどのように影響するかについての理解が深まる。 ここでは,任意のデータ駆動手法の最悪の後悔が,パラメータ \alpha と Time horizon T の両方に関して既存の上界に一致する最初の下界結果である \Omega(\log T/\alpha) によって下界に収まることを示す。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Data-driven optimal stopping: A pure exploration analysis [1.0742675209112622]
  最小限の最適性は、単純な後悔に対する下界を一致させて上界結果を完成させることによって検証される。 本研究は, 具体的な探査・探査戦略について, 簡単な後悔から累積後悔への移動について検討した。
  論文  参考訳（メタデータ） (2023-12-10T13:16:01Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions [7.972544890243396]
  本稿では, 近位降下法(Prox-SubGrad) 型アプローチの統一解析について述べる。 我々は, 誤差有界条件, 対象の下位次数の成長条件, および主次次次次次次数反復の挙動を, 極めて広い目的関数のクラスに関連付けることができる。
  論文  参考訳（メタデータ） (2023-08-30T23:34:11Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。 Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
  論文  参考訳（メタデータ） (2020-02-13T02:16:57Z)

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

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