論文の概要: Comparisons Are All You Need for Optimizing Smooth Functions

• arxiv url: http://arxiv.org/abs/2405.11454v1
• Date: Sun, 19 May 2024 05:39:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-21 17:37:55.781108
• Title: Comparisons Are All You Need for Optimizing Smooth Functions
• Title（参考訳）: スムース関数の最適化に必要な比較
• Authors: Chenyi Zhang, Tongyang Li,
• Abstract要約: 微分自由法を用いてスムーズな関数を最適化するためには,エンファラリソンがすべて必要であることを示す。 さらに,サドル点をエスケープし,エプシロン$秒の定常点に到達するためのアルゴリズムも提供する。
• 参考スコア（独自算出の注目度）: 12.097567715078252
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When optimizing machine learning models, there are various scenarios where gradient computations are challenging or even infeasible. Furthermore, in reinforcement learning (RL), preference-based RL that only compares between options has wide applications, including reinforcement learning with human feedback in large language models. In this paper, we systematically study optimization of a smooth function $f\colon\mathbb{R}^n\to\mathbb{R}$ only assuming an oracle that compares function values at two points and tells which is larger. When $f$ is convex, we give two algorithms using $\tilde{O}(n/\epsilon)$ and $\tilde{O}(n^{2})$ comparison queries to find an $\epsilon$-optimal solution, respectively. When $f$ is nonconvex, our algorithm uses $\tilde{O}(n/\epsilon^2)$ comparison queries to find an $\epsilon$-approximate stationary point. All these results match the best-known zeroth-order algorithms with function evaluation queries in $n$ dependence, thus suggest that \emph{comparisons are all you need for optimizing smooth functions using derivative-free methods}. In addition, we also give an algorithm for escaping saddle points and reaching an $\epsilon$-second order stationary point of a nonconvex $f$, using $\tilde{O}(n^{1.5}/\epsilon^{2.5})$ comparison queries.
• Abstract（参考訳）: 機械学習モデルを最適化する場合、勾配計算が困難である、あるいは不可能である、さまざまなシナリオが存在する。 さらに、強化学習(RL)においては、選択肢間の比較のみを行う嗜好に基づくRLは、大規模言語モデルにおける人間からのフィードバックによる強化学習を含む幅広い応用がある。 本稿では,滑らかな関数 $f\colon\mathbb{R}^n\to\mathbb{R}$ の最適化について,二つの点における関数値を比較してより大きい値を示すオラクルを仮定して,体系的に研究する。 f$が凸であるとき、それぞれ$\tilde{O}(n/\epsilon)$と$\tilde{O}(n^{2})$比較クエリを使って、$\epsilon$-optimalソリューションを見つける。 f$が非凸である場合、我々のアルゴリズムは$\tilde{O}(n/\epsilon^2)$の比較クエリを使って$\epsilon$-approximateの定常点を求める。 これらの結果は、よく知られたゼロ階述語アルゴリズムと$n$依存の関数評価クエリに一致し、従って \emph{comparisons は微分自由な手法で滑らかな関数を最適化するのに必要なすべてである。 さらに、サドルポイントをエスケープし、$\epsilon$-secondの非凸$f$の定常点に到達するためのアルゴリズムを、$\tilde{O}(n^{1.5}/\epsilon^{2.5})$比較クエリを使って提供する。

関連論文リスト

• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
  上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。 我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
  論文  参考訳（メタデータ） (2022-08-07T20:53:42Z)
• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
  オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。 非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
  論文  参考訳（メタデータ） (2021-05-04T21:49:15Z)
• 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)
• 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)
• 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)

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

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