4 papers
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy
Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin +2
Among the various aspects of algorithmic fairness studied in recent years, the tension between satisfying both \textit{sufficiency} and \textit{separation} -- e.g. the ratios of po…
Online k-means Clustering
Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade +1
We study the problem of online clustering where a clustering algorithm has to assign a new point that arrives to one of clusters. The specific formulation we use is the -mea…
Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?
Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu
Motivated by crowdsourced computation, peer-grading, and recommendation systems, Braverman, Mao and Weinberg [STOC'16] studied the \emph{query} and \emph{round} complexity of funda…
Online Optimization of Smoothed Piecewise Constant Functions
Vincent Cohen-Addad, Varun Kanade
We study online optimization of smoothed piecewise constant functions over the domain [0, 1). This is motivated by the problem of adaptively picking parameters of learning algorith…