General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization

• URL: http://arxiv.org/abs/2411.07061v1
• Date: Mon, 11 Nov 2024 15:25:48 GMT
• Title: General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization
• Authors: Kwangjun Ahn, Gagik Magakyan, Ashok Cutkosky,
• Abstract summary: This work investigates the effectiveness schedule-free methods, developed by A. Defazio et al. Specifically, we show that schedule-free iteration for nonsmooth SGD non optimization problems.
• Score: 40.254487017289975
• License:
• Abstract: This work investigates the effectiveness of schedule-free methods, developed by A. Defazio et al. (NeurIPS 2024), in nonconvex optimization settings, inspired by their remarkable empirical success in training neural networks. Specifically, we show that schedule-free SGD achieves optimal iteration complexity for nonsmooth, nonconvex optimization problems. Our proof begins with the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into an optimization algorithm for nonconvex losses. Our general framework not only recovers existing conversions but also leads to two novel conversion schemes. Notably, one of these new conversions corresponds directly to schedule-free SGD, allowing us to establish its optimality. Additionally, our analysis provides valuable insights into the parameter choices for schedule-free SGD, addressing a theoretical gap that the convex theory cannot explain.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• From Inverse Optimization to Feasibility to ERM [11.731853838892487]
  We study the contextual inverse setting that utilizes additional contextual information to better predict parameters. We experimentally validate our approach on synthetic and real-world problems and demonstrate improved performance compared to existing methods.
  arXiv  Detail & Related papers  (2024-02-27T21:06:42Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
  -freeness in online learning refers to the adaptivity of an algorithm with respect to the optimal decision in hindsight. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the optimistic updates required by parameter-freeness. We propose a simple yet powerful algorithm for Online Linear Optimization (OLO) with switching cost, which improves the existing suboptimal regret bound [ZCP22a] to the optimal rate.
  arXiv  Detail & Related papers  (2022-05-13T18:44:27Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  We introduce a new family of oracle-efficient algorithms for $varepsilon$-misspecified contextual bandits. We obtain the first algorithm that achieves the optimal $O(dsqrtT + varepsilonsqrtdT)$ regret bound for unknown misspecification level.
  arXiv  Detail & Related papers  (2021-07-12T21:30:41Z)
• Obtaining Adjustable Regularization for Free via Iterate Averaging [43.75491612671571]
  Regularization for optimization is a crucial technique to avoid overfitting in machine learning. We establish an averaging scheme that converts the iterates of SGD on an arbitrary strongly convex and smooth objective function to its regularized counterpart. Our approaches can be used for accelerated and preconditioned optimization methods as well.
  arXiv  Detail & Related papers  (2020-08-15T15:28:05Z)
• Momentum with Variance Reduction for Nonconvex Composition Optimization [9.657813709239335]
  Composition optimization is widely-applied in non machine learning. Various advanced algorithms that adopt momentum and variance reduction techniques have been developed. Our algorithm converges significantly faster than existing algorithms.
  arXiv  Detail & Related papers  (2020-05-15T19:29:33Z)

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.