Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective

• URL: http://arxiv.org/abs/2403.16317v2
• Date: Mon, 04 Nov 2024 17:44:26 GMT
• Title: Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective
• Authors: Jelena Diakonikolas, Cristóbal Guzmán,
• Abstract summary: We study nonsmooth optimization problems under bounded local subgradient variation. The resulting class of objective encapsulates the classes of objective based on the defined classes.
• Score: 17.5796206457693
• License:
• Abstract: We initiate the study of nonsmooth optimization problems under bounded local subgradient variation, which postulates bounded difference between (sub)gradients in small local regions around points, in either average or maximum sense. The resulting class of objective functions encapsulates the classes of objective functions traditionally studied in optimization, which are defined based on either Lipschitz continuity of the objective or H\"{o}lder/Lipschitz continuity of its gradient. Further, the defined class contains functions that are neither Lipschitz continuous nor have a H\"{o}lder continuous gradient. When restricted to the traditional classes of optimization problems, the parameters defining the studied classes lead to more fine-grained complexity bounds, recovering traditional oracle complexity bounds in the worst case but generally leading to lower oracle complexity for functions that are not ``worst case.'' Some highlights of our results are that: (i) it is possible to obtain complexity results for both convex and nonconvex problems with the (local or global) Lipschitz constant being replaced by a constant of local subgradient variation and (ii) mean width of the subdifferential set around the optima plays a role in the complexity of nonsmooth optimization, particularly in parallel settings. A consequence of (ii) is that for any error parameter $\epsilon > 0$, parallel oracle complexity of nonsmooth Lipschitz convex optimization is lower than its sequential oracle complexity by a factor $\tilde{\Omega}\big(\frac{1}{\epsilon}\big)$ whenever the objective function is piecewise linear with polynomially many pieces in the input size. This is particularly surprising as existing parallel complexity lower bounds are based on such classes of functions. The seeming contradiction is resolved by considering the region in which the algorithm is allowed to query the objective.

Related papers

• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• 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)
• Global Convergence of Model Function Based Bregman Proximal Minimization Algorithms [17.740376367999705]
  Lipschitz mapping of a continuously differentiable function plays a crucial role in various optimization algorithms. We propose a globally convergent algorithm called Model $$L$mad property.
  arXiv  Detail & Related papers  (2020-12-24T08:09:22Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization [21.435973899949285]
  We derive tight lower complexity bounds of randomized incremental gradient methods, including SAG, SAGA, SVRG, and SARAH, for two typical cases of finite-sum optimization. Our results tightly match the upper complexity of Katyusha or VRADA when each component function is strongly convex and smooth, and tightly match the upper complexity of SDCA without duality and of KatyushaX when the finite-sum function is strongly convex and the component functions are average smooth.
  arXiv  Detail & Related papers  (2020-10-17T11:19:07Z)

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.