Are Convex Optimization Curves Convex?

• URL: http://arxiv.org/abs/2503.10138v3
• Date: Sat, 28 Jun 2025 20:25:33 GMT
• Title: Are Convex Optimization Curves Convex?
• Abstract summary: An initial plateau is followed by a sharp decrease, making it difficult to decide when optimization should stop.<n>We show, perhaps surprisingly, that the answer depends on choice of step size.
• Score: 30.115763608084485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study when we might expect the optimization curve induced by gradient descent to be \emph{convex} -- precluding, for example, an initial plateau followed by a sharp decrease, making it difficult to decide when optimization should stop. Although such undesirable behavior can certainly occur when optimizing general functions, might it also occur in the benign and well-studied case of smooth convex functions? As far as we know, this question has not been tackled in previous work. We show, perhaps surprisingly, that the answer crucially depends on the choice of the step size. In particular, for the range of step sizes which are known to result in monotonic convergence to an optimal value, we characterize a regime where the optimization curve will be provably convex, and a regime where the curve can be non-convex. We also extend our results to gradient flow, and to the closely-related but different question of whether the gradient norm decreases monotonically.

Related papers

• Nonsmooth Optimization via Orthogonalized Momentum [11.546795991978613]
  We show that for every fixed momentum factor $in[0,1)$, Muon can fail to approach the global optimal solution a convex Lipschitz objective.<n>We propose MAGD, which combines momentum with gradient, weighted based on their relative progress.
  arXiv  Detail & Related papers  (2026-09-12T03:08:36Z)
• Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples [0.0]
  We study when the emphoptimization curve of first-order methods is convex.<n>For gradient descent on convex $L$--smooth functions, the curve is convex for all stepsizes $eta le 1.75/L$, and this threshold is tight.
  arXiv  Detail & Related papers  (2025-09-10T19:28:47Z)
• Towards Weaker Variance Assumptions for Stochastic Optimization [19.339358874690568]
  We revisit a classical assumption for analyzing gradient algorithms where the squared norm of the subgradient is allowed to grow as fast as the squared norm of the optimization variable. We analyze convex problems with functional constraints or regularized convex-concave min-max problems. We obtain rates for optimality measures that do not require boundedness of the feasible set.
  arXiv  Detail & Related papers  (2025-04-14T07:26:34Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  We focus on the class of (strongly) convex $(L0)$-smooth functions and derive new convergence guarantees for several existing methods.<n>In particular, we derive improved convergence rates for Gradient Descent with smoothnessed Gradient Clipping and for Gradient Descent with Polyak Stepsizes.
  arXiv  Detail & Related papers  (2024-09-23T13:11:37Z)
• Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
  We show that AdaGrad outperforms SGD by a factor of $d$ under certain conditions. Motivated by this, we introduce assumptions on the smoothness structure of the objective and the gradient variance.
  arXiv  Detail & Related papers  (2024-06-07T02:55:57Z)
• On the Convergence of Gradient Descent for Large Learning Rates [55.33626480243135]
  We show that convergence is impossible when a fixed step size is used. We provide a proof of this in the case of linear neural networks with a squared loss. We also prove the impossibility of convergence for more general losses without requiring strong assumptions such as Lipschitz continuity for the gradient.
  arXiv  Detail & Related papers  (2024-02-20T16:01:42Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  An analysis of convex and non- optimization methods often requires the Lipsitzness gradient, which limits the analysis by this trajectorys. Recent work generalizes the gradient setting via the non-uniform smoothness condition.
  arXiv  Detail & Related papers  (2023-06-02T04:21:59Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  Subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. In this work, we first extend the typical iteration complexity results for the subgradient method to cover non-Lipschitz convex and weakly convex minimization.
  arXiv  Detail & Related papers  (2023-05-23T15:26:36Z)
• Adaptive Approximate Implicitization of Planar Parametric Curves via Weak Gradient Constraints [11.559302398966468]
  We introduce a new regularization constraint for both and non-polynomial curves. We then propose two adaptive algorithms of approximate implicitization for both and non-polynomial curves. More precisely, the idea is gradually increasing the implicit degree, until there is no obvious improvement in the weak gradient loss of the outputs.
  arXiv  Detail & Related papers  (2023-02-23T04:08:53Z)
• Exponential Concentration in Stochastic Approximation [0.8192907805418583]
  We analyze the behavior of approximation algorithms where iterates, in expectation, progress towards an objective at each step. We apply our results to several different Markov Approximation algorithms, specifically Projected Gradient Descent, Kiefer-Wolfowitz and Frank-Wolfe algorithms.
  arXiv  Detail & Related papers  (2022-08-15T14:57:26Z)
• Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
  In a supervised learning setting, we show that if an metric 0 is contracting in someian rate $lambda, it is uniformly uniformly rate with $math. The results hold for gradient and deterministic loss surfaces, in both continuous and stable $-time. They can be shown to be optimal in certain linear settings, such as over Descent$ convex or strongly convex loss surfaces.
  arXiv  Detail & Related papers  (2022-01-17T23:08:47Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  We study first-order methods when the inner optimization problem is convex but non-smooth. We show that the forward-mode differentiation of proximal gradient descent and proximal coordinate descent yield sequences of Jacobians converging toward the exact Jacobian.
  arXiv  Detail & Related papers  (2021-05-04T17:31:28Z)
• Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
  We introduce a new block coordinate method that applies to the general class of variational inequality (VI) problems with monotone operators. The resulting convergence bounds match the optimal convergence bounds of full gradient methods. For $m$ coordinate blocks, the resulting gradient Lipschitz constant in our bounds is never larger than a factor $sqrtm$ compared to the traditional Euclidean Lipschitz constant.
  arXiv  Detail & Related papers  (2021-02-26T00:28:58Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  We generalize the approach Gasnikov et. al., 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle. Our approach reduces $fracnlog n$ times the required number of oracle calls. In the second part of the paper, we analyze the case when such an assumption cannot be made, we propose a general approach on how to modernize the method to solve this problem.
  arXiv  Detail & Related papers  (2020-05-12T16:44:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.