More Like this

1. DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate

   Saeed Soori, Konstantin Mishchenko (January 2020, Proceedings of Machine Learning Research)

   null (Ed.)

   In this paper, we consider distributed algorithms for solving the empirical risk minimization problem under the master/worker communication model. We develop a distributed asynchronous quasi-Newton algorithm that can achieve superlinear convergence. To our knowledge, this is the first distributed asynchronous algorithm with superlinear convergence guarantees. Our algorithm is communication-efficient in the sense that at every iteration the master node and workers communicate vectors of size 𝑂(𝑝), where 𝑝 is the dimension of the decision variable. The proposed method is based on a distributed asynchronous averaging scheme of decision vectors and gradients in a way to effectively capture the local Hessian information of the objective function. Our convergence theory supports asynchronous computations subject to both bounded delays and unbounded delays with a bounded time-average. Unlike in the majority of asynchronous optimization literature, we do not require choosing smaller stepsize when delays are huge. We provide numerical experiments that match our theoretical results and showcase significant improvement comparing to state-of-the-art distributed algorithms. 

   more » « less
2. The random component-wise power method

   https://doi.org/10.1117/12.2530511  

   Teke, Oguzhan; Vaidyanathan, P. P.; Lu, Yue M.; Papadakis, Manos; Van De Ville, Dimitri (September 2019, Proc. SPIE 11138, Wavelets and Sparsity XVIII)

   This paper considers a random component-wise variant of the unnormalized power method, which is similar to the regular power iteration except that only a random subset of indices is updated in each iteration. For the case of normal matrices, it was previously shown that random component-wise updates converge in the mean-squared sense to an eigenvector of eigenvalue 1 of the underlying matrix even in the case of the matrix having spectral radius larger than unity. In addition to the enlarged convergence regions, this study shows that the eigenvalue gap does not directly aect the convergence rate of the randomized updates unlike the regular power method. In particular, it is shown that the rate of convergence is aected by the phase of the eigenvalues in the case of random component-wise updates, and the randomized updates favor negative eigenvalues over positive ones. As an application, this study considers a reformulation of the component-wise updates revealing a randomized algorithm that is proven to converge to the dominant left and right singular vectors of a normalized data matrix. The algorithm is also extended to handle large-scale distributed data when computing an arbitrary rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed algorithms under dierent parameter settings. 

   more » « less
3. Sparks of symmetric matrices and their graphs

   https://doi.org/10.13001/ela.2023.8025  

   Deaett, Louis; Fallat, Shaun; Furst, Veronika; Hutchens, John; Mitchell, Lon; Zhang, Yaqi (November 2023, The Electronic Journal of Linear Algebra)

   The spark of a matrix is the smallest number of nonzero coordinates of any nonzero null vector. For real symmetric matrices, the sparsity of null vectors is shown to be associated with the structure of the graph obtained from the off-diagonal pattern of zero and nonzero entries. The smallest possible spark of a matrix corresponding to a graph is defined as the spark of the graph. Connections are established between graph spark and well-known concepts including minimum rank, forts, orthogonal representations, Parter and Fiedler vertices, and vertex connectivity. 

   more » « less
4. The local solubility for homogeneous polynomials with random coefficients over thin sets

   https://doi.org/10.1112/mtk.12282  

   Lee, Heejong; Lee, Seungsu; Yeon, Kiseok (October 2024, Mathematika)

   Abstract Let and be natural numbers greater or equal to 2. Let be a homogeneous polynomial in variables of degree with integer coefficients , where denotes the inner product, and denotes the Veronese embedding with . Consider a variety in , defined by . In this paper, we examine a set of integer vectors , defined bywhere is a nonsingular form in variables of degree with for some constant depending at most on and . Suppose has a nontrivial integer solution. We confirm that the proportion of integer vectors in , whose associated equation  is everywhere locally soluble, converges to a constant as . Moreover, for each place of , if there exists a nonzero such that and the variety in admits a smooth ‐point, the constant is positive. 

   more » « less
5. A convergent genus expansion for the plateau

   https://doi.org/10.1007/JHEP09(2024)033  

   Saad, Phil; Stanford, Douglas; Yang, Zhenbin; Yao, Shunyu (September 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> We conjecture a formula for the spectral form factor of a double-scaled matrix integral in the limit of large time, large density of states, and fixed temperature. The formula has a genus expansion with a nonzero radius of convergence. To understand the origin of this series, we compare to the semiclassical theory of “encounters” in periodic orbits. In Jackiw-Teitelboim (JT) gravity, encounters correspond to portions of the moduli space integral that mutually cancel (in the orientable case) but individually grow at low energies. At genus one we show how the full moduli space integral resolves the low energy region and gives a finite nonzero answer. 

   more » « less