TL;DR
This paper introduces a novel online learning algorithm that efficiently handles complex, non-convex data models by exploiting their "per-block-convexity." The algorithm achieves provably quadratic convergence rates with linear computational complexity, outperforming existing methods for streaming data analytics.
What Problem Does This Paper Address?
Many real-world applications, such as dictionary learning, non-negative matrix factorization, and subspace clustering, involve optimizing non-convex functions. These functions can be challenging to handle, especially in online settings where data arrives sequentially and computational resources are limited. Traditional methods often struggle with either the non-convexity or the online nature of the problem. Specifically, existing block coordinate descent methods require exact per-block minimization, which can be computationally expensive. Alternating direction methods of multipliers (ADMM) offer an alternative but typically exhibit sublinear convergence for convex problems, with limited results for non-convex scenarios. This paper aims to bridge this gap by developing an efficient, online, and theoretically sound algorithm for a broad class of per-block-convex, non-smooth optimization problems.
Methods
The core of this work is an accelerated stochastic approximation (SA) algorithm designed for per-block-convex optimization. The algorithm leverages the idea that while the overall cost function might be non-convex, it becomes convex when all but one block of variables are held fixed. The proposed method iteratively updates these blocks using first-order (sub)gradient information.
Key methodological contributions include:
- Per-Block-Convexity Exploitation: The algorithm is specifically designed to exploit the property that the cost function is convex with respect to each block of variables individually, even if it's non-convex overall.
- Stochastic Approximation: It operates in an online fashion, processing data sequentially without needing to store the entire dataset. This is crucial for streaming data applications.
- First-Order Acceleration: Instead of requiring exact per-block minimizers (which can be costly), the algorithm uses accelerated first-order methods. This significantly reduces computational complexity per iteration.
- Modular Design: The algorithm is presented in a modular way, allowing for flexibility in handling different types of cost functions and regularizers.
- Theoretical Guarantees: The paper provides rigorous theoretical analysis, proving that the expected cost converges quadratically to an accumulation point of the per-block minima, and that subgradients vanish in a mean-squared sense.
Datasets
The paper evaluates the proposed algorithm on two main types of data:
- Synthetic Data: Used to test a robust linear regression model based on the Total Least-Squares (TLS) criterion.
- Real Data: Network-wide link load data from the Internet2 measurement archive is used to evaluate a semi-supervised dictionary learning approach for tracking and imputing missing entries.
Key Insights and Ideas
- Per-Block-Convexity is a Powerful Structure: The paper demonstrates that even if a function is globally non-convex, its per-block-convexity can be effectively exploited for efficient optimization, especially in an online setting.
- Acceleration for Online Learning: Adapting offline acceleration techniques to the online stochastic approximation paradigm is a significant advancement, leading to faster convergence than standard SA methods.
- Linear Complexity is Achievable: The proposed algorithm achieves computational complexity that scales linearly with the number of unknowns, making it practical for large-scale problems.
- No Need for Exact Per-Block Minimization: This is a crucial insight that distinguishes the proposed method from traditional block coordinate descent, enabling faster iterations.
- Robustness to Unknown Data Statistics: The algorithm does not require knowledge of the underlying data distribution, making it broadly applicable.
Key Results
- Quadratic Convergence Rate: The expected cost is proven to converge to an accumulation point of the per-block minima with a quadratic rate.
- Linear Computational Complexity: The algorithm's computational cost per iteration scales linearly with the number of unknown variables.
- Superior Performance: Numerical tests show that the proposed algorithm outperforms block coordinate descent (BCD) and is comparable to, yet computationally lighter than, ADMM-based methods.
- Effective in Real-World Scenarios: The algorithm demonstrates strong performance on both synthetic (robust linear regression) and real-world (network link load imputation) datasets. For the Internet2 link load tracking, the proposed method achieved a mean normalized estimation error of 0.1166, comparable to a state-of-the-art ADMM-based method.
Limitations and Future Work
- Assumptions: The theoretical guarantees rely on several assumptions, including stationarity of expectations, coercivity, and boundedness of certain quantities. While these are common in SA literature, their practical implications in specific applications might need further investigation.
- Extension to Parallel/Random Block Updates: The authors suggest future work to extend the framework from Gauss-Seidel strategies of visiting blocks to parallel and random ones.
- Data Non-Stationarity: Investigating the effect of data non-stationarities by developing a regret analysis for the per-block convex loss is proposed as a future direction.
Summary updated