Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| DOI | 10.1007/S10107-023-01953-5 | ||||
| Año | 2023 | ||||
| Tipo | artículo de investigación |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that a stochastic approximation variant of these algorithms attains risk bounds vanishing as a function of the dataset size, with respect to the strong gap function; and a sampling with replacement variant achieves optimal risk bounds with respect to a weak gap function. We also show lower bounds of the same order on weak gap function. Hence, our algorithms are optimal. Key to our analysis is the investigation of algorithmic stability bounds, both of which are new even in the nonprivate case. The dependence of the running time of the sampling with replacement algorithms, with respect to the dataset size n, is n(2) for NSEG and O (n(3/2)) for NISPP.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Boob, Digvijay | - |
Southern Methodist Univ - Estados Unidos
Southern Methodist University - Estados Unidos Bobby B. Lyle School of Engineering - Estados Unidos |
| 2 | Guzman, Cristobal | Hombre |
Pontificia Universidad Católica de Chile - Chile
|
| Fuente |
|---|
| National Science Foundation |
| Fondo Nacional de Desarrollo Científico y Tecnológico |
| Institut national de recherche en informatique et en automatique (INRIA) |
| University of Twente |
| SCELC, Statewide California Electronic Library Consortium |
| Agradecimiento |
|---|
| Open access funding provided by SCELC, Statewide California Electronic Library Consortium |
| CG would like to thank Roberto Cominetti for valuable discussions on stochastic variational inequalities and nonexpansive iterations. Part of this work was done while CG was at the University of Twente. |