| Sažetak: | <p>As vast amounts of data are being produced and processed in various fields of science and engineering, optimizing high-dimensional statistical models has become a ubiquitous task in many modern applications. Often, it is crucial to exploit underlying low-dimensional structures to extract useful information from high-dimensional data and models. To this end, numerous optimization algorithms such as gradient descent and its variants have been extensively studied both empirically and theoretically, with a large part of the literature focusing on algorithms based on the Euclidean geometry.</p>
<p>In this thesis, we study mirror descent, an iterative first-order algorithm that can be adapted to possibly non-Euclidean geometries by choosing a suitable mirror map, applied to two canonical models in high-dimensional statistics with underlying low-dimensional structures, namely sparse phase retrieval and matrix sensing. In these two problems, we demonstrate that mirror descent, with different choices for the mirror map, can incorporate the low-dimensional structures of sparsity and low-rankness, respectively.</p>
<p>In sparse phase retrieval, we begin by proposing Hadamard Wirtinger flow (HWF), an algorithm that minimizes the unregularized empirical risk and can be obtained as a first-order approximation to mirror descent equipped with the hypentropy mirror map. In contrast to existing algorithms for sparse phase retrieval, HWF does not require any explicit regularization in the form of added regularization terms or thresholding steps to enforce sparsity of its estimates and is empirically seen to adapt to the sparsity level of the underlying signal. On the theoretical side, we adopt the mirror descent framework and consider the more general setting of noisy sparse phase retrieval, where early stopping becomes necessary to prevent the estimates of mirror descent from deteriorating after a certain number of iterations. We show that early-stopped mirror descent achieves a nearly minimax-optimal rate of convergence in noisy sparse phase retrieval, which shows that, instead of explicit regularization in the form of added regularization terms or thresholding steps, the geometry defined by the hypentropy mirror map and early stopping can be utilized to reconstruct sparse signal vectors from noisy phaseless measurements.</p>
<p>In matrix sensing, we study mirror descent -- with different choices for the mirror map when optimizing over general rectangular and positive semidefinite matrices -- applied to the unregularized empirical risk. We characterize the limiting point of mirror descent via a quantity explicitly related to the nuclear norm, Frobenius norm, and the von Neumann entropy. Assuming either a restricted isometry property or the setting of matrix completion, we obtain recovery guarantees for mirror descent that improve upon existing theoretical results for implicit regularization-based algorithms, which do not rely on minimizing or regularizing the nuclear norm nor on a low-rank factorized parametrization to enforce low-rankness of their estimates, in terms of the sample complexity.</p>
|
|---|