Logo
Vasilis Kontonis vkonton[at]gmail.com

I am an IFML Postdoctoral Fellow based at UT Austin hosted by Adam Klivans and Raghu Meka. I received my PhD in Computer Science from the University of Wisconsin-Madison, where I was advised by Christos Tzamos. Prior to UW-Madison, I studied Electrical and Computer Engineering at the National Technical University of Athens where I was advised by Dimitris Fotakis.

I work on designing efficient algorithms with provable guarantees for machine learning problems with a focus on dealing with imperfect data (e.g., classification with noisy labels and statistical inference from biased or censored data). I am also interested in analyzing and providing formal guarantees for popular machine learning algorithms (e.g., diffusion models).

I am on the 2024/25 job market. Here is my CV.

News

Publications

  1. Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
    w/ G. Chandrasekaran, A. Klivans, R. Meka, K. Stavropoulos
    Best Paper Award COLT 2024
    IPAM 2024 Long Talk Video

  2. Active Learning with Simple Questions
    w/ M. Ma, C. Tzamos
    COLT 2024

  3. Agnostically Learning Multi-index Models with Queries
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    FOCS 2024

  4. Super Non-singular Decompositions of Polynomials and their
    Application to Robustly Learning Low-degree PTFs
    w/ I. Diakonikolas, D M. Kane, S. Liu, N. Zarifis
    STOC 2024

  5. Efficient Discrepancy Testing for Learning with Distribution Shift
    w/ G. Chandrasekaran, A. Klivans, K. Stavropoulos, A. Vasilyan
    NeurIPS 2024

  6. Active Classification with Few Queries under Misspecification
    w/ C. Tzamos, M. Ma
    NeurIPS 2024

  7. Learning Noisy Halfspaces with a Margin: Massart is no Harder than Random
    w/ G. Chandrasekaran, K. Stavropoulos, K. Tian
    NeurIPS 2024

  8. Optimizing Solution-Samplers for Combinatorial Problems:
    The Landscape of Policy Gradient Methods
    w/ C. Caramanis, D. Fotakis, A. Kalavasis, C. Tzamos
    Selected for Oral Presentation
    NeurIPS 2023

  9. SLaM: Student-Label Mixing for Distillation with Unlabeled Examples
    w/ F. Iliopoulos, K. Trinh, C. Baykal, G. Menghani, V. Erik
    NeurIPS 2023

  10. The Gain from Ordering in Online Learning
    w/ M. Ma, C. Tzamos
    NeurIPS 2023

  11. Efficient Testable Learning of Halfspaces with Adversarial Label Noise
    w/ I. Diakonikolas, D M. Kane, S. Liu, N. Zarifis
    NeurIPS 2023

  12. Self Directed Linear Classification
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    COLT 2023

  13. Weighted Distillation with Unlabeled Examples
    w/ F. Iliopoulos, C. Baykal, G. Menghani, K. Trinh, V. Erik
    NeurIPS 2022

  14. Linear Label Ranking with Bounded Noise
    w/ D. Fotakis, A. Kalavasis, C. Tzamos
    Selected for Oral Presentation
    NeurIPS 2022

  15. Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    ICML 2022

  16. Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    COLT 2022

  17. Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    STOC 2022

  18. A Statistical Taylor Theorem and Extrapolation of Truncated Densities
    w/ C. Daskalakis, C. Tzamos, M. Zampetakis
    COLT 2021

  19. Agnostic Proper Learning of Halfspaces under Gaussian Marginals
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    COLT 2021

  20. Efficient Algorithms for Learning from Coarse Labels
    w/ D. Fotakis, A. Kalavasis, C. Tzamos
    COLT 2021

  21. Learning Online Algorithms with Distributional Advice
    w/ I. Diakonikolas, C. Tzamos, A. Vakilian, N. Zarifis
    ICML 2021

  22. A Polynomial Time Algorithm For Learning Halfspaces with Tsybakov Noise
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    STOC 2021

  23. Learning Halfspaces with Tsybakov Noise
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    STOC 2021
    Conference version merged with the above paper

  24. Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    NeurIPS 2020

  25. Learning Halfspaces with Massart Noise Under Structured Distributions
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    COLT 2020

  26. Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
    w/ I. Diakonikolas, D. Kane, N. Zarifis
    COLT 2020

  27. Efficient Truncated Statistics with Unknown Truncation
    w/ C. Tzamos, M. Zampetakis
    FOCS 2019

  28. Removing Bias in Maching Learning via Truncated Statistics
    w/ C. Daskalakis, C. Tzamos, M. Zampetakis
    Manuscript

  29. Opinion Dynamics with Limited Information
    w/ D. Fotakis, V. Kandiros, S. Skoulakis
    WINE 2018

  30. Learning Powers of Poisson Binomial Distributions
    w/ D. Fotakis, P. Krysta, P. Spirakis
    Manuscript

Service

Talks