Research map / Optimization / Nonconvex and smooth optimization
Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails
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.
Derives computable non-asymptotic confidence bounds on the optimal value of stochastic optimization problems that are non-Lipschitzian and hold under heavy-tailed noise, using SAA for convex problems and DRM for nonconvex and over-parameterized problems.
Problem
Constructing non-asymptotic confidence bounds for the optimal value of stochastic optimization problems without relying on a global Lipschitz constant or light-tailed distributions.
Approach
Uses Marcinkiewicz-type moment bounds on SAA for convex problems under p-th moment conditions localized at an optimal solution, and combines SAA lower bounds with diametrical risk minimization upper bounds for nonconvex problems, with a non-negativity and zero-optimal-cost structural assumption to extend to heavy tails.
Key results
- On a stochastic linear program, the proposed convex NCBs have length ratios of 0.599 (estimated quantities) to 0.064 (exact quantities) relative to Oliveira & Thompson (2023) for d from 100 to 4000.
- For nonconvex over-parameterized neural network training, average length ratios relative to the benchmark range from 0.030 down to 0.008 as N and d grow.
- The convex heavy-tailed bound keeps the O(N^-1/2) rate of Guigues et al. (2017) while removing the global Lipschitz constant dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed NCBs instead of the benchmark NCBs | Convex stochastic linear problem; P-NCBE and P-NCB* · Convex stochastic linear problem (d=100 to d=4000) | confidence-bound length ratio r1: P-NCBE: 0.599, 0.419, 0.300, 0.215, 0.170; P-NCB*: 0.281, 0.170, 0.120, 0.085, 0.064 | Helped |
| Use the proposed nonconvex NCBs instead of the benchmark NCBs | P-NCB-NCE · Nonconvex over-parameterized model (d=41, d=961, and d=1681) | average confidence-bound length ratio r2: d=41: 0.030, 0.018, 0.018, 0.017; d=961: 0.023, 0.012, 0.012, 0.011; d=1681: 0.009, 0.009, 0.009, 0.008 | Helped |
Limitations
- Some conservatism remains in the constructed bounds.
- Nonconvex heavy-tailed result requires a strong structural assumption: non-negative cost and zero DRM optimal value, as in over-parameterized models.
- DRM is generally more expensive to compute than SAA.
Experimental setup
Datasets: synthetic power-law distributed data for stochastic linear program synthetic student-t noise for two-layer neural network regression
Benchmarks: synthetic stochastic linear program synthetic over-parameterized two-layer neural network regression
Metrics: empirical coverage probability average confidence interval length ratio relative to benchma
Baselines: Guigues et al. 2017 benchmark NCBs Oliveira & Thompson 2023 NCBs Lan et al. 2012 mirror descent NCBs
Builds on: sample average approximation diametrical risk minimization Guigues et al. 2017 confidence bounds Oliveira & Thompson 2023 confidence bounds
Closest papers by meaning
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.90)
- New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.89)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.89)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.89)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.89)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.89)
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.