Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

arXiv:2609.38561 · math.OC, cs.LG · Submitted 2026-09-29 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling".

Jane: The gist: POEM-ES, a novel parameterfree stochastic zeroth-order algorithm that extends the POEM framework by integrating subspace preconditioning with ellipsoidal randomized sampling,

Tom: First, who's behind it and why it matters.

Title and authors: Jane: We’ve talked about how they use ellipsoidal sampling and subspace preconditioning in "Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling." Now, let's really dig into what the overall summary of this paper is saying.

Lu: The core idea is that traditional zeroth-order methods rely on isotropic random directions, which means they explore equally in all dimensions, but POEM-ES uses a fixed structural symmetric positive semi-definite preconditioner Sigma hat to perform anisotropic sampling.

Tom: So the summary boils down to this: they take the standard POEM method and enhance it by integrating this subspace preconditioning with ellipsoidal randomized sampling.

Meng: They are replacing that simple random direction search with something much more targeted, focusing queries strictly along the most informative directions of the problem landscape.

Jane: This targeting is managed by defining the empirical effective dimension d star as the trace of that preconditioner matrix Sigma hat, which tells us how many significant directions we actually have to worry about.

Lu: They show that this structure allows them to decouple sampling direction and spatial scale, which is crucial for controlling the variance of their gradient estimators.

Tom: The estimator they use is called the subspace-unbiased anisotropic two-point gradient estimator, g t equals r squared mu t F(x t plus mu t Sigma hat one/two vt; xi t) minus F(x t minus mu t Sigma hat one/two vt; xi t) Sigma hat plus one/two vt <ref:2609.38561#pg1>.

Jane: That specific definition is how they ensure that the estimator remains unbiased under certain conditions, effectively bypassing some of the dimensional inflation issues that usually plague these methods.

Meng: They are essentially creating a way to estimate first-order information that is specifically tuned to the low-rank structure they’ve identified.

Lu: And they prove this works by showing an exact algebraic identity for the conditional second-moment matrix, Evtv T F t minus one equals one over r PS, which shows how the integer dimension of the active subspace naturally emerges from spherical integration <ref:2609.38561#pg1>.

Tom: That identity is a piece of mathematical proof that validates their entire approach by showing that the geometry of the active subspace dictates the sampling behavior in a predictable way.

Jane: It confirms that if you know your low-rank structure, you can design an algorithm specifically to exploit it for better performance.

The paper's summary: Tom: Now let’s talk about the specific improvements they propose in this paper, because it’s not just a tweak; it’s a fundamental change in how we approach this optimization problem.

Jane: The most significant improvement is moving from unconstrained directional sampling to matrix-valued space transformation using an ellipsoidal preconditioning matrix Sigma hat.

Lu: By using this preconditioning matrix, they allow the algorithm to focus exploration strictly along the most informative directions of the problem, which is a huge step up from traditional isotropic random approaches.

Meng: This leads directly to their second big point: achieving a dimension-reduced convergence rate under low-rank structural assumptions.

Tom: They manage to reduce that complexity dependency on the ambient dimension d by scaling it based on the structural subspace parameters, specifically r squared kappa of Sigma hat plus d star L2D2 X epsilon squared.

Jane: That means the complexity scales with how complex the structure is, not just how high dimensional our problem space is, which directly addresses a major hurdle in high-dimensional black-box optimization.

Lu: They also introduce a robust step size adaptation where η t is set as r bar t over the square root of Gt, and they adapt the smoothing parameter mu t by setting it to r bar t over d star.

Tom: Those two scheduling mechanisms work together to ensure that both the exploration scale and the noise reduction are adaptively guided by that effective dimension d star.

Meng: This adaptive guidance leads to improved numerical stability and better trajectory following compared to older isotropic methods where you might have fixed parameters for a long time.

Jane: And they also emphasize the empirical source of preconditioning operators, suggesting we can use pilot sampling or historical trajectories to construct Sigma hat without needing heavy online matrix updates.

Lu: They found that this structural preconditioner acts like a very effective heuristic for capturing low-rank task geometry, which is key because we don't always know the true structure beforehand.

Tom: So the improvements are really about making the method robust and efficient by tying every parameter—direction, scale, step size—to that underlying low-rank structure.

Jane: It’s about moving from a brute-force search to an intelligently guided search based on what we know about the problem's shape.

The paper's improvements: Tom: We're wrapping up this discussion on "Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling." In short, the paper presents POEM-ES as a parameterfree stochastic zeroth-order algorithm that integrates subspace preconditioning and ellipsoidal sampling to exploit low-rank geometry.

Jane: The main implication is that this method provides a rigorous theoretical guarantee: for any delta less than one, the functional gap under the true algorithmic output x bar t is bounded by O((r squared kappa of Sigma hat plus d star root T theta t, delta L2D2 X epsilon squared).

Lu: This bound demonstrates that when you assume low-rank structural assumptions hold—specifically that d star is much smaller than the ambient dimension d—the complexity scales based on those structural parameters.

Meng: It means for practitioners, we can tackle massive black-box problems without being completely paralyzed by the high ambient dimension of the data space.

Tom: And numerically, they showed it consistently outperforms both baseline POEM and two-point bandit methods like TPBCO in terms of functional gap reduction and final solution quality.

Jane: So, POEM-ES is a powerful way to solve complex problems because it removes the explicit ambient dimension dependence under those low-rank structural assumptions.

Lu: It’s a significant theoretical refinement in how we understand convergence rates for these types of black-box optimization tasks.

Meng: For practical use, it suggests that if we can find a good way to construct that structural matrix Sigma hat, the resulting algorithm is incredibly efficient and stable.

Tom: That's what this paper is all about: using mathematical structure to tame the complexity of high-dimensional black-box optimization with POEM-ES.

Conclusion: Tom: So we’ve been talking about POEM-ES, the Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling paper by Ren and Luo at arXiv.

Jane: It’s really a method that takes standard zeroth-order optimization and adds this specific geometric preconditioning to focus the search.

Lu: The core idea is using an ellipsoidal preconditioning matrix, Sigma hat, to perform anisotropic sampling instead of just random directions.

Meng: That means the algorithm isn't wasting queries in irrelevant dimensions; it’s concentrating them where the problem is actually interesting.

Tom: Exactly. And they show this works by defining an empirical effective dimension d star based on that matrix Sigma hat, which gives us a way to measure the complexity of the structure we’re exploiting.

Jane: And they get a dimension-reduced convergence rate, O(r squared kappa of Sigma hat plus d star root T theta t, delta L2D2 X epsilon squared).

Lu: That bound is really neat because it shows that the complexity scales with the intrinsic geometry—the rank r and the condition number kappa of Sigma hat—not just the total ambient dimension d.

Meng: I wonder how practical that is. If we can reliably estimate that structural matrix Sigma hat, then we might actually be able to solve problems in much higher dimensions than before.

Tom: That’s the big takeaway for me: it moves us away from scaling purely with the input size d and towards scaling with the actual complexity of the optimization landscape itself.

Jane: And they showed numerically that this approach consistently beats baseline methods like TPBCO in terms of both functional gap reduction and final solution quality on real classification tasks.

Lu: The mathematical proof involving Lemma three about the second-moment matrix identity is what really locks down how that active subspace dimension r emerges naturally from the integration.

Meng: From an engineering standpoint, the fact that they can use pilot sampling or historical runs to build Sigma hat without constant online updates is a huge plus for real-world deployment.

Tom: It’s about building something robust enough to handle complex optimization landscapes without needing a perfect pre-knowledge of the problem structure upfront.

Jane: So, the POEM-ES paper by Ren and Luo gives us a new tool for black-box optimization that leverages low-rank geometry for better scaling.

Lu: It opens up possibilities for applying this idea to areas where we know the underlying function structure is inherently low-rank, like certain scientific simulations.

Meng: We should definitely look into how they handle those non-convex scenarios next, since their analysis focused on convex optimization assumptions.

Tom: Right, and that leads us perfectly into the next paper we’re looking at—it’s about memorization in diffusion models and whether you can probe that energy landscape geometry to check for copies.

Alexander Sholokhov, Alexander Rogozin

Moscow Institute of Physics and Technology

math.OC, cs.LG

Submitted: 2026-09-29

Updated: 2026-10-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: The gist: POEM-ES, a novel parameterfree stochastic zeroth-order algorithm that extends the POEM framework by integrating subspace preconditioning with ellipsoidal randomized sampling, achieves

Key concepts

Ellipsoidal Preconditioning Matrix ($\hat{\Sigma}$): This matrix transforms the search space to focus exploration on the most informative directions of the problem. It encodes the underlying low-dimensional geometry, allowing the algorithm to perform anisotropic sampling instead of relying on isotropic random directions.
Empirical Effective Dimension ($d^*)$: Defined as $\operatorname{tr}(\hat{\Sigma}) \cdot \lambda_{\max}(\hat{\Sigma})$, this scalar ratio reflects the intrinsic dimensionality of the problem. It guides both the sampling strategy and the smoothing parameter schedules, reflecting how many significant directions actually exist.
Anisotropic Sampling: Instead of uniform random directions, POEM-ES generates directional vectors constrained to an active subspace defined by $\hat{\Sigma}$. This allows the algorithm to sample intelligently along the most relevant geometric features of the objective function.

Terminology

Preconditioner — 12× in this paper · explained in 2 episodes
Alignment — 9× in this paper
Core — 9× in this paper · explained in 2 episodes
Objective Function — 6× in this paper · explained in 2 episodes
Trace — 5× in this paper · explained in 2 episodes
Regret — 4× in this paper · explained in 3 episodes
Reinforcement Learning — 3× in this paper · explained in 4 episodes
Adaptation — 2× in this paper · explained in 1 episode
Adversarial Examples — 2× in this paper · explained in 2 episodes
Adversarial Training — 2× in this paper · explained in 1 episode
Query Complexity — 2× in this paper · explained in 2 episodes
Adam — 1× in this paper · explained in 2 episodes
Adversarial Attacks — 1× in this paper · explained in 1 episode
Benchmark — 1× in this paper · explained in 2 episodes
Benchmarking — 1× in this paper · explained in 4 episodes
Curse of Dimensionality — 1× in this paper · explained in 6 episodes
Diffusion Model — 1× in this paper · explained in 10 episodes
Diffusion Models — 1× in this paper · explained in 9 episodes
Hyperparameters — 1× in this paper · explained in 2 episodes
Loss Function — 1× in this paper · explained in 2 episodes
Parameterization — 1× in this paper · explained in 2 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

The gist: POEM-ES, a novel parameterfree stochastic zeroth-order algorithm that extends the POEM framework by integrating subspace preconditioning with ellipsoidal randomized sampling, achieves near-optimal convergence rates under low-rank structural assumptions, requiring only O˜(r 2κ(Σˆ)+d∗)L2D2Xε squared stochastic zeroth-order oracle queries

How it works

The method replaces traditional unconstrained directional sampling with a matrix-valued space transformation using an ellipsoidal preconditioning matrix Σˆ, which focuses exploration strictly along the most informative directions of the problem The update rule follows the projected stochastic gradient descent framework, where xt+1 = ΠX(xt − ηtg˜t) Crucially, POEM-ES decouples sampling direction and spatial scale by generating a uniform directional vector vt on the exact unit sphere of the active subspace and injecting anisotropic geometric scaling via the matrix square root Σˆ1/2 The novel subspace-unbiased anisotropic two-point gradient estimator is defined as g˜t = r 2µt F(xt + µtΣˆ1/2 vt; ξt) − F(xt − µtΣˆ1/2 vt; ξt) Σˆ+1/2 vt

Key Components and Definitions

The algorithm relies on several structural definitions to manage the low-rank geometry of the problem

** Empirical effective dimension d∗ is defined as the continuous scalar ratio: d∗(Σ) ≜ tr(Σ) λmax(Σ), which satisfies the spectral bound 1 ⩽ d∗(Σ) ⩽ r ≤ d This reflects the intrinsic number of significant directions and guides both sampling and randomized smoothing parameter schedules The active low-rank optimization subspace S is defined as range(Σˆ) ≜ range(Σˆ), with algebraic rank r = rank(Σˆ) ⩽ d The structural preconditioner Σˆ is assumed to be normalized such that λmax(Σˆ) = 1 This normalization simplifies the analysis by ensuring λmax(Σˆ) = 1 The distance scaling parameter s0 is introduced, satisfying∥x0 − x⋆∥ ⩽ s0 The maximum traveled distance r¯t is defined as max0≤k≤t∥xk − x0∥∨rϵ, where rϵ > 0 is a small initial mobility constant The accumulated sum of squared gradient estimator norms Gt is defined as Pt k=0∥gk∥2 The step size ηt is set as ηt = r¯t √Gt, which follows the fully parameter-free step size based on the ratio of the maximum traveled distance to the accumulated norm of gradient estimates The smoothing parameter µt is adapted by setting µt ≜ r¯rt/d∗ t+1 This choice is larger than typical smoothing parameters and improves numerical stability in high-dimensional settings The algorithm maintains a fully parameterfree nature, as the step size and smoothing trajectories are guided by the continuous effective dimension d∗ The empirical source of preconditioning operators can be obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge These techniques provide a robust heuristic for capturing lowrank task geometry without requiring heavy online matrix updates The experiments confirm that ellipsoidal preconditioning provides substantial practical acceleration over isotropic baselines by isolating a stable active subspace with an effective dimension of d∗ = 25 and an intrinsic condition number κ = 6 on the mushrooms dataset It also encapsulates a low-rank geometry characterized by d**

35 and κ = 4 on the higher-dimensional w8a dataset

Theoretical Analysis

The theoretical analysis establishes that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions The core mechanism relies on demonstrating that the geometric scales of the preconditioned gradient trajectory are properly decoupled, controlling the estimator norm and variance by the active subspace rank r and condition number κ(Σˆ) Lemma 3 proves that for a random vector vt sampled from N (0, PS) restricted to S, the conditional second-moment matrix satisfies the exact algebraic identity E[vtv TFt−1] = 1/r PS This shows how the integer dimension of the active subspace naturally emerges from spherical integration The core result is Theorem 1, which states that for any δ ∈ (0, 1), the functional gap under the true algorithmic ergodic output x¯τT is bounded by f(¯xτT) − f(x∗) ⩽ O((r 2κ(Σˆ)+d∗√T·θT,δLDX log+DX/rϵ) This bound demonstrates that the complexity scales as T ⩽ O˜(r 2κ(Σˆ)+d∗)L2D2Xε squared

Convergence and Performance

The convergence proof combines several bounds, including the weighted regret control from Lemma 8, the martingale noise concentration from Lemma 9, and the ellipsoidal smoothing bias bound from Lemma 10 The final high-probability bound for any arbitrary step t is f(¯xt) − f(x∗) ⩽ O((r 2κ(Σˆ)+d∗√T·θT,δLDX log+DX/rϵ) This result shows that the ellipsoidal preconditioning removes the explicit ambient-dimension dependence under low-rank structural assumptions The numerical experiments confirm that POEM-ES consistently outperforms both the baseline POEM and the two-point bandit method TPBCO in terms of functional gap reduction and final solution quality This superiority is attributed to average-case subspace alignment, spectral preconditioning that warps ill-conditioned domains into isotropic basins, and spatial noise reduction through adaptive smoothing parameters Future research directions include extending the framework to nonconvex optimization and exploring online adaptive covariance learning strategies that maintain strict spectral stability The paper concludes by showing that the complexity scales as T ⩽ O˜(r 2κ(Σˆ)+d∗)L2D2Xε squared This bound represents a substantial theoretical improvement in high-dimensional black-box optimization

Conclusion

POEM-ES introduces anisotropic directional perturbations guided by a structural matrix Σˆ, which allows the algorithm to explicitly exploit intrinsic low-rank structures commonly present in high-dimensional real-world optimization landscapes The rigorous non-asymptotic theoretical analysis proves that the ellipsoidal preconditioning removes the explicit ambient dimension dependence under stated low-rank structural assumptions Extensive numerical experiments on hinge-loss binary classification tasks using real LibSVM datasets confirm the practical advantages of the proposed approach POEM-ES consistently outperforms both the baseline POEM and the two-point bandit baseline TPBCO in terms of functional gap reduction and final solution quality Future research directions include extending the proposed framework to nonconvex optimization, exploring online adaptive covariance learning strategies that maintain strict spectral stability, and applying POEM-ES to large-scale deep learning or scientific computing domains The complexity scales as T ⩽ O˜(r 2κ(Σˆ)+d∗)L2D2Xε squared This bound represents a substantial theoretical improvement in high-dimensional black-box optimization The paper is complete.

--- Page 17 ---

References

Kunjie Ren and Luo Luo. A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization. arXiv preprint arXiv:2502.05600, 2025
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd’s best friend: A parameterfree dynamic step size schedule. In International Conference on Machine Learning, pages 14465–14499. PMLR, 2023
Yair Carmon and Oliver Hinder. Making sgd parameter-free. In Conference on Learning Theory, pages 2360–2389. PMLR, 2022
Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, 29, 2016
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788–2806, 2015
Ohad Shamir.

Improvements for AI systems

Improved exploration via anisotropic sampling: The POEM-ES method performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner Σˆ that encodes the underlying low-dimensional geometry, concentrating queries along the most informative directions. This allows the AI to focus computational effort on the relevant, low-rank manifold rather than wasting queries in irrelevant ambient dimensions.
Dimension-reduced convergence rate: The system achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only O˜(r 2κ(Σˆ)+d∗)L2D2Xε squared stochastic zeroth-order oracle queries. This means the AI can solve complex black-box problems in high dimensions by scaling its query complexity based on the intrinsic geometry (subspace rank r and effective dimension d∗), avoiding the curse of dimensionality associated with ambient dimension d.
Robust step size adaptation: The algorithm uses a dynamic step size schedule where ηt is then set as ¯rt/√Gt, which adapts to the optimization progress. This, combined with an adaptive smoothing parameter µt = ¯rt/r d∗, ensures the exploratory scale of randomized smoothing is adaptively guided by the effective dimension d∗, leading to improved numerical stability and better trajectory following than isotropic methods.
Subspace-unbiased gradient estimation: POEM-ES employs a subspace-unbiased anisotropic two-point gradient estimator g˜t which, under specific conditions, ensures E[˜gt Ft−1] = PS∇fµt,Σˆ (xt), effectively bypassing dimensional inflation by projecting the gradient onto the active low-rank subspace S.
Practical preconditioning heuristics: The system can utilize empirical methods like Pilot Sampling Heuristics or Historical Trajectory Runs to construct the structural matrix Σˆ. This allows for rapid functional gap minimization by initializing the optimization with an empirically constructed ellipsoidal preconditioning matrix, which is shown to provide a highly effective heuristic for capturing the underlying low-rank task geometry.