論文の概要: Convergence Rates for Non-Log-Concave Sampling and Log-Partition
Estimation
- arxiv url: http://arxiv.org/abs/2303.03237v3
- Date: Tue, 1 Aug 2023 13:09:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-02 17:59:43.080122
- Title: Convergence Rates for Non-Log-Concave Sampling and Log-Partition
Estimation
- Title（参考訳）: 非対数凹サンプリングの収束率と対数分割推定
- Authors: David Holzm\"uller, Francis Bach
- Abstract要約: m$timesの微分可能関数が$d$の場合、$n$(m/d)のアルゴリズムの最適レートは$n(m/d)であることが知られている。
サンプリングと計算に類似したレートが可能であり、独立レートが$d$の時間で実現可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sampling from Gibbs distributions $p(x) \propto \exp(-V(x)/\varepsilon)$ and
computing their log-partition function are fundamental tasks in statistics,
machine learning, and statistical physics. However, while efficient algorithms
are known for convex potentials $V$, the situation is much more difficult in
the non-convex case, where algorithms necessarily suffer from the curse of
dimensionality in the worst case. For optimization, which can be seen as a
low-temperature limit of sampling, it is known that smooth functions $V$ allow
faster convergence rates. Specifically, for $m$-times differentiable functions
in $d$ dimensions, the optimal rate for algorithms with $n$ function
evaluations is known to be $O(n^{-m/d})$, where the constant can potentially
depend on $m, d$ and the function to be optimized. Hence, the curse of
dimensionality can be alleviated for smooth functions at least in terms of the
convergence rate. Recently, it has been shown that similarly fast rates can
also be achieved with polynomial runtime $O(n^{3.5})$, where the exponent $3.5$
is independent of $m$ or $d$. Hence, it is natural to ask whether similar rates
for sampling and log-partition computation are possible, and whether they can
be realized in polynomial time with an exponent independent of $m$ and $d$. We
show that the optimal rates for sampling and log-partition computation are
sometimes equal and sometimes faster than for optimization. We then analyze
various polynomial-time sampling algorithms, including an extension of a recent
promising optimization approach, and find that they sometimes exhibit
interesting behavior but no near-optimal rates. Our results also give further
insights on the relation between sampling, log-partition, and optimization
problems.
- Abstract（参考訳）: Gibbsディストリビューションからサンプリングする$p(x) \propto \exp(-V(x)/\varepsilon)$とそれらのログ分割関数の計算は統計学、機械学習、統計物理学の基本的なタスクである。
しかしながら、効率的なアルゴリズムは凸ポテンシャル$V$で知られているが、非凸の場合、最悪の場合、アルゴリズムが必然的に次元性の呪いに苦しむ場合、状況ははるかに困難である。
サンプリングの低温限界と見なすことができる最適化のために、滑らかな関数 $v$ はより高速な収束率を可能にすることが知られている。
具体的には、$d$次元における$m$-times微分可能関数の場合、$n$関数評価を持つアルゴリズムの最適レートは$O(n^{-m/d})$であることが知られており、定数は$m, d$と最適化される関数に依存する可能性がある。
したがって、次元性の呪いは少なくとも収束率の観点から滑らかな函数に対して緩和することができる。
近年、多項式ランタイム $o(n^{3.5})$ でも同様の速さを達成できることが示されており、指数 $3.5$ は $m$ または $d$ から独立している。
したがって、サンプリングとログ分割計算の類似のレートが可能か、あるいは$m$と$d$に依存しない指数で多項式時間で実現可能かどうかを問うのは自然である。
サンプリングおよびログ分割計算の最適レートは、最適化よりも等しく、時として高速であることを示す。
次に,最近期待されている最適化手法の拡張を含む様々な多項式時間サンプリングアルゴリズムを分析し,興味ある振る舞いを呈するが、ほぼ最適に近い速度は示さないことを示す。
また,サンプリング,ログ分割,最適化問題との関係についても考察した。
関連論文リスト
- Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Weighted least-squares approximation with determinantal point processes and generalized volume sampling [33.33724208084121]
与えられた$m$-次元空間$V_m$の要素によって、函数を$L2$から近似する問題を考える。
近似は、ほぼ確実に$H$-normで測定された最高の近似誤差によって境界づけられていることを示す。
論文 参考訳（メタデータ） (2023-12-21T17:34:18Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC [35.050135428062795]
ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。
我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
論文 参考訳（メタデータ） (2020-10-27T22:52:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。