检索结果-内蒙古大学图书馆

Universally Instance-Optimal Mechanisms for Private Statistical Estimation 37

学校读者我要写书评

暂无评论

Universally Instance-Optimal Mechanisms for Private Statisti...

37th Annual Conference on Learning Theory, COLT 2024

作者： Asi, Hilal Duchi, John C. Haque, Saminul Li, Zewei Ruan, Feng Apple United States Departments of Statistics and Electrical Engineering Stanford University United States Department of Computer Science Stanford University United States Department of Statistics and Data Science Northwestern University United States

We consider the problem of instance-optimal statistical estimation under the constraint of differential privacy where mechanisms must adapt to the difficulty of the input dataset. We prove a new instance specific lower bound using a new divergence and show it characterizes the local minimax optimal rates for private statistical estimation. We propose two new mechanisms that are universally instance-optimal for general estimation problems up to logarithmic factors. Our first mechanism, the total variation mechanism, builds on the exponential mechanism with stable approximations of the total variation distance, and is universally instance-optimal in the high privacy regime Ε ≤ 1/√n. Our second mechanism, the T-mechanism, is based on the T-estimator framework (Birgé, 2006) using the clipped log likelihood ratio as a stable test: it attains instance-optimal rates for any Ε ≤ 1 up to logarithmic factors. Finally, we study the implications of our results to robust statistical estimation, and show that our algorithms are universally optimal for this problem, characterizing the optimal minimax rates for robust statistical estimation. © 2024 H. Asi, J.C. Duchi, S. Haque, Z. Li & F. Ruan.

关键词：

Resampling methods for private statistical inference

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chadha, Karan Duchi, John C. Kuditipudi, Rohith Departments of Electrical Engineering Departments of Statistics Departments of Computer Science Stanford University United States

We propose two private variants of the non-parametric bootstrap for privately computing confidence sets. Each privately computes the median of results of multiple "little" bootstraps, yielding asymptotic bounds on the coverage error of the resulting confidence sets. For a fixed differential privacy parameter Ε, our methods enjoy the same error rates as the non-private bootstrap to within logarithmic factors in the sample size n. We empirically validate the performance of our methods for mean estimation, median estimation, and logistic regression, and our methods achieve similar coverage accuracy to existing methods (and non-private baselines) while providing notably shorter (about 10×) confidence intervals than previous approaches. Copyright © 2024, The Authors. All rights reserved.

关键词： Machine learning

Accelerated gradient methods for nonconvex optimization: Escape trajectories from strict saddle points and convergence to local minima

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dixit, Rishabh Gürbüzbalaban, Mert Bajwa, Waheed U. Department of Electrical and Computer Engineering Departments of Electrical & Computer Engineering Management Science and Information Systems and Statistics United States Departments of Electrical & Computer Engineering and Statistics

This paper considers the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that have proposed effective algorithms, based on Polyak’s heavy ball method and the Nesterov accelerated gradient method, to achieve convergence to a local minimum of nonconvex functions, this work proposes a broad class of Nesterov-type accelerated methods and puts forth a rigorous study of these methods encompassing the escape from saddle-points and convergence to local minima through a both asymptotic and a nonasymptotic analysis. In the asymptotic regime, this paper answers an open question of whether Nesterov’s accelerated gradient method (NAG) with variable momentum parameter avoids strict saddle points almost surely. This work also develops two metrics of asymptotic rate of convergence and divergence, and evaluates these two metrics for several popular standard accelerated methods such as the NAG, and Nesterov’s accelerated gradient with constant momentum (NCM) near strict saddle points. In the local regime, this work provides an analysis that leads to the "linear" exit time estimates from strict saddle neighborhoods for trajectories of these accelerated methods as well the necessary conditions for the existence of such trajectories. Finally, this work studies a sub-class of accelerated methods that can converge in convex neighborhoods of nonconvex functions with a near optimal rate to a local minima and at the same time this sub-class offers superior saddle-escape behavior compared to that of NAG. Copyright © 2023, The Authors. All rights reserved.

关键词： Gradient methods

Invertibility of Discrete-Time Linear Systems with Sparse Inputs 63

学校读者我要写书评

暂无评论

Invertibility of Discrete-Time Linear Systems with Sparse In...

63rd IEEE Conference on Decision and Control, CDC 2024

作者： Poe, Kyle Mallada, Enrique Vidal, Rene University of Pennsylvania Applied Mathematics and Computational Science Group PA19104 United States Johns Hopkins University Mallada Is with the Department of Electrical and Computer Engineering MD21218 United States University of Pennsylvania Radiology Computer and Information Science Statistics and Data Science Departments of Electrical and Systems Engineering PA19104 United States

ISBN: (纸本)9798350316339

One of the fundamental problems of interest for discrete-time linear systems is whether its input sequence may be recovered given its output sequence, a.k.a. the left inversion problem. Many conditions on the state space geometry, dynamics, and spectral structure of a system have been used to characterize the well-posedness of this problem, without assumptions on the inputs. However, certain structural assumptions, such as input sparsity, have been shown to translate to practical gains in the performance of inversion algorithms, surpassing classical guarantees. Establishing necessary and sufficient conditions for left invertibility of systems with sparse inputs is therefore a crucial step toward understanding the performance limits of system inversion under structured input assumptions. In this work, we provide the first necessary and sufficient characterizations of left invertibility for linear systems with sparse inputs, echoing classic characterizations for standard linear systems. The key insight in deriving these results is in establishing the existence of two novel geometric invariants unique to the sparseinput setting, the weakly unobservable and strongly reachable subspace arrangements. By means of a concrete example, we demonstrate the utility of these characterizations. We conclude by discussing extensions and applications of this framework to several related problems in sparse control. © 2024 IEEE.

关键词： State space methods

A Fast Algorithm for Adaptive Private Mean Estimation

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Duchi, John Haque, Saminul Kuditipudi, Rohith Departments of Statistics Departments of Electrical Engineering Departments of Computer Science Stanford University United States

We design an (Ε, δ)-differentially private algorithm to estimate the mean of a d-variate distribution, with unknown covariance Σ, that is adaptive to Σ. To within polylogarithmic factors, the estimator achieves optimal rates of convergence with respect to the induced Mahalanobis norm k·kΣ, takes time Oe(nd2) to compute, has near linear sample complexity for sub-Gaussian distributions, allows Σ to be degenerate or low rank, and adaptively extends beyond sub-Gaussianity. Prior to this work, other methods required exponential computation time or the superlinear scaling n = Ω(d3/2) to achieve non-trivial error with respect to the norm k·kΣ © 2023, CC BY.

关键词：

A fast and slightly robust covariance estimator

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Duchi, John Haque, Saminul Kuditipudi, Rohith Departments of Statistics Stanford University United States Departments of Electrical Engineering Stanford University United States Departments of Computer Science Stanford University United States

Let (formula presented) from a distribution P with mean zero and covariance Σ. Given a dataset X such that (formula presented), we are interested in finding an efficient estimator Σˆ that achieves (formula presented). We focus on the low contamination regime Ε = o(1/√d). In this regime, prior work required either Ω(d3/2) samples or runtime that is exponential in d. We present an algorithm that, for subgaussian data, has near-linear sample complexity n = Ω͂(d) and runtime (formula presented), where ω is the matrix multiplication exponent. We also show that this algorithm works for heavy-tailed data with near-linear sample complexity, but in a smaller regime of Ε. Concurrent to our work, Diakonikolas et al. [2024] give Sum-of-Squares estimators that achieve similar sample complexity but with large polynomial runtime. © 2025, CC BY.

关键词：

A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Features

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zeger, Emi Wang, Yifei Mishkin, Aaron Ergen, Tolga Candès, Emmanuel Pilanci, Mert Stanford University United States Department of Electrical Engineering Department of Computer Science Departments of Statistics and Mathematics

We prove that training neural networks on 1-D data is equivalent to solving convex Lasso problems with discrete, explicitly defined dictionary matrices. We consider neural networks with piecewise linear activations and depths ranging from 2 to an arbitrary but finite number of layers. We first show that two-layer networks with piecewise linear activations are equivalent to Lasso models using a discrete dictionary of ramp functions, with breakpoints corresponding to the training data points. In certain general architectures with absolute value or ReLU activations, a third layer surprisingly creates features that reflect the training data about themselves. Additional layers progressively generate reflections of these reflections. The Lasso representation provides valuable insights into the analysis of globally optimal networks, elucidating their solution landscapes and enabling closed-form solutions in certain special cases. Numerical results show that reflections also occur when optimizing standard deep networks using standard non-convex optimizers. Additionally, we demonstrate our theory with autoregressive time series models. Copyright © 2024, The Authors. All rights reserved.

关键词： Deep neural networks

An information-theoretic lower bound in time-uniform estimation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Duchi, John C. Haque, Saminul Departments of Statistics and Electrical Engineering Stanford University United States Department of Computer Science Stanford University United States

We present an information-theoretic lower bound for the problem of parameter estimation with time-uniform coverage guarantees. Via a new a reduction to sequential testing, we obtain stronger lower bounds that capture the hardness of the time-uniform setting. In the case of location model estimation, logistic regression, and exponential family models, our Ω(Formula Presented) lower bound is sharp to within constant factors in typical settings. © 2024, CC BY.

关键词： Information theory

Calibrated multiple-output quantile regression with representation learning

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research

The Journal of Machine Learning Research 2023年第1期24卷 923-970页

作者： Shai Feldman Stephen Bates Yaniv Romano Department of Computer Science Technion — Israel Institute of Technology Technion City Haifa Israel Departments of Electrical Engineering and Computer Science and of Statistics University of California Berkeley Berkeley CA Departments of Electrical and Computer Engineering and of Computer Science Technion — Israel Institute of Technology Technion City Haifa Israel

We develop a method to generate predictive regions that cover a multivariate response variable with a user-specified probability. Our work is composed of two components. First, we use a deep generative model to learn a representation of the response that has a unimodal distribution. Existing multiple-output quantile regression approaches are effective in such cases, so we apply them on the learned representation, and then transform the solution to the original space of the response. This process results in a flexible and informative region that can have an arbitrary shape, a property that existing methods lack. Second, we propose an extension of conformal prediction to the multivariate response setting that modifies any method to return sets with a pre-specified coverage level. The desired coverage is theoretically guaranteed in the finite-sample case for any distribution. Experiments conducted on both real and synthetic data show that our method constructs regions that are significantly smaller compared to existing techniques.

关键词： conformal prediction uncertainty quantification quantile regression multiple regression variational auto-encoder