We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017), recovering the optimal moment bounds for log-concave distributions. As an immediate corollary, we obtain computationally efficient algorithms with dimension-free error guarantees for a wide range of statistical estimation problems. Our proof proceeds by using stochastic localization to decompose $P$ as an average of strongly log-concave measures, whose centered moments admit the subgaussian certificates (Diakonikolas et al., 2025). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from the variance inequality for quadratic forms (Letwin, 2026) suffices to control this averaging at every even degree.
We prove that any subset $A \subseteq \{1, \dots, N\}$ lacking non-trivial polynomial progressions $(x, x + y, x + y^2)$ satisfies $\lvert A \rvert \le CN \exp\bigl(-c(\log \log N)^\beta\bigr)$ for effective absolute constants $C, c, \beta>0$. The argument develops a density increment framework localized to anisotropic...
For each real $b$, exact upper and lower bounds on the probability $\mathsf P(X\ge b)$ over all random variables $X$ with log-concave p.d.f.'s such that $\mathsf E X=0$ and $\mathsf E X^2=1$ are obtained, as well as the best constant factor $C$ in the inequality $\mathsf P(X\ge b)\le C e^{-b}$ for all real $b\ge0$. Exa...
Let $\mu$ be a log-concave isotropic probability measure on $R^d$ , and let $\mu^n$ denote the law of the normalized sum of $n$ independent random vectors with law $\mu$. We prove that \[ H(\mu^n|\gamma)\leq \frac{C}{n} \min\left\{1+\log(ed)^2H(\mu|\gamma)\ ,\ d\right\}. \] Compared to the previous best known bound, ou...
We estimate the L\'evy distance to the symmetric Bernoulli distribution for normalized Boolean convolution powers of a probability measure with mean zero and variance one. If the absolute moment of order $r$ is finite, we obtain the upper bounds $o(n^{-(r-2)/6})$ for $2<r<5$ and $O(n^{-1/2})$ for $r\ge5$. The proof rel...
We prove an $L^4$ Strichartz estimate for the dispersion $n_1^2+\alpha n_2^2$ on $\mathbb T^2$, for every $\alpha>0$. The loss is controlled by the Shannon entropy of the normalized squared Fourier coefficients and the cardinality of their support $S$. In particular, we obtain a norm loss of $(\log\#S)^{1/2}$ on fixed...
Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\, \mathrm{d} x$ on $\mathbb{R}^d$, where $U$ is continuously differentiable and $m$-strongly convex with a globally $L$-Lipschitz gradient, $0<m\leq L<\infty$, and $\kappa=L/m$. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds...
Qian Qin· 0 citations
Related blog posts
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026