Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing

Mengqi Lou, Kabir Aladin Verchand, Ashwin Pananjady

Abstract

Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large range of step-sizes. In particular, our analysis reveals that this method, though stochastic, converges linearly from a local initialization with a fixed step-size to a statistical error floor. Our analysis also exposes how the batch-size, step-size, and noise level affect the (linear) convergence rate and the eventual statistical estimation error, and we demonstrate how to use our deterministic predictions to perform hyperparameter tuning (e.g. step-size and batch-size selection) without ever running the method. On a technical level, our analysis is enabled in part by showing that the fluctuations of the empirical iterates around our deterministic predictions scale with the error of the previous iterate.

Introduction

Matrix sensing—the task of recovering a hidden matrix from a limited number of noisy, linear measurements—is a cornerstone of modern signal processing, appearing in applications ranging from medical imaging to communications. While stochastic algorithms like the prox-linear method are powerful tools for solving these non-convex problems, they are notoriously sensitive to hyperparameter choices. Practitioners often face a "guess-and-check" challenge: determining the optimal mini-batch size and step size usually requires expensive, high-dimensional simulations. This paper addresses this by deriving deterministic predictions for algorithmic trajectories, bridging the gap between theoretical guarantees and realistic, noisy settings.

The Stochastic Prox-Linear Method

The authors focus on a mini-batched version of the stochastic prox-linear algorithm. Unlike standard Stochastic Gradient Descent (SGD), which simply takes a step against the gradient, the prox-linear method solves a small optimization sub-problem at each step by linearizing the underlying model inside the quadratic loss function.

The core innovation is the derivation of a deterministic trajectory prediction. The behavior of the algorithm in $d$-dimensional space is captured by a 4-dimensional state vector representing the alignment of current estimates with the ground truth and the magnitude of the perpendicular error. By analyzing how these four values evolve, the authors created a deterministic map that mimics the average behavior of the stochastic process. Sophisticated "leave-one-out" analysis techniques show that the random fluctuations of the actual algorithm around their prediction shrink as the algorithm approaches the solution.

Key Insights: Scaling and Convergence

  • Error-Scaled Fluctuations: Most previous theories suggested that predictions become less accurate as error decreases. This work proves that fluctuations scale with the current error, meaning the deterministic prediction remains sharp all the way to the noise floor.
  • Three-Phase Convergence: The analysis reveals three distinct stages: rapid linear decay, a period of stagnation at a "noise floor," and a final sub-linear decay if the step size is further reduced.
  • Linear Speedup: The paper quantifies a "linear speedup" effect—doubling the batch size effectively halves the iterations needed to reach the noise floor, provided the step size is tuned correctly.

Experimental Results and Hyperparameter Tuning

Validation using synthetic datasets ($d=200$, rank-1 matrix recovery) confirms that the deterministic recursion accurately tracks the median error across a wide range of batch sizes ($m$) and step sizes ($\lambda_0$). The authors provide the first two-sided bounds on the convergence rate in noisy settings, showing the method reaches an estimation error of $\sigma^2$ in $\Theta(\frac{d(1+\sigma^2)}{m} \log \frac{1}{\sigma^2})$ iterations.

Error trajectories for varying batch sizes (left) and step sizes (right), demonstrating the accuracy of the deterministic prediction across different regimes.

Because the 4D deterministic map is computationally inexpensive—generating a 1,000-iteration trajectory takes less than 0.25 seconds—it enables lightning-fast hyperparameter tuning. Thousands of combinations of batch and step sizes can be simulated in milliseconds to find the optimal configuration before running the algorithm on actual high-dimensional data.

Limitations and Future Work

The current analysis is limited to rank-1 matrix recovery and relies on Gaussian sensing vectors. Extending these results to general low-rank matrices and non-Gaussian distributions (e.g., Fourier measurements) are key areas for future research. Additionally, the theory currently assumes local initialization and the use of "fresh" samples at every iteration; characterizing global behavior and dynamics in finite-sum settings remains an open challenge.

Summary updated

Abstract

Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large range of step-sizes. In particular, our analysis reveals that this method, though stochastic, converges linearly from a local initialization with a fixed step-size to a statistical error floor. Our analysis also exposes how the batch-size, step-size, and noise level affect the (linear) convergence rate and the eventual statistical estimation error, and we demonstrate how to use our deterministic predictions to perform hyperparameter tuning (e.g. step-size and batch-size selection) without ever running the method. On a technical level, our analysis is enabled in part by showing that the fluctuations of the empirical iterates around our deterministic predictions scale with the error of the previous iterate.
BibTeX
@inproceedings{lou2025hyperparameter,
  author = {Mengqi Lou and Kabir Aladin Verchand and Ashwin Pananjady},
  title = {{Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing}},
  booktitle = {Mathematical},
  year = {2025},
  doi = {10.1007/s10107-025-02279-0},
}
Figure