Frameworks for High Dimensional Convex Optimization

London, 2020

Category: Optimization

Overall Rating

3.1/5 (22/35 pts)

The paper's primary contribution with potential for modern impact is the LOCO framework (Chapter 3), which uniquely applies theoretical Local Computation Algorithms (LCAs) to distributed convex optimization.
Instead of focusing on global consensus, LOCO enables agents to solve small, local problems defined by the sparsity structure of the constraint matrix, requiring minimal communication.
This distinct paradigm could inspire novel research in areas like Edge AI...
...but its practical implementation challenges (e.g., the reliance on specific random rankings) and the potential for more specialized post-2020 methods to offer better practical trade-offs mean it's not a high-priority pursuit...

The thesis's most promising contribution for fueling modern, unconventional research lies in Chapter 3, "Distributed Algorithm with Logarithmic Communication Complexity" (LOCO).
The core idea is the application of Local Computation Algorithms (LCAs) from theoretical computer science to distributed optimization problems, specifically in multi-agent systems.
This differs significantly from current Federated Learning by abandoning the goal of a single, collaboratively trained global model state.
This could unlock training/adaptation of truly massive models on resource-constrained, privacy-sensitive edge devices where current Federated Learning approaches are too communication-heavy or still require sharing too much information about the global model structure.

While the thesis tackles highly relevant problems... a skeptical review reveals several potential limitations and areas where the work may have been surpassed or is based on assumptions that limit its broader impact today.
The LOCO framework relies on generating a "random ordering" r of constraints which, as noted by the author citing [7, 169], "in practice... does not exist."
The theoretical guarantees for the sketched IPM (Theorem 27) are probabilistic (at least 0.9 probability), which is often less appealing than deterministic guarantees in some application domains...
Since 2020, research has likely produced highly specialized methods for specific problems tackled here... that might outperform these more generic "frameworks" by leveraging domain-specific structure more effectively.

Watch