More Like this

1. Central Limit Theorems and Online Inference for Quantiles by Stochastic Gradient Descent

   Wei, Ziyang; Li, Jiaqi; Chen, Likai; Wu, Wei Biao (May 2026, IEEE transactions on information theory)

   Ding, Jie (Ed.)

   This paper develops asymptotic theory for quantile estimation via stochastic gradient descent (SGD) with a constant learning rate. The quantile loss function is neither smooth nor strongly convex. Beyond conventional perspectives and techniques, we view quantile SGD iteration as an irreducible, periodic, and positive recurrent Markov chain, which cyclically converges to its unique stationary distribution regardless of the arbitrarily fixed initialization. To derive the exact form of the stationary distribution, we analyze the structure of its characteristic function by exploiting the stationary equation. We also derive tight bounds for its moment generating function (MGF) and tail probabilities. Synthesizing the aforementioned approaches, we prove that the centered and standardized stationary distribution converges to a Gaussian distribution as the learning rate goes to 0. This finding provides the first central limit theorem (CLT)-type theoretical guarantees for the quantile SGD estimator with constant learning rates. We further propose a recursive algorithm to construct confidence intervals of the estimators with statistical guarantees. Numerical studies demonstrate the effective finite-sample performance of the online estimator and inference procedure. The theoretical tools developed in this study are of independent interest for investigating general SGD algorithms formulated as Markov chains, particularly in non-strongly convex and non-smooth settings. 

   more » « less
2. Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity

   https://doi.org/10.1145/3801901  

   Liu, Kaiwen; Zhang, Qin (May 2026, Proceedings of the ACM on Management of Data)

   We propose a novel framework for statistical estimation on noisy datasets. Within this framework, we focus on the frequency moments (F_p) problem and demonstrate that it is possible to approximateF_pof the unknown ground-truth dataset using sublinear space in the data stream model and sublinear communication in the coordinator model, provided that the approximation ratio is parameterized by a data-dependent quantity, which we call theF_p-mismatch-ambiguity. We also establish a set of lower bounds, which are tight in terms of the input size. Our results yield several interesting insights:-In the data stream model, theF_pproblem is inherently more difficult in the noisy setting than in the noiseless one. In particular, whileF₂can be approximated in logarithmic space in terms of the input size in the noiseless setting, any algorithm forF₂in the noisy setting requires polynomial space. -In the coordinator model, in sharp contrast to the noiseless case, achieving polylogarithmic communication in the input size is generally impossible forF_punder noise. However, when theF_pmismatch ambiguity falls below a certain threshold, it becomes possible to achieve communication that is entirely independent of the input size. 

   more » « less
3. Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure

   https://doi.org/10.1145/3786680  

   Liu, Shuainan; Ji, Tianxi; Fang, Zhongshuo; Wei, Lu; Li, Pan (April 2026, Proceedings of the ACM on Management of Data)

   Noise perturbation is one of the most fundamental approaches for achieving (ε,δ)-differential privacy (DP) guarantees when releasing the result of a query or function ƒ(•)∈R^Mevaluated on a sensitive datasetx. In this approach, calibrated noisen∈ R^Mis used to obscure the difference vectorf(x) 0 f(x'), wherex' is known as a neighboring dataset. A DP guarantee is obtained by studying the tail probability bound of a privacy loss random variable (PLRV), defined as the Radon-Nikodym derivative between two distributions. Whennfollows a multivariate Gaussian distribution, the PLRV is characterized as a specific univariate Gaussian. In this paper, we propose a novel scheme to generatenby leveraging the fact that the perturbation noise is typically spherically symmetric (i.e., the distribution is rotationally invariant around the origin). The new noise generation scheme allows us to investigate the privacy loss from a geometric perspective and express the resulting PLRV using a product measure, W x U; measureWis related to a radius random variable controlling the magnitude ofn, while measureUinvolves a directional random variable governing the angle betweennand the difference ƒ(x)-ƒ(x'). We derive a closed-form moment bound on the product measure to prove (ε,δ)-DP. Under the same (ε,δ)-DP guarantee, our mechanism yields a smaller expected noise magnitude than the classic Gaussian noise in high dimensions, thereby significantly improving the utility of the noisy result ƒ(x)+n. To validate this, we consider privacy-preserving convex and non-convex empirical risk minimization (ERM) problems in high dimensional space. We propose leveraging our developed noise in output perturbation, objective perturbation, and gradient perturbation to establish DP guarantees when solving ERMs. Experiments on multiple datasets show that our method achieves significant utility improvements for convex ERM models (e.g., regression and SVM) under the same privacy guarantees. For non-convex models (e.g., neural networks), it provides substantially stronger privacy guarantees under comparable utility. Code Repository: https://github.com/issleepgroup/Product-Noise-ERM 

   more » « less
4. Calibration method for a multi-focus microscopic 3D imaging system

   https://doi.org/10.1364/OL.498283  

   Chen, Liming; Xiang, Wang; Zhang, Song (January 2023, Optics Letters)

   This Letter presents a novel, to the best of our knowledge, method to calibrate multi-focus microscopic structured-light three-dimensional (3D) imaging systems with an electrically adjustable camera focal length. We first leverage the conventional method to calibrate the system with a reference focal lengthf₀. Then we calibrate the system with other discrete focal lengthsf_iby determining virtual features on a reconstructed white plane usingf₀. Finally, we fit the polynomial function model using the discrete calibration results forf_i. Experimental results demonstrate that our proposed method can calibrate the system consistently and accurately. 

   more » « less
5. Surrogate Losses for Online Learning of Stepsizes in Stochastic Non-Convex Optimization

   Zhuang, Zhenxun; Cutkosky, Ashok; Orabona, Francesco (June 2019, Proceedings of the 36th International Conference on Machine Learning)

   Stochastic Gradient Descent (SGD) has played a central role in machine learning. However, it requires a carefully hand-picked stepsize for fast convergence, which is notoriously tedious and time-consuming to tune. Over the last several years, a plethora of adaptive gradient-based algorithms have emerged to ameliorate this problem. In this paper, we propose new surrogate losses to cast the problem of learning the optimal stepsizes for the stochastic optimization of a non-convex smooth objective function onto an online convex optimization problem. This allows the use of no-regret online algorithms to compute optimal stepsizes on the fly. In turn, this results in a SGD algorithm with self-tuned stepsizes that guarantees convergence rates that are automatically adaptive to the level of noise. 

   more » « less