Sketched Linear Contrastive Learning: Approximation, Optimization, and Statistical Scaling

• URL: http://arxiv.org/abs/2606.26617v1
• Date: Thu, 25 Jun 2026 05:20:21 GMT
• Title: Sketched Linear Contrastive Learning: Approximation, Optimization, and Statistical Scaling
• Abstract summary: We study a sketched linear model for contrastive learning under a paired Gaussian latent-variable setup.<n>We derive a risk decomposition into irreducible risk, approximation error, GD bias, GD variance, and a cross term.<n>Compared with standard linear-regression scaling laws, the contrastive setting must learn interactions between two views.
• Score: 12.993805198900498
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Scaling laws describe how learning performance varies with model size, data size, and compute. While recent theoretical work has established scaling laws for sketched linear regression, much less is understood for contrastive representation learning. In this paper, we study a sketched linear model for contrastive learning under a paired Gaussian latent-variable setup. The learner observes only sketched views of two correlated variables and trains a bilinear contrastive score by full-batch empirical gradient descent. We analyze a Gaussian-negative quadratic contrastive surrogate under aligned power-law spectra and a contrastive source condition, where we derive a risk decomposition into irreducible risk, approximation error, GD bias, GD variance, and a cross term. The cross term is controlled by the bias and variance and therefore does not affect the upper-bound scaling. Our main theorem gives an explicit scaling law with respect to sketch dimension $M$, sample size $N$, and effective optimization horizon $L_{\mathrm{eff}}γ$. Compared with standard linear-regression scaling laws, the contrastive setting must learn interactions between two views, and this changes how optimization and finite-sample noise scale with model size, data, and training time. This provides a first theoretical step toward understanding scaling behavior in contrastive learning and gives guidance for balancing model size, data, and optimization compute.

Related papers

• SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws [55.81298869922287]
  We study the training dynamics of multiclass logistic regression on high-dimensional Gaussian mixture models with a large number of classes.<n>We establish precise scaling laws governing the cross-entropy risk under gradient-based optimization.
  arXiv  Detail & Related papers  (2026-09-07T18:30:09Z)
• Towards Robust Scaling Laws for Optimizers [89.21160945066737]
  Empirical scaling laws are widely used to predict loss as model size and training data grow.<n>We show that Chinchilla-style scaling laws emerge naturally as a result of loss decomposition into irreducible, approximation, and optimization errors.
  arXiv  Detail & Related papers  (2026-02-07T21:40:33Z)
• Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data [15.766916122461923]
  Scaling laws describe how learning performance improves with data, compute, or training time, and have become a central theme in modern deep learning.<n>We study this phenomenon in a canonical nonlinear model: phase retrieval with anisotropic Gaussian inputs whose covariance spectrum follows a power law.<n>Unlike the isotropic case, where dynamics collapse to a two-dimensional system, anisotropy yields a qualitatively new regime in which an infinite hierarchy of equations governs the evolution of the summary statistics.
  arXiv  Detail & Related papers  (2025-11-24T00:21:17Z)
• HAM: A Hyperbolic Step to Regulate Implicit Bias [14.701241300621648]
  We show that HAM (Hyperbolic Minimization) alternates between an overhead step and a new hyperbolic mirror step.<n>Ham's implicit bias consistently boosts performance--even of dense training.<n>Ham is especially effective in combination with different sparsification methods, improving upon the state of the art.
  arXiv  Detail & Related papers  (2025-06-03T08:47:16Z)
• Do Larger Language Models Generalize Better? A Scaling Law for Implicit Reasoning at Pretraining Time [73.22651918134808]
  This work shows counterintuitive effects of model size scaling and provides new insights into the relationship between scaling and reasoning in language models (LMs)<n>We pretrain LMs from scratch on a synthetic implicit multihop reasoning environment designed to replicate the structure and distribution of real-world large-scale knowledge graphs.<n>We then assess the LMs' ability to complete the missing edges in the graph, which requires multi-hop reasoning that can be viewed as a simplification of implicit reasoning during real-world pretraining.
  arXiv  Detail & Related papers  (2025-04-04T17:57:22Z)
• Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches [28.569601803576845]
  We show that for models with Transformer architecture, the test loss exhibits a power-law relationship with model size, dataset size, and the amount of computation used in training.<n>Our analysis provides deeper insights into the scaling law, potentially enhancing our understanding of Large Language Models.
  arXiv  Detail & Related papers  (2025-03-03T08:57:49Z)
• Scaling Law for Stochastic Gradient Descent in Quadratically Parameterized Linear Regression [5.801904710149222]
  In machine learning, the scaling law describes how the model performance improves with the model and data size scaling up.<n>This paper studies the scaling law over a linear regression with the model being quadratically parameterized.<n>As a result, in the canonical linear regression, we provide explicit separations for curves between generalization with and without feature learning, and the information-theoretical lower bound that is to parametrization method and the algorithm.
  arXiv  Detail & Related papers  (2025-02-13T09:29:04Z)
• Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
  We study the theory of scaling laws in an infinite dimensional linear regression setup.<n>We show that the reducible part of the test error is $Theta(-(a-1) + N-(a-1)/a)$.<n>Our theory is consistent with the empirical neural scaling laws and verified by numerical simulation.
  arXiv  Detail & Related papers  (2024-06-12T17:53:29Z)
• A Dynamical Model of Neural Scaling Laws [79.59705237659547]
  We analyze a random feature model trained with gradient descent as a solvable model of network training and generalization. Our theory shows how the gap between training and test loss can gradually build up over time due to repeated reuse of data.
  arXiv  Detail & Related papers  (2024-02-02T01:41:38Z)
• Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression [53.15502562048627]
  Recent work has built the connection between self-supervised learning and the approximation of the top eigenspace of a graph Laplacian operator. This work delves into a statistical analysis of augmentation-based pretraining.
  arXiv  Detail & Related papers  (2023-06-01T15:18:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.