Author name cluster

Roman Vershynin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

JMLR Journal 2023 Journal Article

Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval

Yan Shuo Tan
Roman Vershynin

In recent literature, a general two step procedure has been formulated for solving the problem of phase retrieval. First, a spectral technique is used to obtain a constant-error initial estimate, following which, the estimate is refined to arbitrary precision by first-order optimization of a non-convex loss function. Numerical experiments, however, seem to suggest that simply running the iterative schemes from a random initialization may also lead to convergence, albeit at the cost of slightly higher sample complexity. In this paper, we prove that, in fact, constant step size online stochastic gradient descent (SGD) converges from arbitrary initializations for the non-smooth, non-convex amplitude squared loss objective. In this setting, online SGD is also equivalent to the randomized Kaczmarz algorithm from numerical analysis. Our analysis can easily be generalized to other single index models. It also makes use of new ideas from stochastic process theory, including the notion of a summary state space, which we believe will be of use for the broader field of non-convex optimization. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

PDF Details

AIJ Journal 2023 Journal Article

The quarks of attention: Structure and capacity of neural attention building blocks

Pierre Baldi
Roman Vershynin

Attention plays a fundamental role in both natural and artificial intelligence systems. In deep learning, attention-based neural architectures, such as transformer architectures, are widely used to tackle problems in natural language processing and beyond. Here we investigate the most fundamental building blocks of attention and their computational properties within the standard model of deep learning. We first derive a systematic taxonomy of all possible attention mechanisms within, or as extensions of the standard model into 18 classes depending on the origin of the attention signal, the target of the attention signal, and whether the interaction is additive or multiplicative. Second, using this taxonomy, we identify three key attention mechanisms: additive activation attention (multiplexing), multiplicative output attention (output gating), and multiplicative synaptic attention (synaptic gating). Output gating and synaptic gating are proper extensions of the standard model and all current attention-based architectures, including transformers, use either output gating or synaptic gating, or a combination of both. Third, we develop a theory of attention capacity and derive mathematical results about the capacity of basic attention networks comprising linear or polynomial threshold gates. For example, the output gating of a linear threshold gate of n variables by another linear threshold gate of the same n variables has capacity 2 n 2 ( 1 + o ( 1 ) ), achieving the maximal doubling of the capacity for a doubling of the number of parameters. Perhaps surprisingly, multiplexing attention is used in the proofs of these results. Synaptic and output gating provide computationally efficient extensions of the standard model enabling sparse quadratic activation functions. They can also be viewed as primitives for collapsing several layers of processing in the standard model into shallow compact representations.

Details DOI

NeurIPS Conference 2018 Conference Paper

On Neuronal Capacity

Pierre Baldi
Roman Vershynin

We define the capacity of a learning machine to be the logarithm of the number (or volume) of the functions it can implement. We review known results, and derive new results, estimating the capacity of several neuronal models: linear and polynomial threshold gates, linear and polynomial threshold gates with constrained weights (binary weights, positive weights), and ReLU neurons. We also derive capacity estimates and bounds for fully recurrent networks and layered feedforward networks.

PDF Details

STOC Conference 2007 Conference Paper

One sketch for all: fast algorithms for compressed sensing

Anna C. Gilbert
Martin J. Strauss
Joel A. Tropp
Roman Vershynin

Compressed Sensing is a new paradigm for acquiring the compressible signals that arise in many applications. These signals can be approximated using an amount of information much smaller than the nominal dimension of the signal. Traditional approaches acquire the entire signal and process it to extract the information. The new approach acquires a small number of nonadaptive linear measurements of the signal and uses sophisticated algorithms to determine its information content. Emerging technologies can compute these general linear measurements of a signal at unit cost per measurement.

Details

FOCS Conference 2006 Conference Paper

Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method

Roman Vershynin

Spielman and Teng proved that the shadow-vertex simplex method had polynomial smoothed complexity. On a slight random perturbation of arbitrary linear program, the simplex method finds the solution after a walk on the feasible polytope(s) with expected length polynomial in the number of constraints n, the number of variables d and the inverse standard deviation of the perturbation 1/sigma. We show that the length of walk is actually polylogarithmic in the number of constraints n. We thus improve Spielman-Teng's bound on the walk O*(n 86 d 55 sigma -30 ) to O(max(d 5 log 2 n, d 9 log 4 d, d 3 sigma -4 )). This in particular shows that the tight Hirsch conjecture n - d on the diameter of polytopes is not a limitation for the smoothed linear programming. Random perturbations create short paths between vertices. We propose a randomized phase-I for solving arbitrary linear programs. Instead of finding a vertex of a feasible set, we add a vertex at random to the feasible set. This does not affect the solution of the linear program with constant probability. So, in expectation it takes a constant number of independent trials until a correct solution is found. This overcomes one of the major difficulties of smoothed analysis of the simplex method - one can now statistically decouple the walk from the smoothed linear program. This yields a much better reduction of the smoothed complexity to a geometric quantity - the size of planar sections of random polytopes. We also improve upon the known estimates for that size

Details

FOCS Conference 2005 Conference Paper

Error Correction via Linear Programming

Emmanuel J. Candès
Mark Rudelson
Terence Tao
Roman Vershynin

Suppose we wish to transmit a vector f ϵ R n reliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?

Details