Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements

• URL: http://arxiv.org/abs/2107.08011v1
• Date: Fri, 16 Jul 2021 16:59:40 GMT
• Title: Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements
• Authors: Kimon Antonakopoulos and Panayotis Mertikopoulos
• Abstract summary: We propose a new family of adaptive first-order methods for convex minimization problems that fail to be Lipschitz continuous or smooth. The proposed method - which we call adaptive mirror descent (AdaMir) - aims to close this gap by concurrently achieving min-max optimal rates in problems that are relatively continuous or smooth.
• Score: 34.70493893170415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new family of adaptive first-order methods for a class of convex minimization problems that may fail to be Lipschitz continuous or smooth in the standard sense. Specifically, motivated by a recent flurry of activity on non-Lipschitz (NoLips) optimization, we consider problems that are continuous or smooth relative to a reference Bregman function - as opposed to a global, ambient norm (Euclidean or otherwise). These conditions encompass a wide range of problems with singular objectives, such as Fisher markets, Poisson tomography, D-design, and the like. In this setting, the application of existing order-optimal adaptive methods - like UnixGrad or AcceleGrad - is not possible, especially in the presence of randomness and uncertainty. The proposed method - which we call adaptive mirror descent (AdaMir) - aims to close this gap by concurrently achieving min-max optimal rates in problems that are relatively continuous or smooth, including stochastic ones.

Related papers

• 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. 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)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization [32.939120407900035]
  Our algorithms feature a simple update rule that requires solving only one linear system per iteration. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization.
  arXiv  Detail & Related papers  (2024-06-04T06:56:41Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  This paper presents a subgradient-based algorithm for constrained nonsmooth convex computation. Our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. Similar performance is observed when deterministic subgradients are replaced with subgradients.
  arXiv  Detail & Related papers  (2023-11-18T23:06:33Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization [24.784754071913255]
  Adaptive algorithms like AdaGrad and AMS are successful in nonspecific parameters robustness. We show that NeAda can achieve the near-optimal level of knowledge.
  arXiv  Detail & Related papers  (2022-06-01T20:11:05Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  We present a new family of minmax optimization algorithms that automatically exploit the geometry of the gradient data observed at earlier iterations. Thanks to this adaptation mechanism, the proposed method automatically detects whether the problem is smooth or not. It converges to an $varepsilon$-optimal solution within $mathcalO (1/varepsilon)$ iterations in smooth problems, and within $mathcalO (1/varepsilon)$ iterations in non-smooth ones.
  arXiv  Detail & Related papers  (2020-10-22T22:54:54Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• 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.