6 papers
Efficiently Learning Drifting Halfspaces with Massart Noise
Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1
We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labe…
Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals
Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma
We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples from a distribution over $\mathbb{R}^d \tim…
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…
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…
K-median: exact recovery in the extended stochastic ball model
Alberto Del Pia, Mingchen Ma
We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (2015), the authors give a ti…
Proximity in Concave Integer Quadratic Programming
Alberto Del Pia, Mingchen Ma
A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of on the proximity of optimal solutions of an Integer Linear Programming problem and its sta…