4 papers
Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective
Fangzhou Wu, Sandeep Silwal, Qiuyi +1
KV caching is a fundamental technique for accelerating Large Language Model (LLM) inference by reusing key-value (KV) pairs from previous queries, but its effectiveness under limit…
Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization
Taha El Bakkali, Rayane Bouftini, Qiuyi Zhang +1
We study smooth nonconvex optimization using only noisy pairwise comparisons, without access to gradients or function values. We propose Noisy-Comparison Random Search (NCRS), a si…
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
Sandeep Silwal, David P. Woodruff, Qiuyi Zhang
We study beyond worst-case dimensionality reduction for -sparse vectors. Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: We…
Computing Approximate Sensitivities
Swati Padmanabhan, David P. Woodruff, Qiuyi Zhang
Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offerin…