arXiv:2004. 05813v3 Announce Type: replace-cross Abstract: Suppose that we are given independent, identically distributed random samples $x_1,\cdots,x_n$ from a mixture at most $k$ many $d$-dimensional spherical Gaussian distributions $\mu_1,\cdots,\mu_{k_0}$ of identical and known variance $\sigma^2$ in each coordinate, such that the minimum $\ell^2$ distance between two distinct centers $y_l$ and $y_j$ is greater than $2\Delta\sigma \min\{\sqrt{d},\sqrt k\}$, where $\Delta>C_0$, and $C_0$ is a sufficiently large universal constant.
By Somnath Chakraborty, Hariharan Narayanan
arXiv:2410. 23212v3 Announce Type: replace-cross Abstract: In graph-based data analysis, $k$-nearest neighbor ($k$NN) graphs are widely used due to their adaptivity to local data densities.
By Xiuyuan Cheng, Yixuan Tan, Nan Wu
arXiv:2606. 14488v1 Announce Type: cross Abstract: Recent finite-time analyses of nonlinear two-time-scale stochastic approximation show that under contractive assumptions the slow iterate $Y_k$ with stepsizes $\beta_k=\Theta(k^{-1})$ and $\alpha_k=\Theta(k^{-a})$, $a\in(1/2,1)$, generally satisfies a mean-square rate of order $k^{-a}$; decoupled $k^{-1}$ rates require strong local linearity.
By Dhruv Sarkar, Vaneet Aggarwal
arXiv:2608. 13467v1 Announce Type: new Abstract: We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target \[ \pi(dx)\propto \exp\{-f(x)-g(x)\}\,dx, \qquad x\in\mathbb R^d, \] where \(f\) is \(m\)-strongly convex with \(L_f\)-Lipschitz gradient and \(g\) is convex and \(G\)-Lipschitz.
By Yuchen Xin, Zhihua Zhang
arXiv:2607. 10751v1 Announce Type: new Abstract: Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions \(f: V\to\{0,1,\ast\}\); equivalently, its concepts partition the ground set into black ($f^{-1}(1)$), grey ($f^{-1}(\ast)$), and white parts ($f^{-1}(0)$).
By Grigory Ivanov, Attila Jung, M\'arton Nasz\'odi
arXiv:2608. 04686v1 Announce Type: new Abstract: We study distributionally robust PAC learning for the $0$--$1$-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order $k>1$ and radius $\rho\geq 0$.
By Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss
arXiv:2607. 14304v1 Announce Type: cross Abstract: We study sparse random geometric graphs generated by connecting pairs of high-dimensional vectors whose inner product exceeds a threshold.
By Manuel Fernandez V, Yizhe Zhu
arXiv:2608. 03353v1 Announce Type: cross Abstract: For a Markov kernel $T$ with an invariant probability measure $\pi$, we give a self-contained proof of the Markov chain convergence theorem via a criterion called asymptotic equivalence with the target.
By Patrick Forr\'e
arXiv:2604. 14614v2 Announce Type: replace-cross Abstract: We give an algorithm for PAC learning intersections of $k$ halfspaces with a $\rho$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, \rho^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/\rho) \log k})\right)$.
By Shyamal Patel, Santosh Vempala
We study distributionally robust PAC learning for the $0$--$1$-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order $k>1$ and radius $ρ\geq 0$. For hypothesis classes with VC dimension $d$, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors.
arXiv:2602. 20376v3 Announce Type: replace-cross Abstract: We study the problem of maximizing a complex-valued quadratic form over the $K^{\text{th}}$ roots of unity.
By Ria Stevens, Fangshuo Liao, Barbara Su, Thanasis Hadjidimoulas, Jianqiang Li, Anastasios Kyrillidis
arXiv:2409. 08469v4 Announce Type: replace-cross Abstract: We provide finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy ($\mathsf{KSD}$) and Wasserstein-2 metrics.
By Sayan Banerjee, Krishnakumar Balasubramanian, Promit Ghosal