Timezone: »
A soft-max function has two main efficiency measures: (1) approximation - which corresponds to how well it approximates the maximum function, (2) smoothness - which shows how sensitive it is to changes of its input. Our goal is to identify the optimal approximation-smoothness tradeoffs for different measures of approximation and smoothness. This leads to novel soft-max functions, each of which is optimal for a different application. The most commonly used soft-max function, called exponential mechanism, has optimal tradeoff between approximation measured in terms of expected additive approximation and smoothness measured with respect to Renyi Divergence. We introduce a soft-max function, called piece-wise linear soft-max, with optimal tradeoff between approximation, measured in terms of worst-case additive approximation and smoothness, measured with respect to l_q-norm. The worst-case approximation guarantee of the piece-wise linear mechanism enforces sparsity in the output of our soft-max function, a property that is known to be important in Machine Learning applications Martins et al. 16, Laha et al. 18 and is not satisfied by the exponential mechanism. Moreover, the l_q-smoothness is suitable for applications in Mechanism Design and Game Theory where the piece-wise linear mechanism outperforms the exponential mechanism. Finally, we investigate another soft-max function, called power mechanism, with optimal tradeoff between expected multiplicative approximation and smoothness with
respect to the Renyi Divergence, which provides improved theoretical and practical results in differentially private submodular optimization.
Author Information
Alessandro Epasto (Google)

I am a staff research scientist at Google, New York working in the Google Research Algorithms and Optimization team lead by Vahab Mirrokni. I received a Ph.D in computer science from Sapienza University of Rome, where I was advised by Professor Alessandro Panconesi and supported by the Google Europe Ph.D. Fellowship in Algorithms, 2011. I was also a post-doc at the department of computer science of Brown University in Providence (RI), USA where I was advised by Professor Eli Upfal. My research interests include algorithmic problems in machine learning and data mining, in particular in the areas of clustering, privacy, and large scale graphs analysis.
Mohammad Mahdian (Google Research)
Vahab Mirrokni (Google Research NYC)
Emmanouil Zampetakis (Massachusetts Institute of Technology)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Poster: Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions »
Thu. Dec 10th 05:00 -- 07:00 PM Room Poster Session 5 #1672
More from the Same Authors
-
2022 : Scalable and Improved Algorithms for Individually Fair Clustering »
Mohammadhossein Bateni · Vincent Cohen-Addad · Alessandro Epasto · Silvio Lattanzi -
2022 : Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank »
Alessandro Epasto · Vahab Mirrokni · Bryan Perozzi · Anton Tsitsulin · Peilin Zhong -
2023 Poster: $k$-Means Clustering with Distance-Based Privacy »
Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2023 Poster: Private estimation algorithms for stochastic block models and mixture models »
Hongjie Chen · Vincent Cohen-Addad · Tommaso d'Orsi · Alessandro Epasto · Jacob Imola · David Steurer · Stefan Tiegel -
2023 Poster: Learning Exponential Families from Truncated Samples »
Jane Lee · Andre Wibisono · Emmanouil Zampetakis -
2022 Poster: Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank »
Alessandro Epasto · Vahab Mirrokni · Bryan Perozzi · Anton Tsitsulin · Peilin Zhong -
2022 Poster: Near-Optimal Private and Scalable $k$-Clustering »
Vincent Cohen-Addad · Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2022 Poster: Learning and Covering Sums of Independent Random Variables with Unbounded Support »
Alkis Kalavasis · Konstantinos Stavropoulos · Emmanouil Zampetakis -
2020 Poster: Truncated Linear Regression in High Dimensions »
Constantinos Daskalakis · Dhruv Rohatgi · Emmanouil Zampetakis -
2020 Poster: Sliding Window Algorithms for k-Clustering Problems »
Michele Borassi · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam -
2020 Poster: Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Benjamin Moseley · Philip Pham · Sergei Vassilvitskii · Yuyan Wang -
2020 Poster: Smoothly Bounding User Contributions in Differential Privacy »
Alessandro Epasto · Mohammad Mahdian · Jieming Mao · Vahab Mirrokni · Lijie Ren -
2020 Poster: Contextual Reserve Price Optimization in Auctions via Mixed Integer Programming »
Joey Huchette · Haihao Lu · Hossein Esfandiari · Vahab Mirrokni -
2020 Poster: Constant-Expansion Suffices for Compressed Sensing with Generative Priors »
Constantinos Daskalakis · Dhruv Rohatgi · Emmanouil Zampetakis -
2020 Spotlight: Constant-Expansion Suffices for Compressed Sensing with Generative Priors »
Constantinos Daskalakis · Dhruv Rohatgi · Emmanouil Zampetakis -
2020 : Learning Multiple Embeddings »
Alessandro Epasto -
2020 : Clustering At Scale »
Vahab Mirrokni -
2020 : Similarity Ranking »
Alessandro Epasto -
2020 : Application Story: Privacy »
Alessandro Epasto -
2020 Expo Workshop: Mining and Learning with Graphs at Scale »
Vahab Mirrokni · Bryan Perozzi · Jakub Lacki · Jonathan Halcrow · Jaqui C Herman -
2020 : Introduction »
Vahab Mirrokni -
2019 : Coffee Break & Poster Session 2 »
Juho Lee · Yoonho Lee · Yee Whye Teh · Raymond A. Yeh · Yuan-Ting Hu · Alex Schwing · Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Christian Bueno · Aditya Sanghi · Pradeep Kumar Jayaraman · Ignacio Arroyo-Fernández · Andrew Hryniowski · Vinayak Mathur · Sanjay Singh · Shahrzad Haddadan · Vasco Portilheiro · Luna Zhang · Mert Yuksekgonul · Jhosimar Arias Figueroa · Deepak Maurya · Balaraman Ravindran · Frank NIELSEN · Philip Pham · Justin Payan · Andrew McCallum · Jinesh Mehta · Ke SUN -
2019 : Contributed Talk - Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Philip Pham -
2019 : Coffee Break & Poster Session 1 »
Yan Zhang · Jonathon Hare · Adam Prugel-Bennett · Po Leung · Patrick Flaherty · Pitchaya Wiratchotisatian · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam · Theja Tulabandhula · Fabian Fuchs · Adam Kosiorek · Ingmar Posner · William Hang · Anna Goldie · Sujith Ravi · Azalia Mirhoseini · Yuwen Xiong · Mengye Ren · Renjie Liao · Raquel Urtasun · Haici Zhang · Michele Borassi · Shengda Luo · Andrew Trapp · Geoffroy Dubourg-Felonneau · Yasmeen Kussad · Christopher Bender · Manzil Zaheer · Junier Oliva · Michał Stypułkowski · Maciej Zieba · Austin Dill · Chun-Liang Li · Songwei Ge · Eunsu Kang · Oiwi Parker Jones · Kelvin Ka Wing Wong · Joshua Payne · Yang Li · Azade Nazi · Erkut Erdem · Aykut Erdem · Kevin O'Connor · Juan J Garcia · Maciej Zamorski · Jan Chorowski · Deeksha Sinha · Harry Clifford · John W Cassidy -
2019 Poster: Contextual Bandits with Cross-Learning »
Santiago Balseiro · Negin Golrezaei · Mohammad Mahdian · Vahab Mirrokni · Jon Schneider -
2019 Poster: Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions »
Negin Golrezaei · Adel Javanmard · Vahab Mirrokni -
2019 Poster: A Robust Non-Clairvoyant Dynamic Mechanism for Contextual Auctions »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni -
2019 Poster: Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond »
Lin Chen · Hossein Esfandiari · Gang Fu · Vahab Mirrokni -
2019 Poster: Variance Reduction in Bipartite Experiments through Correlation Clustering »
Jean Pouget-Abadie · Kevin Aydin · Warren Schudy · Kay Brodersen · Vahab Mirrokni -
2017 Poster: Dynamic Revenue Sharing »
Santiago Balseiro · Max Lin · Vahab Mirrokni · Renato Leme · IIIS Song Zuo -
2017 Poster: Affinity Clustering: Hierarchical Clustering at Scale »
Mohammadhossein Bateni · Soheil Behnezhad · Mahsa Derakhshan · MohammadTaghi Hajiaghayi · Raimondas Kiveris · Silvio Lattanzi · Vahab Mirrokni -
2016 Poster: Bi-Objective Online Matching and Submodular Allocations »
Hossein Esfandiari · Nitish Korula · Vahab Mirrokni -
2016 Poster: Community Detection on Evolving Graphs »
Stefano Leonardi · Aris Anagnostopoulos · Jakub Łącki · Silvio Lattanzi · Mohammad Mahdian -
2016 Poster: Linear Relaxations for Finding Diverse Elements in Metric Spaces »
Aditya Bhaskara · Mehrdad Ghadiri · Vahab Mirrokni · Ola Svensson -
2014 Poster: Distributed Balanced Clustering via Mapping Coresets »
Mohammadhossein Bateni · Aditya Bhaskara · Silvio Lattanzi · Vahab Mirrokni