13 papers
When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Qixin Zhang, Shi Fu, Shengminjie Chen +2
Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algor…
Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomization
Shizhan Cai, Qixin Zhang, Siyuan Ma +3
Bilevel data selection is a fundamental task with numerous applications in machine learning and statistics. A common strategy for tackling this problem is to relax the original bil…
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Shi Fu, Youming Qiao, Dacheng Tao +2
Over the past decade, a growing body of research has shown that -weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural networ…
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Huibo Xu, Shi Fu, Youming Qiao +1
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…
A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over Entails Exponential Queries or Linear Recourse
Shi Fu, Qixin Zhang, Dacheng Tao
Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models dim…
Synchronization Strings over the Optimal Alphabet
Huibo Xu, Shi Fu, Youming Qiao +1
Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subseq…
Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
Huibo Xu, Shi Fu, Qixin Zhang +1
In high-dimensional online prediction, sparse comparators motivate regret bounds that depend on sparsity rather than ambient dimension. Feature priming seeks such adaptation by rew…
Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails
Shi Fu, Huibo Xu, Qixin Zhang +1
Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is , where $w(…
Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection
Qixin Zhang, Wei Huang, Yan Sun +3
Identifying the most representative subset for a close-to-submodular objective while satisfying the predefined partition constraint is a fundamental task with numerous applications…
Near-Oracle KV Selection via Pre-hoc Sparsity for Long-Context Inference
Yifei Gao, Lei Wang, Rong-Cheng Tu +3
A core bottleneck in large language model (LLM) inference is the cost of attending over the ever-growing key-value (KV) cache. Although near-oracle top-k KV selection can preserve…
Time Is All It Takes: Spike-Retiming Attacks on Event-Driven Spiking Neural Networks
Yi Yu, Qixin Zhang, Shuhan Ye +6
Spiking neural networks (SNNs) compute with discrete spikes and exploit temporal structure, yet most adversarial attacks change intensities or event counts instead of timing. We st…
Efficient Differentiable Causal Discovery via Reliable Super-Structure Learning
Pingchuan Ma, Qixin Zhang, Shuai Wang +1
Recently, differentiable causal discovery has emerged as a promising approach to improve the accuracy and efficiency of existing methods. However, when applied to high-dimensional…
Sparse by Rule: Probability-Based N:M Pruning for Spiking Neural Networks
Shuhan Ye, Yi Yu, Qixin Zhang +4
Brain-inspired Spiking neural networks (SNNs) promise energy-efficient intelligence via event-driven, sparse computation, but deeper architectures inflate parameters and computatio…