Pith. sign in

REVIEW 3 major objections 4 minor 61 references

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A distance-driven step-size and smoothing schedule makes stochastic zeroth-order convex optimization parameter-free at the near-optimal oracle complexity.

desk verdict The adaptive smoothing is a nice idea, but the proof of the main theorem conditions on a data-dependent event and then treats a conditional expectation as an unconditional one, so the near-optimal rate is not established as written. read the letter →

arxiv 2502.05600 v2 pith:6WY257G7 submitted 2025-02-08 math.OC

Kunjie Ren , Luo Luo This is my paper · ORCID
classification math.OC MSC 90C2590C15
keywords parameter-freeoptimizationzeroth-orderstochasticconvexrandomizedsmoothingfinitedifferenceadaptivestepsizeoraclecomplexitymartingaleconcentration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that stochastic convex optimization with only two noisy function evaluations per step can be made genuinely parameter-free without sacrificing the best known convergence rate. The proposed method, POEM, sets its own step size from the distance its iterates have traveled divided by the accumulated norm of its finite-difference estimates, and it shrinks the smoothing radius adaptively with the same distance measure. The main theorem bounds the expected optimality gap by $O((d/T + \sqrt{d}/\sqrt{T}) L D_X \log(D_X/r_\epsilon))$ with high probability, which yields an oracle complexity of $\tilde{O}(d L^2 D_X^2 / \epsilon^2)$. This matches the lower bound for stochastic zeroth-order optimization, while no knowledge of the Lipschitz constant, the iteration budget, or the target accuracy is required. The paper also shows that on unbounded domains, such ideal parameter-freedom is impossible, and a modified version needs only estimates of the initial distance and the Lipschitz constant.

What carries the argument

The engine of the proof is the distance-over-finite-difference schedule: at each step $t$, the step size is $\eta_t = \bar{r}_t/\sqrt{G_t}$ and the smoothing parameter is $\mu_t = \bar{r}_t\sqrt{d/(t+1)}$, where $\bar{r}_t = \max\{r_\epsilon, \max_{k\le t}\|x_k-x_0\|\}$. This couples both algorithmic constants to the trajectory actually taken, so they adapt to the problem instead of requiring $L$, $T$, or $\epsilon$. The analysis decomposes the optimality gap of the weighted average $\bar{x}_t$ into three parts: a weighted regret term bounded by Lemma 3 as $\bar{r}_t(2\bar{s}_t+\bar{r}_t)\sqrt{G_{t-1}}$, a martingale noise term from the random finite-difference estimates controlled by a time-uniform concentration inequality, and a smoothing-bias term of order $\sum_k 2L\bar{r}_k\mu_k$. A summation lemma converts the weighted-average denominator into the factor $T/\log_+(D_X/r_\epsilon)$, which is what turns the adaptive schedule into the near-optimal rate.

What would settle it

Construct a stochastic convex instance where $f(x)=E_\xi[F(x,\xi)]$ is $L$-Lipschitz but each realization $F(\cdot;\xi)$ has unbounded or realization-dependent Lipschitz constants, and run POEM on it: if the observed oracle complexity exceeds $\tilde{O}(dL^2D_X^2/\epsilon^2)$ or the step-size process becomes unstable, the per-sample Lipschitz assumption is the load-bearing premise. Concretely, check whether the two inequalities $\|g_t\|\le Ld$ and $E\|g_t\|^2\le cL^2d$ from Lemma 4 still hold on such an instance.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that the two parameters usually hand-tuned in zeroth-order methods—the step size and the smoothing radius—can both be driven by a single observable, the running maximum distance $\bar{r}_t$ of iterates from the starting point. Concretely, POEM takes $\eta_t = \bar{r}_t/\sqrt{G_t}$ and $\mu_t = \bar{r}_t\sqrt{d/(t+1)}$, where $G_t$ accumulates squared norms of the finite-difference gradient estimates. Theorem 1 then shows that, under per-sample Lipschitz continuity, $E[f(\bar{x}_{\tau_T})-f(x_*)\mid \mathcal{F}_\delta] \le O((d/T + \sqrt{d}/\sqrt{T}) \theta_{T,\delta} L D_X \log_+(D_X/r_\epsilon))$ with probability at least $1-\delta$, giving $\tilde{O}(d L^2 D_X^2/\epsilon^2)$ stochastic zeroth-order oracle complexity. Because only logarithmic factors depend on $r_\epsilon$, the initialization is effectively not a tuning parameter, and the rate matches the known lower bound [15]. For unbounded domains, a variant that knows $s_0=\|x_0-x_*\|$ within a constant factor and an upper bound on $L$ achieves $\tilde{O}(d L^2 s_0^2/\epsilon^2)$, and the paper proves that any fully parameter-free zeroth-order algorithm in that setting must fail.

Load-bearing premise

The load-bearing premise is Assumption 3: every individual realization $F(\cdot;\xi)$ must be $L$-Lipschitz with the same constant $L$, not merely the averaged objective $f$; if only $f$ is Lipschitz, the finite-difference norm bounds and the martingale variance control in the proof no longer hold.

Editorial extensions

If this is right

  • For bounded domains, a user can run POEM with no knowledge of the Lipschitz constant, iteration budget, or target accuracy and still obtain $\tilde{O}(dL^2D_X^2/\epsilon^2)$ oracle complexity, matching the known lower bound [15].
  • The initial movement $r_\epsilon$ affects only a logarithmic factor, so a conservative small choice (such as $r_\epsilon=10^{-2}$ in the experiments) does not change the asymptotic rate.
  • The adaptive smoothing radius $\mu_t=\bar{r}_t\sqrt{d/(t+1)}$ is larger than the shrinking radii used in earlier methods, which stabilizes the finite-difference quotient without slowing the convergence rate.
  • On unbounded domains, a near-optimal rate requires using a valid lower bound on the initial distance $\|x_0-x_*\|$ and an upper bound on $L$; Theorem 3 shows that an ideal parameter-free zeroth-order method cannot exist in that setting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If Assumption 3 is weakened to require only that the expected objective $f$ is $L$-Lipschitz, the bounds $\|g_t\|\le Ld$ and $E\|g_t\|^2\le cL^2d$ that drive Lemma 4 no longer follow from this proof, so a heavy-tailed noise test is the natural stress case.
  • The same running-distance schedule could be transplanted to zeroth-order minimax, bilevel, or finite-sum problems; the main obstacle would be controlling the smoothing-bias term for each nested objective.
  • The impossibility result for unbounded domains suggests that 'parameter-free' is a property of the bounded-domain model: any extension to unbounded feasible sets must accept a dimension-dependent factor or consume estimates of the initial distance and Lipschitz constant.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes POEM, a parameter-free stochastic zeroth-order method for convex minimization. The step size follows the Distance over Gradients (DoG) schedule and the smoothing parameter is made adaptive, so neither requires knowledge of the Lipschitz constant, the iteration budget, or the target accuracy. The central result, Theorem 1, claims a high-probability bound of order O((d/T + sqrt(d)/sqrt(T)) theta_{T,delta} L D_X log_+(D_X/r_epsilon)) on a conditional expectation of the function-value gap, yielding an SZO oracle complexity of O~(d L^2 D_X^2 / epsilon^2), matching the lower bound of Duchi et al. Section 5 extends the method to unbounded domains under an overestimate of L and an underestimate of the initial distance, and gives an impossibility result for fully parameter-free zeroth-order optimization in that setting. Numerical experiments on three classification datasets show that POEM is competitive with tuned baselines and more robust to parameter choices.

Significance. If Theorem 1 were correct as stated, this would be a substantial contribution: it would provide the first parameter-free zeroth-order method with near-optimal oracle complexity, and the adaptive smoothing parameter is a natural and practically relevant idea. The paper has genuine strengths: the complexity is compared with an external lower bound from Duchi et al., the analysis imports rather than invents the DoG regret and concentration tools, and the experiments are run with both theory-prescribed and tuned baselines. The unbounded-domain lower bound in Theorem 3 is an interesting contribution that goes beyond the bounded-domain analysis. However, the proof of Theorem 1 contains a load-bearing gap in the treatment of the conditioning event, and the theorem's probabilistic statement is nonstandard. Because the near-optimal complexity claim rests on that step, the main contribution is not established as written.

major comments (3)
  1. [Section 4, definition of F_delta before Theorem 1] The collection F_delta = {A : A subset Omega_delta} intersect F0 is not a sigma-field: it is not closed under complement, since the complement of Omega_delta is not contained in Omega_delta and Omega0 belongs to F_delta only in the trivial case Omega_delta = Omega0. Consequently the object E[cdot | F_delta] used in Theorem 1 is not a standard conditional expectation, and Lemma 14, whose proof requires the set {E[X1|F] - E[X2|F] >= epsilon} to be in F, cannot be applied. The same construction is repeated for F~_delta in Appendix C.3 and Theorem 2. The theorem's phrase 'with probability at least 1 - delta' therefore attaches to a nonstandard object and must be reformulated, for example as a high-probability inequality on the function-value gap itself or as an unconditional expectation bound.
  2. [Appendix B.5, display after Eq. (18)] The step E[G_{T-1} | F_delta] = E[E[G_{T-1}] | F_delta] = sum_k E[E[||g_k||^2] | F_delta] is invalid. The random variable G_{T-1} is not independent of the good event Omega_delta, which is defined through the same noise increments g_k, so conditioning on Omega_delta can inflate the expected sum of squared gradients. The deterministic bound ||g_k|| <= Ld gives only E[G_{T-1} | F_delta] <= L^2 d^2 T pointwise, which changes the second term of the rate from sqrt(d)/sqrt(T) to d/sqrt(T) and the oracle complexity from O~(d L^2 D_X^2 / epsilon^2) to O~(d^2 L^2 D_X^2 / epsilon^2). The unconditional bound E[G_{T-1}] <= c L^2 d T can at best yield an in-expectation bound with an additional delta-tail term, not the displayed conditional inequality. This step is load-bearing for the near-optimality claim, and the analogous step for G'_{T-1} in the proof of Theorem 2 has the same problem.
  3. [Theorem 1, statement of the guarantee] Even if F_delta were a genuine sigma-field, an inequality of the form E[f(xbar_tau_T) - f(x*) | F_delta] <= epsilon holding on the high-probability event Omega_delta does not imply a high-probability bound on the random gap f(xbar_tau_T) - f(x*). Applying Markov's inequality conditionally on Omega_delta gives P(f(xbar_tau_T) - f(x*) > epsilon | Omega_delta) <= E[gap | Omega_delta] / epsilon <= 1, which is vacuous. The notion of a 'conditional expected epsilon-suboptimal solution' is nonstandard, and the claimed SZO complexity must be restated as a bound on E[gap] <= epsilon or P(gap <= epsilon) >= 1 - delta and proved in that form.
minor comments (4)
  1. [Section 2.1, Assumption 3] Assumption 3 requires every realization F(.;xi) to be L-Lipschitz, which is stronger than assuming only the expectation f is Lipschitz. Since the pointwise bound ||g_t|| <= Ld in Lemma 4 and the martingale increment bound in Lemma 5 rely on this per-sample condition, the paper should state this restriction explicitly and discuss whether the results extend under the weaker condition.
  2. [Appendix B.2, proof of Lemma 5] In the displayed bound for b_t, the symbol 'bar d_{t-1}' appears instead of 'bar s_{t-1}'; this typo should be corrected for consistency with the statement of Lemma 5.
  3. [Equation (12) and surrounding text] The definition of G'_t uses G_{t-1} on the right-hand side, while the sentence below writes 'G_t' with the same notation as in Section 3; this double use of the subscript is confusing and should be harmonized, for example by writing G_t for the sum through t and G'_{t} only for the modified quantity.
  4. [Algorithm 1 and Section 4] The definition of tau_T is typeset ambiguously in Algorithm 1 ('tau_T = arg max_{t <= T} t-1 sum ...'); it should be stated clearly that tau_T maximizes sum_{k=0}^{t-1} bar r_k / bar r_t over t = 1, ..., T.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: POEM's rate is benchmarked against an external lower bound and its imported lemmas serve as tools, not as the conclusion.

full rationale

The paper's derivation chain is self-contained against external benchmarks. The central result, Theorem 1, is compared with the independent lower bound of Duchi et al. [15], and the claimed near-optimality is not obtained by re-importing the desired rate from a self-citation. The weighted-regret and concentration lemmas (Lemma 3, Lemma 7, Lemma 12) are imported from Ivgi et al. [23] as general tools for SGD-type iterations and martingale differences; their statements do not assume the POEM rate. Lemma 4 is attributed to Shamir [49] and is a bound on the zeroth-order gradient estimator, not a restatement of the final complexity. The adaptive step size and smoothing parameter are designed to make these generic lemmas applicable, and the final oracle complexity is checked against an external lower bound, so no fitted constant is renamed as a prediction. The only same-author citation, [10] (Chen, Xu, and Luo), appears in the introduction as related work on gradient-free algorithms and is not load-bearing for the theorems. A technical concern about conditioning on the data-dependent event F_delta, flagged in Appendix B.5, is a proof-validity issue rather than circularity, because it does not make the theorem's conclusion an input to its own derivation. Therefore, no circular step satisfies the required evidentiary standard.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

POEM's central bound rests on four domain assumptions: compact convex domain (Assumption 1), per-realization convexity (Assumption 2), per-realization Lipschitzness (Assumption 3), and a two-point oracle returning evaluations with the same noise xi (Assumption 4). The algorithm itself has one user-chosen parameter r_eps in (0, D_X] in the bounded case, plus an overestimate Lbar >= L in the unbounded extension. The proof imports the DoG regret bound and martingale concentration from Ivgi et al. [23] and the sphere concentration from Shamir [49]; these are standard external results rather than new postulates. No new physical or mathematical entities are introduced.

free parameters (2)
  • r_eps (initial movement) = not fitted; user-chosen, e.g., 1e-2 in experiments
    POEM requires r_eps in (0, D_X] in the bounded-domain theorem (Algorithm 1 line 2). The bound's log term is log_+(D_X/r_eps), so it does not affect the O(dL^2D_X^2/eps^2) complexity, but the algorithm is not strictly parameter-free without it. In the unbounded extension, r_eps in (0, 3s0] is required, needing an estimate of s0.
  • Lbar (Lipschitz overestimate) = must satisfy Lbar >= L; not fitted
    Required in the unbounded-domain extension through G'_t (Eq. 12) and Theorem 2. If Lbar < L, the proof of Proposition 2 fails. The authors acknowledge this and prove an impossibility result showing such knowledge is unavoidable.
assumptions (6)
  • domain assumption Assumption 3: F(x;xi) is L-Lipschitz in x for every realization xi
    Used in Lemma 4 to bound ||g_t|| <= Ld and E||g_t||^2 <= cL^2d, which underpins the martingale concentration in Lemma 5 and the variance term in Theorem 1. Stronger than assuming only f = E[F] is Lipschitz.
  • domain assumption Assumption 4: two-point SZO oracle returns evaluations F(x;xi) and F(y;xi) with the same xi
    Needed for the finite difference to be an unbiased estimator of grad f_mu(x) (Lemma 2), basis of equations (9)-(10) and Lemma 5.
  • domain assumption Assumption 1: domain X is compact and convex
    Provides D_X < infinity used to bound rbar_t in Theorem 1 and to define r_eps in (0, D_X].
  • domain assumption Assumption 2: F(x;xi) is convex per realization
    Ensures f and its smoothing f_mu are convex, needed for the Jensen bound in Eq. (8) and the convexity inequality in Eq. (9).
  • standard math Lemmas 3 and 12 of Ivgi et al. [23] (DoG regret bound and time-uniform martingale concentration)
    Imported unchanged in Section 4 (Lemmas 3 and 5). The paper does not re-derive them.
  • standard math Lemma 11 of Shamir [49] (concentration on the sphere)
    Used in the proof of Lemma 4 to bound the variance of the smooth function value under the uniform sphere.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization." pith.science (2026). https://pith.science/paper/6WY257G7

@misc{pith2026250205600,
  author       = {Pith},
  title        = {Pith review of: A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6WY257G7}},
  note         = {Machine review of arXiv:2502.05600}
}
read the original abstract

This paper considers zeroth-order optimization for stochastic convex minimization problem. We propose a parameter-free stochastic zeroth-order method (POEM) by introducing a step-size scheme based on the distance over finite difference and an adaptive smoothing parameter. We provide the theoretical analysis to show that POEM achieves the near-optimal stochastic zeroth-order oracle complexity. We further conduct the numerical experiments to demonstrate POEM outperforms existing zeroth-order methods in practice.

Figures

Figures reproduced from arXiv: 2502.05600 by the authors.

Figure 1
Figure 1. The comparison on the SZO complexity against the function value during the iterations. [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. The comparison on parameter settings (rϵ for POEM and 1/L for other methods) against f(xT ). 10 0 10 2 10 4 10 6 Iterations 10 8 10 6 10 4 Step Sizes r² = 10¡1 r² = 10¡3 r² = 10¡4 r² = 10¡5 r² = 10¡7 10 0 10 2 10 4 10 6 Iterations 10 7 10 5 10 3 Step Sizes r² = 10¡1 r² = 10¡3 r² = 10¡4 r² = 10¡5 r² = 10¡7 10 0 10 2 10 4 10 6 Iterations 10 8 10 6 10 4 Step Sizes r² = 10¡1 r² = 10¡3 r² = 10¡4 r² = 10¡5 r² = 10¡7 (a) m… view at source ↗
Figure 3
Figure 3. The change of the step size with difference [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 40 canonical work pages

  1. [1]

    Optimal algorithms for online convex optimization with multi-point bandit feedback

    Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28–40. Citeseer, 2010

    work page 2010

  2. [2]

    Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates

    Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates. Advances in Neural Information Processing Systems , 31, 2018

    work page 2018

  3. [3]

    Two-point step size gradient methods

    Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1):141–148, 1988

    work page 1988

  4. [4]

    On the distance between two neural networks and the stability of learning

    Jeremy Bernstein, Arash Vahdat, Yisong Yue, and Ming-Yu Liu. On the distance between two neural networks and the stability of learning. Advances in Neural Information Processing Systems , 33:21370– 21381, 2020

    work page 2020

  5. [5]

    Training neural networks for and by interpolation

    Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Training neural networks for and by interpolation. In International conference on machine learning , pages 799–809. PMLR, 2020

    work page 2020

  6. [6]

    Online learning with imperfect hints

    Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In International Conference on Machine Learning , pages 822–831. PMLR, 2020

    work page 2020

  7. [7]

    Making sgd parameter-free

    Yair Carmon and Oliver Hinder. Making sgd parameter-free. In Conference on Learning Theory, pages 2360–2389. PMLR, 2022

    work page 2022

  8. [8]

    Libsvm: a library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST) , 2(3):1–27, 2011

    2011

Show all 61 references
  1. [9]

    Better parameter-free stochastic optimization with ode updates for coin-betting

    Keyi Chen, John Langford, and Francesco Orabona. Better parameter-free stochastic optimization with ode updates for coin-betting. In AAAI, 2022

    2022

  2. [10]

    Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization

    Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. In International Conference on Machine Learning , pages 5219–5233. PMLR, 2023

    2023

  3. [11]

    Black-box reductions for parameter-free online learning in banach spaces

    Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1493–1529. PMLR, 2018

    2018

  4. [12]

    Learning-rate-free learning by d-adaptation

    Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by d-adaptation. In International Conference on Machine Learning , pages 7449–7479. PMLR, 2023

    2023

  5. [13]

    Adaptive subgradient methods for online learning and stochastic optimization

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research , 12(7), 2011

    2011

  6. [14]

    Duchi, Peter L

    John C. Duchi, Peter L. Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization , 22(2):674–701, 2012

    2012

  7. [15]

    Duchi, Michael I

    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

    2015

  8. [16]

    Probability: theory and examples , volume 49

    Rick Durrett. Probability: theory and examples , volume 49. Cambridge university press, 2019

    2019

  9. [17]

    Online convex optimization in the bandit setting: gradient descent without a gradient

    Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007 , 2004

    2004 arXiv

  10. [18]

    The power of first-order smooth optimization for black-box non-smooth problems

    Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii, Farshed Abdukhakimov, Dmitry Kamzolov, Aleksandr Beznosikov, Martin Tak´ aˇ c, Pavel Dvurechensky, and Bin Gu. The power of first-order smooth optimization for black-box non-smooth problems. arXiv preprint arXiv:2201.12289 , 2022

    2022 arXiv

  11. [19]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming

    Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization , 23(4):2341–2368, 2013. 12

    2013

  12. [20]

    Explaining and harnessing adversarial examples

    Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572 , 2014

    2014 arXiv

  13. [21]

    Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon

    Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics , 49(2):1055 – 1080, 2021

    2021

  14. [22]

    Prior convictions: Black-box adversarial attacks with bandits and priors

    Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint arXiv:1807.07978 , 2018

    2018 arXiv

  15. [23]

    Dog is SGD’s best friend: A parameter-free dynamic step size schedule

    Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is SGD’s best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning , pages 14465–14499. PMLR, 2023

    2023

  16. [24]

    Dog is sgd’s best friend: A parameter-free dynamic step size schedule, 2023

    Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd’s best friend: A parameter-free dynamic step size schedule, 2023. URL https://arxiv.org/abs/2302.12022

    2023 arXiv

  17. [25]

    Parameter-free mirror descent

    Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Conference on Learning Theory, pages 4160–4211. PMLR, 2022

    2022

  18. [26]

    Tuning-free stochastic optimization

    Ahmed Khaled and Chi Jin. Tuning-free stochastic optimization. arXiv preprint arXiv:2402.07793 , 2024

    2024 arXiv

  19. [27]

    Stochastic estimation of the maximum of a regression function

    Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics , pages 462–466, 1952

    1952

  20. [28]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2014

    2014

  21. [29]

    An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization

    Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research , 25(122):1–14, 2024

    2024

  22. [30]

    Optimal and parameter-free gradient minimization methods for smooth optimization

    Guanghui Lan, Yuyuan Ouyang, and Zhe Zhang. Optimal and parameter-free gradient minimization methods for smooth optimization. arXiv preprint arXiv:2310.12139 , 2023

    2023 arXiv

  23. [31]

    A simple uniformly optimal method without line search for convex optimization

    Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex optimization. arXiv preprint arXiv:2310.10082 , 2023

    2023 arXiv

  24. [32]

    Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization

    Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160–26175, 2022

    2022

  25. [33]

    A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications

    Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod K Varshney. A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine , 37(5):43–54, 2020

    2020

  26. [34]

    Delving into transferable adversarial examples and black-box attacks

    Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. arXiv preprint arXiv:1611.02770 , 2016

    2016 arXiv

  27. [35]

    Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence

    Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics , pages 1306–1314. PMLR, 2021

    2021

  28. [36]

    Achieving all with no parameters: Adanormalhedge

    Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory, pages 1286–1304. PMLR, 2015

    2015

  29. [37]

    Simple random search provides a competitive approach to reinforcement learning

    Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides a competitive approach to reinforcement learning. arXiv preprint arXiv:1803.07055 , 2018

    2018 arXiv

  30. [38]

    Lipschitz and comparator-norm adaptivity in online learning

    Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory, pages 2858–2887. PMLR, 2020

    2020

  31. [39]

    Adaptive first-and zeroth-order methods for weakly convex stochastic optimization problems

    Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Adaptive first-and zeroth-order methods for weakly convex stochastic optimization problems. arXiv preprint arXiv:2005.09261 , 2020. 13

    2005 arXiv

  32. [40]

    Random gradient-free minimization of convex functions

    Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Founda- tions of Computational Mathematics , 17(2):527–566, 2017

    2017

  33. [41]

    Coin betting and parameter-free online learning.Advances in Neural Information Processing Systems, 29, 2016

    Francesco Orabona and D´ avid P´ al. Coin betting and parameter-free online learning.Advances in Neural Information Processing Systems, 29, 2016

    2016

  34. [42]

    Training deep networks without learning rates through coin betting

    Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. Advances in Neural Information Processing Systems , 30, 2017

    2017

  35. [43]

    A stochastic line search method with expected complexity analysis

    Courtney Paquette and Katya Scheinberg. A stochastic line search method with expected complexity analysis. SIAM Journal on Optimization , 30(1):349–376, 2020

    2020

  36. [44]

    Introduction to optimization

    Boris T Polyak. Introduction to optimization . New York, Optimization Software,, 1987

    1987

  37. [45]

    An optimal structured zeroth-order algorithm for non-smooth optimization

    Marco Rando, Cesare Molinari, Lorenzo Rosasco, and Silvia Villa. An optimal structured zeroth-order algorithm for non-smooth optimization. Advances in Neural Information Processing Systems , 36, 2024

    2024

  38. [46]

    L4: Practical loss-based stepsize adaptation for deep learning

    Michal Rolinek and Georg Martius. L4: Practical loss-based stepsize adaptation for deep learning. Advances in neural information processing systems , 31, 2018

    2018

  39. [47]

    Understanding adversarial training: Increasing local stability of supervised models through robust optimization

    Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing local stability of supervised models through robust optimization. Neurocomputing, 307:195–204, 2018

    2018

  40. [48]

    Online learning and online convex optimization

    Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends® in Machine Learning , 4(2):107–194, 2012

    2012

  41. [49]

    An optimal algorithm for bandit and zero-order convex optimization with two-point feedback

    Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research , 18(52):1–11, 2017

    2017

  42. [50]

    Adafactor: Adaptive learning rates with sublinear memory cost

    Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning , pages 4596–4604. PMLR, 2018

    2018

  43. [51]

    No-regret algorithms for unconstrained online convex optimization

    Matthew Streeter and H Brendan McMahan. No-regret algorithms for unconstrained online convex optimization. arXiv preprint arXiv:1211.2260 , 2012

    2012 arXiv

  44. [52]

    Barzilai-borwein step size for stochastic gradient descent

    Conghui Tan, Shiqian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic gradient descent. Advances in neural information processing systems , 29, 2016

    2016

  45. [53]

    Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude

    Tijmen Tieleman. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning , 4(2):26, 2012

    2012

  46. [54]

    Painless stochastic gradient: Interpolation, line-search, and convergence rates

    Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019

    2019

  47. [55]

    Provable adaptivity of adam under non-uniform smoothness

    Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, Tie-Yan Liu, Zhi- Quan Luo, and Wei Chen. Provable adaptivity of adam under non-uniform smoothness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 2960–2...

    2024

  48. [56]

    Generalized polyak step size for first order optimization with momentum

    Xiaoyu Wang, Mikael Johansson, and Tong Zhang. Generalized polyak step size for first order optimization with momentum. In International Conference on Machine Learning , pages 35836–35863. PMLR, 2023

    2023

  49. [57]

    Finite sample convergence rates of zero-order stochastic optimization methods

    Andre Wibisono, Martin J Wainwright, Michael Jordan, and John C Duchi. Finite sample convergence rates of zero-order stochastic optimization methods. Advances in Neural Information Processing Systems , 25, 2012

    2012

  50. [58]

    Large batch training of convolutional networks

    Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arXiv:1708.03888, 2017. 14

    2017 arXiv

  51. [59]

    On stochastic gradient and subgradient methods with adaptive steplength sequences

    Farzad Yousefian, Angelia Nedi´ c, and Uday V Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56–67, 2012

    2012

  52. [60]

    Adadelta: an adaptive learning rate method

    Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701 , 2012

    2012 arXiv

  53. [61]

    Adam-mini: Use fewer learning rates to gain more

    Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. Adam-mini: Use fewer learning rates to gain more. arXiv preprint arXiv:2406.16793 , 2024. 15 A Some Basic Results We first present some basic lemmas. Lemma 8. Suppose the func...

    2024 arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.