{"ID":2881361,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.12228","arxiv_id":"2508.12228","title":"Can a One-Point Feedback Zeroth-order Algorithm Achieve Linear Dimension Dependent Sample Complexity?","abstract":"We revisit the one-point feedback zeroth-order (ZO) optimization problem, a classical setting in derivative-free optimization where only a single noisy function evaluation is available per query. Compared to their two-point counterparts, existing one-point feedback ZO algorithms typically suffer from poor dimension dependence in their sample complexities -- often quadratic or worse -- even for convex problems. This gap has led to the open question of whether one-point feedback ZO algorithms can match the optimal \\emph{linear} dimension dependence achieved by two-point methods. In this work, we answer this question \\emph{affirmatively}.","short_abstract":"We revisit the one-point feedback zeroth-order (ZO) optimization problem, a classical setting in derivative-free optimization where only a single noisy function evaluation is available per query. Compared to their two-point counterparts, existing one-point feedback ZO algorithms typically suffer from poor dimension dep...","url_abs":"https://arxiv.org/abs/2508.12228","url_pdf":"https://arxiv.org/pdf/2508.12228v1","authors":"[\"Haishan Ye\",\"Xiangyu Chang\"]","published":"2025-08-17T04:01:51Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}