Extended convexity and smoothness and their applications in deep learning

• URL: http://arxiv.org/abs/2410.05807v2
• Date: Wed, 15 Jan 2025 09:53:49 GMT
• Title: Extended convexity and smoothness and their applications in deep learning
• Authors: Binchuan Qi, Wei Gong, Li Li,
• Abstract summary: This paper introduces an optimization framework aimed at providing a theoretical foundation for a class of composite optimization problems, particularly those in deep learning. We analyze the smoothness of Lipschitz's concepts of Lipschitz's descent and descent methods for objective functions that are $mathcalH(Phi)$-smoothness.
• Score: 5.281849820329249
• License:
• Abstract: This paper introduces an optimization framework aimed at providing a theoretical foundation for a class of composite optimization problems, particularly those encountered in deep learning. In this framework, we introduce $\mathcal{H}(\phi)$-convexity and $\mathcal{H}(\Phi)$-smoothness to generalize the existing concepts of Lipschitz smoothness and strong convexity. Furthermore, we analyze and establish the convergence of both gradient descent and stochastic gradient descent methods for objective functions that are $\mathcal{H}(\Phi)$-smooth. We prove that the optimal convergence rates of these methods depend solely on the homogeneous degree of $\Phi$. Based on these findings, we construct two types of non-convex and non-smooth optimization problems: deterministic composite and stochastic composite optimization problems, which encompass the majority of optimization problems in deep learning. To address these problems, we develop the gradient structure control algorithm and prove that it can locate approximate global optima. This marks a significant departure from traditional non-convex analysis framework, which typically settle for stationary points. Therefore, with the introduction of $\mathcal{H}(\phi)$-convexity and $\mathcal{H}(\Phi)$-smoothness, along with the GSC algorithm, the non-convex optimization mechanisms in deep learning can be theoretically explained and supported. Finally, the effectiveness of the proposed framework is substantiated through empirical experimentation.

Related papers

• Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation [2.3342885570554652]
  We introduce a piecewise approximation for process kernels and a corresponding MIQP representation for acquisition functions. We empirically demonstrate the framework on synthetic functions, constrained benchmarks, and hyper tuning tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:56:52Z)
• PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates [17.777466668123886]
  We introduce PROMISE ($textbfPr$econditioned $textbfO$ptimization $textbfM$ethods by $textbfI$ncorporating $textbfS$calable Curvature $textbfE$stimates), a suite of sketching-based preconditioned gradient algorithms. PROMISE includes preconditioned versions of SVRG, SAGA, and Katyusha.
  arXiv  Detail & Related papers  (2023-09-05T07:49:10Z)
• 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)
• A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization [26.68351521813062]
  Existing bi-level algorithms cannot handle nonsmooth or hyper-smooth regularizers. In this paper, we show that an implicit differentiation (AID) scheme can be used to speed up comprehensive machine learning applications.
  arXiv  Detail & Related papers  (2022-03-30T18:53:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• 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)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• 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)
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems [12.010310883787911]
  We analyze a new family of adaptive subgradient methods for solving an important class of weakly convex (possibly nonsmooth) optimization problems. Experimental results indicate how the proposed algorithms empirically outperform its zerothorder gradient descent and its design variant.
  arXiv  Detail & Related papers  (2020-05-19T07:44:52Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.