論文の概要: A qualitative difference between gradient flows of convex functions in
finite- and infinite-dimensional Hilbert spaces
- arxiv url: http://arxiv.org/abs/2310.17610v1
- Date: Thu, 26 Oct 2023 17:33:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-27 18:37:04.488598
- Title: A qualitative difference between gradient flows of convex functions in
finite- and infinite-dimensional Hilbert spaces
- Title（参考訳）: 有限次元および無限次元ヒルベルト空間における凸関数の勾配流の質的差
- Authors: Jonathan W. Siegel, Stephan Wojtowytsch
- Abstract要約: 凸対象関数に対する勾配流/勾配降下とボール/加速勾配降下の最適化について検討する。
ヒルベルト空間において、これは最適である:$f(x_t) - inf f$ は、モノトンが減少し$infty$で可積分である任意の関数と同じくらいゆっくりと$0$に崩壊することができる。
- 参考スコア（独自算出の注目度）: 2.7195102129095003
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider gradient flow/gradient descent and heavy ball/accelerated
gradient descent optimization for convex objective functions. In the gradient
flow case, we prove the following:
1. If $f$ does not have a minimizer, the convergence $f(x_t)\to \inf f$ can
be arbitrarily slow.
2. If $f$ does have a minimizer, the excess energy $f(x_t) - \inf f$ is
integrable/summable in time. In particular, $f(x_t) - \inf f = o(1/t)$ as
$t\to\infty$.
3. In Hilbert spaces, this is optimal: $f(x_t) - \inf f$ can decay to $0$ as
slowly as any given function which is monotone decreasing and integrable at
$\infty$, even for a fixed quadratic objective.
4. In finite dimension (or more generally, for all gradient flow curves of
finite length), this is not optimal: We prove that there are convex monotone
decreasing integrable functions $g(t)$ which decrease to zero slower than
$f(x_t)-\inf f$ for the gradient flow of any convex function on $\mathbb R^d$.
For instance, we show that any gradient flow $x_t$ of a convex function $f$ in
finite dimension satisfies $\liminf_{t\to\infty} \big(t\cdot \log^2(t)\cdot
\big\{f(x_t) -\inf f\big\}\big)=0$.
This improves on the commonly reported $O(1/t)$ rate and provides a sharp
characterization of the energy decay law. We also note that it is impossible to
establish a rate $O(1/(t\phi(t))$ for any function $\phi$ which satisfies
$\lim_{t\to\infty}\phi(t) = \infty$, even asymptotically.
Similar results are obtained in related settings for (1) discrete time
gradient descent, (2) stochastic gradient descent with multiplicative noise and
(3) the heavy ball ODE. In the case of stochastic gradient descent, the
summability of $\mathbb E[f(x_n) - \inf f]$ is used to prove that $f(x_n)\to
\inf f$ almost surely - an improvement on the convergence almost surely up to a
subsequence which follows from the $O(1/n)$ decay estimate.
- Abstract（参考訳）: 凸対象関数に対する勾配流/勾配降下とボール/加速勾配降下最適化について検討する。
勾配フローの場合、1: $f$ が最小値を持たない場合、収束 $f(x_t)\to \inf f$ は任意に遅くなる。
2.$f$ が最小値を持つ場合、余剰エネルギー $f(x_t) - \inf f$ は可積分/可算である。
特に、$f(x_t) - \inf f = o(1/t)$ as $t\to\infty$ である。
3. ヒルベルト空間において、これは最適である: $f(x_t) - \inf f$ は、固定二次目的であっても、単調減少かつ$\infty$ で可積分である任意の与えられた函数と同様に、0$ で崩壊することができる。
4 有限次元(あるいはより一般的には、有限長のすべての勾配流曲線に対して)において、これは最適ではない: 積分可能関数 $g(t)$ が $f(x_t)-\inf f$ よりもゼロに減少する凸単調減少函数 $g(t)$ が存在することを証明する。
例えば、有限次元の凸函数の任意の勾配流 $x_t$ は、$\liminf_{t\to\infty} \big(t\cdot \log^2(t)\cdot \big\{f(x_t) -\inf f\big\}\big)=0$ を満たす。
これは一般的に報告されているO(1/t)$レートを改善し、エネルギー崩壊法則の鋭い特徴を与える。
また、任意の関数$\phi$に対して$o(1/(t\phi(t))$を確立することは不可能であり、これは$\lim_{t\to\infty}\phi(t) = \infty$である。
同様の結果は,(1)離散時間勾配降下,(2)乗算雑音を伴う確率的勾配降下,(3)重球odeという設定で得られた。
確率的勾配降下の場合、$\mathbb e[f(x_n) - \inf f]$ の和は、$f(x_n)\to \inf 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) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded
Geometric Penalties [21.141544548229774]
我々は$min_x max_y f(x, y) という形式で、$mathcalN$ は Hadamard である。
我々は、勾配収束定数を減少させることにより、グローバルな関心が加速されることを示す。
論文 参考訳（メタデータ） (2023-05-25T15:43:07Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文 参考訳（メタデータ） (2021-12-30T20:31:46Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳（メタデータ） (2021-10-12T09:36:41Z) - Convergence Rate of the (1+1)-Evolution Strategy with Success-Based
Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
1+1)-進化戦略(ES)と成功に基づくステップサイズ適応を一般凸二次関数で解析する。
1+1)-ES の収束速度は、一般凸二次函数上で明示的に厳密に導かれる。
論文 参考訳（メタデータ） (2021-03-02T09:03:44Z) - On the Convergence of Langevin Monte Carlo: The Interplay between Tail
Growth and Smoothness [10.482805367361818]
リプシッツ勾配を持つポテンシャル、すなわち$beta=1$の場合、我々の速度は最もよく知られた依存性の速度を回復する。
この結果は、ターゲット分布において$nu_* = eff$、KL分割において$nu_*$に適用できる。
論文 参考訳（メタデータ） (2020-05-27T00:26:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。