Research map / Optimization / Nonconvex and smooth optimization
An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions
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 an online adaptive-sampling proximal DC algorithm for stochastic nonsmooth DC problems under time-varying distributions, with distinct sample rates for convex and concave parts, and proves an O(sqrt(p/n)) SAA rate for subdifferential mappings.
Problem
Stochastic nonsmooth difference-of-convex optimization where data come from time-varying distributions, so past samples may be stale and subgradient selectors may be non-measurable.
Approach
Online proximal DCA that resamples fresh data each iteration (discarding past samples), uses separate adaptive sample sizes for the convex and concave parts guided by the step-size norm, and bounds SAA error of subdifferential sets via support functions without requiring a measurable subgradient selector.
Key results
- Establishes an O(sqrt(p/n)) (modulo log factors) pointwise SAA convergence rate for subdifferential mappings, near the smooth-case rate; squared-error rate O(1/n^{2α}) with α<1/2.
- Proves almost-sure subsequential convergence of iterates to DC critical points under summable Wasserstein-1 drift and summable sample-size conditions (alpha_g in (0,1/2), alpha_h in (0,1)).
- In synthetic sparse robust regression experiments, adaptive ospDCA outperforms S(p)DCA and fixed-sample ospDCA baselines in convergence error versus time (specific numeric values not given in extracted text).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive sampling instead of a predetermined sublinearly growing sample size (ablation) | ospDCA · Online sparse robust regression | distance to optimal solution | Helped |
| use adaptive sampling instead of one new sample per iteration with aggregated samples | ospDCA · Online sparse robust regression | convergence efficiency | Helped |
| use adaptive sampling instead of a fixed sample size of 100 per iteration (ablation) | ospDCA · Online sparse robust regression | convergence efficiency | Helped |
| use adaptive sampling instead of a fixed sample size of 1000 per iteration (ablation) | ospDCA · Online sparse robust regression | convergence efficiency | Helped |
Limitations
- Only asymptotic convergence (subsequential, almost sure); no non-asymptotic iteration complexity derived.
- Sample-size conditions require summable sequences; practical adaptive rule relies on constants (Cg, Ch) and tuning.
- Experiments limited to a single synthetic sparse robust regression problem.
Experimental setup
Datasets: synthetic online sparse robust regression data (features uniform on [-1,1]^p, time-varying shift)
Benchmarks: synthetic online sparse robust regression (p=50, p=200)
Metrics: distance between iterate and optimal solution computational time sample size per iteration
Baselines: S(p)DCA (Le Thi et al. 2024) ospDCA with fixed sublinear sample size t^2.1 ospDCA with 100 samples per iteration ospDCA with 1000 samples per iteration
Builds on: DC algorithm (DCA) SDCA (Le Thi et al. 2022) S(p)DCA (Le Thi et al. 2024) Hömander's formula / support function analysis
Closest papers by meaning
- Anytime Online-to-Batch, Optimism and Acceleration (ICML 2019 · similarity 0.89)
- Approximation Guarantees for Adaptive Sampling (ICML 2018 · similarity 0.89)
- Fast Rate Analysis of Some Stochastic Optimization Algorithms (ICML 2016 · similarity 0.88)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.88)
- Stochastic Optimization with Arbitrary Recurrent Data Sampling (ICML 2024 · similarity 0.88)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (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.