Research map / Optimization / Nonconvex and smooth optimization
Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization
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 projection-free iteratively regularized conditional gradient methods (IR-SCG for one-sample stochastic, IR-FSCG for finite-sum) for simple bilevel problems that use linear optimization only over the base set, with STORM/SPIDER gradient estimators and anytime convergence guarantees.
Problem
Stochastic simple bilevel optimization: minimize an outer stochastic objective over the solution set of a convex stochastic inner problem, where projections or linear optimization over the optimal set are unavailable and existing projection-free methods need halfspace-intersection oracles.
Approach
Iteratively regularized conditional gradient on the blended objective sigma_t F + G with decreasing sigma_t, using only linear minimization over the base set X, with STORM (one-sample) or SPIDER (finite-sum) variance-reduced gradient estimators, and a weighted averaging iterate z_t.
Key results
- Under convex outer objective, one-sample IR-SCG achieves Õ(t^{-1/4}) rates for both outer and inner objectives; finite-sum IR-FSCG achieves Õ(t^{-1/2}).
- Nonconvex outer objective: Õ(t^{-1/7}) one-sample and Õ(t^{-1/4}) finite-sum rates.
- In over-parameterized regression and dictionary learning experiments, IR-SCG and IR-FSCG outperform SBCGI, SBCGF, aR-IP-SeG and SDBGD in time-limited runs and complete more iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Projection-free IR-SCG (linear oracle only over X) instead of SBCGI baseline | stochastic simple bilevel regression/dictionary learning · Over-parameterized regression and dictionary learning | iterations within fixed time budget | Helped |
| Mini-batch finite-sum IR-FSCG vs single-sample IR-SCG in outer-level accuracy | over-parameterized regression · Over-parameterized regression | outer-level optimality gap | Helped |
| Proposed methods vs existing baselines (SBCGI, SBCGF, aR-IP-SeG, SDBGD) | stochastic simple bilevel problems · Over-parameterized regression and dictionary learning | inner and outer optimality gap over time | Helped |
| Adopt aR-IP-SeG and SDBGD (projection-based) instead of linear oracle | over-parameterized regression · Over-parameterized regression | outer-level optimality gap progress | No clear effect |
| Baseline SBCGI and SBCGF inner-level gap over time | SBCGI, SBCGF baselines · Over-parameterized regression and dictionary learning | inner-level optimality gap | Hurt |
Surprising findings
- SBCGI and SBCGF show degradation in inner-level optimality gap over time, consistent with their weaker guarantees.
Limitations
- Convergence rates are slower than the best known rates of halfspace-based methods (e.g., Õ(t^{-1/2}) vs Õ(t^{-1/2})-ish comparisons are weaker in the convex finite-sum case, e.g. O(t^{-1} log t) of prior work).
- Nonconvex outer rates (t^{-1/7} one-sample) are slower than prior work's t^{-1/3}-type rate in the nonconvex setting.
- Results assume compact convex X, smoothness and sub-Gaussian noise; experiments limited to two synthetic/small-scale tasks.
Experimental setup
Datasets: Wikipedia Math Essential dataset synthetic dictionary learning dataset
Benchmarks: over-parameterized regression (Wikipedia Math Essential) dictionary learning (synthetic)
Metrics: inner-level optimality gap outer-level objective gap number of iterations and oracle calls within time budget
Baselines: SBCGI SBCGF aR-IP-SeG SDBGD
Builds on: Frank-Wolfe / conditional gradient STORM SPIDER iterative regularization for simple bilevel problems
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.93)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.92)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.92)
- Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization (NeurIPS 2026 · similarity 0.92)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.91)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.91)
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.