From inexact optimization to learning via gradient concentration

• URL: http://arxiv.org/abs/2106.05397v1
• Date: Wed, 9 Jun 2021 21:23:29 GMT
• Title: From inexact optimization to learning via gradient concentration
• Authors: Bernhard Stankewitz, Nicole M\"ucke, Lorenzo Rosasco
• Abstract summary: In this paper, we investigate the phenomenon in the context of linear models with smooth loss functions. We propose a proof technique combining ideas from inexact optimization and probability theory, specifically gradient concentration.
• Score: 22.152317081922437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization was recently shown to control the inductive bias in a learning process, a property referred to as implicit, or iterative regularization. The estimator obtained iteratively minimizing the training error can generalise well with no need of further penalties or constraints. In this paper, we investigate this phenomenon in the context of linear models with smooth loss functions. In particular, we investigate and propose a proof technique combining ideas from inexact optimization and probability theory, specifically gradient concentration. The proof is easy to follow and allows to obtain sharp learning bounds. More generally, it highlights a way to develop optimization results into learning guarantees.

Related papers

• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  gradient-variation online learning aims to achieve regret guarantees that scale with variations in gradients of online functions. Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms. We provide the applications for fast-rate convergence in games and extended adversarial optimization.
  arXiv  Detail & Related papers  (2024-08-17T02:22:08Z)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective. We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices. Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
  arXiv  Detail & Related papers  (2023-10-31T16:15:13Z)
• Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
  Implicit Bayesian meta-learning (iBaML) method broadens the scope of learnable priors, but also quantifies the associated uncertainty. Analytical error bounds are established to demonstrate the precision and efficiency of the generalized implicit gradient over the explicit one.
  arXiv  Detail & Related papers  (2023-03-31T02:10:30Z)
• EXACT: How to Train Your Accuracy [6.144680854063938]
  We propose a new optimization framework by introducing ascentity to a model's output and optimizing expected accuracy. Experiments on linear models and deep image classification show that the proposed optimization method is a powerful alternative to widely used classification losses.
  arXiv  Detail & Related papers  (2022-05-19T15:13:00Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• Deep learning: a statistical viewpoint [120.94133818355645]
  Deep learning has revealed some major surprises from a theoretical perspective. In particular, simple gradient methods easily find near-perfect solutions to non-optimal training problems. We conjecture that specific principles underlie these phenomena.
  arXiv  Detail & Related papers  (2021-03-16T16:26:36Z)
• 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)
• A Random Matrix Theory Approach to Damping in Deep Learning [0.7614628596146599]
  We conjecture that the inherent difference in generalisation between adaptive and non-adaptive gradient methods in deep learning stems from the increased estimation noise. We develop a novel random matrix theory based damping learner for second order optimiser inspired by linear shrinkage estimation.
  arXiv  Detail & Related papers  (2020-11-15T18:19:42Z)

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.