Stochastic linear optimization never overfits with quadratically-bounded losses on general data

• URL: http://arxiv.org/abs/2202.06915v1
• Date: Mon, 14 Feb 2022 18:12:38 GMT
• Title: Stochastic linear optimization never overfits with quadratically-bounded losses on general data
• Abstract summary: This work shows that a diverse collection of linear optimization methods, when run on general data, fail to overfit, despite lacking any explicit constraints or regularization. This analysis is powered by an elementary but flexible proof scheme which can handle many settings.
• Score: 20.41989568533313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work shows that a diverse collection of linear optimization methods, when run on general data, fail to overfit, despite lacking any explicit constraints or regularization: with high probability, their trajectories stay near the curve of optimal constrained solutions over the population distribution. This analysis is powered by an elementary but flexible proof scheme which can handle many settings, summarized as follows. Firstly, the data can be general: unlike other implicit bias works, it need not satisfy large margin or other structural conditions, and moreover can arrive sequentially IID, sequentially following a Markov chain, as a batch, and lastly it can have heavy tails. Secondly, while the main analysis is for mirror descent, rates are also provided for the Temporal-Difference fixed-point method from reinforcement learning; all prior high probability analyses in these settings required bounded iterates, bounded updates, bounded noise, or some equivalent. Thirdly, the losses are general, and for instance the logistic and squared losses can be handled simultaneously, unlike other implicit bias works. In all of these settings, not only is low population error guaranteed with high probability, but moreover low sample complexity is guaranteed so long as there exists any low-complexity near-optimal solution, even if the global problem structure and in particular global optima have high complexity.

Related papers

• Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult [67.12978375116599]
  We show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm.<n>We derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting.
  arXiv  Detail & Related papers  (2026-09-15T17:24:09Z)
• High-Probability Convergence of SGD via Batched Updates [4.862625283098196]
  Batched SGD is a simple variant that iterates online epochs into optimizations.<n>Our main contribution demonstrates that this mechanism enables a surprisingly simple high-probability analysis.
  arXiv  Detail & Related papers  (2026-09-11T12:17:18Z)
• Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules [42.38093055717409]
  We develop new confidence-sequence techniques and a general time-uniform empirical Bernstein inequality for adapted processes.<n>We show that the resulting stopping rules can require several orders of fewer than natural gradient horizons.
  arXiv  Detail & Related papers  (2026-08-26T09:02:46Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Nearly Instance-Optimal Parameter Recovery from Many Trajectories via Hellinger Localization [19.74516565968901]
  We extend the scope of instance-optimal rates in multi-trajectory settings via the Hellinger localization framework.<n>We instantiate our framework across four diverse case studies.<n>Our bounds nearly match the instance-optimal rates from normality, substantially improving over standard reductions.
  arXiv  Detail & Related papers  (2025-10-07T20:12:04Z)
• Optimal Implicit Bias in Linear Regression [20.710343135282116]
  We find the optimal implicit bias that leads to the best generalization performance.<n>In particular, we obtain a tight lower bound on the best generalization error possible among this class of interpolators.
  arXiv  Detail & Related papers  (2025-06-20T17:41:39Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• 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)
• It's All in the Mix: Wasserstein Classification and Regression with Mixed Features [5.106912532044251]
  We develop and analyze distributionally robust prediction models that faithfully account for the presence of discrete features. We demonstrate that our models can significantly outperform existing methods that are agnostic to the presence of discrete features.
  arXiv  Detail & Related papers  (2023-12-19T15:15:52Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  gradient, clipping is one of the key algorithmic ingredients to derive good high-probability guarantees. Clipping can spoil the convergence of the popular methods for composite and distributed optimization.
  arXiv  Detail & Related papers  (2023-10-03T07:49:17Z)
• Probabilistic Learning of Multivariate Time Series with Temporal Irregularity [21.361823581838355]
  Real-world time series often suffer from temporal irregularities, including nonuniform intervals and misaligned variables. We propose an end-to-end framework that models temporal irregularities while capturing the joint distribution of variables at arbitrary continuous-time points.
  arXiv  Detail & Related papers  (2023-06-15T14:08:48Z)
• The Decaying Missing-at-Random Framework: Doubly Robust Causal Inference with Partially Labeled Data [10.021381302215062]
  In real-world scenarios, data collection limitations often result in partially labeled datasets, leading to difficulties in drawing reliable causal inferences. Traditional approaches in the semi-parametric (SS) and missing data literature may not adequately handle these complexities, leading to biased estimates. This framework tackles missing outcomes in high-dimensional settings and accounts for selection bias.
  arXiv  Detail & Related papers  (2023-05-22T07:37:12Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Support Vector Machines with the Hard-Margin Loss: Optimal Training via Combinatorial Benders' Cuts [8.281391209717105]
  We show how to train the hard-margin SVM model to global optimality. We introduce an iterative sampling and sub decomposition algorithm that solves the problem.
  arXiv  Detail & Related papers  (2022-07-15T18:21:51Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  We consider differentially private convex optimization for heavy-tailed data with the guarantee of being differentially private (DP) We establish new convergence results and improved complexity bounds for the proposed algorithm called AClipped-dpSGD for constrained and unconstrained convex problems.
  arXiv  Detail & Related papers  (2022-06-27T01:39:15Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• The Implicit Bias of Gradient Descent on Separable Data [44.98410310356165]
  We show the predictor converges to the direction of the max-margin (hard margin SVM) solution. This can help explain the benefit of continuing to optimize the logistic or cross-entropy loss even after the training error is zero.
  arXiv  Detail & Related papers  (2017-10-27T21:47:58Z)

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.