88 citations · 311 across the 59 of their papers we have counts for
70 papers
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…
First Order Stochastic Optimization with Oblivious Noise
Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park +1
We initiate the study of stochastic optimization with oblivious noise, broadly generalizing the standard heavy-tailed noise setup. In our setting, in addition to random observation…
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…
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions
Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park +1
We demonstrate the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We assume we have sample access…
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…
Buying Information for Stochastic Optimization
Mingchen Ma, Christos Tzamos
Stochastic optimization is one of the central problems in Machine Learning and Theoretical Computer Science. In the standard model, the algorithm is given a fixed distribution know…
Weitzman's Rule for Pandora's Box with Correlations
Evangelia Gergatsouli, Christos Tzamos
Pandora's Box is a central problem in decision making under uncertainty that can model various real life scenarios. In this problem we are given boxes, each with a fixed openin…
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms…
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…
Graph Connectivity with Noisy Queries
Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis +2
Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its op…
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…
Buy-Many Mechanisms for Many Unit-Demand Buyers
Shuchi Chawla, Rojin Rezvan, Yifeng Teng +1
A recent line of research has established a novel desideratum for designing approximately-revenue-optimal multi-item mechanisms, namely the buy-many constraint. Under this constrai…
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…
Approximating Pandora's Box with Correlations
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan +1
We revisit the classic Pandora's Box (PB) problem under correlated distributions on the box values. Recent work of arXiv:1911.01632 obtained constant approximate algorithms for a 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…