We study the problem of estimating the trace of a matrix A that can only be accessed through
matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which …

We consider the problem of black-box control: the task of controlling an unknown linear time-
invariant dynamical system from a single trajectory without a stabilizing controller. Under the …

We show that any memory-constrained, first-order algorithm which minimizes $ d $-
dimensional, $1 $-Lipschitz convex functions over the unit ball to $1/\mathrm {poly}(d) …

Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but
the corresponding problem of proving lower bounds for this task has remained elusive, with …

We study iterative methods based on Krylov subspaces for low-rank approximation under
any Schatten-p norm. Here, given access to a matrix A through matrix-vector products, an …

Given a symmetric matrix A, we show from the simple sketch GAG T, where G is a Gaussian
matrix with k= O (1/є2) rows, that there is a procedure for approximating all eigenvalues of A …

We consider algorithms with access to an unknown matrix M ε F n× d via matrix-vector
products, namely, the algorithm chooses vectors v1, ⃛, vq, and observes Mv1, ⃛, Mvq. Here …

We show that any randomized first-order algorithm which minimizes a d-dimensional, 1-
Lipschitz convex function over the unit ball must either use Ω\left(d^2-δ\right) bits of memory …

We consider the problem of rank-1 low-rank approximation (LRA) in the matrix-vector
product model under various Schatten norms: _ ‖ u ‖ _ 2= 1\left ‖ A\left (Iu u …

We consider the general problem of learning about a matrix through vector-matrix-vector
queries. These queries provide the value of $\boldsymbol {u}^{\mathrm {T}}\boldsymbol …