Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome convergent results for Backtracking Gradient Descent method on Banach spaces
57
0
0.0
(
0
)
Added by
Tuyen Truong
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Tuyen Trung Truong
Ask ChatGPT about the research
No Arabic abstract
Our main result concerns the following condition: {bf Condition C.} Let $X$ be a Banach space. A $C^1$ function $f:Xrightarrow mathbb{R}$ satisfies Condition C if whenever ${x_n}$ weakly converges to $x$ and $lim _{nrightarrowinfty}|| abla f(x_n)||=0$, then $ abla f(x)=0$. We assume that there is given a canonical isomorphism between $X$ and its dual $X^*$, for example when $X$ is a Hilbert space. {bf Theorem.} Let $X$ be a reflexive, complete Banach space and $f:Xrightarrow mathbb{R}$ be a $C^2$ function which satisfies Condition C. Moreover, we assume that for every bounded set $Ssubset X$, then $sup _{xin S}|| abla ^2f(x)||<infty$. We choose a random point $x_0in X$ and construct by the Local Backtracking GD procedure (which depends on $3$ hyper-parameters $alpha ,beta ,delta _0$, see later for details) the sequence $x_{n+1}=x_n-delta (x_n) abla f(x_n)$. Then we have: 1) Every cluster point of ${x_n}$, in the {bf weak} topology, is a critical point of $f$. 2) Either $lim _{nrightarrowinfty}f(x_n)=-infty$ or $lim _{nrightarrowinfty}||x_{n+1}-x_n||=0$. 3) Here we work with the weak topology. Let $mathcal{C}$ be the set of critical points of $f$. Assume that $mathcal{C}$ has a bounded component $A$. Let $mathcal{B}$ be the set of cluster points of ${x_n}$. If $mathcal{B}cap A ot= emptyset$, then $mathcal{B}subset A$ and $mathcal{B}$ is connected. 4) Assume that $X$ is separable. Then for generic choices of $alpha ,beta ,delta _0$ and the initial point $x_0$, if the sequence ${x_n}$ converges - in the {bf weak} topology, then the limit point cannot be a saddle point.
rate research
Read More
In unconstrained optimisation on an Euclidean space, to prove convergence in Gradient Descent processes (GD) $x_{n+1}=x_n-delta _n abla f(x_n)$ it usually is required that the learning rates $delta _n$s are bounded: $delta _nleq delta $ for some positive $delta $. Under this assumption, if the sequence $x_n$ converges to a critical point $z$, then with large values of $n$ the update will be small because $||x_{n+1}-x_n||lesssim || abla f(x_n)||$. This may also force the sequence to converge to a bad minimum. If we can allow, at least theoretically, that the learning rates $delta _n$s are not bounded, then we may have better convergence to better minima. A previous joint paper by the author showed convergence for the usual version of Backtracking GD under very general assumptions on the cost function $f$. In this paper, we allow the learning rates $delta _n$ to be unbounded, in the sense that there is a function $h:(0,infty)rightarrow (0,infty )$ such that $lim _{trightarrow 0}th(t)=0$ and $delta _nlesssim max {h(x_n),delta }$ satisfies Armijos condition for all $n$, and prove convergence under the same assumptions as in the mentioned paper. It will be shown that this growth rate of $h$ is best possible if one wants convergence of the sequence ${x_n}$. A specific way for choosing $delta _n$ in a discrete way connects to Two-way Backtracking GD defined in the mentioned paper. We provide some results which either improve or are implicitly contained in those in the mentioned paper and another recent paper on avoidance of saddle points.
We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) dont increase the stepsize too fast and 2) dont overstep the local curvature. No need for functional values, no line search, no information about the function except for the gradients. By following these rules, you get a method adaptive to the local geometry, with convergence guarantees depending only on the smoothness in a neighborhood of a solution. Given that the problem is convex, our method converges even if the global smoothness constant is infinity. As an illustration, it can minimize arbitrary continuously twice-differentiable convex function. We examine its performance on a range of convex and nonconvex problems, including logistic regression and matrix factorization.
Despite the strong theoretical guarantees that variance-reduced finite-sum optimization algorithms enjoy, their applicability remains limited to cases where the memory overhead they introduce (SAG/SAGA), or the periodic full gradient computation they require (SVRG/SARAH) are manageable. A promising approach to achieving variance reduction while avoiding these drawbacks is the use of importance sampling instead of control variates. While many such methods have been proposed in the literature, directly proving that they improve the convergence of the resulting optimization algorithm has remained elusive. In this work, we propose an importance-sampling-based algorithm we call SRG (stochastic reweighted gradient). We analyze the convergence of SRG in the strongly-convex case and show that, while it does not recover the linear rate of control variates methods, it provably outperforms SGD. We pay particular attention to the time and memory overhead of our proposed method, and design a specialized red-black tree allowing its efficient implementation. Finally, we present empirical results to support our findings.
Bayesian inference problems require sampling or approximating high-dimensional probability distributions. The focus of this paper is on the recently introduced Stein variational gradient descent methodology, a class of algorithms that rely on iterated steepest descent steps with respect to a reproducing kernel Hilbert space norm. This construction leads to interacting particle systems, the mean-field limit of which is a gradient flow on the space of probability distributions equipped with a certain geometrical structure. We leverage this viewpoint to shed some light on the convergence properties of the algorithm, in particular addressing the problem of choosing a suitable positive definite kernel function. Our analysis leads us to considering certain nondifferentiable kernels with adjusted tails. We demonstrate significant performs gains of these in various numerical experiments.
Assume that $mathcal{I}$ is an ideal on $mathbb{N}$, and $sum_n x_n$ is a divergent series in a Banach space $X$. We study the Baire category, and the measure of the set $A(mathcal{I}):=left{t in {0,1}^{mathbb{N}} colon sum_n t(n)x_n textrm{ is } mathcal{I}textrm{-convergent}right}$. In the category case, we assume that $mathcal{I}$ has the Baire property and $sum_n x_n$ is not unconditionally convergent, and we deduce that $A(mathcal{I})$ is meager. We also study the smallness of $A(mathcal{I})$ in the measure case when the Haar probability measure $lambda$ on ${0,1}^{mathbb{N}}$ is considered. If $mathcal{I}$ is analytic or coanalytic, and $sum_n x_n$ is $mathcal{I}$-divergent, then $lambda(A(mathcal{I}))=0$ which extends the theorem of Dindov{s}, v{S}alat and Toma. Generalizing one of their examples, we show that, for every ideal $mathcal{I}$ on $mathbb{N}$, with the property of long intervals, there is a divergent series of reals such that $lambda(A(Fin))=0$ and $lambda(A(mathcal{I}))=1$.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
