Research map / Optimization / Nonconvex and smooth optimization
Improved Dimensionality Dependence for Zeroth-Order Optimisation over Cross-Polytopes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes mirror descent with a symmetric negative 1/2-Tsallis entropy plus an ℓ1-ellipsoidal smoothing gradient estimator to improve the dimensionality dependence of zeroth-order optimisation over cross-polytopes from O(√(d log d)) to O(√d), and extends the idea to nonsmooth nonconvex stochastic optimisation.
Problem
Gradient-free (bandit) convex optimisation with two-point feedback over cross-polytopes, and zeroth-order stationarity finding for nonsmooth nonconvex functions, where prior dimensionality dependence (√(d log d)) is not matched by the known lower bound.
Approach
Replace the ℓ2/ℓ∞-geometry based approach with an ℓ1-ellipsoidal smoothing gradient estimator whose per-coordinate variance scales with the inverse of the decision variable, and run mirror descent with a symmetric extension of the negative 1/2-Tsallis entropy (inspired by INF) to normalise this variance.
Key results
- Bandit convex optimisation over cross-polytopes with two-point feedback achieves regret O(√(dT)) (scaled by L1), improving the best prior dimensionality dependence by a factor of √log d.
- Nonsmooth nonconvex stochastic zeroth-order method finds a (δ, ϵ)-stationary point with O(d L1^2 δ^-1 ϵ^-3) function evaluations, matching the best known result of Kornowski & Shamir (2023).
- Symmetric negative 1/2-Tsallis entropy update with ℓ1-ellipsoidal smoothing normalises gradient variance, removing the log d factor from the regret bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace ℓ1-ball sampling and entropy mirror descent with ℓ1-ellipsoid sampling and symmetric Tsallis-entropy mirror descent | Bandit convex optimisation over cross-polytopes · Bandit convex optimisation with two-point feedback over cross-polytopes | regret upper bound: T^{1/2} (d log d)^{1/2} -> T^{1/2} d^{1/2} | Helped |
| Apply ℓ1 geometry and the proposed smoothing and mirror-descent approach | Stochastic nonconvex, non-smooth optimisation · Gradient-free nonconvex and non-smooth optimisation | function evaluations: O(d^{3/2}L_2^2δ^{-1}ϵ^{-3}) -> O(dL_1^2δ^{-1}ϵ^{-3}) | Helped |
Limitations
- Practical performance not evaluated experimentally; the paper says rigorous experiments are required.
- Decision-variable-dependent smoothing makes advanced variance reduction (e.g., recursive gradient) difficult while keeping small dimensionality dependence.
- Nonsmooth nonconvex result only matches, not improves, the best known complexity of Kornowski & Shamir (2023) in dimensionality.
Experimental setup
Metrics: regret upper bound iteration/function-evaluation complexity
Baselines: Shamir 2017 Akhavan et al. 2022 Lin et al. 2022 Chen et al. 2023a Kornowski & Shamir 2023
Builds on: INF (Implicitly Normalised Forecaster) ℓ1-ball smoothing (Akhavan et al., 2022) online-to-nonconvex conversion (Cutkosky et al., 2023) Kornowski & Shamir 2023 gradient-free nonsmooth method
Closest papers by meaning
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results (NeurIPS 2025 · similarity 0.85)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.85)
- Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity (NeurIPS 2026 · similarity 0.85)
- Mirror and Preconditioned Gradient Descent in Wasserstein Space (NeurIPS 2024 · similarity 0.85)
- Mirror Descent-Ascent for mean-field min-max problems (NeurIPS 2026 · similarity 0.84)
- Non-convex Stochastic Composite Optimization with Polyak Momentum (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.