Pith. sign in

REVIEW 3 major objections 4 minor 57 references

On quasi-convex smooth optimization problems by a comparison oracle

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

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

Pith's one-line read This paper proves that a comparison oracle suffices to minimize smooth strictly quasi-convex functions, using O((nD^2/epsilon^2) log(nD/epsilon)) comparisons to reach v_f(x,x*) <= epsilon.

desk verdict The paper's main theorem is vacuous: the assumed uniform lower bound on the gradient norm is incompatible with L-smoothness on R^n, so the headline comparison-oracle complexity result holds for no non-degenerate strictly quasi-convex function. read the letter →

arxiv 2411.16745 v1 pith:65VJMABT submitted 2024-11-23 math.OC

A. V. Gasnikov , M. S. Alkousa , A. V. Lobanov , Y. V. Dorn , F. S. Stonyakin , I. A. Kuruzov , S. R. Singh This is my paper · ORCID
classification math.OC MSC 90C2690C56
keywords quasi-convexoptimizationcomparisonoraclezeroth-ordermethodsnormalizedgradientdescentderivative-freesmoothnonconvexcomplexity
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

The paper sets out to show that a comparison oracle — a black box that answers only 'which of these two points has the larger function value?' — is enough to minimize a smooth strictly quasi-convex function on $\mathbb{R}^n$. It proposes Algorithm 3, which estimates the direction of the gradient by comparisons, then takes a normalized-gradient step of size $D/\sqrt{2k}$ at iteration $k$. The main result is a query-complexity bound: $\mathcal{O}\left((n D^2/\varepsilon^2)\log(nD/\varepsilon)\right)$ comparisons guarantee a point with $v_f(x,x^*) \le \varepsilon$, where $v_f$ measures how well the normalized gradient points toward the optimum. The significance is that prior comparison-oracle results covered convex and strongly convex objectives, and this paper extends the reach of that oracle model to a broader nonconvex class used in economics, control, and geometric reconstruction. The extension is conditional on a strong global steepness assumption, stated below.

What carries the argument

The load-bearing mechanism is the comparison-based gradient direction estimation subroutine (Algorithm 2, from [56]): at a point $x$ with a known lower bound $\gamma \le \|\nabla f(x)\|_*$, it uses directional-preference comparisons to determine the sign of each coordinate of the gradient and then binary-searches ratios to locate a unit vector $\hat{g}$ within $\delta$ of $\nabla f(x)/\|\nabla f(x)\|_*$, spending $O(n\log(n/\delta))$ comparisons. Algorithm 3 wraps this routine in normalized gradient descent with step sizes $h_k=D/\sqrt{2k}$. The analytic core is Lemma 4.2: for any unit-norm direction estimate with error $\delta$, the telescoping sum over squared distances to $x^*$ gives $\min_k v_f(x_k,x^*) \le 3D/\sqrt{2N}+\delta D$. Strict quasi-convexity enters through the asserted uniform lower bound on the gradient norm, which justifies calling the subroutine with $\gamma=\varepsilon$; without that bound, Theorem 3.1's direction estimate is not guaranteed.

What would settle it

Take $f(x)=x^2$ on $\mathbb{R}$, which is $L$-smooth with $L=2$ and strictly quasi-convex in the sense that the gradient vanishes only at $x^*=0$. For any $\varepsilon>0$, the set $\{x:|f'(x)|<\varepsilon\}=\{x:2|x|<\varepsilon\}$ is nonempty, so no global $\gamma>0$ with $\|\nabla f(x)\|_* \ge \gamma$ exists; running Algorithm 3 on this function with $\gamma=\varepsilon$ will eventually produce an iterate inside that set, where the direction-estimation guarantee used in Lemma 4.3 no longer applies. Checking this example directly settles whether the paper's standing assumption is compatible with its stated function class.

Watch

Extended reading notes

Core claim

On its own terms, the paper's claim is that strict quasi-convexity plus $L$-smoothness makes a comparison oracle sufficient for approximate minimization. The target is not function error but $v_f(x,x^*)$, the projection of the normalized gradient onto the direction toward $x^*$; Lemma 2.2 says that for quasi-convex functions this quantity controls function suboptimality through a modulus $\omega$. Algorithm 3 sets $\gamma=\varepsilon$ as a lower bound on $\|\nabla f(x)\|_*$, uses the comparison-based direction estimator to get unit vectors $\hat{g}_k$ within distance $\delta=\varepsilon/(2D)$ of the true normalized gradient, and updates $x_{k+1}=x_k-(D/\sqrt{2k})\hat{g}_k$. Lemma 4.2 telescopes the squared-distance decreases and yields $\min_k v_f(x_k,x^*) \le 3D/\sqrt{2N}+\delta D$; with $N=18D^2/\varepsilon^2$ this becomes the advertised $\varepsilon$ guarantee. The proof's engine is that the direction-estimation error enters only additively, so it can be absorbed by setting $\delta$ proportional to $\varepsilon/D$.

Load-bearing premise

Everything rests on the requirement that the gradient length never falls below the target accuracy $\varepsilon$ away from the optimum, yet a smooth function on all of $\mathbb{R}^n$ always has points arbitrarily close to the optimum where the gradient length is smaller than $\varepsilon$, so the assumption cannot hold for the functions the theorem describes.

Editorial extensions

If this is right

  • Smooth strictly quasi-convex minimization is solvable by pairwise comparisons alone, with a total comparison budget that grows like $n/\varepsilon^2$ times a logarithmic factor.
  • Each iteration of the method uses only comparisons and no gradient values, so the result applies to black-box settings where gradients are unavailable or too expensive to compute.
  • The convergence guarantee is expressed in terms of $v_f(x,x^*)$, the normalized-gradient progress toward the optimum, not directly in function values; converting it to function error requires the modulus $\omega$ from Lemma 2.2.
  • The per-iteration comparison cost is $O(n\log(n/\varepsilon))$, so the dominant cost in high accuracy is the $O(D^2/\varepsilon^2)$ iteration count.
  • For fixed dimension $n$, the paper's bound becomes $\widetilde{O}(1/\varepsilon^2)$, the same order as the normalized-gradient-descent iteration count up to logarithms.

Reading between the lines

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

  • The paper leaves implicit that the global lower-gradient assumption is what does the work; on a bounded domain that excludes an $\varepsilon$-neighborhood of the minimizer, or under a local lower-gradient condition, the same proof would give a valid local rate without the contradiction with smoothness.
  • A direct extension would be to replace the exact comparisons with noisy or stochastic comparisons and ask how the $n\log(n/\varepsilon)$ direction-estimation cost degrades; the paper does not address noise.
  • Because $v_f$ can be small even when the function value is far from optimal for quasi-convex functions with flat sublevel sets, practical use of this criterion would need an additional comparison-based stopping rule, such as checking that a step fails to decrease the value.
  • A natural test of tightness is whether the factor $n$ per iteration is necessary; the paper gives no lower bound for comparison-only quasi-convex minimization, so it may be possible to estimate the gradient direction with $o(n)$ comparisons using random projections.
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 a comparison-oracle method for minimizing L-smooth strictly quasi-convex functions on R^n. It combines the existing Comparison-based Gradient Direction Estimation (Algorithm 2, from Zhang and Li, reference [56]) with a normalized gradient descent scheme (Algorithm 3) and claims an oracle complexity of O((nD^2/epsilon^2) log(nD/epsilon)) comparison queries to find a point x with v_f(x, x*) <= epsilon. The analysis consists of Lemma 4.2 (convergence of an idealized approximate normalized gradient descent under a direction-estimate accuracy assumption), Lemma 4.3 (application of the direction estimation within Algorithm 3), and Theorem 4.4 (the headline complexity bound).

Significance. If the main theorem were valid, the paper would extend comparison-based zeroth-order optimization to quasi-convex functions, a class not handled by the cited comparison-oracle literature. The idealized convergence analysis in Lemma 4.2 is a clean and correct derivation conditional on the availability of accurate unit-norm direction estimates, and the comparison-to-direction reduction is clearly credited to prior work. However, the central theorem rests on an impossible assumption: the uniform lower bound on the gradient norm required by Algorithm 3 is incompatible with differentiability at the minimizer and with L-smoothness on R^n. The hypothesis class is empty, so the claimed complexity result is vacuous over the stated problem class.

major comments (3)
  1. [Definition 2.1] The 'in other words' in Definition 2.1 is false. Strict quasi-convexity defined as 'gradients vanish only at the global minima' is not equivalent to the existence of a uniform gamma > 0 with ||grad f(y)||_* >= gamma for all y in R^n. For any differentiable f that attains its minimum at x*, Fermat's condition gives grad f(x*) = 0, so a uniform positive lower bound over all of R^n cannot hold. This false equivalence is used verbatim in the proof of Theorem 4.4 ('there is gamma := epsilon > 0 ... such that ||grad f(x)||_* >= gamma, for all x in R^n (see Definition 2.1)'), so the theorem's premise is unsatisfiable for the class of functions under consideration.
  2. [Lemma 4.3 / Algorithm 3] The assumption stated in Lemma 4.3 via Algorithm 3's line 1, that ||grad f(x)||_* > epsilon for all x in R^n, contradicts L-smoothness on R^n. Since grad f(x*) = 0 and grad f is L-Lipschitz, ||grad f(x)||_* <= L||x - x*|| for all x, so the lower bound fails on the whole ball B(x*, epsilon/L). Algorithm 3 has no mechanism to avoid this ball, so the invocation of Theorem 3.1 to produce accurate direction estimates at every iterate is unjustified. Consequently Lemma 4.3 does not prove the claimed bound, and the proof of Theorem 4.4 collapses.
  3. [Theorem 4.4 / Abstract] The headline complexity claim is vacuous over the stated class of objectives. As shown above, no non-degenerate L-smooth strictly quasi-convex function on R^n with a finite minimizer satisfies the uniform gradient lower bound required by Algorithm 3; hence Theorem 4.4 gives no guarantee for any function in the intended class. The problem would need a reformulation, for instance a gradient-norm lower bound only on a bounded sublevel set known to contain the iterates, or a local version of the condition, before the analysis could apply to a nonempty class.
minor comments (4)
  1. [Abstract and Section 1] There are several typographical errors: 'Comparioson' should be 'Comparison', 'Nelson-Mead' should be 'Nelder-Mead', and 'Lipchitz' should be 'Lipschitz'.
  2. [Theorem 4.4] The query complexity expression in the theorem statement reads O(nD^2/epsilon^2 log(n*delta/epsilon)), whereas the proof and the abstract give O(nD^2/epsilon^2 log(nD/epsilon)); since delta = epsilon/(2D), the intended factor is log(n/delta) = log(2nD/epsilon), so the theorem statement should be corrected to match the proof.
  3. [Algorithm 3] The 'Require' line states 'D > 0 such that ||x - x*|| <= D; for all x in R^n', which is impossible on unbounded R^n; the intended meaning is that D bounds the distance from x* for the initial point and all generated iterates, as stated in the abstract and used in Lemma 4.2.
  4. [Lemma 4.2] The proof introduces h_0 = infinity and uses the telescoping sum with 1/h_k; this is acceptable but should be flagged as an abuse of notation, and the step from equation (4.2) to the telescoped inequality could be expanded slightly for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the convergence proof is a standard telescoping-sum argument with analytic parameter choices, not a reduction of the conclusion to its inputs; the paper's serious flaw is an impossible gradient lower-bound assumption, which is a correctness issue rather than circular reasoning.

full rationale

The paper's derivation chain is not circular. Algorithm 3 chooses N = 18D^2/eps^2 and delta = eps/(2D) analytically, and Lemma 4.2 proves min v_f <= 3D/sqrt(2N) + delta D by summing inequality (4.2) and using Cauchy-Schwarz; the final bound equals eps because both terms are set to eps/2. This is ordinary parameter tuning, not a fitted quantity being relabeled as a prediction. The direction-estimation subroutine is imported from [56] (Zhang and Li), not from the present authors, and Theorem 3.1 is cited as an external result, so no load-bearing self-citation is present. The only serious defect is Lemma 4.3's assertion 'From line 2 in Algorithm 3, we have ||grad f(x)||_* > eps, for all x in R^n', which rests on Definition 2.1's false 'In other words' claim that strict quasi-convexity implies a uniform positive lower bound on the gradient. That assumption is impossible for a differentiable function attaining its minimum on R^n, since grad f(x*) = 0, and it makes the stated hypothesis class empty or at least collapses the proof's applicability. However, the conclusion v_f(x_k,x*) <= eps is not definitionally identical to the gradient lower bound: the argument still does substantive telescoping and norm-estimate work. Thus the flaw is an unsound, vacuous assumption, not circularity, and the circularity score is 0.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central claim rests on an impossible uniform lower bound on the gradient norm, which is misstated as part of the definition of strict quasi-convexity. The other assumptions (bounded iterates with known D, known L) are standard but unproven for the algorithm's trajectory.

free parameters (3)
  • gamma (gradient norm lower bound) = gamma = epsilon
    Algorithm 3 sets gamma := epsilon, assuming ||grad f(x)|| >= epsilon for all x. This is not a known property of the function class and is in fact impossible for L-smooth functions on R^n.
  • D (distance bound) = unknown, assumed
    D is assumed to upper-bound ||x - x*|| for all iterates and indeed all x in R^n (stated in Lemma 4.2). This bound is not proven to hold for the generated sequence.
  • epsilon (target accuracy) = user-supplied
    The target accuracy; the algorithm also sets gamma = epsilon, making feasibility depend on epsilon.
assumptions (3)
  • ad hoc to paper There exists gamma > 0 with ||grad f(x)||_* >= gamma for all x in R^n (with f(x) > f*).
    Introduced in Definition 2.1 as an equivalent restatement of strict quasi-convexity, but it is not equivalent and is impossible for L-smooth functions on R^n. Used in Theorem 3.1 hypotheses and Lemma 4.3.
  • domain assumption The iterates satisfy ||x_k - x*|| <= D for all k, where D is known.
    Required in Lemma 4.2 for the Cauchy-Schwarz step and to bound the direction error term. Assumed without proof; the descent update does not guarantee staying in the D-ball.
  • domain assumption The smoothness constant L is known to the algorithm (needed in Algorithm 1).
    Algorithm 1 queries x + (2*delta/L)v, so L must be known or estimated; the paper only states f is L-smooth.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On quasi-convex smooth optimization problems by a comparison oracle." pith.science (2026). https://pith.science/paper/65VJMABT

@misc{pith2026241116745,
  author       = {Pith},
  title        = {Pith review of: On quasi-convex smooth optimization problems by a comparison oracle},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/65VJMABT}},
  note         = {Machine review of arXiv:2411.16745}
}
abstract

Frequently, when dealing with many machine learning models, optimization problems appear to be challenging due to a limited understanding of the constructions and characterizations of the objective functions in these problems. Therefore, major complications arise when dealing with first-order algorithms, in which gradient computations are challenging or even impossible in various scenarios. For this reason, we resort to derivative-free methods (zeroth-order methods). This paper is devoted to an approach to minimizing quasi-convex functions using a recently proposed comparison oracle only. This oracle compares function values at two points and tells which is larger, thus by the proposed approach, the comparisons are all we need to solve the optimization problem under consideration. The proposed algorithm to solve the considered problem is based on the technique of comparison-based gradient direction estimation and the comparison-based approximation normalized gradient descent. The normalized gradient descent algorithm is an adaptation of gradient descent, which updates according to the direction of the gradients, rather than the gradients themselves. We proved the convergence rate of the proposed algorithm when the objective function is smooth and strictly quasi-convex in $\mathbb{R}^n$, this algorithm needs $\mathcal{O}\left( \left(n D^2/\varepsilon^2 \right) \log\left(n D / \varepsilon\right)\right)$ comparison queries to find an $\varepsilon$-approximate of the optimal solution, where $D$ is an upper bound of the distance between all generated iteration points and an optimal solution.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 52 canonical work pages

  1. [56]

    Comparisons Are All You Need for Optimizi ng Smooth Functions, arXiv:2405.11454 (19 May 2024)

    Zhang C., Li T. Comparisons Are All You Need for Optimizi ng Smooth Functions, arXiv:2405.11454 (19 May 2024)

    arXiv 2024

  2. [1]

    Disciplined quasiconvex programmin g, Optim Lett, 2020, vol

    Agrawal A., Boyd S. Disciplined quasiconvex programmin g, Optim Lett, 2020, vol. 14, pp. 1643–1657

    work page 2020

  3. [2]

    A gradient e stimator via l1- randomization for online zero-order optimization with two point feedback, in Ad- vances in Neural Information Processing Systems, vol

    Akhavan A., Chzhen E., Pontil M., Tsybakov A. A gradient e stimator via l1- randomization for online zero-order optimization with two point feedback, in Ad- vances in Neural Information Processing Systems, vol. 35, 2022, pp. 7685–7696

    work page 2022

  4. [3]

    Alashqar B., Gasnikov A., Dvinskikh D., Lobanov A. Gradi ent-free federated learning methods with l1 and l2-randomization for non-smooth convex stochastic optimiza tion problems, Computational Mathematics and Mathematical Phy sics, 2023, vol. 63, no. 9, pp. 1600–1653

    work page 2023

  5. [4]

    Mesh adaptive direct search algorith ms for constrained optimiza- tion, SIAM Journal on Optimization, 2006, vol

    Audet C., Dennis J. Mesh adaptive direct search algorith ms for constrained optimiza- tion, SIAM Journal on Optimization, 2006, vol. 17, no. 1, pp. 188–217

    work page 2006

  6. [5]

    Goal -driven dynamics learning via bayesian optimization, in IEEE 56th Annual Conference on Decision and Control (CDC), 2017, pp

    Bansal S., Calandra R., Xiao T., Levine S., Tomlin C. Goal -driven dynamics learning via bayesian optimization, in IEEE 56th Annual Conference on Decision and Control (CDC), 2017, pp. 5168–5173

    work page 2017

  7. [6]

    Highly-smooth zero-th order online o ptimization, in Conference on Learning Theory, PMLR, 2016, pp

    Bach F., Perchet V. Highly-smooth zero-th order online o ptimization, in Conference on Learning Theory, PMLR, 2016, pp. 257–283

    work page 2016

  8. [7]

    Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionality, and saddle poi nts, Found Comput Math, 2022, vol

    Balasubramanian K., Ghadimi S. Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionality, and saddle poi nts, Found Comput Math, 2022, vol. 22, pp. 35-76

    work page 2022

Show all 57 references
  1. [8]

    Stochastic three p oints method for uncon- strained smooth minimization, SIAM Journal on Optimizatio n, 2020, vol

    Bergou H., Gorbunov E., Richt´ arik P. Stochastic three p oints method for uncon- strained smooth minimization, SIAM Journal on Optimizatio n, 2020, vol. 30, no. 4, pp. 2726–2749

    2020

  2. [9]

    Convex Optimization , New York: Cambridge University Press, 2004

    Boyd S., Vandenberghe L. Convex Optimization , New York: Cambridge University Press, 2004

    2004

  3. [10]

    Algorithms for Minimization Without Derivatives , Dover Books on Mathe- matics, Dover Publications, 1973

    Brent R. Algorithms for Minimization Without Derivatives , Dover Books on Mathe- matics, Dover Publications, 1973. QUASI-CONVEX SMOOTH OPTIMIZATION BY A COMPARISON ORACLE 11

    1973

  4. [11]

    Regret analysis of stochast ic and nonstochastic multi- armed bandit problems, Foundations and Trends in Machine Le arning, 2012, vol

    Bubeck S., Cesa-Bianchi N. Regret analysis of stochast ic and nonstochastic multi- armed bandit problems, Foundations and Trends in Machine Le arning, 2012, vol. 5, no. 1, pp. 1-122

    2012

  5. [12]

    Zoo: Zeroth o rder optimization based black-box attacks to deep neural networks without training substitute models, in Proc

    Chen P., Zhang H., Sharma Y., Yi J., Hsieh C. Zoo: Zeroth o rder optimization based black-box attacks to deep neural networks without training substitute models, in Proc. of the 10th ACM Workshop on Artificial Intelligence and Security, 2017, pp. 15–26

    2017

  6. [13]

    Optimizing simula- tions with noise-tolerant structured exploration, in IEEE International Conference on Robotics and Automation (ICRA), 2018, pp

    Choromanski K., Iscen A., Sindhwani V., Tan J., Coumans E. Optimizing simula- tions with noise-tolerant structured exploration, in IEEE International Conference on Robotics and Automation (ICRA), 2018, pp. 2970-2977

    2018

  7. [14]

    Introduction to Derivative-Free Optimization , MOS-SIAM Series on Optimization, 2009

    Conn A., Scheinberg K., Vicente L. Introduction to Derivative-Free Optimization , MOS-SIAM Series on Optimization, 2009

    2009

  8. [15]

    Federated bayesian optimizat ion via thompson sampling, in Advances in Neural Information Processing Systems, vol

    Dai Z., Low B., Jaillet P. Federated bayesian optimizat ion via thompson sampling, in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 9687–9699

    2020

  9. [16]

    Direct search methods on parallel machines, SIAM Journal on Optimization, 1991, vol

    Dennis J., Torczon V. Direct search methods on parallel machines, SIAM Journal on Optimization, 1991, vol. 1, no. 4, pp. 448–474

    1991

  10. [17]

    Optimal rates for zero-order con- vex optimization: The power of two function evaluations, IE EE Transactions on Information Theory, 2015, vol

    Duchi J., Jordan M., Wainwright M., Wibisono A. Optimal rates for zero-order con- vex optimization: The power of two function evaluations, IE EE Transactions on Information Theory, 2015, vol. 61, no. 5, pp. 2788–2806

    2015

  11. [18]

    Adaptive subgradient meth ods for online learning and stochastic optimization, Journal of Machine Learning Research , 2011, vol

    Duchi J., Hazan E., Singer Y. Adaptive subgradient meth ods for online learning and stochastic optimization, Journal of Machine Learning Research , 2011, vol. 12, no. 7, pp. 2121–2159

    2011

  12. [19]

    Eppstein D., Quasiconvex programming, Combinatorial and Computational Geome- try, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2 005, pp. 287–331

  13. [20]

    SPIDER: Near-optimal non -convex optimization via stochastic path-integrated differential estimator, in Advances in Neural Information Processing Systems, vol

    Fang C., Li C., Lin Z., Zhang T. SPIDER: Near-optimal non -convex optimization via stochastic path-integrated differential estimator, in Advances in Neural Information Processing Systems, vol. 31, 2018

    2018

  14. [21]

    Stochastic approximation of minima with impr oved asymptotic speed, Ann

    Fabian V. Stochastic approximation of minima with impr oved asymptotic speed, Ann. Math. Statist., 1967, vol. 38, no. 1, pp. 191-200

    1967

  15. [22]

    Convex cones, sets, and functions , Lecture Notes

    Fenchel W. Convex cones, sets, and functions , Lecture Notes. Princeton University, Department of Mathematics, 1953

    1953

  16. [23]

    Gao J., Lanchantin J., Soffa M., Qi, Y.Black-box generat ion of adversarial text se- quences to evade deep learning classifiers, in IEEE Security and Privacy Workshops (SPW), 2018, pp. 50–56

    2018

  17. [24]

    Methods for Convex ( L0, L 1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity, arXiv:2409.14989 (23 Sep 2024)

    Gorbunov E., Tupitsa N., Choudhury S., Aliev A., Richt´ arik P., Horv´ ath S., Tak´ aˇ c M. Methods for Convex ( L0, L 1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity, arXiv:2409.14989 (23 Sep 2024)

    2024 arXiv

  18. [25]

    A stochastic derivative free optimization method with momentum, in International Conference on Learning Representations, 2020

    Gorbunov E., Bibi A., Sener O., Bergou H., Richtarik P. A stochastic derivative free optimization method with momentum, in International Conference on Learning Representations, 2020

    2020

  19. [26]

    28, 2015

    Hazan E., Levy K., Shalev-Shwartz S., Beyond convexity : Stochastic quasi-convex optimization, in Advances in neural information processing systems, vol. 28, 2015

    2015

  20. [27]

    Improved zeroth-order v ariance reduced algorithms and analysis for nonconvex optimization, in International Conference on Machine Learning, PMLR, 2019, pp

    Ji K., Wang Z., Zhou Y., Liang Y. Improved zeroth-order v ariance reduced algorithms and analysis for nonconvex optimization, in International Conference on Machine Learning, PMLR, 2019, pp. 3100–3109

    2019

  21. [28]

    Uncertainty models in quasiconvex opti mization for geometric re- construction, in IEEE Computer Society Conference on Computer Vision and Pat tern Recognition (CVPR’06), vol

    Ke Q., Kanade T. Uncertainty models in quasiconvex opti mization for geometric re- construction, in IEEE Computer Society Conference on Computer Vision and Pat tern Recognition (CVPR’06), vol. 1, 2006, pp. 1199–1205

    2006

  22. [29]

    Quasiconvex optimization for robust ge ometric reconstruction, in Tenth IEEE International Conference on Computer Vision (Be ijing, China), vol

    Ke Q., Kanade T. Quasiconvex optimization for robust ge ometric reconstruction, in Tenth IEEE International Conference on Computer Vision (Be ijing, China), vol. 1, 2005, pp. 986-993

    2005

  23. [30]

    Online to offline conversions, universality and ad aptive minibatch sizes, in Advances in Neural Information Processing Systems, vol

    Kfir L. Online to offline conversions, universality and ad aptive minibatch sizes, in Advances in Neural Information Processing Systems, vol. 30, 2017. 12 GASNIKOV, ALKOUSA, LOBANOV, DORN, STONYAKIN, KURUZOV, A ND SINGH

    2017

  24. [31]

    Convergence and efficiency of subgradient meth ods for quasiconvex mini- mization, Math

    Kiwiel K. Convergence and efficiency of subgradient meth ods for quasiconvex mini- mization, Math. Program., 2001, vol. 90, no. 1, pp. 1-25

    2001

  25. [32]

    Adam: A method for stochastic optimizat ion, in International Conference on Learning Representations, 2015

    Kingma D., Ba J. Adam: A method for stochastic optimizat ion, in International Conference on Learning Representations, 2015

    2015

  26. [33]

    Optimization by direct se arch: New perspectives on some classical and modern methods, SIAM Review, 2003, vol

    Kolda T., Lewis R., Torczon V. Optimization by direct se arch: New perspectives on some classical and modern methods, SIAM Review, 2003, vol. 4 5, no. 3, pp. 385–482

    2003

  27. [34]

    On convergence properties of a subgradient me thod, Optimization Methods and Software, 2003, vol

    Konnov I. On convergence properties of a subgradient me thod, Optimization Methods and Software, 2003, vol. 18, no. 1, pp. 53-62

    2003

  28. [35]

    The theory of incentives: the principal-agent model , Prince- ton university press, 2009

    Laffont J., Martimort D. The theory of incentives: the principal-agent model , Prince- ton university press, 2009

    2009

  29. [36]

    Acceleration Exist s! Optimization Problems When Oracle Can Only Compare Objective Function Values

    Lobanov A., Gasnikov A., Krasnov A. Acceleration Exist s! Optimization Problems When Oracle Can Only Compare Objective Function Values. arXiv:2402.09014 (24 May 2024)

    2024 arXiv

  30. [37]

    overparametrization

    Lobanov A., Gasnikov A. Accelerated zero-order sgd met hod for solving the black box optimization problem under “overparametrization” con dition, in International Conference on Optimization and Applications, Springer, 2023, pp. 72–83

    2023

  31. [38]

    Quasi-convex programming, SIAM J

    Luenberger D. Quasi-convex programming, SIAM J. Appl. Math., 1968, vol. 16, pp. 1090–1095

    1968

  32. [39]

    To wards deep learning models resistant to adversarial attacks, in International Conference on Learning Rep- resentations, 2018

    Madry A., Makelov A., Schmidt L., Tsipras D., Vladu A. To wards deep learning models resistant to adversarial attacks, in International Conference on Learning Rep- resentations, 2018

    2018

  33. [40]

    Smooth convex optimizat ion using sub-zeroth- order oracles, in Proc

    Mustafa O., Karabag N., Ufuk T. Smooth convex optimizat ion using sub-zeroth- order oracles, in Proc. of the AAAI Conference on Artificial Intelligence, vol. 35, no. 5, 2021, pp. 3815–3822

    2021

  34. [41]

    Lectures on convex optimization , Switzerland: Springer Optimization and Its Applications, 2018

    Nesterov Yu. Lectures on convex optimization , Switzerland: Springer Optimization and Its Applications, 2018

    2018

  35. [42]

    Random gradient-free minimi zation of convex functions, Foundations of Computational Mathematics , 2017, 17, pp

    Nesterov Yu., Spokoiny V. Random gradient-free minimi zation of convex functions, Foundations of Computational Mathematics , 2017, 17, pp. 527–566

    2017

  36. [43]

    Minimization methods for nonsmooth conve x and quasiconvex functions, Matekon, 1984, vol

    Nesterov Yu. Minimization methods for nonsmooth conve x and quasiconvex functions, Matekon, 1984, vol. 29, pp. 519-531

    1984

  37. [44]

    A simplex method for function minimiz ation, The Computer Journal, 1965, vol

    Nelder J., Mead R. A simplex method for function minimiz ation, The Computer Journal, 1965, vol. 7, no. 4, pp. 308–313

    1965

  38. [45]

    On von Neumann’s minimax theorem, Pac

    Nikaidˆ o H. On von Neumann’s minimax theorem, Pac. J. Ma th., 1954, vol. 4, pp. 65–72

    1954

  39. [46]

    Distributed online and bandit convex optimiza- tion, in OPT 2022: Optimization for Machine Learning (NeurIPS 2022 W orkshop), 2022

    Patel K., Saha A., Wang L., Srebro N. Distributed online and bandit convex optimiza- tion, in OPT 2022: Optimization for Machine Learning (NeurIPS 2022 W orkshop), 2022

    2022

  40. [47]

    Practical black- box attacks against machine learning, in Proc

    Papernot N., McDaniel P., Goodfellow I., Jha S., Celik B ., Swami A. Practical black- box attacks against machine learning, in Proc. of the 2017 ACM on Asia Conference on Computer and Communications Security, 2017, pp. 506–519

    2017

  41. [48]

    An automatic method for finding the greate st or least value of a function, The Computer Journal, 1960, vol

    Rosenbrock H. An automatic method for finding the greate st or least value of a function, The Computer Journal, 1960, vol. 3, pp. 175-184

    1960

  42. [49]

    Evolu tion strategies as a scalable alternative to reinforcement learning, arXiv:1703.03864 (7 Sep 2017)

    Salimans T., Ho J., Chen X., Sidor S., Sutskever I. Evolu tion strategies as a scalable alternative to reinforcement learning, arXiv:1703.03864 (7 Sep 2017)

    2017 arXiv

  43. [50]

    Quasiconvex sum-of-squares progra mming, in 49th IEEE Confer- ence on Decision and Control (CDC), 2010, pp

    Seiler P., Balas G. Quasiconvex sum-of-squares progra mming, in 49th IEEE Confer- ence on Decision and Control (CDC), 2010, pp. 3337–3342

    2010

  44. [51]

    Zeroth-order optimization m eets human feedback: Provable learning via ranking oracles, in ICML 2023 Workshop The Many Facets of Preference-Based Learning, 2023

    Tang Z., Rybin D., Chang T. Zeroth-order optimization m eets human feedback: Provable learning via ranking oracles, in ICML 2023 Workshop The Many Facets of Preference-Based Learning, 2023

    2023

  45. [52]

    O ptimizing ( L0, L 1)- Smooth Functions by Gradient Methods, arXiv:2410.10800 (14 Oct 2024)

    Vankov D., Rodomanov A., Nedich A., Sankar L., Stich S. O ptimizing ( L0, L 1)- Smooth Functions by Gradient Methods, arXiv:2410.10800 (14 Oct 2024)

    2024 arXiv

  46. [53]

    Price discrimination and social welfare, The American Economic Review, 1985, pp

    Varian H. Price discrimination and social welfare, The American Economic Review, 1985, pp. 870-875. QUASI-CONVEX SMOOTH OPTIMIZATION BY A COMPARISON ORACLE 13

    1985

  47. [54]

    Vabo: Violation- aware bayesian optimization for closed-loop control perfo rmance optimization with unmodeled constraints, in 2022 American Control Conference (ACC), IEEE, 2022, pp

    Xu W., Jones C., Svetozarevic B., Laughman C., Chakraba rty A. Vabo: Violation- aware bayesian optimization for closed-loop control perfo rmance optimization with unmodeled constraints, in 2022 American Control Conference (ACC), IEEE, 2022, pp. 5288–5293

    2022

  48. [55]

    Topics in microeconomics: Industrial organization, aucti ons, and in- centives, Cambridge University Press, 1999

    Wolfstetter E. Topics in microeconomics: Industrial organization, aucti ons, and in- centives, Cambridge University Press, 1999

    1999

  49. [57]

    Zeroth-order negative curvatu re finding: Escaping saddle points without gradients, in Advances in Neural Information Processing Systems, vol

    Zhang H., Xiong H., Gu B. Zeroth-order negative curvatu re finding: Escaping saddle points without gradients, in Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 38332–38344. (A. V. Gasnikov) Innopolis University, Moscow Institute of Physics and Tech - nolo...

    2022

Pith tools

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