Differentially Private Quasi-Concave Optimization - Bypassing the Lower Bound and Application to Geometric Problems

Attend this academic lecture exploring how to bypass established lower bounds in differentially private optimization of quasi-concave functions. Learn about a new class of approximated quasi-concave functions and discover a generic differentially private optimizer with significantly improved sample complexity of Õ(log*|X|), compared to the previously proven lower bound of Ω(2^log*|X|). Examine practical applications including privately selecting center points in d-dimensional space and PAC learning d-dimensional halfspaces, where the speaker demonstrates improved upper bounds of Õ(d^5.5 log*|X|) for both problems - reducing the dependency on domain cardinality from exponential to logarithmic. Explore the theoretical foundations and geometric implications of this breakthrough research that advances the intersection of differential privacy, optimization theory, and machine learning, presented by Eliad Tsfadia from Bar-Ilan University as part of joint work with Kobbi Nissim and Chao Yan.