18 citations · 42 across the 16 of their papers we have counts for
18 papers
Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
Devansh Gupta, Cristóbal Guzman, Enayat Ullah
Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory.…
Calibeating for general proper losses: A Bregman divergence approach
Maximilian Fichtl, Cristóbal Guzmán, Nishant A. Mehta
This work introduces a general framework for calibeating based on regret minimization. As compared to Foster and Hart's seminal calibeating work which had specialized treatments of…
Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates
Michael Menart, Enayat Ullah, Raman Arora +2
We study private empirical risk minimization (ERM) problem for losses satisfying the -Kurdyka-Łojasiewicz (KL) condition. The Polyak-Łojasiewicz (PL) condition is a special…
Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap
Raef Bassily, Cristóbal Guzmán, Michael Menart
We show that convex-concave Lipschitz stochastic saddle point problems (also known as stochastic minimax optimization) can be solved under the constraint of -differential pr…
Optimal Algorithms for Stochastic Complementary Composite Minimization
Alexandre d'Aspremont, Cristóbal Guzmán, Clément Lezane
Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization in the stochastic setting. This problem corresponds to the m…
Faster Rates of Convergence to Stationary Points in Differentially Private Optimization
Raman Arora, Raef Bassily, Tomás González +3
We study the problem of approximating stationary points of Lipschitz and smooth functions under -differential privacy (DP) in both the finite-sum and stochastic se…
Differentially Private Generalized Linear Models Revisited
Raman Arora, Raef Bassily, Cristóbal Guzmán +2
We study the problem of -differentially private learning of linear predictors with convex losses. We provide results for two subclasses of loss functions. The first case is…
Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions
Xufeng Cai, Chaobing Song, Cristóbal Guzmán +1
We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel varian…
Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness
Sarah Sachs, Hédi Hadiji, Tim van Erven +1
Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamen…
Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
Raef Bassily, Cristóbal Guzmán, Michael Menart
We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs…
Best-Case Lower Bounds in Online Learning
Cristóbal Guzmán, Nishant A. Mehta, Ali Mortazavi
Much of the work in online learning focuses on the study of sublinear upper bounds on the regret. In this work, we initiate the study of best-case lower bounds in online convex opt…
An Optimal Algorithm for Strict Circular Seriation
Santiago Armstrong, Cristóbal Guzmán, Carlos A. Sing-Long
We study the problem of circular seriation, where we are given a matrix of pairwise dissimilarities between objects, and the goal is to find a {\em circular order} of the objec…
Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems
Digvijay Boob, Cristóbal Guzmán
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 priva…
The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
Siqi Zhang, Junchi Yang, Cristóbal Guzmán +2
This paper studies the complexity for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) smooth minimax problems, in both general and averaged smooth finit…
Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Raef Bassily, Cristóbal Guzmán, Anupama Nandi
Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex…
Complementary Composite Minimization, Small Gradients in General Norms, and Applications
Jelena Diakonikolas, Cristóbal Guzmán
Composite minimization is a powerful framework in large-scale convex optimization, based on decoupling of the objective function into terms with structurally different properties a…
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán +1
Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. A…
An Optimal Affine Invariant Smooth Minimization Algorithm
Alexandre d'Aspremont, Cristóbal Guzmán, Martin Jaggi
We formulate an affine invariant implementation of the accelerated first-order algorithm in Nesterov (1983). Its complexity bound is proportional to an affine invariant regularity…