論文の概要: Stochastic Zeroth Order Gradient and Hessian Estimators: Variance
Reduction and Refined Bias Bounds
- arxiv url: http://arxiv.org/abs/2205.14737v1
- Date: Sun, 29 May 2022 18:53:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 17:49:28.700281
- Title: Stochastic Zeroth Order Gradient and Hessian Estimators: Variance
Reduction and Refined Bias Bounds
- Title（参考訳）: 確率零次勾配とヘシアン推定器:分散低減と補充バイアス境界
- Authors: Yasong Feng, Tianyu Wang
- Abstract要約: 我々は$mathbbRn$における実数値関数に対するゼロ次数とヘッセン推定器について検討する。
ランダムな方向に沿って有限差分を取ることにより、勾配有限差分推定器の分散を著しく低減できることを示す。
- 参考スコア（独自算出の注目度）: 6.137707924685666
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic zeroth order gradient and Hessian estimators for
real-valued functions in $\mathbb{R}^n$. We show that, via taking finite
difference along random orthogonal directions, the variance of the stochastic
finite difference estimators can be significantly reduced. In particular, we
design estimators for smooth functions such that, if one uses $ \Theta \left( k
\right) $ random directions sampled from the Stiefel's manifold $ \text{St}
(n,k) $ and finite-difference granularity $\delta$, the variance of the
gradient estimator is bounded by $ \mathcal{O} \left( \left( \frac{n}{k} - 1
\right) + \left( \frac{n^2}{k} - n \right) \delta^2 + \frac{ n^2 \delta^4 }{ k
} \right) $, and the variance of the Hessian estimator is bounded by
$\mathcal{O} \left( \left( \frac{n^2}{k^2} - 1 \right) + \left( \frac{n^4}{k^2}
- n^2 \right) \delta^2 + \frac{n^4 \delta^4 }{k^2} \right) $. When $k = n$, the
variances become negligibly small. In addition, we provide improved bias bounds
for the estimators. The bias of both gradient and Hessian estimators for smooth
function $f$ is of order $\mathcal{O} \left( \delta^2 \Gamma \right)$, where
$\delta$ is the finite-difference granularity, and $ \Gamma $ depends on high
order derivatives of $f$. Our results are evidenced by empirical observations.
- Abstract（参考訳）: 我々は$\mathbb{R}^n$における実数値関数に対する確率零次勾配とヘッセン推定器について検討する。
ランダム直交方向に沿って有限差分を取ることにより,確率的有限差分推定器の分散を著しく低減できることを示す。
In particular, we design estimators for smooth functions such that, if one uses $ \Theta \left( k \right) $ random directions sampled from the Stiefel's manifold $ \text{St} (n,k) $ and finite-difference granularity $\delta$, the variance of the gradient estimator is bounded by $ \mathcal{O} \left( \left( \frac{n}{k} - 1 \right) + \left( \frac{n^2}{k} - n \right) \delta^2 + \frac{ n^2 \delta^4 }{ k } \right) $, and the variance of the Hessian estimator is bounded by $\mathcal{O} \left( \left( \frac{n^2}{k^2} - 1 \right) + \left( \frac{n^4}{k^2} - n^2 \right) \delta^2 + \frac{n^4 \delta^4 }{k^2} \right) $.
k = n$ の場合、分散は無視できるほど小さくなる。
さらに,推定者に対するバイアスバウンダリも改善した。
滑らかな関数 $f$ に対する勾配とヘッセン推定子のバイアスは次数 $\mathcal{O} \left( \delta^2 \Gamma \right)$ であり、$\delta$ は有限差分粒度であり、$ \Gamma $ は $f$ の高階微分に依存する。
我々の結果は実証的な観察によって証明される。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization [20.54801745090522]
我々は、mathbbRd f(x) 三角形q mathbbE_xi [Fxi]$inf(x)$ Lipschitz における $min_x という形式の問題を考察する。
最近提案された勾配なし法は、少なくとも$mathcalO(L4 d3/2 epsilon-4 + Goldstein L d3/2 delta-1 epsilon-4)$ 0次複雑性を必要とする。
論文 参考訳（メタデータ） (2023-01-16T13:33:37Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Towards Sharp Stochastic Zeroth Order Hessian Estimators over Riemannian
Manifolds [5.7569764948783355]
O(1)$関数評価を用いたゼロ階ヘッセン推定器を新たに導入する。
リプシッツ・ヘッセン(英語版)による滑らかな実数値関数 $f$ に対して、我々の推定子は位数 $ O left(L delta + gamma delta2 right)$ のバイアス境界を達成する。
論文 参考訳（メタデータ） (2022-01-26T07:09:25Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。
確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
論文 参考訳（メタデータ） (2020-10-22T17:52:45Z) - GO Hessian for Expectation-Based Objectives [73.06986780804269]
GOグラデーションは、最近予測に基づく目的に対して$mathbbE_q_boldsymboldsymboldsymbolgamma(boldsymboly) [f(boldsymboly)]$として提案された。
GO勾配に基づいて、$mathbbE_q_boldsymboldsymboldsymbolgamma(boldsymboly) [f(boldsymboly)]$ an unbiased low-variance Hessian estimator, named GO Hessian を示す。
論文 参考訳（メタデータ） (2020-06-16T02:20:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。