CS Paper Radar

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

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

cs.AI math.OCcs.LG ·submitted 2026-08-31 05:29 UTC · v3

Abstract

We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of $\widetilde O(\sqrt{T})$. Over $T$ rounds, each agent uses $T$ neighbor-mixing steps and $\widetilde O(T)$ separation-oracle calls. We give wrapper instantiations covering four up-concave or DR-submodular maximization problems.

Closest papers

Nearest neighbours by meaning across the whole index.

Decentralized Online Exp-Concave Optimization

cs.LG ·2026-10-18 ·Hao Qiu, Mengxiao Zhang, Yuanyu Wan
theory similarity 0.66
Abstract

Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of $O\left(Nd(1-σ_2)^{-1/2}\,\log^2(T) \right)$ where $N$ is the number of agents, $d$ is the dimension, $T$ is the horizon, and $1-σ_2$ represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of $Ω\left(Nd (1-σ_2)^{-1/2}\,\log(T/N) \right)$ showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded and features and labels are locally observed. By gossiping covariance and label-feature statistics, we also achieve logarithmic regret.

0.12

Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

cs.LG cs.AIcs.CCstat.ML ·2026-09-02 ·Vaneet Aggarwal, Yiyang Lu
theory similarity 0.66
Abstract

We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has $O(T^{3/4})$ regret and uses $O(dT^{1/4})$ oracle calls per round. More generally, for every $δ\in[0,1/4]$, batching gives $O(T^δ)$ calls per round and $O(T^{4/5-δ/5})$ regret, including a one-call $O(T^{4/5})$ endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with $O(T^{5/6})$ one-point bandit regret.

0.10

Group Distributionally Robust Optimization over Decentralized Networks

cs.LG math.OC ·2026-10-21 ·Haomin Bai, Junyan Sun, Quan Cheng, Yuanyu Wan, Lijun Zhang
similarity 0.66
Abstract

We study group distributionally robust optimization (GDRO) over decentralized networks, where workers collaborate to learn robust models by minimizing the maximum local risk. Existing methods optimize only dual-regularized surrogates and establish guarantees for a globally averaged model that is not available to workers. In this paper, we directly optimize the original GDRO objective and establish guarantees for local models in semi-decentralized (SemiDec) and fully decentralized (Dec) settings. A key difficulty is that applying the primal-dual decomposition from centralized GDRO yields worker-dependent losses whose evaluation requires unavailable cross-worker information. To address this challenge, we develop a novel error decomposition that recasts decentralized GDRO as (i) a decentralized online convex optimization (D-OCO) problem and a prediction-with-expert-advice problem in SemiDec, and as (ii) two coupled D-OCO problems in Dec, with discrepancy terms capturing inconsistencies among local decisions. By isolating consensus errors in analysis, we develop modular frameworks that support different consensus routines. We then establish the \emph{first} per-worker convergence guarantees for optimizing the original GDRO objective over decentralized networks. Instantiations with accelerated gossip and Choco-gossip achieve an $O(\sqrt{(\log m)/T})$ convergence rate over $T$ update rounds, while experiments demonstrate improved worst-worker performance over baselines.

0.36

0.4633-Approximation for Online and Offline on-Monotone DR-Submodular Maximization

cs.DS ·2026-10-15 ·Vaneet Aggarwal, Donglei Du
similarity 0.65
Abstract

We obtain the approximation coefficient $α_0=54440750000/117486474169>0.463378$ for maximizing nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the unit cube, with queries allowed throughout the cube. This improves the previous best coefficient, $4/9$. A coordinatewise map, exponential on small coordinates and linear-fractional on large ones, turns the learner's state, a feasible point, into a feasible action whose value is at least $α_0$ times that of any feasible point, up to a linear term. The proof is analytical and reduces to one-dimensional inequalities. The linear term has an unbiased estimator from one noisy-gradient query, so online maximization reduces to linear learning. Under a uniform bound on the gradients, the expected approximate regret is $O(\sqrt T)$ with projected ascent and $O(T^{3/4})$ with one linear-maximization call per round; with one noisy value per round, it is $O(T^{3/4})$ and $O(T^{7/8})$. Online-to-batch conversion gives offline guarantees. With exact values and gradients, contracting the objective toward a feasible interior point yields an expected $(α_0-\varepsilon)$-approximation for every nonnegative $C^1$ DR-submodular objective, with oracle counts polynomial in $n$ and $\varepsilon^{-1}$ and no gradient or smoothness parameter. Sampling and standard rounding give $(α_0-\varepsilon)$-approximation for submodular set functions under one matroid or a fixed number of knapsack constraints.

0.38

Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback

cs.LG cs.DSstat.ML ·2026-10-12 ·Tao Hu, Rohan Ghuge
similarity 0.65
Abstract · 68 pages, 20 figures, 1 table

Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is $\widetilde O(n\sqrt T)$, where $n$ is the number of variables and $T$ the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve $\widetilde O(\sqrt{nT})$ using problem-specific algorithms. \emph{Can a general online-to-offline reduction achieve this improved rate?} We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves $\widetilde O(\sqrt{nT})$ expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for $T\ge n$, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves $\widetilde O(n^{3/4}\sqrt T)$ expected approximation regret, improving the previous linear dependence on $n$. The exponent $3/4$ is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-$K$ selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.

0.39

Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization

cs.LG ·2026-09-30 ·Vaneet Aggarwal, Yiyang Lu
theory similarity 0.64
Abstract

We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets $K\subseteq[0,1]^d$ that contain a supplied diagonal point $ζ\mathbf{1}$. Our online algorithm earns at least $\underlineα(ζ)=\frac{1}{2}-\frac{(1-2ζ)_+^2}{2(3-2ζ)^2}$ times the reward of the best fixed feasible point, minus $O(\sqrt{T})$, using one possibly stochastic gradient query and one projection per round; $\underlineα(0)=4/9$. One post-decision noisy value query per round gives $O(T^{3/4})$ regret, and two exact value queries give $O(\sqrt{T})$. Conversely, no offline algorithm with polynomially many exact value-and-gradient queries attains a coefficient above an explicit $β_*\approx 0.4704$ at $ζ=0$, improving the bound $2(e^{-1/2}-e^{-1})\approx 0.478$ of Oveis Gharan and Vondrák (2011); for $ζ>0$, two families of hard instances give an upper bound that we reduce exactly to finitely many convex problems below $ζ=1/8$ and give in closed form above it. The bound $β_*$ also holds for nonnegative submodular set functions under a cardinality constraint, improving the previous $0.478$. Online-to-offline conversion gives $\underlineα(ζ)-\varepsilon$ offline, and the upper bound also limits online learners with polynomial query budgets and uniform $O(T^κ)$ regret, $κ<1$. Both coefficients equal $1/2$ for $ζ\ge 1/2$ and fall short of $1/2$ by order $(1/2-ζ)^2$ below. For quadratic objectives we attain $1/2$, and for cubic objectives $\max\{8/17,\,2\sqrt{3-4r}/(1+\sqrt{3-4r})^2\}$ with $r=\min\{ζ,1/2\}$. For submodular set functions, rounding the multilinear extension gives $\underlineα(ζ)-\varepsilon$ under a matroid whose polytope contains $ζ\mathbf{1}$ and $4/9-\varepsilon$ under a fixed number of knapsack constraints.

0.26

KKT-Perturbation-Aware Communication for Fully Distributed Online Convex Optimization with Nonseparable Coupling

cs.LG ·2026-11-09 ·Zhaoye Pan, Tao Li, Yunjie Guo, Guanpu Chen
similarity 0.62
Abstract

Nonseparable costs and coupled constraints in distributed online convex optimization often arise when system performance and operational constraints depend on the joint configuration of all agents and cannot be decomposed into individual contributions. Such nonseparability leads to fully distributed decision-making with challenging partial local information, where each agent evaluates its local primal-dual update using estimated global information via a local belief of the joint action and the shared Lagrange multiplier to be exchanged with neighbors. While the belief consensus established by prior works ensures no-regret learning, exchanging beliefs comprising full-dimensional primal and dual states at every round imposes a communication overhead that scales with both the joint decision dimension and the network size. Existing event-triggered schemes typically activate communication according to state variation or consensus error. Under nonseparable coupling, however, errors of equal magnitude can produce markedly different perturbations after passing through the KKT operator. We therefore propose a randomized KKT-perturbation-aware communication mechanism, where the triggering of each agent's primal and dual communication channels depends on their impact on the KKT operator. The proposed mechanism transfers the adaptive-sampling principle of coordinate descent from allocating computation across decision blocks to allocating communication across information channels: channels with larger estimated perturbations receive greater priority for refresh. Under standard regularity assumptions, the resulting algorithm achieves $O({T}^{2/3})$ expected static regret and $O({T}^{2/3})$ expected cumulative constraint violation. Numerical experiments demonstrate improved learning and constraint-enforcement performance per transmitted bit over belief consensus baselines.

0.19

Personalized Projected Ascent for Federated Stackelberg Optimization

cs.LG ·2026-10-15 ·M Yashwanth, Sharannya Ghosh, Saikiran Bulusu, Anirban Chakraborty
similarity 0.62
Abstract

Federated minimax problems, such as distributionally robust optimization and adversarial training, include an inner maximization variable built from each client's local data. These variables differ in meaning and dimension from one client to the next, so averaging them across clients, as standard federated minimax methods do, is ill-posed. We therefore study a federated minimax problem where the minimization variable $\mathbf{x}$ is shared and aggregated, while each client retains the maximization variable $\mathbf{y}_i$ (personalized). Because these applications constrain $\mathbf{y}_i$ to a compact convex set, we analyze projected ascent directly. We show that, in the nonconvex-concave regime, this projected personalized scheme attains the standard sublinear rate. In the nonconvex-PL regime, however, it hits a stepsize-invariant noise floor due to stochastic $\mathbf{y}_i$ updates. To mitigate this, we propose VR-SGDA, incorporating a variance-reduced ascent step where each client maintains a private variable snapshot. By evaluating current and snapshot gradients on the same sample, the constant variance is replaced by a vanishing drift under a two-timescale regime. VR-SGDA eliminates the noise floor, attaining sublinear leading rates while preserving personalization and projection. Experiments on subpopulation-robustness and NLP adversarial training confirm both the worst-group robustness benefits and the two-timescale tracking mechanism.

0.13