論文の概要: Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?

• arxiv url: http://arxiv.org/abs/2603.25657v1
• Date: Thu, 26 Mar 2026 17:12:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-27 20:52:48.393739
• Title: Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?
• Title（参考訳）: インスタンス最適確率凸最適化:サンプル平均と頑健な確率近似で改善できるか?
• Authors: Liwei Jiang, Ashwin Pananjady,
• Abstract要約: 本研究では,加法雑音と乗法雑音の両方を導入するオラクルの下で,スムーズかつ強凸な集団損失関数の制約のない最小化について検討する。 その結果, VISOR の加速変種はインスタンス最適であり, 対数的因子の最大化を達成できる可能性が示唆された。
• 参考スコア（独自算出の注目度）: 19.235225166737354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the unconstrained minimization of a smooth and strongly convex population loss function under a stochastic oracle that introduces both additive and multiplicative noise; this is a canonical and widely-studied setting that arises across operations research, signal processing, and machine learning. We begin by showing that standard approaches such as sample average approximation and robust (or averaged) stochastic approximation can lead to suboptimal -- and in some cases arbitrarily poor -- performance with realistic finite sample sizes. In contrast, we demonstrate that a carefully designed variance reduction strategy, which we term VISOR for short, can significantly outperform these approaches while using the same sample size. Our upper bounds are complemented by finite-sample, information-theoretic local minimax lower bounds, which highlight fundamental, instance-dependent factors that govern the performance of any estimator. Taken together, these results demonstrate that an accelerated variant of VISOR is instance-optimal, achieving the best possible sample complexity up to logarithmic factors while also attaining optimal oracle complexity. We apply our theory to generalized linear models and improve upon classical results. In particular, we obtain the best-known non-asymptotic, instance-dependent generalization error bounds for stochastic methods, even in linear regression.
• Abstract（参考訳）: 本研究では,加法的および乗法的ノイズを生じる確率的オラクルの下で,スムーズで強凸な集団損失関数の制約のない最小化について検討する。 まず、サンプル平均近似やロバストな(あるいは平均化された)確率近似のような標準的なアプローチが、現実的な有限標本サイズを持つ準最適(あるいは任意に劣る)パフォーマンスをもたらすことを示す。 対照的に、VISOR(略してVISOR)と呼ばれる慎重に設計された分散低減戦略は、同じサンプルサイズを用いて、これらのアプローチを著しく上回っていることを実証する。 我々の上界は有限サンプル、情報理論的局所ミニマックス下界で補われ、これはどの推定器の性能も支配する基本的、インスタンスに依存した要因を浮き彫りにする。 これらの結果は、ViSORの加速変種がインスタンス最適であることを示し、最適なオラクルの複雑さを達成しつつ、対数的要因まで可能な限りのサンプルの複雑さを達成する。 一般化線形モデルに我々の理論を適用し、古典的な結果を改善する。 特に、線形回帰においても、確率的手法に対する最もよく知られた非漸近的、インスタンス依存の一般化誤差境界を得る。

関連論文リスト

• Variance-Reduced Model Predictive Path Integral via Quadratic Model Approximation [18.217598791860684]
  本稿では,事前モデルをサンプリングプロセスに統合したハイブリッド分散再生MPPIフレームワークを提案する。 本研究では,2次近似を適用すれば,情報領域のサンプルを効果的に濃縮する閉形式モデルガイダンスの導出が可能になることを実証する。
  論文  参考訳（メタデータ） (2026-02-03T15:23:17Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  MIDX-Samplerは、逆多重インデックスアプローチに基づく新しい適応型サンプリング戦略である。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。
  論文  参考訳（メタデータ） (2025-01-15T04:09:21Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Tuning Stochastic Gradient Algorithms for Statistical Inference via Large-Sample Asymptotics [18.93569692490218]
  勾配アルゴリズムのチューニングは、一般化可能な理論ではなく、試行錯誤に基づくことが多い。 固定ステップの大きい平均化は、チューニングパラメータの選択に対して堅牢であることを示す。 我々は他の勾配モンテカルロアルゴリズムの体系的解析の基礎を築いた。
  論文  参考訳（メタデータ） (2022-07-25T17:58:09Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Sparse recovery by reduced variance stochastic approximation [5.672132510411465]
  雑音観測によるスパース信号回復問題に対する反復2次最適化ルーチンの適用について論じる。 本稿では,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法について述べる。
  論文  参考訳（メタデータ） (2020-06-11T12:31:20Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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