論文の概要: Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

• arxiv url: http://arxiv.org/abs/2609.38561v2
• Date: Thu, 08 Oct 2026 14:17:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:53.318092
• Title: Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
• Title（参考訳）: 楕円型サンプリングによるパラメータフリーゼロ階最適化
• Abstract要約: POEMESは、勾配情報が利用できない、あるいは計算に費用がかかるブラックボックス問題に対するパラメータフリーゼロ次アルゴリズムである。 等方的ランダムな方向に依存する従来のゼロ階のアプローチとは対照的に、POEMESは固定された構造対称正の半定値プレコンディショナー$hat$で導かれる異方的サンプリングを行う。 我々は、POEM-ESが低ランク構造仮定の下で次元還元収束率を達成できることを証明し、$tildemathcalOleft( fracleft( r2 (hat) +)しか必要としない。
• 参考スコア（独自算出の注目度）: 85.30100781543337
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-ES, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating subspace preconditioning with ellipsoidal randomized sampling. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-ES performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner $\hatΣ$ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where $λ_{\max}(\hatΣ) = 1$, we introduce the use of the empirical effective dimension $d^* = \operatorname{tr}(\hatΣ)$, which reflects the intrinsic dimensionality of the problem and guides both the sampling and randomized smoothing parameter schedules. In practice, such a preconditioner can be effectively obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge. We prove that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only $\tilde{\mathcal{O}}\left( \frac{\left( r^2 κ(\hatΣ) + d^* \right) L^2 D_{\mathcal{X}}^2}{\varepsilon^2} \right)$ stochastic zeroth-order oracle queries. The method remains fully parameter-free and demonstrates significant improvements over the original POEM in problems with low-rank structure where $d^* \ll d$. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.
• Abstract（参考訳）: 勾配情報が利用できない、あるいは計算に費用がかかるブラックボックス問題の解決には、ゼロ階最適化法が不可欠である。 本稿では,小空間プレコンディショニングと楕円型ランダム化サンプリングを統合することで,最新のPOEM法を拡張したパラメータフリー確率ゼロ階法であるPOEM-ESを提案する。 等方的ランダムな方向に依存する従来のゼロ階のアプローチとは対照的に、POEM-ESは、下層の低次元幾何学を符号化する固定構造対称半定値(SPSD)プレコンディショナー$\hatΣ$で導かれる異方的サンプリングを行う。 標準的な構造スペクトル正規化では、$λ_{\max}(\hatΣ) = 1$ であり、経験的有効次元 $d^* = \operatorname{tr}(\hatΣ)$ の使用を導入する。 実際に、そのようなプレコンディショナーは、パイロットサンプリング、過去の軌跡、ドメイン固有の専門家の知識によって効果的に得ることができる。 POEM-ES が低ランク構造仮定の下で次元還元収束速度を達成できることを証明し、$\tilde{\mathcal{O}}\left( \frac{\left(r^2 κ(\hatΣ) + d^* \right) L^2 D_{\mathcal{X}}^2}{\varepsilon^2} \right)$ 確率零次オラクルクエリを要求される。 この手法は完全にパラメータフリーであり、$d^* \ll d$という低ランク構造を持つ問題において、元のPOEMよりも大幅に改善されている。 LibSVMデータセットを用いたヒンジロスバイナリ分類タスクの数値実験により,提案手法の実用的優位性が確認された。

関連論文リスト

• Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning [1.0282274843007797]
  外部補間(QMME)フレームワークを導入し,その逐次収束特性を確立する。 実効性を示すために,大規模カーネル正規化学習問題にQMMEを適用した。
  論文  参考訳（メタデータ） (2025-07-06T05:17:28Z)
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• 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)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold [16.099883128428054]
  直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。 ODCGMはベクトル空間へのプロジェクションのみを必要とする。 以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
  論文  参考訳（メタデータ） (2023-03-16T12:25:53Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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