論文の概要: Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization

• arxiv url: http://arxiv.org/abs/2405.16805v1
• Date: Mon, 27 May 2024 03:52:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-28 19:06:16.193920
• Title: Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization
• Title（参考訳）: 勾配圧縮センシング:高次元ゼロ階最適化のためのクエリ効率の良い勾配推定器
• Authors: Ruizhong Qiu, Hanghang Tong,
• Abstract要約: 我々は,1ステップあたり$Obig(slogfrac dsbig)$クエリのみを使用する勾配のクエリ効率と精度の高い推定器を提案する。 Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。
• 参考スコア（独自算出の注目度）: 48.84672493756553
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study nonconvex zeroth-order optimization (ZOO) in a high-dimensional space $\mathbb R^d$ for functions with approximately $s$-sparse gradients. To reduce the dependence on the dimensionality $d$ in the query complexity, high-dimensional ZOO methods seek to leverage gradient sparsity to design gradient estimators. The previous best method needs $O\big(s\log\frac ds\big)$ queries per step to achieve $O\big(\frac1T\big)$ rate of convergence w.r.t. the number T of steps. In this paper, we propose *Gradient Compressed Sensing* (GraCe), a query-efficient and accurate estimator for sparse gradients that uses only $O\big(s\log\log\frac ds\big)$ queries per step and still achieves $O\big(\frac1T\big)$ rate of convergence. To our best knowledge, we are the first to achieve a *double-logarithmic* dependence on $d$ in the query complexity under weaker assumptions. Our proposed GraCe generalizes the Indyk--Price--Woodruff (IPW) algorithm in compressed sensing from linear measurements to nonlinear functions. Furthermore, since the IPW algorithm is purely theoretical due to its impractically large constant, we improve the IPW algorithm via our *dependent random partition* technique together with our corresponding novel analysis and successfully reduce the constant by a factor of nearly 4300. Our GraCe is not only theoretically query-efficient but also achieves strong empirical performance. We benchmark our GraCe against 12 existing ZOO methods with 10000-dimensional functions and demonstrate that GraCe significantly outperforms existing methods.
• Abstract（参考訳）: 約$s$スパース勾配を持つ関数に対する高次元空間 $\mathbb R^d$ における非凸ゼロ階最適化 (ZOO) について検討する。 問合せ複雑性における次元$d$への依存を低減するため、高次元ZOO法は勾配間隔を利用して勾配推定器を設計する。 前の最良の方法は、ステップ数 T に対して$O\big(\frac1T\big)$収束率を達成するために、ステップ当たり$O\big(s\log\frac ds\big)$クエリが必要である。 本稿では,⁰,⁰,⁰,</sup>,⁰,</sup>,⁰,</sup>,⁰,⁰,</sup>,⁰,⁰,⁰,⁰,⁰,⁰,⁰,⁰,⁰,³,⁰,^,³,³,,^,,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,^,,<sup>,</sup,</sup,</sup,<sup>,<I,<sup,<sup,<I,<I, 我々の知る限りでは、より弱い仮定の下でクエリ複雑性の$d$に対する*double-logarithmic*依存を実現するのは、私たちは初めてです。 Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。 さらに,IPWアルゴリズムは不規則に大きい定数のため純粋に理論的であるため,我々の*依存ランダムパーティション*技術によるIPWアルゴリズムの改良とそれに対応する新しい解析を行い,定数を4300倍近く減少させることに成功した。 GraCeは理論的にクエリ効率が高いだけでなく、経験的性能も高い。 我々はGraCeを10000次元関数を持つ既存の12のZOOメソッドに対してベンチマークし、GraCeが既存のメソッドよりも大幅に優れていることを示す。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Quantum state tomography via non-convex Riemannian gradient descent [13.100184125419691]
  本研究では,kappa$のスケール依存性を改善する量子状態トモグラフィースキームを導出する。 この改良は、非多様体勾配(RGD)アルゴリズムの適用によるものである。 超高速収束とほぼ最適誤差境界の理論的結果は数値的な結果と相関する。
  論文  参考訳（メタデータ） (2022-10-10T14:19:23Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• A One-bit, Comparison-Based Gradient Estimator [29.600975900977343]
  正規化勾配の頑健で信頼性の高い推定器を構築するために、1ビット圧縮センシングのツールを利用する方法を示す。 勾配降下法において,この推定器を用いたSCOBOというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-06T05:01:38Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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