The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a \log(K) factor, where K is the number of groups. In this work, we venture beyond the minimax perspective via a novel notion of sparsity that we dub (\lambda, \beta)-sparsity. In short, this condition means that at any parameter \theta, there is a set of at most \beta groups whose risks at \theta all are at least \lambda larger than the risks of the other groups. To find an \epsilon-optimal \theta, we show via a novel algorithm and analysis that the \epsilon-dependent term in the sample complexity can swap a linear dependence on K for a linear dependence on the potentially much smaller \beta. This improvement leverages recent progress in sleeping bandits, showing a fundamental connection between the two-player zero-sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. We next show an adaptive algorithm which, up to log factors, gets a sample complexity bound that adapts to the best (\lambda, \beta)-sparsity condition that holds. We also show how to get a dimension-free semi-adaptive sample complexity bound with a computationally efficient method. Finally, we demonstrate the practicality of the (\lambda, \beta)-sparsity condition and the improved sample efficiency of our algorithms on both synthetic and real-life datasets.

Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. The corresponding lower bounds are based on a novel block-diagonal construction that is combined with existing DP mean estimation lower bounds. Next, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Furthermore, by introducing novel analyses of bias reduction in mean estimation and randomly-stopped biased SGD we obtain nearly dimension-independent rates for near-stationary points for the empirical risk in nonconvex settings under approximate-DP.

"Generating differentially private (DP) synthetic data that closely resembles the original private data is a scalable way to mitigate privacy concerns in the current data-driven world. In contrast to current practices that train customized models for this task, we aim to generate DP Synthetic Data via APIs (DPSDA), where we treat foundation models as blackboxes and only utilize their inference APIs. Such API-based, training-free approaches are easier to deploy as exemplified by the recent surge in the number of API-based apps. These approaches can also leverage the power of large foundation models which are only accessible via their inference APIs. However, this comes with greater challenges due to strictly more restrictive model access and the need to protect privacy from the API provider. In this paper, we present a new framework called Private Evolution (PE) to solve this problem and show its initial promise on synthetic images. Surprisingly, PE can match or even outperform state-of-the-art (SOTA) methods without any model training. For example, on CIFAR10 (with ImageNet as the public data), we achieve FID <= 7.9 with privacy cost {\epsilon} = 0.67, significantly improving the previous SOTA from {\epsilon} = 32. We further demonstrate the promise of applying PE on large foundation models such as Stable Diffusion to tackle challenging private datasets with a small number of high-resolution images. The code and data are released at this https URL."

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 derive new mixing time bounds for the projected LA which are, in some important cases, dimension-free and poly-logarithmic on the accuracy, closely matching the existing results in the smooth convex case. Additionally, we establish new upper bounds for the privacy curve of the subsampled noisy SGD algorithm. These bounds show a crucial dependency on the regularity of gradients, and are useful for a wide range of convex losses beyond the smooth case. Our analysis relies on a suitable extension of the Privacy Amplification by Iteration (PABI) framework (Feldman et al., 2018; Altschuler and Talwar, 2022, 2023) to noisy iterations whose gradient map is not necessarily nonexpansive. This extension is achieved by designing an optimization problem which accounts for the best possible Rényi divergence bound obtained by an application of PABI, where the tractability of the problem is crucially related to the modulus of continuity of the associated gradient mapping. We show that, in several interesting cases -- including the nonsmooth convex, weakly smooth and (strongly) dissipative -- such optimization problem can be solved exactly and explicitly. This yields the tightest possible PABI-based bounds, where our results are either new or substantially sharper than those in previous works.

We develop algorithms for the optimization of convex objectives that have Hölder continuous q-th derivatives by using a q-th order oracle, for any q \geq 1. Our algorithms work for general norms under mild conditions, including the \ell_p-settings for 1\leq p\leq \infty. We can also optimize structured functions that allow for inexactly implementing a non-Euclidean ball optimization oracle. We do this by developing a non-Euclidean inexact accelerated proximal point method that makes use of an \emph{inexact uniformly convex regularizer}. We show a lower bound for general norms that demonstrates our algorithms are nearly optimal in high-dimensions in the black-box oracle model for \ell_p-settings and all q \geq 1, even in randomized and parallel settings. This new lower bound, when applied to the first-order smooth case, resolves an open question in parallel convex optimization.

Publisher: SIAM Journal on Optimization  Link>

ABSTRACT

Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization in the stochastic setting. This problem corresponds to the minimization of the sum of a (weakly) smooth function endowed with a stochastic first-order oracle and a structured uniformly convex (possibly nonsmooth and non-Lipschitz) regularization term. Despite intensive work on closely related settings, prior to our work no complexity bounds for this problem were known. We close this gap by providing novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems. We conclude by providing numerical results comparing our methods to the state of the art.

We introduce PREM (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that achieves a {\em relative} error guarantee for statistical queries under (ε,δ) -differential privacy (DP). Namely, for a domain X , a family F of queries f:X→{0,1} , and ζ>0 , our framework yields a mechanism that on input dataset D∈Xn outputs a synthetic dataset Dˆ∈Xn such that all statistical queries in F on D namely ∑x∈Df(x) for f∈F , are within a 1±ζ {\em multiplicative} factor of the corresponding value on Dˆ up to an {\em additive} error that is polynomial in log|F| , log|X| , logn , log(1/δ) , 1/ε , and 1/ζ . In contrast, any (ε,δ) -DP mechanism is known to require worst-case additive error that is polynomial in at least one of n,|F| , or |X| . We complement our algorithm with nearly matching lower bounds.

In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational inequalities (SVI) under the constraint of ( ϵ , δ ) -differential privacy (DP) in both Euclidean and non-Euclidean setups. We first consider Lipschitz convex-concave SSPs in the ℓ p / ℓ q setup, p , q ∈ [ 1 , 2 ] . That is, we consider the case where the primal problem has an ℓ p -setup (i.e., the primal parameter is constrained to an ℓ p bounded domain and the loss is ℓ p -Lipschitz with respect to the primal parameter) and the dual problem has an ℓ q setup. Here, we obtain a bound of ~ O ( 1 √ n + √ d n ϵ ) on the strong SP-gap, where n is the number of samples and d is the dimension. This rate is nearly optimal for any p , q ∈ [ 1 , 2 ] . Without additional assumptions, such as smoothness or linearity requirements, prior work under DP has only obtained this rate when p = q = 2 (i.e., only in the Euclidean setup). Further, existing algorithms have each only been shown to work for specific settings of p and q and under certain assumptions on the loss and the feasible set, whereas we provide a general algorithm for DP SSPs whenever p , q ∈ [ 1 , 2 ] . Our result is obtained via a novel analysis of the recursive regularization algorithm. In particular, we develop new tools for analyzing generalization, which may be of independent interest. Next, we turn our attention towards SVIs with a monotone, bounded and Lipschitz operator and consider ℓ p -setups, p ∈ [ 1 , 2 ] . Here, we provide the first analysis which obtains a bound on the strong VI-gap of ~ O ( 1 √ n + √ d n ϵ ) . For p − 1 = Ω ( 1 ) , this rate is near optimal due to existing lower bounds. To obtain this result, we develop a modified version of recursive regularization. Our analysis builds on the techniques we develop for SSPs as well as employing additional novel components which handle difficulties arising from adapting the recursive regularization framework to SVIs

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) with either labeled or unlabeled public data. For complete/labeled public data, we show that any -PA-DP has excess risk , where is the dimension, is the number of public samples, is the number of private samples, and . These lower bounds are established via our new lower bounds for PA-DP mean estimation, which are of a similar form. Up to constant factors, these lower bounds show that the simple strategy of either treating all data as private or discarding the private data, is optimal. We also study PA-DP supervised learning with \textit{unlabeled} public samples. In contrast to our previous result, we here show novel methods for leveraging public data in private supervised learning. For generalized linear models (GLM) with unlabeled public data, we show an efficient algorithm which, given unlabeled public samples, achieves the dimension independent rate . We develop new lower bounds for this setting which shows that this rate cannot be improved with more public samples, and any fewer public samples leads to a worse rate. Finally, we provide extensions of this result to general hypothesis classes with finite fat-shattering dimension with applications to neural networks and non-Euclidean geometries.

Tracking the solution of time-varying variational inequalities is an important problem with applications in game theory, optimization, and machine learning. Existing work considers time-varying games or time-varying optimization problems. For strongly convex optimization problems or strongly monotone games, these results provide tracking guarantees under the assumption that the variation of the time-varying problem is restrained, that is, problems with a sublinear solution path. In this work we extend existing results in two ways: In our first result, we provide tracking bounds for (1) variational inequalities with a sublinear solution path but not necessarily monotone functions, and (2) for periodic time-varying variational inequalities that do not necessarily have a sublinear solution path-length. Our second main contribution is an extensive study of the convergence behavior and trajectory of discrete dynamical systems of periodic time-varying VI. We show that these systems can exhibit provably chaotic behavior or can converge to the solution. Finally, we illustrate our theoretical results with experiments.