論文の概要: A Parameter-Free Zeroth-Order Method with Covariance Matrix Adaptation and Effective Dimension

• arxiv url: http://arxiv.org/abs/2609.38561v1
• Date: Tue, 29 Sep 2026 21:22:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:26.754447
• Title: A Parameter-Free Zeroth-Order Method with Covariance Matrix Adaptation and Effective Dimension
• Title（参考訳）: 共分散行列適応と有効次元を用いたパラメータフリーゼロ階法
• Abstract要約: POEMCMAは複雑なブラックボックス問題に対する新しいパラメータフリーゼロ次アルゴリズムである。 我々は, POEMCMA がほぼ最適収束速度を達成し, L2 D_mathcalX2varepsilon2right)$ 0 次オラクルクエリを必要とせず, 約$tildemathcalOleft(fracd* (hat) L2 D_mathcalX2varepsilon2right) のみを必要とすることを示した。
• 参考スコア（独自算出の注目度）: 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-CMA, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating covariance matrix alignment and the notion of effective dimension. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-CMA performs anisotropic sampling by constructing a covariance matrix from gradient estimates. This enables the algorithm to focus sampling efforts on the most informative directions. We introduce the use of the empirical effective dimension $d^* = \frac{\operatorname{tr}(\hatΣ)}{λ_{\max}(\hatΣ)}$, which reflects the intrinsic dimensionality of the problem and replaces the ambient dimension in both sampling and complexity analysis. We prove that POEM-CMA achieves a near-optimal convergence rate, requiring only $\tilde{\mathcal{O}}\left(\frac{d^* κ(\hatΣ) 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-CMAを提案する。 等方的ランダム方向に依存する従来のゼロ階法とは異なり、POEM-CMAは勾配推定から共分散行列を構成することにより異方的サンプリングを行う。 これにより、アルゴリズムは最も情報に富む方向にサンプリング作業に集中することができる。 実験的な有効次元である $d^* = \frac{\operatorname{tr}(\hatΣ)}{λ_{\max}(\hatΣ)}$ の使用を導入する。 POEM-CMAがほぼ最適収束速度を達成できることを証明し、$\tilde{\mathcal{O}}\left(\frac{d^* κ(\hatΣ) L^2 D_{\mathcal{X}}^2}{\varepsilon^2}\right)$ stochastic zeroth-order oracle query。 この手法は完全にパラメータフリーであり、$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)

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

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