Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification

• URL: http://arxiv.org/abs/2505.22359v1
• Date: Wed, 28 May 2025 13:39:14 GMT
• Title: Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
• Authors: Matan Schliserman, Tomer Koren,
• Abstract summary: We study generalization performance of unregularized methods for separable linear classification.<n>We show that convergence rates are crucially influenced by the geometry of the loss template.
• Score: 27.33243506775655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the generalization performance of unregularized gradient methods for separable linear classification. While previous work mostly deal with the binary case, we focus on the multiclass setting with $k$ classes and establish novel population risk bounds for Gradient Descent for loss functions that decay to zero. In this setting, we show risk bounds that reveal that convergence rates are crucially influenced by the geometry of the loss template, as formalized by Wang and Scott (2024), rather than of the loss function itself. Particularly, we establish risk upper bounds that holds for any decay rate of the loss whose template is smooth with respect to the $p$-norm. In the case of exponentially decaying losses, our results indicates a contrast between the $p=\infty$ case, where the risk exhibits a logarithmic dependence on $k$, and $p=2$ where the risk scales linearly with $k$. To establish this separation formally, we also prove a lower bound in the latter scenario, demonstrating that the polynomial dependence on $k$ is unavoidable. Central to our analysis is a novel bound on the Rademacher complexity of low-noise vector-valued linear predictors with a loss template smooth w.r.t.~general $p$-norms.

Related papers

• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Any-stepsize Gradient Descent for Separable Data under Fenchel--Young Losses [17.835960292396255]
  We show arbitrary-stepsize gradient convergence for a general loss function based on the framework of emphFenchel--Young losses.<n>We argue that these better rate is possible because of emphseparation margin of loss functions, instead of the self-bounding property.
  arXiv  Detail & Related papers  (2025-02-07T12:52:12Z)
• Generalization and Robustness of the Tilted Empirical Risk [17.48212403081267]
  generalization error (risk) of a supervised statistical learning algorithm quantifies its prediction ability on previously unseen data.<n>Inspired by exponential tilting, citetli 2020tilted proposed the it tilted empirical risk (TER) as a non-linear risk metric for machine learning applications.
  arXiv  Detail & Related papers  (2024-09-28T18:31:51Z)
• Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
  We study a generalization of the problem of online learning in adversarial linear contextual bandits by incorporating loss functions that belong to a Hilbert kernel space. We propose a new optimistically biased estimator for the loss functions and reproducing near-optimal regret guarantees.
  arXiv  Detail & Related papers  (2023-10-02T19:59:39Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Tight Risk Bounds for Gradient Descent on Separable Data [33.593203156666746]
  We study the generalization properties of unregularized gradient methods applied to separable linear classification. Risk lower bounds are the first in this context and establish the tightness of our upper bounds for any given tail decay rate.
  arXiv  Detail & Related papers  (2023-03-02T10:31:58Z)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models [33.36787620121057]
  We prove a new generalization bound that shows for any class of linear predictors in Gaussian space. We use our finite-sample bound to directly recover the "optimistic rate" of Zhou et al. (2021) We show that application of our bound generalization using localized Gaussian width will generally be sharp for empirical risk minimizers.
  arXiv  Detail & Related papers  (2022-10-21T16:16:55Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Localization, Convexity, and Star Aggregation [0.0]
  Offset Rademacher complexities have been shown to imply sharp, linear-dependent upper bounds for the square loss. We show that in the statistical setting, the offset bound can be generalized to any loss satisfying certain uniform convexity.
  arXiv  Detail & Related papers  (2021-05-19T00:47:59Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
  We show that gradient descent finds halfspaces with classification error $tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
  arXiv  Detail & Related papers  (2020-10-01T16:48:33Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

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.