Papers › Multi-Step Stochastic ADMM in High Dimensions: Applications to Sparse Optimization and...
Multi-Step Stochastic ADMM in High Dimensions: Applications to Sparse Optimization and Noisy Matrix Decomposition
Hanie Sedghi, Anima Anandkumar, Edmond Jonckheere
We propose an efficient ADMM method with guarantees for high-dimensional problems. We provide explicit bounds for the sparse optimization problem and the noisy matrix decomposition problem. For sparse optimization, we establish that the modified ADMM method has an optimal convergence rate of 𝒪(slogd/T), where s is the sparsity level, d is the data dimension and T is the number of steps. This matches with the minimax lower bounds for sparse estimation. For matrix decomposition into sparse and low rank components, we provide the first guarantees for any online method, and prove a convergence rate of 𝒪̃((s+r)β²(p) /T) + 𝒪(1/p) for a p×p matrix, where s is the sparsity level, r is the rank and Θ(√(p))≤β(p)≤Θ(p). Our guarantees match the minimax lower bound with respect to s,r and T. In addition, we match the minimax lower bound with respect to the matrix dimension p, i.e. β(p)=Θ(√(p)), for many important statistical models including the independent noise model, the linear Bayesian network and the latent Gaussian graphical model under some conditions. Our ADMM method is based on epoch-based annealing and consists of inexpensive steps which involve projections on to simple norm balls. Experiments show that for both sparse optimization and matrix decomposition problems, our algorithm outperforms the state-of-the-art methods. In particular, we reach higher accuracy with same time complexity.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections