We prove new small-ball inequalities for boolean matrix-series. The leading example is $\mathbb E_s[{\text{det}(I-S^2)^\beta\,\mathbf 1_{\{\|S\|<1\}}}]\ge e^{-O(\beta\tau)}$, which holds for boolean matrix-series $S=\sum_i s_iA_i$ formed using symmetric matrices $A_1,\dots,A_n$ and uniformly random signs $s\in\{\pm1\}^...
A verifiable and accurate termination criterion for PWS optimization is introduced and like the gradient norm in smooth optimization, this certificate tightly characterizes the optimality gap under the QG condition and can be evaluated without knowledge of any problem parameters.
We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $...
Guo, Fang, and Lu recently proved the Koml\'os conjecture: for vectors $v_1,\ldots,v_n\in\mathbb R^d$ of Euclidean norm at most one, there are signs $\varepsilon_j\in\{-1,1\}$ with $\|\sum_j\varepsilon_jv_j\|_\infty\le3\sqrt{2\pi}$. We give a short proof of the bound $3\pi$ that keeps the geometric lifting framework of...
We develop a novel approach to matrix discrepancy based on matrix small-ball estimates. Specifically, we use a determinantal weight (obtained from the log-barrier) to scale the small-ball probability into a partition function of a tilt of the Gaussian measure. We then employ matrix-weighted Poincar\'e inequalities to c...
The dynamics of Stochastic Gradient Descent is studied by modeling the stochastic gradient flow as a percolation process, in which nested architectural symmetries force subnetworks to merge in discrete blocks rather than by single-edge attachment.
Sai Niranjan Ramachandran, Suvrit Sra· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
