File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Jointly Private Convex Programming

TitleJointly Private Convex Programming
Authors
Issue Date2016
PublisherSociety for Industrial and Applied Mathematics (SIAM).
Citation
The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA., 10-12 January 2016. In Conference Proceedings, 2016, p. 580-599 How to Cite?
AbstractWe present a general method for approximately solving convex programs defined by private information from agents, when the solution can be naturally partitioned among the agents. This class of problems includes multi-commodity flow problems, general allocation problems, and multi-dimensional knapsack problems, among other examples. The accuracy of our algorithm depends on the number of coupling constraints, which bind multiple agents. On the other hand, our accuracy is nearly independent of the number of variables, and in many cases, actually improves as the number of agents increases. A special case of our result (solving general allocation problems beyond 'Gross Substitute' preferences) resolves the main open problem from [Hsu et al. STOC 2014]. We also consider strategic agents who have preferences over their part of the solution. For any convex program in our class that maximizes social welfare, we show how to create an approximately dominant strategy truthful mechanism, approximately maximizing welfare. The central idea is to charge agents prices based on the approximately optimal dual variables, which are themselves computed under differential privacy. Our results substantially broaden the class of problems that are known to be solvable under privacy and/or incentive constraints.
Persistent Identifierhttp://hdl.handle.net/10722/232173
ISBN

 

DC FieldValueLanguage
dc.contributor.authorHsu, J-
dc.contributor.authorHuang, Z-
dc.contributor.authorRoth, A-
dc.contributor.authorWu, ZS-
dc.date.accessioned2016-09-20T05:28:13Z-
dc.date.available2016-09-20T05:28:13Z-
dc.date.issued2016-
dc.identifier.citationThe 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA., 10-12 January 2016. In Conference Proceedings, 2016, p. 580-599-
dc.identifier.isbn978-151081967-2-
dc.identifier.urihttp://hdl.handle.net/10722/232173-
dc.description.abstractWe present a general method for approximately solving convex programs defined by private information from agents, when the solution can be naturally partitioned among the agents. This class of problems includes multi-commodity flow problems, general allocation problems, and multi-dimensional knapsack problems, among other examples. The accuracy of our algorithm depends on the number of coupling constraints, which bind multiple agents. On the other hand, our accuracy is nearly independent of the number of variables, and in many cases, actually improves as the number of agents increases. A special case of our result (solving general allocation problems beyond 'Gross Substitute' preferences) resolves the main open problem from [Hsu et al. STOC 2014]. We also consider strategic agents who have preferences over their part of the solution. For any convex program in our class that maximizes social welfare, we show how to create an approximately dominant strategy truthful mechanism, approximately maximizing welfare. The central idea is to charge agents prices based on the approximately optimal dual variables, which are themselves computed under differential privacy. Our results substantially broaden the class of problems that are known to be solvable under privacy and/or incentive constraints.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics (SIAM).-
dc.relation.ispartofAnnual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 Proceedings-
dc.rights27th Annual ACM-SIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.-
dc.titleJointly Private Convex Programming-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.natureLink_to_subscribed_fulltext-
dc.identifier.doi10.1137/1.9781611974331.ch43-
dc.identifier.scopuseid_2-s2.0-84963542261-
dc.identifier.hkuros263131-
dc.identifier.spage580-
dc.identifier.epage599-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 160926-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats