88 citations · 311 across the 59 of their papers we have counts for
12 papers · 1 filter
Convergence and Sample Complexity of SGD in GANs
Vasilis Kontonis, Sihan Liu, Christos Tzamos
We provide theoretical convergence guarantees on training Generative Adversarial Networks (GANs) via SGD. We consider learning a target distribution modeled by a 1-layer Generator…
Optimal Private Median Estimation under Minimal Distributional Assumptions
Christos Tzamos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Ilias Zadik
We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distr…
Computationally and Statistically Efficient Truncated Regression
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos +1
We provide a computationally and statistically efficient estimator for the classical problem of truncated linear regression, where the dependent variable and its co…
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, the label of every sample is independently flipped with…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
Efficient Parameter Estimation of Truncated Boolean Product Distributions
Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
We study the problem of estimating the parameters of a Boolean product distribution in dimensions, when the samples are truncated by a set accessible thr…
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model. For a broad family of structured distributions, including log-concave d…
Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the efficient PAC learnability of halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, each label is independently flipped with some probability whic…
Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms
Shuchi Chawla, Yifeng Teng, Christos Tzamos
We study the multi-item mechanism design problem where a monopolist sells heterogeneous items to a single buyer. We focus on buy-many mechanisms, a natural class of mechanisms…
Black-box Methods for Restoring Monotonicity
Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
In many practical applications, heuristic or approximation algorithms are used to efficiently solve the task at hand. However their solutions frequently do not satisfy natural mono…
Learning Halfspaces with Massart Noise Under Structured Distributions
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the problem of learning halfspaces with Massart noise in the distribution-specific PAC model. We give the first computationally efficient algorithm for this problem with r…
On Robust Mean Estimation under Coordinate-level Corruption
Zifan Liu, Jongho Park, Theodoros Rekatsinas +1
We study the problem of robust mean estimation and introduce a novel Hamming distance-based measure of distribution shift for coordinate-level corruptions. We show that this measur…