论文检索

Optimization · Large Scale, Parallel and Distributed

Yaoshuai Ma, Xiao Wang, Wei Yao, Jin Zhang

Distributed optimization over time-varying directed graphs has shown promising performance in addressing challenges posed by complex communication constraints in real-world scenarios. In many practical settings, however, the direct application of distributed optimization algorithms encounters additional difficulties, most notably hyperparameter tuning, which our empirical observations suggest can be effectively mitigated by integrating bilevel optimization. Motivated by these findings, we study distributed bilevel optimization over time-varying directed networks, a problem that remains largely unexplored due to the compounded challenges arising from consensus bias in dynamic unbalanced communication and the nested optimization structure. In this work, we propose a fully first-order distributed gradient-based algorithm that integrates the Push–Pull (also known as AB) communication strategy with a value function-based penalty method and establish its non-asymptotic convergence properties. Notably, a simplified variant of our analysis framework for nonconvex single-level distributed optimization establishes a convergence rate for the Push–Pull algorithm, thereby resolving an open question concerning its convergence over time-varying directed graphs. Empirical evaluations across diverse tasks, including hyperparameter tuning, data hyper-cleaning, and reinforcement learning, validate the effectiveness and efficiency of the proposed algorithm.

General Machine Learning · Supervised Learning

Yongxiang Tang, Chao Wang, Jincheng Lu, Yanhua Cheng, Xialong Liu, Peng Jiang

Learning to rank can be cast as a probabilistic modeling problem over permutations, where the goal is to estimate the likelihood of an observed total ordering of items. This formulation naturally involves full-order probabilities of the form $\mathbb{P}(\mathrm{z}_1 < \cdots < \mathrm{z}_n)$, whose exact computation and optimization are intractable due to the factorial growth of the permutation space with respect to list size. We introduce the *Full-Order Bound* (FOB), a tractable lower bound on the probability of an observed ordering, constructed from a subset of ordering constraints that factorizes across items while avoiding low-dimensional surrogate objectives and preserving order-reversal invariance. FOB induces a convex inner tightening problem over latent cut points, which we solve efficiently during training using a *safe-region gradient ascent* (SRGA) procedure. Experiments on synthetic ranking tasks and large-scale learning-to-rank benchmarks show that FOB consistently improves performance over pairwise and listwise surrogates, Plackett--Luce style sequential factorization models, and differentiable sorting baselines. Code is available at [https://anonymous.4open.science/r/FOB_2026-46C4](https://anonymous.4open.science/r/FOB_2026-46C4).

Shinji Ito, Kenshi Abe, Kaito Ariu, Taira Tsuchiya

We study last-iterate convergence for stochastic smooth and monotone variational inequalities (VIs), a framework that captures convex-concave saddle points and Nash equilibrium computation in monotone games with noisy payoff feedback. In contrast to the well-understood average-iterate guarantees, anytime last-iterate guarantees in stochastic settings remain limited, despite their relevance for uncoupled learning dynamics that output a single current strategy. We analyze two single-call regularized methods, the \emph{regularized gradient (RG)} and the \emph{regularized optimistic gradient (ROG)} methods, and establish anytime last-iterate convergence rates in terms of the squared gap function. For monotone VIs, RG attains $O(t^{-2/5})$ while ROG achieves the variance-adaptive rate $O(\sigma^{4/5} t^{-2/5} + t^{-1})$, where $\sigma^2$ is the noise variance. For $\lambda$-strongly monotone VIs, ROG yields $O(\sigma^2 / (\lambda^2 t) + t^{-c})$ for any constant $c \ge 2$. These results give anytime last-iterate guarantees without knowing the horizon and show that optimism improves convergence in the low-noise regime.

Optimization · Convex

Aikaterini Karoni, Rajit Rajpal, Benedict Leimkuhler, Gabriel Stoltz

Momentum Stochastic Gradient Descent (mSGD) relies on a fixed momentum coefficient shared across all parameters, failing to account for the heterogeneous structure of modern loss landscapes. In this work, we adopt a continuous-time formulation to introduce individual, adaptive momentum coefficients regulated by the kinetic energy of each model parameter. This mechanism automatically adjusts to local curvature to maintain stability without sacrificing convergence speed. We demonstrate that this adaptive friction is inextricably linked to cubic damping, a suppression mechanism from structural dynamics. We additionally introduce two optimization schemes by augmenting the continuous dynamics of mSGD and Adam with a cubic damping term. Empirically, our methods demonstrate robustness and match or outperform Adam on training ViT, BERT, and GPT2; tasks where mSGD typically struggles. We further provide theoretical results establishing the exponential convergence of the proposed schemes.

Social Aspects · Privacy

Shuli Jiang, Walid Krichene, Nicolas Mayoraz

We study differentially private (DP) regression in settings where each data sample includes public, non-sensitive features—common in applications like recommendation or advertising systems. While such label DP or DP with semi-sensitive features settings have been primarily explored in the context of classification, effective approaches for regression remain underexplored. We introduce $\textsf{Cond-DP}$, a conditioned variant of $\textsf{DPSGD}$ that leverages the structure of public feature matrices to improve optimization under privacy constraints. Motivated by the observation that these public features often exhibit rapidly decaying spectra, $\textsf{Cond-DP}$ incorporates a data-driven conditioning matrix to reshape the optimization landscape and accelerate convergence. We provide convergence guarantees for convex, strongly convex and non-convex settings, and recover standard $\textsf{DPSGD}$ as a special case when the conditioning matrix is the identity. We show how to construct an effective conditioning matrix for $\textsf{Cond-DP}$ directly from public features, enabling faster convergence than $\textsf{DPSGD}$ in private linear regression, without incurring additional privacy cost. Empirically, $\textsf{Cond-DP}$ with this conditioning matrix consistently outperforms state-of-the-art baselines across a wide range of datasets and model architectures under label DP, demonstrating strong and robust performance in practice.

Optimization · Discrete and Combinatorial Optimization

Yang Huang, Yifan Zhang, Jian Cheng

We propose an OT-guided sampling framework for solving graph combinatorial optimization through exact multilinear relaxation. Graph combinatorial optimization problems can be written as quadratic unconstrained binary optimization(QUBO). Leveraging a classical result in combinatorial optimization, we obtain a continuous multi-linear relaxation of QUBO that is exact, in the sense that it preserves the optimal binary solutions. The challenge is that the resulting energy landscape is highly nonconvex. We address this by treating the objective as an energy function and optimizing via sampling from the induced Boltzmann distribution to escape poor local optima. Viewing sampling as transporting a simple reference distribution to the target distribution, we use optimal transport to characterize more efficient probability flow and derive a stochastic optimal control problem whose solution yields an optimal sampling dynamics. We parameterize the control policy with graph neural networks to approximate the optimal control. Experiments show improved solution quality and efficiency over strong combinatorial and learning-based baselines.

Optimization · Convex

Junchi Yan, Liangliang Shi, Jiaxi Liu, Fangyuan Zhou, Wenzheng Pan, Zhongteng Gui, Yihui Tu

One essential limitation of neural networks is how to enforce (hard) constraints on prediction. We propose a plug-in, differentiable layer, which involves a fast implicit (convex) optimization procedure to enforce the general linear constraint. It aims to minimize a divergence between unconstrained and constrained outputs. Connecting to and beyond existing handcrafted layers, we show that our layer degrades to classic layers like Softmax, Sinkhorn and tanh etc. when the corresponding constraint is enforced by KL-divergence minimization. We further show that by replacing the KL-div with a Euclidean distance, a closed-form solution can be derived for highly-efficient constraint enforcing. We evaluate the above two variants of layers, termed as BLCLayer and GLCLayer, with their corresponding neural solver BLCNet and GLCNet with simple MLP/GNN-like backbone. Experiments on linear programming, as well as two real-world problems: partial graph matching and portfolio allocation which involve other discrete constraints.

Optimization · Convex

Jannis Halbey, Daniel Deza, Max Zimmer, Christophe Roux, Bartolomeo Stellato, Sebastian Pokutta

We present a constructive lower bound of $\Omega(1/\sqrt{\varepsilon})$ for Frank-Wolfe (FW) when both the objective and the constraint set are smooth and strongly convex, showing that the known uniform $\mathcal{O}(1/\sqrt{\varepsilon})$ guarantees in this regime are tight. It is known that under additional assumptions on the position of the optimizer, FW can converge linearly. However, it remained unclear whether strong convexity of the set can yield rates \emph{uniformly} faster than $\mathcal{O}(1/\sqrt{\varepsilon})$, i.e., irrespective of the position of the optimizer. To investigate this question, we focus on a simple yet representative problem class: minimizing a strongly convex quadratic over the Euclidean unit ball, with the optimizer on the boundary. We analyze the dynamics of FW for this problem in detail and develop a novel computational approach to construct worst-case FW trajectories, which is of independent interest. Guided by these constructions, we develop an analytical proof establishing the lower bound.

General Machine Learning · Transfer, Multitask and Meta-learning

Siyang Guo, Junbo Wang, Zibin Zheng

As pre-trained models evolve rapidly, transferring fine-tuning knowledge to updated models without retraining has become a critical challenge. Most existing methods reuse parameter updates, yet the same dataset can induce substantially different updates across base models due to mismatched local loss landscapes, making such transfer unstable. We instead adopt a Bayesian-updating perspective: a base model defines a prior, while fine-tuning contributes a task-update factor that is prior-agnostic, thereby making it feasible to reuse the update across base models. Specifically, we formalize a reusable task-update factor by requiring *invariance across base models* and *a fixed-dimensional parameterization*. Our main theoretical result shows that such reusable factors exist when the variational family is a half-space, and it is already maximal among convex families. In particular, an ideal regime arises when the priors and their Bayesian posteriors remain within a shared exponential family, as it always admits a reusable update factor. Building on this existence, we propose ***B**ayesian Task Update **Transfer*** (*BTransfer*), which extracts a reusable task-update factor from a single fine-tuning run and applies it to a new prior. For deep networks, we implement *BTransfer* with a ``lift–transfer–return'' pipeline: 1) lift model parameters to distributions; 2) transfer the extracted task-update factor in the exponential family distributions; and 3) return the updated posterior distribution to parameter space. Extensive experiments demonstrate that our approach effectively reuses fine-tuning knowledge across models without post-training.

Social Aspects · Privacy

Anneliese Riess, Felipe Gomez, Flavio Calmon, Julia Schnabel, Georgios Kaissis

We prove the conjecture stated in Appendix F.3 of Zhu et al.: among all conversion rules that map a Rényi Differential Privacy (RDP) profile $\tau \mapsto \rho(\tau)$ to a valid hypothesis-testing trade-off $f$ (or equivalently, an $(\varepsilon,\delta)$-Differential Privacy curve), the rule based on the intersection of single-order RDP privacy regions is optimal. This optimality holds simultaneously for all valid RDP profiles and for all Type I error levels $\alpha$. Concretely, we show that in the space of trade-off functions, the tightest possible bound is $f_{\rho(\cdot)}(\alpha) = \sup_{\tau \geq 0.5} f_{\tau,\rho(\tau)}(\alpha)$: the pointwise maximum of the single-order bounds for each RDP privacy region. Our proof unifies and sharpens the insights of Balle et al., Asoodeh et al., and Zhu et al.. Our analysis relies on a precise geometric characterization of the RDP privacy region, leveraging its convexity and the fact that its boundary is determined exclusively by Bernoulli mechanisms. Our results establish that the "intersection-of-RDP-privacy-regions" rule is not only valid, but optimal: no other black-box conversion can uniformly dominate it in the Blackwell sense, marking the fundamental limit of what can be inferred about a mechanism's privacy solely from its RDP guarantees.

Theory · Optimization

Matan Schliserman, Shira Vansover-Hager, Tomer Koren

Understanding the generalization behavior of learning algorithms is a central goal of learning theory. A recently emerging explanation is that learning algorithms are successful in practice because they converge to flat minima, which have been consistently associated with improved generalization performance. In this work, we study the link between flat minima and generalization in the canonical setting of stochastic convex optimization with a non-negative, $\beta$-smooth objective. Our first finding is that, even in this fundamental setting, flat empirical minima may incur trivial $\Omega(1)$ population risk while sharp minima generalizes optimally. We then demonstrate that this phenomenon extends to sharpness-aware algorithms introduced by Foret et al. (2021), namely Sharpness-Aware Gradient Descent (SA-GD) and Sharpness-Aware Minimization (SAM). For SA-GD we prove that it successfully converges to a flat minimum at a fast rate, but the population risk of the solution can still be as large as $\Omega(1)$. For SAM we show that although it minimizes the empirical loss, it may converge to a sharp minimum and also incur population risk $\Omega(1)$. Finally, we establish population risk upper bounds for both SA-GD and SAM using algorithmic stability techniques.

Applications · Robotics

Zihan Wang, Jiashun Wang, Jeff Tan, Yiwen Zhao, Jessica Hodgins, Shubham Tulsiani, Deva Ramanan

We introduce CRISP, a method that recovers simulatable human motion and scene geometry from monocular video. Prior work on joint human--scene reconstruction relies on data-driven priors and joint optimization with no physics in the loop, or recovers noisy geometry with artifacts that cause motion-tracking policies with scene interactions to fail. In contrast, our key insight is to fit simulation-ready convex planar primitives to a depth-based point cloud reconstruction of the scene via a simple clustering pipeline over depth, normals, and flow. To reconstruct scene geometry that might be occluded during interactions, we use human--scene contact modeling (e.g., using human posture to reconstruct the occluded seat of a chair). Finally, we ensure that human and scene reconstructions are physically plausible by using them to drive a humanoid controller via reinforcement learning. Our approach reduces motion-tracking failure rates from 55.2\% to 6.9\% on human-centric video benchmarks (EMDB, PROX), while delivering 43\% faster RL simulation throughput. This demonstrates CRISP's ability to generate physically valid human motion and interaction environments at scale, advancing real-to-sim applications for robotics. Code and interactive demos are available at our project website: https://crisp-real2sim.github.io/CRISP-Real2Sim

Theory · Learning Theory

Tingkai Yan, Haodong Wen, Binghui Li, Kairong Luo, Wenguang Chen, Kaifeng Lyu

While data scaling laws of large language models (LLMs) have been widely examined in the one-pass regime with massive corpora, their form under limited data and repeated epochs remains largely unexplored. This paper presents a theoretical analysis of how a common workaround, training for multiple epochs on the same dataset, reshapes the data scaling laws in linear regression. Concretely, we ask: to match the performance of training on a dataset of size $N$ for $K$ epochs, how much larger must a dataset be if the model is trained for only one pass? We quantify this using the $\textit{effective reuse rate}$ of the data, $E(K, N)$, which we define as the multiplicative factor by which the dataset must grow under one-pass training to achieve the same test loss as $K$-epoch training. Our analysis precisely characterizes the scaling behavior of $E(K, N)$ for SGD in linear regression under either strong convexity or Zipf-distributed data: (1) When $K$ is small, we prove that $E(K, N) \approx K$, indicating that every new epoch yields a linear gain; (2) As $K$ increases, $E(K, N)$ plateaus at a problem-dependent value that grows with $N$ ($\Theta(\log N)$ for the strongly-convex case), implying that larger datasets can be repeated more times before the marginal benefit vanishes. These theoretical findings point out a neglected factor in a recent empirical study by [Muennighoff et al. (2023)](https://arxiv.org/abs/2305.16264), which claimed that training LLMs for up to $4$ epochs results in negligible loss differences compared to using fresh data at each step, $\textit{i.e.}$, $E(K, N) \approx K$ for $K \le 4$ in our notation. Supported by further empirical validation with LLMs, our results reveal that the maximum $K$ value for which $E(K, N) \approx K$ in fact depends on the data size and distribution, and underscore the need to explicitly model both factors in future studies of scaling laws with data reuse.

Optimization · Large Scale, Parallel and Distributed

Alexander Tyurin

We consider centralized distributed optimization in the classical federated learning setup, where $n$ workers jointly find an $\varepsilon$-stationary point of an $L$-smooth, $d$-dimensional nonconvex function $f$, having access only to unbiased stochastic gradients with variance $\sigma^2$. Each worker requires at most $h$ seconds to compute a stochastic gradient, and the communication times from the server to the workers and from the workers to the server are $\tau_{\textnormal{s}}$ and $\tau_{\textnormal{w}}$ seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to $n$. For instance, it is well known that the distributed version of \algname{SGD} has a variance-dependent runtime term $\frac{h \sigma^2 L \Delta}{n \varepsilon^2},$ which improves with the number of workers $n,$ where $\Delta := f(x^0) - f^*,$ and $x^0 \in \mathbb{R}^d$ is the starting point. Similarly, using unbiased sparsification compressors, it is possible to reduce \emph{both} the variance-dependent runtime term and the communication runtime term from $\tau_{\textnormal{w}} d \frac{L \Delta}{\varepsilon}$ to $\frac{\tau_{\textnormal{w}} d L \Delta}{n \varepsilon} + \sqrt{\frac{\tau_{\textnormal{w}} d h \sigma^2}{n \varepsilon}} \cdot \frac{L \Delta}{\varepsilon},$ which also benefits from increasing $n.$ However, once we account for the communication from the server to the workers $\tau_{\textnormal{s}}$, we prove that it becomes infeasible to design a method using unbiased random sparsification compressors that scales both the server-side communication runtime term $\tau_{\textnormal{s}} d \frac{L \Delta}{\varepsilon}$ and the variance-dependent runtime term $\frac{h \sigma^2 L \Delta}{\varepsilon^2},$ better than poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same function or distribution. Indeed, when $\tau_{\textnormal{s}} \simeq \tau_{\textnormal{w}},$ our lower bound is $\tilde{\Omega}(\min[h (\frac{\sigma^2}{n \varepsilon} + 1) \frac{L \Delta}{\varepsilon} + {\tau_{\textnormal{s}} d \frac{L \Delta}{\varepsilon}},\; h \frac{L \Delta}{\varepsilon} + {h \frac{\sigma^2 L \Delta}{\varepsilon^2}}]).$ To establish this result, we construct a new ``worst-case'' function and develop a new lower bound framework that reduces the analysis to the concentration of a random sum, for which we prove a concentration bound. These results reveal fundamental limitations in scaling distributed optimization, even under the homogeneous (i.i.d.) assumption.

Optimization · Everything Else

Zijian Liu

Optimization under heavy-tailed noise has become popular recently, since it better fits many modern machine learning tasks, as captured by empirical observations. Concretely, instead of a finite second moment on gradient noise, a bounded $\mathfrak{p}$-th moment where $\mathfrak{p}\in(1,2]$ has been recognized to be more realistic (say being upper bounded by $\sigma_{\mathfrak{l}}^{\mathfrak{p}}$ for some $\sigma_{\mathfrak{l}}\geq0$). A simple yet effective operation, gradient clipping, is known to handle this new challenge successfully. Specifically, Clipped Stochastic Gradient Descent (Clipped SGD) guarantees a high-probability rate $\mathcal{O}(\sigma_{\mathfrak{l}}\ln(1/\delta)T^{\frac{1}{\mathfrak{p}}-1})$ (resp. $\mathcal{O}(\sigma_{\mathfrak{l}}^{2}\ln^{2}(1/\delta)T^{\frac{2}{\mathfrak{p}}-2})$) for nonsmooth convex (resp. strongly convex) problems, where $\delta\in(0,1]$ is the failure probability and $T\in\mathbb{N}$ is the time horizon. In this work, we provide a refined analysis for Clipped SGD and offer two faster rates, $\mathcal{O}(\sigma_{\mathfrak{l}}d_{\mathrm{eff}}^{-\frac{1}{2\mathfrak{p}}}\ln^{1-\frac{1}{\mathfrak{p}}}(1/\delta)T^{\frac{1}{\mathfrak{p}}-1})$ and $\mathcal{O}(\sigma_{\mathfrak{l}}^{2}d_{\mathrm{eff}}^{-\frac{1}{\mathfrak{p}}}\ln^{2-\frac{2}{\mathfrak{p}}}(1/\delta)T^{\frac{2}{\mathfrak{p}}-2})$, than the aforementioned best results, where $d_{\mathrm{eff}}\geq1$ is a quantity we call the generalized effective dimension. Our analysis improves upon the existing approach in two respects: better utilization of Freedman's inequality and finer bounds for clipping error under heavy-tailed noise. In addition, we extend the refined analysis to convergence in expectation and obtain new rates that break the known lower bounds. Lastly, to complement the study, we establish new lower bounds for both high-probability and in-expectation convergence. Notably, the in-expectation lower bounds match our new upper bounds, indicating the optimality of our refined analysis for convergence in expectation.

Optimization · Non-Convex

Haocheng Luo, Zehang Deng, Thanh-Toan Do, Mehrtash Harandi, Dinh Phung, Trung Le

Direct Preference Optimization (DPO) has emerged as a popular algorithm for aligning pretrained large language models with human preferences, owing to its simplicity and training stability. However, DPO suffers from the recently identified *squeezing effect* (also known as *likelihood displacement*), where the probability of preferred responses decreases unintentionally during training. To understand and mitigate this phenomenon, we develop a theoretical framework that models the coordinate-wise dynamics in logit space. Our analysis reveals that negative-gradient updates cause residuals to expand rapidly along high-curvature directions, which underlies the squeezing effect, whereas Sharpness-Aware Minimization (SAM) can suppress this behavior through its curvature-regularization effect. Building on this insight, we investigate *logits-SAM*, a computationally efficient variant that perturbs only the output layer with negligible overhead. Extensive experiments on Pythia-2.8B, Mistral-7B, and Gemma-2B-IT across multiple datasets and benchmarks demonstrate that logits-SAM consistently improves the effectiveness of DPO and integrates seamlessly with other DPO variants. Code is available at .

Theory · Reinforcement Learning and Planning

Anand Brahmbhatt, Gon Buzaglo, Sofiia Druchyna, Elad Hazan

We propose a new method for controlling linear dynamical systems under adversarial disturbances and cost functions. Our algorithm achieves a running time that scales polylogarithmically with the inverse of the stability margin, improving upon prior methods with polynomial dependence maintaining the same regret guarantees. The technique, which may be of independent interest, is based on a novel convex relaxation that approximates linear control policies using spectral filters constructed from the eigenvectors of a specific Hankel matrix.

Optimization · Learning for Optimization

Panagiotis D. Grontas, Antonio Terpin, Efe Balta, Raffaello D&amp;#x27;Andrea, John Lygeros

We introduce an output layer for neural networks that ensures satisfaction of convex constraints. Our approach, $\Pi$net, leverages operator splitting for rapid and reliable projections in the forward pass, and the implicit function theorem for backpropagation. We deploy $\Pi$net as a feasible-by-design optimization proxy for parametric constrained optimization problems and obtain modest-accuracy solutions faster than traditional solvers when solving a single problem, and significantly faster for a batch of problems. We surpass state-of-the-art learning approaches by orders of magnitude in terms of training time, solution quality, and robustness to hyperparameter tuning, while maintaining similar inference times. Finally, we tackle multi-vehicle motion planning with non-convex trajectory preferences and provide $\Pi$net as a GPU-ready package implemented in JAX.

Optimization · Large Scale, Parallel and Distributed

Xiaowen Jiang, Anton Rodomanov, Sebastian Stich

Different federated optimization algorithms typically employ distinct client-selection strategies: some methods communicate only with a randomly sampled subset of clients at each round, while others need to periodically communicate with all clients or use a hybrid scheme that combines both strategies. However, existing metrics for comparing optimization methods typically do not distinguish between these strategies, which often incur different communication costs in practice. To address this disparity, we introduce a simple and natural model of federated optimization that quantifies communication and local computation complexities. This new model allows for several commonly used client-selection strategies and explicitly associates each with a distinct cost. Within this setting, we propose a new algorithm that achieves the best-known communication and local complexities among existing federated optimization methods for non-convex optimization. This algorithm is based on the inexact composite gradient method with a carefully constructed gradient estimator and a special procedure for solving the auxiliary subproblem at each iteration. The gradient estimator is based on SAGA, a popular variance-reduced gradient estimator. We first derive a new variance bound for it, showing that SAGA can exploit functional similarity. We then introduce the Recursive-Gradient technique as a general way to potentially improve the error bound of a given conditionally unbiased gradient estimator, including both SAGA and SVRG. By applying this technique to SAGA, we obtain a new estimator, RG-SAGA, which has an improved error bound compared to the original one.

Optimization · Non-Convex

Yudong Wei, Liang Zhang, Bingcong Li, Niao He

While normalization techniques are widely used in deep learning, their theoretical understanding remains relatively limited. In this work, we establish the benefits of (generalized) weight normalization (WN) applied to the overparameterized matrix sensing problem. We prove that WN with Riemannian optimization achieves linear convergence, yielding an $\textit{exponential}$ speedup over standard methods that do not use WN. Our analysis further demonstrates that both iteration and sample complexity improve polynomially as the level of overparameterization increases. To the best of our knowledge, this work provides the first characterization of how WN leverages overparameterization for faster convergence in matrix sensing.