論文の概要: Stochastic Bias-Reduced Gradient Methods
- arxiv url: http://arxiv.org/abs/2106.09481v1
- Date: Thu, 17 Jun 2021 13:33:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 15:36:13.858464
- Title: Stochastic Bias-Reduced Gradient Methods
- Title(参考訳): 確率バイアス誘導勾配法
- Authors: Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin and Aaron Sidford
- Abstract要約: モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
- 参考スコア(独自算出の注目度): 44.35885731095432
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a new primitive for stochastic optimization: a low-bias, low-cost
estimator of the minimizer $x_\star$ of any Lipschitz strongly-convex function.
In particular, we use a multilevel Monte-Carlo approach due to Blanchet and
Glynn to turn any optimal stochastic gradient method into an estimator of
$x_\star$ with bias $\delta$, variance $O(\log(1/\delta))$, and an expected
sampling cost of $O(\log(1/\delta))$ stochastic gradient evaluations. As an
immediate consequence, we obtain cheap and nearly unbiased gradient estimators
for the Moreau-Yoshida envelope of any Lipschitz convex function, allowing us
to perform dimension-free randomized smoothing.
We demonstrate the potential of our estimator through four applications.
First, we develop a method for minimizing the maximum of $N$ functions,
improving on recent results and matching a lower bound up logarithmic factors.
Second and third, we recover state-of-the-art rates for projection-efficient
and gradient-efficient optimization using simple algorithms with a transparent
analysis. Finally, we show that an improved version of our estimator would
yield a nearly linear-time, optimal-utility, differentially-private non-smooth
stochastic optimization method.
- Abstract(参考訳): 我々は、任意のリプシッツ強凸関数の最小値$x_\star$の低バイアスで低コストな推定器である確率最適化のための新しいプリミティブを開発する。
特に、ブランシェットとグリンによるマルチレベルモンテカルロ法を用いて、任意の最適確率勾配法をバイアス$\delta$のx_\star$、分散$o(\log(1/\delta))$、期待サンプリングコスト$o(\log(1/\delta))$確率勾配評価の推定値に変換する。
その結果、任意のリプシッツ凸関数のモロー・吉田包絡に対して、安価でほぼ偏りのない勾配推定器を得ることができ、次元フリーなランダム化平滑化が可能となった。
4つの応用を通して推定器の可能性を示す。
まず, 最大n$関数を最小化し, 最近の結果を改良し, 低バウンドアップ対数因子をマッチングする手法を開発した。
第2と第3に、透過的解析を用いた単純なアルゴリズムを用いて、投影効率と勾配効率の最適化のための最先端率を復元する。
最後に, 近似器の改良版では, ほぼ線形時間, 最適利用率, 微分プライベートな非滑らか確率最適化法が得られることを示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - On the Stochastic (Variance-Reduced) Proximal Gradient Method for
Regularized Expected Reward Optimization [12.244251361123396]
我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。
特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon-stationaryポイントに含めることが示されている。
追加条件下では,サンプルの複雑さが$epsilon-4)$から$O(epsilon-3)$に改善できることが示されている。
論文 参考訳(メタデータ) (2024-01-23T06:01:29Z) - Variance-reduced Clipping for Non-convex Optimization [24.765794811146144]
グラディエント・クリッピング(Gradient clipping)は、大規模言語モデリングのようなディープラーニングアプリケーションで用いられる技法である。
最近の実験的な訓練は、秩序の複雑さを緩和する、非常に特別な振る舞いを持っている。
論文 参考訳(メタデータ) (2023-03-02T00:57:38Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳(メタデータ) (2022-11-29T18:38:40Z) - Efficient Minimax Optimal Global Optimization of Lipschitz Continuous
Multivariate Functions [0.0]
我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
論文 参考訳(メタデータ) (2022-06-06T06:28:38Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳(メタデータ) (2022-03-29T17:59:10Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳(メタデータ) (2021-02-19T12:22:56Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。