論文の概要: Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions

• arxiv url: http://arxiv.org/abs/2512.16200v1
• Date: Thu, 18 Dec 2025 05:46:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-19 18:10:31.930261
• Title: Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions
• Title（参考訳）: スムース関数に基づくランクベースゼロ階アルゴリズムの明示的および非漸近的クエリ複雑性
• Authors: Haishan Ye,
• Abstract要約: ランクベースのゼロ階凸最適化(関数の順序のみに依存する)は、ノイズや変換に対して強い堅牢性を提供する。 広く使われているにもかかわらず、ランクベースのZO法の理論的理解は依然として限られている。
• 参考スコア（独自算出の注目度）: 17.238068736229014
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Rank-based zeroth-order (ZO) optimization -- which relies only on the ordering of function evaluations -- offers strong robustness to noise and monotone transformations, and underlies many successful algorithms such as CMA-ES, natural evolution strategies, and rank-based genetic algorithms. Despite its widespread use, the theoretical understanding of rank-based ZO methods remains limited: existing analyses provide only asymptotic insights and do not yield explicit convergence rates for algorithms selecting the top-$k$ directions. This work closes this gap by analyzing a simple rank-based ZO algorithm and establishing the first \emph{explicit}, and \emph{non-asymptotic} query complexities. For a $d$-dimension problem, if the function is $L$-smooth and $μ$-strongly convex, the algorithm achieves $\widetilde{\mathcal O}\!\left(\frac{dL}μ\log\!\frac{dL}{μδ}\log\!\frac{1}{\varepsilon}\right)$ to find an $\varepsilon$-suboptimal solution, and for smooth nonconvex objectives it reaches $\mathcal O\!\left(\frac{dL}{\varepsilon}\log\!\frac{1}{\varepsilon}\right)$. Notation $\cO(\cdot)$ hides constant terms and $\widetilde{\mathcal O}(\cdot)$ hides extra $\log\log\frac{1}{\varepsilon}$ term. These query complexities hold with a probability at least $1-δ$ with $0<δ<1$. The analysis in this paper is novel and avoids classical drift and information-geometric techniques. Our analysis offers new insight into why rank-based heuristics lead to efficient ZO optimization.
• Abstract（参考訳）: ランクベースのゼロ階数最適化(ZO)は、関数評価の順序のみに依存するもので、ノイズやモノトーン変換に対して強い堅牢性を提供し、CMA-ES、自然進化戦略、ランクベースの遺伝的アルゴリズムなどの多くの成功アルゴリズムの基盤となっている。 既存の分析は漸近的な洞察しか提供せず、トップ$k$方向を選択するアルゴリズムに対して明確な収束率を得られない。 この研究は、単純な階数ベースのZOアルゴリズムを分析し、最初の \emph{explicit} と \emph{non-asymptotic} のクエリ複雑さを確立することで、このギャップを埋める。 d$次元問題の場合、関数が$L$-smoothと$μ$-strongly convexであれば、アルゴリズムは$\widetilde{\mathcal O}\! \left(\frac{dL}μ\log\! \frac{dL}{μδ}\log\! \frac{1}{\varepsilon}\right)$ to find a $\varepsilon$-suboptimal solution, and for smooth nonconvex objectives to reach $\mathcal O\! \left(\frac{dL}{\varepsilon}\log\! \frac{1}{\varepsilon}\right)$ Notation $\cO(\cdot)$ hides constant term and $\widetilde{\mathcal O}(\cdot)$ hides extra $\log\log\frac{1}{\varepsilon}$ term。 これらの問合せ複雑性は、少なくとも1-δ$と0<δ<1$の確率で成り立つ。 本稿では,古典的ドリフトと情報幾何学的手法の回避をめざして,新しい解析手法を提案する。 我々の分析は、ランクに基づくヒューリスティックスがなぜ効率的なZO最適化につながるのか、新たな知見を提供する。

関連論文リスト

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。 この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
  論文  参考訳（メタデータ） (2024-06-26T18:19:10Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Local Search Algorithms for Rank-Constrained Convex Optimization [7.736462653684946]
  階数制約付き凸最適化のための欲望と局所探索アルゴリズムを提案する。 我々は、$R$のランク制限条件番号が$kappa$であれば、$A$のランク$O(r*cdot minkappa log fracR(mathbf0)-R(A*)epsilon、kappa2)$と$R(A)leq R(A*)+epsilon$のソリューションが回復できることを示しています。
  論文  参考訳（メタデータ） (2021-01-15T18:52:02Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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