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

• arxiv url: http://arxiv.org/abs/2512.19104v1
• Date: Mon, 22 Dec 2025 07:18:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-23 18:54:32.654541
• Title: Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithm on Stochastic Smooth Functions
• Title（参考訳）: 確率的滑らか関数上のランクベースゼロ階アルゴリズムの明示的および非漸近的クエリ複雑性
• Authors: Haishan Ye,
• Abstract要約: 命令フィードバックによるゼロオーダー(ZO)最適化は、現代の機械学習システムにおける根本的な問題として現れている。 単純で計算効率の良いランクベースZOアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 17.238068736229014
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Zeroth-order (ZO) optimization with ordinal feedback has emerged as a fundamental problem in modern machine learning systems, particularly in human-in-the-loop settings such as reinforcement learning from human feedback, preference learning, and evolutionary strategies. While rank-based ZO algorithms enjoy strong empirical success and robustness properties, their theoretical understanding, especially under stochastic objectives and standard smoothness assumptions, remains limited. In this paper, we study rank-based zeroth-order optimization for stochastic functions where only ordinal feedback of the stochastic function is available. We propose a simple and computationally efficient rank-based ZO algorithm. Under standard assumptions including smoothness, strong convexity, and bounded second moments of stochastic gradients, we establish explicit non-asymptotic query complexity bounds for both convex and nonconvex objectives. Notably, our results match the best-known query complexities of value-based ZO algorithms, demonstrating that ordinal information alone is sufficient for optimal query efficiency in stochastic settings. Our analysis departs from existing drift-based and information-geometric techniques, offering new tools for the study of rank-based optimization under noise. These findings narrow the gap between theory and practice and provide a principled foundation for optimization driven by human preferences.
• Abstract（参考訳）: オーディショナルフィードバックによるゼロオーダー(ZO)最適化は、現代の機械学習システム、特に人間のフィードバックからの強化学習、優先学習、進化戦略などのループ内設定において、基本的な問題として現れている。 階数に基づくZOアルゴリズムは、強い経験的成功と堅牢性を持っているが、その理論的理解は、特に確率的目的や標準滑らか性仮定の下では限定的である。 本稿では,確率関数の順序フィードバックのみを利用できる確率関数の階数に基づくゼロ次最適化について検討する。 単純で計算効率の良いランクベースZOアルゴリズムを提案する。 滑らか性、強凸性、確率勾配の有界2次モーメントを含む標準的な仮定の下で、凸目的と非凸目的の両方に対して漸近的でないクエリ複雑性境界を確立する。 特に,本研究の結果は値に基づくZOアルゴリズムでよく知られたクエリ複雑度と一致し,正規化情報だけでは確率的条件下での最適なクエリ効率に十分であることを示す。 我々の分析は、既存のドリフトベースおよび情報幾何学的手法から離れ、ノイズ下でのランクベース最適化の研究のための新しいツールを提供する。 これらの知見は理論と実践のギャップを狭め、人間の嗜好によって駆動される最適化の原則的基礎を提供する。

関連論文リスト

• New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition [11.530542389959347]
  L-凸性(QC)、擬似成長(SmoothQG)、制限不等式(RSI)などの非次元設定における一階最適化の基本的限界を示す。
  論文  参考訳（メタデータ） (2025-02-19T19:21:00Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Beyond Single-Model Views for Deep Learning: Optimization versus Generalizability of Stochastic Optimization Algorithms [13.134564730161983]
  本稿では、勾配降下(SGD)とその変種に着目し、ディープラーニングの最適化に新しいアプローチを採用する。 我々はSGDとその変種がSAMのような平らなミニマと同等の性能を示すことを示した。 本研究は、トレーニング損失とホールドアウト精度の関係、およびSGDとノイズ対応変種の性能について、いくつかの重要な知見を明らかにした。
  論文  参考訳（メタデータ） (2024-03-01T14:55:22Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)

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

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