88 citations · 311 across the 59 of their papers we have counts for
29 papers · 1 filter
Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
Learning intersections of halfspaces is a central problem in Computational Learning Theory. Even for just two halfspaces, it remains a major open question whether learning is possi…
Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of l…
Active Learning with Simple Questions
Vasilis Kontonis, Mingchen Ma, Christos Tzamos
We consider an active learning setting where a learner is presented with a pool S of n unlabeled examples belonging to a domain X and asks queries to find the underlying labeling t…
Online Learning of Halfspaces with Massart Noise
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the task of online learning in the presence of Massart noise. Instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the con…
Agnostically Learning Multi-index Models with Queries
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the power of query access for the task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels and the goal is t…
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods
Constantine Caramanis, Dimitris Fotakis, Alkis Kalavasis +2
Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network…
Self-Directed Linear Classification
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
In online classification, a learner is presented with a sequence of examples and aims to predict their labels in an online fashion so as to minimize the total number of mistakes. I…
Perfect Sampling from Pairwise Comparisons
Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
In this work, we study how to efficiently obtain perfect samples from a discrete distribution given access only to pairwise comparisons of elements of its support. Sp…
Clustering with Queries under Semi-Random Noise
Alberto Del Pia, Mingchen Ma, Christos Tzamos
The seminal paper by Mazumdar and Saha \cite{MS17a} introduced an extensive line of work on clustering with noisy queries. Yet, despite significant progress on the problem, the pro…
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the fundamental problem of learning a single neuron, i.e., a function of the form for monotone activations $σ:\mathbb{R}\ma…
Contextual Pandora's Box
Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli +2
Pandora's Box is a fundamental stochastic optimization problem, where the decision-maker must find a good alternative while minimizing the search cost of exploring the value of eac…
Online Learning for Min Sum Set Cover and Pandora's Box
Evangelia Gergatsouli, Christos Tzamos
Two central problems in Stochastic Optimization are Min Sum Set Cover and Pandora's Box. In Pandora's Box, we are presented with boxes, each containing an unknown value and the…
ReLU Regression with Massart Noise
Ilias Diakonikolas, Jongho Park, Christos Tzamos
We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data. This supervised learning task is efficiently solvable in the r…
Efficient Algorithms for Learning from Coarse Labels
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis +1
For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the…
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning halfspaces on with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the labe…
Forster Decomposition and Learning Halfspaces with Noise
Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any di…
Boosting in the Presence of Massart Noise
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane +3
We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each exampl…
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose sample…
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…
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…
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…
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…