Over the past decade, a growing body of research has shown that $\gamma$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $\gamma$-weakly submodular function subject to a general matro...
Shi Fu, Youming Qiao, Da-Cheng Tao et al.· 0 citations
Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We determine how finite graph structure controls their sharp spectral growth. For every fixed simple graph shape in the dense Rademacher model...
Hui-Bo Xu, Shi Fu, Youming Qiao et al.· 0 citations
This work proves that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is 1-1/e-\varepsilon, and determines the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$ for weighted coverage with weighted coverage with $O(\varepsilon^{-1})$ recourse.
Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)^2$, where $w(A)$ is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law...
Shi Fu, Hui-Bo Xu, Qi-Xin Zhang et al.· 0 citations
This analysis identifies a common obstruction: cheap nuisance interpolation causes the refit to underweight the truly predictive coordinate, and an exact target-mass identity and a two-sign argument turn this effect into clipped prediction loss.
Huibo Xu, Shi Fu, Qixin Zhang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
