We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. show new lower bound releasing halfspace continuous domain. Despite this, we give time algorithm releases information queries, slightly relaxed definition of usefulness. Inspired by learning theory, introduce notion data privacy, which call distributional and...

In this article, we demonstrate that, ignoring computational constraints, it is possible to release synthetic databases that are useful for accurately answering large classes of queries while preserving differential privacy. Specifically, give a mechanism privately releases data class over discrete domain with error grows as function the size smallest net approximately representing answers queries. We show in particular implies counting gives guarantees grow only VC-dimension queries, which...

The 2024 Index is our most comprehensive to date and arrives at an important moment when AI's influence on society has never been more pronounced. This year, we have broadened scope extensively cover essential trends such as technical advancements in AI, public perceptions of the technology, geopolitical dynamics surrounding its development. Featuring original data than ever before, this edition introduces new estimates AI training costs, detailed analyses responsible landscape, entirely...

We propose weakening the assumption made when studying price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be computationally hard find), we only selfish so as minimize their own regret. Regret minimization can done via simple, efficient algorithms in many settings where number action choices for each player is exponential natural parameters problem. prove despite our weakened assumptions, several broad classes games,...

There has been substantial work developing simple, efficient no-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an individual can use that give strong guarantees on performance even in adversarially-changing environments. also analyzing properties Nash equilibria routing games. In this paper, we consider the question: if each player game uses strategy, will behavior converge to equilibrium? general games answer...

Consider the following problem: given a metric space, some of whose points are clients, select set at most k facility locations to minimize average distance from clients their nearest facility. This is just well-studied k-median problem, for which many approximation algorithms and hardness results known. Note that objective function encourages opening facilities in areas where there solution, it often possible get good idea located. raises quandary: what if sensitive information we would...

Previous chapter Next Full AccessProceedings Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Differentially Private Combinatorial OptimizationAnupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal TalwarAnupam Talwarpp.1106 - 1125Chapter DOI:https://doi.org/10.1137/1.9781611973075.90PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Consider following problem: given a metric space, some whose points are...

What can we, as users of microdata, formally guarantee to the individuals (or firms) in our dataset, regarding their privacy? We retell a few stories, well-known data-privacy circles, failed anonymization attempts publicly released datasets. then provide mostly informal introduction several ideas from literature on differential privacy, an active computer science that studies formal approaches preserving privacy statistical databases. apply some its insights situations routinely faced by...

We present a new approach for mitigating unfairness in learned classifiers. In particular, we focus on binary classification tasks over individuals from two populations, where, as our criterion fairness, wish to achieve similar false positive rates both and negative populations. As proof of concept, implement empirically evaluate its ability fairness accuracy, using datasets the fields criminal risk assessment, credit, lending, college admissions.

Welcome to the sixth edition of AI Index Report. This year, report introduces more original data than any previous edition, including a new chapter on public opinion, thorough technical performance chapter, analysis about large language and multimodal models, detailed trends in global legislation records, study environmental impact systems, more. The Report tracks, collates, distills, visualizes related artificial intelligence. Our mission is provide unbiased, rigorously vetted, broadly...

We consider a geometric model for the problem of minimizing access control lists (ACLs) in network routers, that also has applications to rectilinear picture compression and figure drawing common graphics software packages. Here goal is create colored pattern within an initially white rectangular canvas, basic operation choose subrectangle paint it single color, overwriting all previous colors rectangle. Rectangle Rule List (RRL) minimization finding shortest list rules needed given pattern....

We consider the problem of designing a survey to aggregate non-verifiable information from privacy-sensitive population: an analyst wants compute some statistic private bits held by each member population, but cannot verify correctness reported participants in his survey. Individuals population are strategic agents with cost for privacy, ie, they not only account payments expect receive mechanism, also their privacy costs any revealed about them mechanism's outcome---the computed as well...

No abstract available.

We present new theoretical results on differentially private data release useful with respect to any target class of counting queries, coupled experimental a variety real world sets. Specifically, we study simple combination the multiplicative weights approach [Hardt and Rothblum, 2010] exponential mechanism [McSherry Talwar, 2007]. The framework allows us maintain improve distribution approximating given set queries. use select those queries most incorrectly tracked by current distribution....

We consider the problem of a data analyst who may purchase an unbiased estimate some statistic from multiple providers. From each provider i, has choice: she that variance chosen finite menu options. Each level cost associated with it, reported (possibly strategically) by provider. The wants to choose minimum set levels, one provider, will let her combine purchased estimators into aggregate estimator at most fixed desired level. Moreover, do so in such way incentivizes providers truthfully...

The traditional notion of generalization---i.e., learning a hypothesis whose empirical error is close to its true error---is surprisingly brittle. As has recently been noted in [DFH+15b], even if several algorithms have this guarantee isolation, the need not hold are composed adaptively. In paper, we study three notions generalization---increasing strength---that robust postprocessing and amenable adaptive composition, examine relationships between them. We call weakest such Robust...

This work studies formal utility and privacy guarantees for a simple multiplicative database transformation, where the data are compressed by random linear or affine reducing number of records substantially, while preserving original input variables.We provide an analysis framework inspired recent concept known as differential privacy. Our goal is to show that, despite general difficulty achieving guarantee, it possible publish synthetic that useful common statistical learning applications....

In an online linear optimization problem, on each period t, algorithm chooses $s_t\in\mathcal{S}$ from a fixed (possibly infinite) set $\mathcal{S}$ of feasible decisions. Nature (who may be adversarial) weight vector $w_t\in\mathbb{R}^n$, and the incurs cost $c(s_t,w_t)$, where c is function that in vector. full-information setting, $w_t$ then revealed to algorithm, bandit only experienced, revealed. The goal perform nearly as well best $s\in\mathcal{S}$ hindsight. Many repeated...

We propose a simple model where individuals in privacy-sensitive population decide whether or not to participate pre-announced noisy computation by an analyst, so that the database itself is endogenously determined individuals' participation choices. The privacy agent receives depends both on announced noise level, as well how many agents choose database. Each has some minimum requirement, and decides based her requirement compares against expectation of she will receive if participates...