Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization

What the math gives to ML

The paper's transferable contribution is a decentralized online optimizer that keeps each worker's communication state in dual space, rather than repeatedly exchanging model parameters or full historical gradients. Barrier-FTRL combines cumulative surrogate gradients with a self-concordant barrier, producing feasible iterates even when the action set is accessed only through separation queries; approximate Newton solves make the update computationally practical. For neural networks, the most direct test is a constrained federated optimizer for simplex, box, or norm-bounded parameters, where local clients mix dual gradient states and solve a barrier-regularized proximal subproblem. The expected benefit is improved stability under heterogeneous client objectives and exact feasibility without projection clipping.