Let $f:\mathbb{R}^d \rightarrow \mathbb{R}$. We consider gradient descent $x_{n+1} = x_n - \tau_n \nabla f(x_n)$, where the stepsize $\tau_n = \tau \cdot e^{rn}$ is exponentially growing (with $\tau>0$ and $0<r \ll 1$). This diverges for almost all initial values. We show that restarting the algorithm whenever $\|x_{n+1} - x_n\| \geq e^r\|x_n - x_{n-1}\|$ has good properties: it works very well in practice; we determine the limiting convergence rate in the case of convergence to a non-degenerate local minimum: it improves on classic gradient descent even though computational cost is comparable. The precise choice of $0<r \ll 1$ does not matter much and the method is virtually independent of an initial stepsize $\tau$ that is too small: while the convergence rate for gradient descent decays linearly as $\tau \rightarrow 0$, it decays as $1/\log(1/\tau)$ in this modified version; numerical examples illustrate the results.
Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\,\mathrm{d} x$ on $\mathbb R^d$, where $0<m\leq L<\infty$, $mI_d\preceq\nabla^2U(x)\preceq LI_d$, and $\kappa=L/m$. It is known that, under warm-start assumptions, fixed-step Metropolis-adjusted Langevin algorithm (MALA) with properly tuned step size has mixing time of order $\ka...
Let $\boldsymbol{X} = (X_1,\ldots,X_n)$ be a centered Gaussian vector, not necessarily nondegenerate. It is proved that, for every $\alpha_1,\ldots,\alpha_n>0$, \[ \mathsf{E}\left[\prod_{i=1}^n |X_i|^{\alpha_i}\right] \geq \prod_{i=1}^n \mathsf{E}\left[|X_i|^{\alpha_i}\right]. \] When all marginal variances are positiv...
Let $\mu$ be a log-concave probability measure on $\mathbb R^n$ and let $f\colon\mathbb R^n\to\mathbb R^k$ be a polynomial mapping of degree at most $d$. We show that \[ \mu(f\in A) \le C\bigl(\lambda_k(A)\bigr)^{\frac{1}{k(d-1)+1}} \] for every Borel set $A\subset\mathbb R^k$ whenever the image measure $\mu\circ f^{-1...
For $N\geq 1$, $p\geq 1$, and $\delta>0$, consider the nonlocal threshold functional \[ I_{\delta,p}(u)=\iint_{\{|u(x)-u(y)|>\delta\}} \frac{\delta^p}{|x-y|^{N+p}}\,\dd x\,\dd y. \] Nguyen and Squassina \cite{NguyenSquassina} asked whether $I_{\delta,p}$ decreases under Schwarz rearrangement. We give a negative answer...
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})$, we prove an $\Omega\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)$ non-anytime lower bound. In the anytime setting, every infinite schedule h...
We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we...
Rui-Jie Li, Kang Chen, Tian-Yu Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
