Research map / Optimization / Distributed and compressed
Safe-EF: Error Feedback for Non-smooth Constrained 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.
Establishes lower complexity bounds for contractive-compressed first-order methods on non-smooth constrained convex problems and proposes Safe-EF, an EF14-based method with constraint-driven subgradient switching that matches the bound, extended to stochastic and humanoid-robot RL experiments.
Problem
Error feedback and contractive (e.g., Top-K) compression fail or are unproven for non-smooth convex objectives with safety constraints in distributed/federated optimization, and no provably convergent compressed method existed for such constrained non-smooth problems.
Approach
Safe-EF uses EF14-type error feedback on subgradients with a switching rule that uses the objective subgradient when the constraint violation is below a threshold c and the constraint subgradient otherwise, plus EF21-P server-to-worker compression; the paper proves a matching lower bound and that EF21 diverges on a simple non-smooth example.
Key results
- Top-K Safe-EF reaches the fixed performance J_r=7500 with roughly 2000x less communication than uncompressed CGD in the humanoid experiment.
- EF21 diverges and EF14 violates the constraint in the humanoid experiment, while Safe-EF satisfies the constraint with slight performance loss.
- Safe-EF attains O(RM/sqrt(delta_s delta T)) convergence for objective and constraint, matching the proved lower bound up to constants under unidirectional compression.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Safe-EF with Top-K compression instead of constrained CGD | Humanoid Robot Fleet · Humanoid Robot Fleet | communication required to reach \hat{J}_r = 7500: about 2000× improvement in communication reduction | Helped |
| Use Safe-EF with Rand-K compression instead of constrained CGD | Humanoid Robot Fleet · Humanoid Robot Fleet | communication required to reach \hat{J}_r = 7500 | Helped |
| Use Safe-EF instead of EF14 | Humanoid Robot Fleet · Humanoid Robot Fleet | constraint satisfaction | Helped |
| Use Safe-EF instead of EF21 | Humanoid Robot Fleet · Humanoid Robot Fleet | convergence | Helped |
| Use Safe-EF instead of Parallel-CRPO at the same communication budget | Humanoid Robot Fleet · Humanoid Robot Fleet | convergence | Helped |
| Use Safe-EF instead of other tested methods | Synthetic non-smooth problem · Synthetic data, s ∈ {0.1, 1.0} | convergence speed | Helped |
| Use Safe-EF instead of EControl | Synthetic non-smooth problem · Synthetic data, s = 10.0 | function value over training | Mixed |
| Increase the number of workers (ablation) | Safe-EF · Humanoid Robot Fleet | convergence performance | Helped |
| Increase the number of workers beyond a certain threshold (ablation) | Safe-EF · Humanoid Robot Fleet | convergence performance | No clear effect |
| Increase constraint-evaluation batch size from 1024 to 2048 (ablation) | Safe-EF · Humanoid Robot Fleet | convergence: 1024 to 2048 | Helped |
| Increase constraint-evaluation batch size from 2048 to 4096 (ablation) | Safe-EF · Humanoid Robot Fleet | convergence: 2048 to 4096 | No clear effect |
| Use constraint-evaluation batch size 256 or 512 (ablation) | Safe-EF · Humanoid Robot Fleet | convergence | Hurt |
Surprising findings
- EF21 fails to converge on the simple non-smooth function ||x||_1 with Top-1 compression, even though it works in smooth settings, and diverges with rate growing with T.
- Vanilla compressed gradient descent with Top-1 makes no progress on ||x||_1 regardless of stepsize.
Limitations
- Analysis assumes convexity of all functions, while experiments are on non-convex RL tasks.
- Stochastic setting requires large batch sizes and has suboptimal sample complexity O(1/eps^4); small batches did not converge.
- Bidirectional compression rate degrades by sqrt(delta_s delta), an open question for improvement.
Experimental setup
Datasets: synthetic non-smooth least-absolute-deviation problems simulated humanoid robot CMDP trajectories
Benchmarks: humanoid robot CMDP (objective J_r and constraint J_c) synthetic non-smooth L1 problem
Metrics: objective value constraint violation communication in gigabytes per worker
Baselines: CGD EF21 EF21M EControl EF14 Parallel-CRPO
Builds on: EF14 EF21 EF21-P PPO CRPO
Closest papers by meaning
- EFSkip: A New Error Feedback with Linear Speedup for Compressed Federated Learning with Arbitrary Data Heterogeneity (AAAI 2025 · similarity 0.88)
- Tight analyses of first-order methods with error feedback (NeurIPS 2025 · similarity 0.88)
- Error Feedback Reloaded: From Quadratic to Arithmetic Mean of Smoothness Constants (ICLR 2024 · similarity 0.87)
- EControl: Fast Distributed Optimization with Compression and Error Control (ICLR 2024 · similarity 0.85)
- Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold (ICML 2025 · similarity 0.85)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.85)
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.