Convex Optimization for Big Data

Abstract

This article reviews recent advances in convex optimization algorithms for Big Data, which aim to reduce the computational, storage, and communications bottlenecks. We provide an overview of this emerging field, describe contemporary approximation techniques like first-order methods and randomization for scalability, and survey the important role of parallel and distributed computation. The new Big Data algorithms are based on surprisingly simple principles and attain staggering accelerations even on classical problems.

23 pages, 4 figurs, 8 algorithms

References in corpus (10)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• The Convex Geometry of Linear Inverse Problems
• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• A Proximal Decomposition Method for Solving Convex Variational Inverse Problems
• Computational and Statistical Tradeoffs via Convex Relaxation
• Composite Self-Concordant Minimization
• Convexity in source separation: Models, geometry, and algorithms

Cited by in corpus (57)

• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• Linked Component Analysis from Matrices to High Order Tensors: Applications to Biomedical Data
• ADD-OPT: Accelerated Distributed Directed Optimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Decentralized Quasi-Newton Methods
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
• Distributed Discrete-time Optimization in Multi-agent Networks Using only Sign of Relative State
• Optimization and Learning with Information Streams: Time-varying Algorithms and Applications
• Proximity Without Consensus in Online Multi-Agent Optimization
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems
• Adaptive Restart of the Optimized Gradient Method for Convex Optimization
• On the convergence analysis of the optimized gradient method
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Randomized Subspace Newton Convex Method Applied to Data-Driven Sensor Selection Problem
• On the Linear Convergence of Distributed Optimization over Directed Graphs
• A Universal Primal-Dual Convex Optimization Framework
• Network Newton-Part II: Convergence Rate and Implementation
• A Framework for Parallel and Distributed Training of Neural Networks
• Network Newton-Part I: Algorithm and Convergence
• Universal gradient descent
• Randomized Group-Greedy Method for Large-Scale Sensor Selection Problems
• Proximal Gradient Algorithms: Applications in Signal Processing
• Local and Global Convergence of a General Inertial Proximal Splitting Scheme
• Bayesian computation: a perspective on the current state, and sampling backwards and forwards
• Distributed Proximal Splitting Algorithms with Rates and Acceleration
• The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
• Cover Tree Compressed Sensing for Fast MR Fingerprint Recovery
• Classical simulation of boson sampling with sparse output
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• A Scalable and Distributed Solution to the Inertial Motion Capture Problem
• Online Sparse Subspace Clustering
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Geometric Convergence for Distributed Optimization with Barzilai-Borwein Step Sizes
• A Simple Adaptive Step-size Choice for Iterative Optimization Methods
• ParMAC: distributed optimisation of nested functions, with application to learning binary autoencoders
• Distributed Subgradient Projection Algorithm over Directed Graphs
• Decentralized RLS with Data-Adaptive Censoring for Regressions over Large-Scale Networks
• Linear convergence in optimization over directed graphs with row-stochastic matrices
• Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs
• Parallel Computing for Copula Parameter Estimation with Big Data: A Simulation Study
• Dual Smoothing and Level Set Techniques for Variational Matrix Decomposition
• Adaptive Stochastic Gradient Descent on the Grassmannian for Robust Low-Rank Subspace Recovery and Clustering
• Distributed Resource Allocation Over Random Networks Based on Stochastic Approximation
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Inexact Gradient Projection and Fast Data Driven Compressed Sensing
• Gradient-Free Multi-Agent Nonconvex Nonsmooth Optimization
• Parallel Stochastic Optimization Framework for Large-Scale Non-Convex Stochastic Problems
• A core-set approach for distributed quadratic programming in big-data classification
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• Fast Greedy Approaches for Compressive Sensing of Large-Scale Signals