論文の概要: The Multi-Query Paradox in Zeroth-Order Optimization

• arxiv url: http://arxiv.org/abs/2509.15552v1
• Date: Fri, 19 Sep 2025 03:10:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 18:18:10.976245
• Title: The Multi-Query Paradox in Zeroth-Order Optimization
• Title（参考訳）: ゼロ階最適化におけるマルチクエリパラドックス
• Authors: Wei Lin, Qingyu Song, Hong Xu,
• Abstract要約: Zeroth-order Alignment (ZO)は、明示的な勾配が利用できない問題に対して強力なフレームワークを提供する。
• 参考スコア（独自算出の注目度）: 6.777975824808536
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Zeroth-order (ZO) optimization provides a powerful framework for problems where explicit gradients are unavailable and have to be approximated using only queries to function value. The prevalent single-query approach is simple, but suffers from high estimation variance, motivating a multi-query paradigm to improves estimation accuracy. This, however, creates a critical trade-off: under a fixed budget of queries (i.e. cost), queries per iteration and the total number of optimization iterations are inversely proportional to one another. How to best allocate this budget is a fundamental, under-explored question. This work systematically resolves this query allocation problem. We analyze two aggregation methods: the de facto simple averaging (ZO-Avg), and a new Projection Alignment method (ZO-Align) we derive from local surrogate minimization. By deriving convergence rates for both methods that make the dependence on the number of queries explicit across strongly convex, convex, non-convex, and stochastic settings, we uncover a stark dichotomy: For ZO-Avg, we prove that using more than one query per iteration is always query-inefficient, rendering the single-query approach optimal. On the contrary, ZO-Align generally performs better with more queries per iteration, resulting in a full-subspace estimation as the optimal approach. Thus, our work clarifies that the multi-query problem boils down to a choice not about an intermediate query size, but between two classic algorithms, a choice dictated entirely by the aggregation method used. These theoretical findings are also consistently validated by extensive experiments.
• Abstract（参考訳）: Zeroth-order (ZO) 最適化は、明示的な勾配が利用できない問題に対して強力なフレームワークを提供する。 一般的な単一クエリのアプローチは単純であるが、高い推定ばらつきに悩まされており、推定精度を向上させるためにマルチクエリのパラダイムを動機付けている。 しかし、これは重要なトレードオフを生み出す: 固定されたクエリの予算(すなわちコスト)の下では、イテレーション毎のクエリと最適化の合計回数は互いに逆比例する。 この予算をどう割り当てるかは、根本的な、未調査の質問である。 この作業は、このクエリ割り当て問題を体系的に解決する。 本稿では, 局所代理最小化によるデファクト単純平均化法 (ZO-Avg) と新しい投影アライメント法 (ZO-Align) の2つのアグリゲーション法を解析した。 強い凸、凸、非凸、確率的な設定で明示的なクエリ数に依存する2つのメソッドの収束率を導出することにより、スターク二分法が明らかになる。 それとは対照的に、ZO-Alignはイテレーション毎にクエリ数を増やすことでパフォーマンスが向上し、結果として完全なサブスペース推定が最適なアプローチとなる。 そこで本研究は, 中間クエリサイズではなく, 2つの古典的アルゴリズムにおいて, 使用するアグリゲーション法によって決定される選択に, 複数クエリの問題が起因していることを明らかにする。 これらの理論的な発見は、広範な実験によって一貫して検証される。

関連論文リスト

• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。 インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。 この問題を解決するための3つのアプローチを開発する。
  論文  参考訳（メタデータ） (2024-10-31T13:48:46Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• l1-norm regularized l1-norm best-fit lines [3.0963566281269594]
  簡単な比率とソート手法を用いた新しいフィッティング法を提案する。 提案アルゴリズムは、O$(n2 m log n)$の最悪の時間複雑性を示し、ある場合にはスパース部分空間に対する大域的最適性を達成する。
  論文  参考訳（メタデータ） (2024-02-26T16:30:58Z)
• RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
  そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。 我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。 いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
  論文  参考訳（メタデータ） (2023-11-10T13:56:15Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• A Retrospective Approximation Approach for Smooth Stochastic Optimization [0.2867517731896504]
  グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
  論文  参考訳（メタデータ） (2021-03-07T16:29:36Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)

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

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