Research map / Bandits and online learning / Online convex optimization and games
Designing smoothing functions for improved worst-case competitive ratio in online optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add a regularization/smoothing (optimal smoothing for separable psi on positive orthant) to the greedy primal-dual algorithm instead of unsmoothed psi | Adwords (simultaneous algorithm) · Adwords | competitive ratio: from 1/2 to 1 - 1/e | Helped |
| Optimal smoothing of separable psi for sequential algorithm via convex problem (12) with parameter c | Sequential algorithm (Algorithm 1) on adwords · Adwords with bound c | competitive ratio | Helped |
| Replace Nesterov smoothing with optimal smoothing from convex program (10) for piecewise linear psi | Simultaneous algorithm, psi=min(.75,u,.5u+.25) · Simulated n=m, min competitive ratio over permutations, m from 1 to 30 | competitive ratio | Helped |
| Unsmoothed psi (greedy with no smoothing) for adwords with small bid-to-budget ratio | Sequential algorithm (Algorithm 1) on adwords · Adwords | competitive ratio | No clear effect |
Closest papers by meaning
- Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization (NeurIPS 2019 · similarity 0.91)
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.87)
- Fairness-Regularized Online Optimization with Switching Costs (NeurIPS 2025 · similarity 0.87)
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search (ICML 2025 · similarity 0.86)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · similarity 0.86)
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.86)
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.