English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Zeroth-order optimization is a fundamental research topic that has been afocus of various learning tasks, such as black-box adversarial attacks,bandits, and reinforcement learning. However, in theory, most complexityresults assert a linear dependency on the dimension of optimization variable,which implies paralyzations of zeroth-order algorithms for high-dimensionalproblems and cannot explain their effectiveness in practice. In this paper, wepresent a novel zeroth-order optimization theory characterized by complexitiesthat exhibit weak dependencies on dimensionality. The key contribution lies inthe introduction of a new factor, denoted as $\mathrm{ED}_{\alpha}=\sup_{x\in\mathbb{R}^d}\sum_{i=1}^d\sigma_i^\alpha(\nabla^2 f(x))$ ($\alpha>0$,$\sigma_i(\cdot)$ is the $i$-th singular value in non-increasing order), whicheffectively functions as a measure of dimensionality. The algorithms we proposedemonstrate significantly reduced complexities when measured in terms of thefactor $\mathrm{ED}_{\alpha}$. Specifically, we first study a well-knownzeroth-order algorithm from Nesterov and Spokoiny (2017) on quadraticobjectives and show a complexity of$\mathcal{O}\left(\frac{\mathrm{ED}_1}{\sigma_d}\log(1/\epsilon)\right)$ forthe strongly convex setting. Furthermore, we introduce novel algorithms thatleverages the Heavy-ball mechanism. Our proposed algorithm exhibits acomplexity of$\mathcal{O}\left(\frac{\mathrm{ED}_{1/2}}{\sqrt{\sigma_d}}\cdot\log{\frac{L}{\mu}}\cdot\log(1/\epsilon)\right)$.We further expand the scope of the method to encompass generic smoothoptimization problems under an additional Hessian-smooth condition. Theresultant algorithms demonstrate remarkable complexities which improve by anorder in $d$ under appropriate conditions. Our analysis lays the foundation forzeroth-order optimization methods for smooth functions within high-dimensionalsettings.

Zeroth-order Optimization with Weak Dimension Dependency