Juspreet Singh Sandhu

David Jekel, Juspreet Singh Sandhu, Jonathan Shi · harvard

We present the first iterative spectral algorithm to find near-optimal solutions for a random quadratic objective over the discrete hypercube, resolving a conjecture of Subag [Subag, Communications on Pure and Applied Mathematics, 74(5), 2021]. The algorithm is a randomized Hessian ascent in the solid cube, with the objective modified by subtracting an instance-independent potential function [Chen et al., Communications on Pure and Applied Mathematics, 76(7), 2023]. Using tools from free probability theory, we construct an approximate projector into the top eigenspaces of the Hessian, which serves as the covariance matrix for the random increments. With high probability, the iterates' empirical distribution approximates the solution to the primal version of the Auffinger-Chen SDE [Auffinger et al., Communications in Mathematical Physics, 335, 2015]. The per-iterate change in the modified objective is bounded via a Taylor expansion, where the derivatives are controlled through Gaussian concentration bounds and smoothness properties of a semiconcave regularization of the Fenchel-Legendre dual to the Parisi PDE. These results lay the groundwork for (possibly) demonstrating low-degree sum-of-squares certificates over high-entropy step distributions for a relaxed version of the Parisi formula [Open Question 1.8, arXiv:2401.14383].

Ewan Davies, Holden Lee, Juspreet Singh Sandhu et al.

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington--Kirkpatrick model with negligible total-variation distance (TVD) error up to inverse temperature $β< 1/2$. Prior work obtained TVD error guarantees only up to $β\approx 0.295$, while results covering the entire replica-symmetric regime $β< 1$ gave guarantees only in Wasserstein distance. Our approach demonstrates that the same potential Hessian ascent previously developed for optimization also functions as a sampling algorithm by implementing algorithmic stochastic localization at high temperature. By estimating the covariance of the tilted Gibbs distribution via Gaussian integration by parts, overlap concentration, and precise cavity estimates, we show that a Hessian-ascent process achieves an $O(1)$ Wasserstein error guarantee for finite-time localization, improving on the previous $o(n)$. A careful comparison of stochastic localization with the Hessian ascent process and a free probability argument controlling the diagonal sub-algebra of the Hessian improves this to $O(1)$ in KL divergence. We then use Jarzynski's equality with rejection sampling, along with a restricted log-Sobolev inequality on the time-$T$ localized distribution, to refine the error to $o(1)$ in TVD up to a constant time $T$ and to complete the sampling with Glauber dynamics.

Emil T. Khabiboulline, Juspreet Singh Sandhu, Marco Ugo Gambetta et al.

Ensuring security and integrity of elections constitutes an important challenge with wide-ranging societal implications. Classically, security guarantees can be ensured based on computational complexity, which may be challenged by quantum computers. We show that the use of quantum networks can enable information-theoretic security for the desirable aspects of a distributed voting scheme in a resource-efficient manner. In our approach, ballot information is encoded in quantum states that enable an exponential reduction in communication complexity compared to classical communication. In addition, we provide an efficient and secure anonymous queuing protocol. As a result, our scheme only requires modest quantum memories with size scaling logarithmically with the number of voters. This intrinsic efficiency together with certain noise-robustness of our protocol paves the way for its physical implementation in realistic quantum networks.

Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang et al.

One of the challenges in analyzing learning algorithms is the circular entanglement between the objective value and the stochastic noise. This is also known as the "chicken and egg" phenomenon and traditionally, there is no principled way to tackle this issue. People solve the problem by utilizing the special structure of the dynamic, and hence the analysis would be difficult to generalize. In this work, we present a streamlined three-step recipe to tackle the "chicken and egg" problem and give a general framework for analyzing stochastic dynamics in learning algorithms. Our framework composes standard techniques from probability theory, such as stopping time and martingale concentration. We demonstrate the power and flexibility of our framework by giving a unifying analysis for three very different learning problems with the last iterate and the strong uniform high probability convergence guarantee. The problems are stochastic gradient descent for strongly convex functions, streaming principal component analysis, and linear bandit with stochastic gradient descent updates. We either improve or match the state-of-the-art bounds on all three dynamics.