EGGROLL, Unrolled: Understanding and Improving Low-Rank Evolution Strategies at Scale

• URL: http://arxiv.org/abs/2609.10980v1
• Date: Thu, 10 Sep 2026 01:58:02 GMT
• Title: EGGROLL, Unrolled: Understanding and Improving Low-Rank Evolution Strategies at Scale
• Abstract summary: EGGROLL makes evolution strategies practical for LLMs by replacing dense Gaussian weight perturbations with low-rank Gaussian products.<n>We analyze the error of its finite-population estimator.<n>LOO-ROLL, a leave-one-out estimator, preserves the finite-rank population field while replacing EGGROLL's two antithetic evaluations per direction by one.
• Score: 9.562123195246393
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: EGGROLL makes evolution strategies (ES) practical for LLMs by replacing dense Gaussian weight perturbations with low-rank Gaussian products, often of rank one. This choice is computationally attractive but geometrically severe: each rank-one perturbation lies in a zero-volume subset of the ambient matrix space, despite having identity covariance. We characterize the mean EGGROLL update field at finite rank and nonzero perturbation radii, then analyze the error of its finite-population estimator. The population field is obtained by applying an explicit resolvent to the gradient of the objective smoothed by the perturbations. We show that the resolvent can introduce a nonconservative component and can reverse the local stability of an optimum. EGGROLL is nevertheless exact on every quadratic objective at every rank and radius. For smooth objectives, its first local finite-rank correction is $O(σ^2/r)$, and nonasymptotic bounds control the resulting field error under smoothness assumptions. Under a local affine model, rank-one perturbations increase the variance of the gradient estimator by only $\frac{2(m+n+1)}{mn+1}$ relative to dense Gaussian ES, or $0.098\%$ for a $4096\times4096$ matrix. We then introduce LOO-ROLL, a leave-one-out estimator that preserves the finite-rank population field while replacing EGGROLL's two antithetic evaluations per direction by one. At equal evaluation cost, LOO-ROLL halves estimator MSE in transformer blocks. At matched wall time across ten post-training settings and models up to 8B parameters, LOO-ROLL improves seven outcomes in individual paired tests, with no significant loss. On the GSM8K test set, accuracy increases from $38.1\%$ to $63.0\%$ at 0.6B and from $65.9\%$ to $80.0\%$ at 8B. Transformer measurements recover the predicted finite-rank variance, while the rank comparisons show no reproducible reward-based advantage for rank eight.

Related papers

• Laplace-Fisher Gate Identities for Optimal Matrix-Gated Blended Score Estimation [0.0]
  Laplace-Fisher Gate Identity (LFGI)<n> finite-reference LFGI estimator to normalized density evaluation for Bayesian inverse problems.<n>Experiments using LFGI with known model evidence check absolute evidence calibration in both Gaussian and non-Gaussian settings.
  arXiv  Detail & Related papers  (2026-06-23T21:00:32Z)
• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  We study the feedback in a Gaussian single-index model with $r*(x) = *(langle *, xrangle)$ and $x sim N(0, I_d)$.<n>We analyze a two-stage neural reward model that first learns the hidden direction $*$ from reward-weighted samples and then fits the readout layer by weighted ridge regression.
  arXiv  Detail & Related papers  (2026-05-23T22:00:38Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression [12.805268849262243]
  We study online covariance matrix estimation for Polyak-Ruppert averaged gradient descent (SGD)<n>The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.
  arXiv  Detail & Related papers  (2026-04-12T20:49:33Z)
• Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions [3.6997773420183866]
  We develop new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method.<n>Unlike unbiased estimators such as mini-batching, developing biased variants faces a fundamental technical challenge.<n>We show that the best oracle complexities for the $n$-finite-sum and expectation settings are $mathcalO(n2/3-2)$ and $mathcalO(-10/3)$, respectively, when employing loopless-SVRG or SAGA.
  arXiv  Detail & Related papers  (2026-03-16T17:39:25Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Information Hidden in Gradients of Regression with Target Noise [2.8911861322232686]
  We show that the gradients alone can reveal the Hessian.<n>We provide non-asymptotic operator-norm guarantees under sub-Gaussian inputs.
  arXiv  Detail & Related papers  (2026-01-26T14:50:16Z)
• Evolution Strategies at the Hyperscale [57.75314521465674]
  We introduce EGGROLL, an evolution strategies (ES) algorithm designed to scale backprop-free optimization to large population sizes.<n>ES is a set of powerful blackbox optimisation methods that can handle non-differentiable or noisy objectives.<n>EGGROLL overcomes these bottlenecks by generating random matrices $Ain mathbbRmtimes r, Bin mathbbRntimes r$ with $rll min(m,n)$ to form a low-rank matrix perturbation $A Btop$
  arXiv  Detail & Related papers  (2025-11-20T18:56:05Z)
• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
  Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)<n>Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)
  arXiv  Detail & Related papers  (2025-05-19T07:32:56Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Gradient Estimation for Binary Latent Variables via Gradient Variance Clipping [6.234350105794441]
  gradient estimation is often necessary for fitting generative models with discrete latent variables. DisARM and other estimators have potentially exploding variance near the boundary of the parameter space. We propose a new gradient estimator textitbitflip-1 that has lower variance at the boundaries of the parameter space.
  arXiv  Detail & Related papers  (2022-08-12T05:37:52Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.