We prove convergence rates of Zeroth-order Gradient Descent (ZGD) algorithms for Łojasiewicz functions. Our results show that for smooth Łojasiewicz functions with Łojasiewicz exponent larger than 0.5 and smaller than 1, the functions values can converge much faster than the (zeroth-order) gradient descent trajectory. Similar results hold for convex nonsmooth Łojasiewicz functions. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0247 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0247 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a$T$-step problem with Lipschitz reward of zooming dimension$d_{z}$, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate$\widetilde {\mathcal {O}}\left ({T^{\frac {d_{z}+1}{d_{z}+2}}}\right)$using only$\mathcal {O} \left ({\log \log T}\right) $batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that$\Omega (\log \log T)$batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate (up to logarithmic factors) using minimal communication.

In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a $T$-step problem with Lipschitz reward of zooming dimension $d_z$, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate $\widetilde{\mathcal{O}}\left(T^{\frac{d_z+1}{d_z+2}}\right)$ using only $ \mathcal{O} \left( \log\log T\right) $ batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that $\Omega(\log\log T)$ batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate using minimal communication.

Q-compensated reverse time migration (Q-RTM) can compensate seismic attenuation caused by the anelastic behavior of subsurface media. Although, the traditional Q-RTM has high computational efficiency, it is instable because the high frequency or wavenumber ambient noise is exponentially boosted during forward and backward seismic wavefield propagation. The existing stable Q-RTM method costs twice as much computing time and memory compared to the traditional Q-RTM. In this letter, we propose a new Q-RTM method to address the above issues simultaneously. First, a new viscoacoustic wave equation is derived based on a wavefield decomposition method to obtain the velocity-dispersion-only and viscoacoustic wavefields efficiently. Then, a theoretical framework of stable and high-efficiency Q-RTM method is proposed based on the velocity-dispersion-only and viscoacoustic wavefields. The synthetic example shows that the new stable Q-RTM results match well with the reference images (without attenuation images). Moreover, the field data images also demonstrate the stability and high-efficiency of our proposed Q-RTM method.