Self-Regularized Learning Methods

• URL: http://arxiv.org/abs/2603.17160v1
• Date: Tue, 17 Mar 2026 21:45:50 GMT
• Title: Self-Regularized Learning Methods
• Abstract summary: We introduce a general framework for analyzing learning algorithms based on the notion of self-regularization.<n>We provide a thorough statistical analysis of such algorithms including minmax-optimal rates.
• Score: 6.30853901017231
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a general framework for analyzing learning algorithms based on the notion of self-regularization, which captures implicit complexity control without requiring explicit regularization. This is motivated by previous observations that many algorithms, such as gradient-descent based learning, exhibit implicit regularization. In a nutshell, for a self-regularized algorithm the complexity of the predictor is inherently controlled by that of the simplest comparator achieving the same empirical risk. This framework is sufficiently rich to cover both classical regularized empirical risk minimization and gradient descent. Building on self-regularization, we provide a thorough statistical analysis of such algorithms including minmax-optimal rates, where it suffices to show that the algorithm is self-regularized -- all further requirements stem from the learning problem itself. Finally, we discuss the problem of data-dependent hyperparameter selection, providing a general result which yields minmax-optimal rates up to a double logarithmic factor and covers data-driven early stopping for RKHS-based gradient descent.

Related papers

• Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis [44.468416523840965]
  We develop a theory of algorithm-dependent generalisation for high-dimensional diffusion models.<n>We derive generalisation bounds in terms of score stability, and apply our framework to several fundamental learning settings.
  arXiv  Detail & Related papers  (2025-07-04T18:07:06Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Regularization and Optimal Multiclass Learning [10.168670899305232]
  This work is to characterize the role of regularization in perhaps the simplest setting for which empirical risk minimization fails: multiclass learning with arbitrary label sets. Using one-inclusion graphs (OIGs), we exhibit optimal learning algorithms that dovetail with tried-and-true algorithmic principles.
  arXiv  Detail & Related papers  (2023-09-24T16:49:55Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Iterative regularization for low complexity regularizers [18.87017835436693]
  Iterative regularization exploits the implicit bias of an optimization algorithm to regularize ill-posed problems. We propose and study the first iterative regularization procedure able to handle biases described by non smooth and non strongly convex functionals.
  arXiv  Detail & Related papers  (2022-02-01T14:09:00Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Fine-grained Generalization Analysis of Vector-valued Learning [28.722350261462463]
  We start the generalization analysis of regularized vector-valued learning algorithms by presenting bounds with a mild dependency on the output dimension and a fast rate on the sample size. To understand the interaction between optimization and learning, we further use our results to derive the first bounds for descent with vector-valued functions. As a byproduct, we derive a Rademacher complexity bound for loss function classes defined in terms of a general strongly convex function.
  arXiv  Detail & Related papers  (2021-04-29T07:57:34Z)
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory [11.840747467007963]
  We study problem-dependent rates that scale near-optimally with the variance, the effective loss errors, or the norms evaluated at the "best gradient hypothesis" We introduce a principled framework dubbed "uniform localized convergence" We show that our framework resolves several fundamental limitations of existing uniform convergence and localization analysis approaches.
  arXiv  Detail & Related papers  (2020-11-12T04:07:29Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)

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.