論文の概要: A One-bit, Comparison-Based Gradient Estimator

• arxiv url: http://arxiv.org/abs/2010.02479v3
• Date: Sat, 23 Apr 2022 08:35:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 06:01:37.820156
• Title: A One-bit, Comparison-Based Gradient Estimator
• Title（参考訳）: 1ビット比較型勾配推定器
• Authors: HanQin Cai, Daniel Mckenzie, Wotao Yin, Zhenliang Zhang
• Abstract要約: 正規化勾配の頑健で信頼性の高い推定器を構築するために、1ビット圧縮センシングのツールを利用する方法を示す。 勾配降下法において,この推定器を用いたSCOBOというアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 29.600975900977343
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study zeroth-order optimization for convex functions where we further assume that function evaluations are unavailable. Instead, one only has access to a $\textit{comparison oracle}$, which given two points $x$ and $y$ returns a single bit of information indicating which point has larger function value, $f(x)$ or $f(y)$. By treating the gradient as an unknown signal to be recovered, we show how one can use tools from one-bit compressed sensing to construct a robust and reliable estimator of the normalized gradient. We then propose an algorithm, coined SCOBO, that uses this estimator within a gradient descent scheme. We show that when $f(x)$ has some low dimensional structure that can be exploited, SCOBO outperforms the state-of-the-art in terms of query complexity. Our theoretical claims are verified by extensive numerical experiments.
• Abstract（参考訳）: 凸関数のゼロ次最適化について検討し,関数評価は利用できないと仮定する。 代わりに、$\textit{comparison oracle}$にしかアクセスできないため、2つのポイントが与えられた$x$と$y$は、どのポイントがより大きな関数値を持つかを示す情報の1ビットを返す。 (x)$または$f (y)$。 勾配を未知の信号として処理することにより,1ビット圧縮センシングのツールを用いて,正規化勾配のロバストで信頼性の高い推定器を構築する方法を示す。 次に、勾配降下法において、この推定器を用いたSCOBOというアルゴリズムを提案する。 $fのとき、 (x)$は、利用可能な低次元構造を持ち、SCOBOはクエリの複雑さの観点から最先端の手法より優れている。 我々の理論的な主張は広範な数値実験によって検証される。

関連論文リスト

• Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization [48.84672493756553]
  我々は,1ステップあたり$Obig(slogfrac dsbig)$クエリのみを使用する勾配のクエリ効率と精度の高い推定器を提案する。 Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。
  論文  参考訳（メタデータ） (2024-05-27T03:52:53Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Gradient Descent for Low-Rank Functions [36.56489593549855]
  例えば、深層ニューラルネットワークのトレーニングのような機械学習タスクでは、損失関数は入力のわずか数方向に大きく変化する。 提案した emphLowRank Descent は $mathcalO(plog(1/epsilon))$gd と $mathcalOp/epsilon2)$p/epsilon2)$を識別して $epsilon 勾配関数を求める。
  論文  参考訳（メタデータ） (2022-06-16T15:58:05Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Escape saddle points by a simple gradient-descent based algorithm [6.7298812735467095]
  非最適化において、サドルポイントのエスケープは中心的な研究トピックである。 滑らかな関数 $fcolonmathbbRntomathbbR$ に対して、$epsilonO(log n)2/epsilon4)$ を出力する。 技術的に、我々の主な貢献は勾配のみを用いたロバストなヘッセンパワー手法の実装である。
  論文  参考訳（メタデータ） (2021-11-28T07:32:54Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
  サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。 対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。 我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
  論文  参考訳（メタデータ） (2021-03-29T23:03:24Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling [29.600975900977343]
  我々はZOROと呼ばれる新しい$textbfZ$eroth-$textbfO$rder $textbfR$egularized $textbfO$ptimization法を提案する。 基礎となる勾配がイテレートでほぼスパースである場合、ZOROは目的関数を減少させる新しいイテレートを得るために、非常に少数の客観的関数評価を必要とする。
  論文  参考訳（メタデータ） (2020-03-29T11:01:17Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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