論文の概要: Finding Stationary Points by Comparisons

• arxiv url: http://arxiv.org/abs/2606.27082v1
• Date: Thu, 25 Jun 2026 14:20:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-26 18:46:32.319573
• Title: Finding Stationary Points by Comparisons
• Title（参考訳）: 比較による定常点の探索
• Abstract要約: 目的物にアクセスする際には,非広範関数の定常点を見つけるという課題が解決される。 量子比較オラクルモデルを用いて、重ね合わせでクエリを作成できる。
• 参考スコア（独自算出の注目度）: 20.896343737785745
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $ε$-stationary point using $\widetilde O(n^2/ε^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $δ$ using $\widetilde O(n^2\log(1/δ))$ queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $ε$-stationary point, which takes $\widetilde O(n/ε^{1.5})$ queries.
• Abstract（参考訳）: 目的物へのアクセスが2つの点を与えられた場合、より大きな関数値を持つ出力である比較オラクルを通してのみ提供される場合、非凸関数の定常点を求める問題について検討する。 2つの微分可能な$f\colon\mathbb R^n\to\mathbb R$とLipschitz勾配とHessianに対して、$\widetilde O(n^2/ε^{1.5})$クエリを使って$ε$定常点を訪問するアルゴリズムを開発する。 我々のアプローチでは、正規化されたヘッセンを$δ$と推定するサブルーチンを使い、$\widetilde O(n^2\log(1/δ))$クエリを使って精度を$δ$とする。 さらに、この問題を重ね合わせでクエリを作成できる量子比較オラクルモデルを用いて研究し、$ε$-定常点を求める最初の量子アルゴリズムを開発し、$\widetilde O(n/ε^{1.5})$クエリーを求める。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
  非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。 f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
  論文  参考訳（メタデータ） (2026-05-13T17:34:24Z)
• Computational Hardness of Private Coreset [84.99100741615423]
  与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。 no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。 $k$-means in the
  論文  参考訳（メタデータ） (2026-02-19T15:58:49Z)
• Fixed Point Computation: Beating Brute Force with Smoothed Analysis [28.978340288565118]
  本稿では,$varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $ell$ unit ball to itself。 アルゴリズムのランタイムは、スムーズな分析フレームワークの下で、$eO(n)/varepsilon$でバウンドされる。
  論文  参考訳（メタデータ） (2025-01-18T21:32:26Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain [11.562923882714093]
  Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。 我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
  論文  参考訳（メタデータ） (2021-10-08T07:46:18Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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