Research map / Optimization / Nonconvex and smooth optimization
Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes trust region methods (first- and second-order, with variance reduction) for nonconvex stochastic optimization under (L0,L1)-generalized smoothness, with a second-order generalized smoothness condition for penalized DRO.
Problem
Stochastic nonconvex optimization where the gradient is not globally Lipschitz, i.e. under (L0,L1)-smoothness as arises in deep networks and DRO; existing methods only guarantee first-order stationary points.
Approach
Cast generalized-smooth stochastic optimization as a trust region subproblem with a bounded-norm B_t; the first-order case recovers normalized and clipped SGD, and the second-order case (B_t = Hessian estimate) reaches second-order stationary points, with a variance-reduced variant matching the O(eps^-3) rate. It also introduces a second-order generalized smoothness condition satisfied by smoothed
Key results
- On imbalanced CIFAR-10 with chi-square DRO loss, SOTRGS reports worst-category accuracy 0.681 and overall accuracy 0.889, versus SGD at 0.629 and 0.894.
- Theoretically, FOTRGS achieves O(eps^-4) and FOTRGS-VR achieves O(eps^-3) first-order sample complexity under (L0,L1)-smoothness.
- SOTRGS reaches (eps, sqrt(eps))-SOSP with O(eps^-3.5) sample complexity, and SOTRGS-VR with O(eps^-3) total complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, χ² loss | worst-category accuracy: 0.629 -> 0.705 | Helped |
| Use FOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, χ² loss | overall accuracy: 0.894 -> 0.898 | Helped |
| Use SOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, χ² loss | worst-category accuracy: 0.629 -> 0.681 | Helped |
| Use SOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, χ² loss | overall accuracy: 0.894 -> 0.889 | Hurt |
| Use FOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, CVaR loss | worst-category accuracy: 0.607 -> 0.615 | Helped |
| Use FOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, CVaR loss | overall accuracy: 0.888 -> 0.899 | Helped |
| Use SOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, CVaR loss | worst-category accuracy: 0.607 -> 0.616 | Helped |
| Use SOTRGS instead of SGD | DRO classification · Imbalanced CIFAR10, CVaR loss | overall accuracy: 0.888 -> 0.896 | Helped |
Surprising findings
- On imbalanced CIFAR-10 with CVaR loss, SGD and trust region methods have similar overall accuracy (0.894 vs 0.896 for SOTRGS), with a small worst-class gap.
Limitations
- Experiments are small-scale classification on imbalanced MNIST, Fashion-MNIST and CIFAR-10 with a loosely described architecture; the paper calls them preliminary.
- The second-order generalized smoothness condition is shown for penalized DRO only; the authors leave other ML problems open.
- Exact trust-region subproblem solving is costly at scale, so the inexact subspace variant relies on an additional Hessian-approximation assumption.
Experimental setup
Datasets: MNIST Fashion-MNIST CIFAR-10
Benchmarks: imbalanced MNIST imbalanced Fashion-MNIST imbalanced CIFAR-10
Metrics: worst-class accuracy overall test accuracy training loss curves
Baselines: SGD normalized SGD clipped SGD (L0,L1)-SPIDER
Builds on: (L0,L1)-smoothness normalized SGD clipped SGD SPIDER stochastic trust region (STR)
Closest papers by meaning
- Delving into the Convergence of Generalized Smooth Minimax Optimization (ICML 2024 · similarity 0.88)
- Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes (ICML 2024 · similarity 0.87)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.87)
- Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization (NeurIPS 2026 · similarity 0.87)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.87)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.