Optimal Sample Complexity of Contrastive Learning

Speaker: Dmitrii Avdiukhin , Northwestern Uniersity

Date: Thursday, April 18, 2024

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-D507

Event Type: Seminar

Room Description: 32-D507

Host: Noah Golowich, MIT

Contact: Noah Golowich, nzg@csail.mit.edu

Relevant URL: https://arxiv.org/abs/2312.00379

Speaker URL: https://dyukha.github.io/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Dmitrii Avdiukhin: Optimal Sample Complexity of Contrastive Learning

Abstract: Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, both general ℓp-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning ℓp-distances for integer p. For any p≥1 we show that Θ̃ (min(nd,n2)) labeled tuples are necessary and sufficient for learning d-dimensional representations of n-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2024.

Created by Noah Golowich Email at Sunday, April 14, 2024 at 11:57 AM.