1 citations · 1 across the 15 of their papers we have counts for
17 papers
Near-Optimal Acceleration for Smooth / Nondual Convex First-Order Oracle Optimization
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1
We study the optimization of convex objectives with -Hölder-continuous gradients in over , . (MG26) provides selectors with a movement bound fo…
Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
David Martínez-Rubio, Cristóbal Guzmán
We study efficient algorithms for realizing the first-order oracle complexity of optimization of -Lipschitz convex functions with respect to the -norm over an $\ell_{p…
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1
We study first-order black-box convex optimization over an -ball for objectives Lipschitz in the -norm, solving in the affirmative the nonsmooth version of the COLT…
Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio
We study the oracle complexity of computing a point with small fixed-point residual , for a general norm and a self-map of a compact convex set.…
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth…
Computational Hardness of Private Coreset
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
We study the problem of differentially private (DP) computation of coreset for the -means objective. For a given input set of points, a coreset is another set of points such tha…
How to DP-fy Your Data: A Practical Guide to Generating Synthetic Data With Differential Privacy
Natalia Ponomareva, Zheng Xu, H. Brendan McMahan +12
High quality data is needed to unlock the full potential of AI for end users. However finding new sources of such data is getting harder: most publicly-available human generated da…
PREM: Privately Answering Statistical Queries with Relative Error
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +4
We introduce (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a relative error guarantee for stati…
Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity
Mario Bravo, Juan P. Flores-Mella, Cristóbal Guzmán
We study the mixing time of the projected Langevin algorithm (LA) and the privacy curve of noisy Stochastic Gradient Descent (SGD), beyond nonexpansive iterations. Specifically, we…
Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry
Raef Bassily, Cristóbal Guzmán, Michael Menart
In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational inequalities (SVI) under the constraint of -differential pri…
Non-Euclidean High-Order Smooth Convex Optimization
Juan Pablo Contreras, Cristóbal Guzmán, David Martínez-Rubio
We develop algorithms for the optimization of convex objectives that have Hölder continuous -th derivatives by using a -th order oracle, for any . Our algorithms wo…
Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
Quan Nguyen, Nishant A. Mehta, Cristóbal Guzmán
The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a factor, where is the number of groups. In this work, we…
Tracking solutions of time-varying variational inequalities
Hédi Hadiji, Sarah Sachs, Cristóbal Guzmán
Tracking the solution of time-varying variational inequalities is an important problem with applications in game theory, optimization, and machine learning. Existing work considers…
Differentially Private Optimization with Sparse Gradients
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +2
Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optim…
Public-data Assisted Private Stochastic Optimization: Power and Limitations
Enayat Ullah, Michael Menart, Raef Bassily +2
We study the limits and capability of public-data assisted differentially private (PA-DP) algorithms. Specifically, we focus on the problem of stochastic convex optimization (SCO)…
Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective
Jelena Diakonikolas, Cristóbal Guzmán
We initiate the study of nonsmooth optimization problems under bounded local subgradient variation, which postulates bounded difference between (sub)gradients in small local region…
Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems
Tomás González, Cristóbal Guzmán, Courtney Paquette
We study the problem of differentially-private (DP) stochastic (convex-concave) saddle-points in the setting. We propose -DP algorithms based on stochast…