論文の概要: Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
- arxiv url: http://arxiv.org/abs/2610.13871v1
- Date: Fri, 09 Oct 2026 17:20:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.698438
- Title: Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
- Title（参考訳）: ゼロ次残差追跡による部分インフォームド確率最適化
- Abstract要約: 部分的インフォームド最適化(PISO)は、利用可能なコンポーネントと残余イテレーションの実行推定を組み合わせたものである。
滑らかな非目的に対して、残差の初期等級に依存する収束保証を確立する。
PISOは、リプシッツと(O(d2varepsilon-5)の下で、さらにリプシッツとヘッセンの仮定の下で、主要な関数探索複合体(Od2varepsilon-6)を得る。
- 参考スコア（独自算出の注目度）: 38.97446792838266
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of \(O(d^{2}\varepsilon^{-6})\) under Lipschitz gradients and \(O(d^{2}\varepsilon^{-5})\) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.
- Abstract（参考訳）: 多くの最適化問題は勾配の一部のみへの直接アクセスを提供し、残りのコンポーネントは関数評価から推論する必要がある。
この構造は、性能予測、性能強化学習、ブラックボックス低レベルによる双レベル最適化に現れる。
本稿では、利用可能な勾配成分と残差のランニング推定を組み合わせた部分的インフォームド確率最適化(PISO)を導入する。
この推定について各ゼロ階観測を遠ざけることにより、PISOは残差の大きさよりも追尾誤差に依存するランダムな確率による分散を導出する。
これにより、明示的な収縮機構と原理化された運動量解釈を備えたランダム化されたスケッチ反復が得られる。
滑らかな非凸目的に対して、不利用可能な勾配成分に一様に束縛されることなく、残差の変動と初期等級に依存する収束保証を確立する。
独立にサンプリングされた関数評価とガウスまたは球面プローブにより、PISO はリプシッツ勾配の下で \(O(d^{2}\varepsilon^{-6})\) と、追加のリプシッツ-ヘッセン仮定の下で \(O(d^{2}\varepsilon^{-5})\) の主関数評価複雑性を得る。
これらのレートは1回のプローブ方向、2回の関数サンプル、1回の更新で既知のサンプルを必要とする。
この分析は、より少ないデプロイメントのために、どのようにバッチ処理が観察を交換するかを定量化する。
5つの設定にまたがって、PISOの変種はテストベースラインを改善し、3つに匹敵するオラクルアクセスを達成し、双レベルルーティングにおいて同等のソリューションに到達し、実行時強化学習において応答モデルデリバティブのないメソッドの中で最善を尽くす。
関連論文リスト
- Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization [59.75358446504504]
本稿では,複数のスムーズな非パラメータからなるネスト構成を目的とするマルチレベル最適化について検討する。
我々は、運動量勾配推定器を構築するために、ミニバッチを持つ運動量ベース推定器を用いる。
また,関数値のクリッピングに一階近似を組み込んだバッチフリー手法を開発した。
論文 参考訳（メタデータ） (2026-10-01T12:32:40Z) - A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
本研究は,期待されるコストの和を最小化するための近位次法を導入する。
クルディカ・ロジャシエヴィチ(KL)特性を用いて、全軌道の1つの定常点への収束を保証する。
論文 参考訳（メタデータ） (2026-08-05T23:07:27Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
既存の手法の潜在的な制限は、ステップサイズが提案されない限り、ほとんどの摂動推定器に固有のバイアスである。
本稿では, 良好な構成を維持しつつ, バイアスを排除した非バイアス勾配スケーリング推定器のファミリーを提案する。
論文 参考訳（メタデータ） (2025-10-22T18:25:43Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - Sparse Representations of Positive Functions via First and Second-Order
Pseudo-Mirror Descent [15.340540198612823]
推定器の範囲が非負である必要がある場合、予測されるリスク問題を考察する。
Emphpseudo-gradientsを用いた近似ミラーの1階および2階の変種を開発した。
実験は、実際に不均一なプロセス強度推定に好適な性能を示す。
論文 参考訳（メタデータ） (2020-11-13T21:54:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。