Subsampled Optimization: Statistical Guarantees, Mean Squared Error Approximation, and Sampling Method
For optimization on large-scale data, exactly calculating its solution may be computationally difficulty because of the large size of the data. In this paper we consider subsampled optimization for fast approximating the exact solution. In this approach, one gets a surrogate dataset by sampling from the full data, and then obtains an approximate solution by solving the subsampled optimization based on the surrogate. One main theoretical contributions are to provide the asymptotic properties of the approximate solution with respect to the exact solution as statistical guarantees, and to rigorously derive an accurate approximation of the mean squared error (MSE) and an approximately unbiased MSE estimator. These results help us better diagnose the subsampled optimization in the context that a confidence region on the exact solution is provided using the approximate solution. The other consequence of our results is to propose an optimal sampling method, Hessian-based sampling, whose probabilities are proportional to the norms of Newton directions. Numerical experiments with least-squares and logistic regression show promising performance, in line with our results.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Statistical Guarantees for Link Prediction using Graph Neural Networks
This paper derives statistical guarantees for the performance of Graph Neural Networks (GNNs) in link prediction tasks on graphs generated by a graphon. We propose a linear GNN architecture (LG-GNN) that produces consist…
Link PredictionPredictionData-Driven Prediction with Stochastic Data: Confidence Regions and Minimum Mean-Squared Error Estimates
Recently, direct data-driven prediction has found important applications for controlling unknown systems, particularly in predictive control. Such an approach provides exact prediction using behavioral system theory when…
PredictionvalidDebiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions
Random sampling is a fundamental tool in modern machine learning and numerical linear algebra for reducing the computational cost of large-scale matrix problems. Existing analyses, however, rely primarily on subspace emb…
Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guarantees
Optimization problems over discrete or quantized variables are very challenging in general due to the combinatorial nature of their search space. Piecewise-affine regularization (PAR) provides a flexible modeling and com…
Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition
We consider the problem of computing tight privacy guarantees for the composition of subsampled differentially private mechanisms. Recent algorithms can numerically compute the privacy parameters to arbitrary precision b…