PaperlayerView exact revision on arXiv

Source-linked AI summary

Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

Mohammad Pedramfar, Yididiya Y. Nadew, Christopher J. Quinn, Vaneet Aggarwal

arXiv:2403.10063v2cs.LGcs.AIcs.CCmath.OC

TL;DR

Adversarial continuous DR-submodular optimization involves varied objective, constraint, feedback, and oracle settings, while most prior research focused on monotone objectives and/or full-information stochastic-gradient feedback. The paper proposes unified projection-free Frank-Wolfe algorithms spanning monotone and non-monotone objectives, convex feasible sets, and full-information, semi-bandit, or bandit feedback. For non-monotone DR-submodular functions, the algorithms achieve the best (in some cases the first) sublinear α-regret bounds across all feedback models and feasible region geometries considered.

  • Problem

    Adversarial continuous DR-submodular optimization involves varied objective, constraint, feedback, and oracle settings, while most prior research focused on monotone objectives and/or full-information stochastic-gradient feedback.

    Source: §1 · p. 1

  • Method

    The paper proposes unified projection-free Frank-Wolfe algorithms spanning monotone and non-monotone objectives, convex feasible sets, and full-information, semi-bandit, or bandit feedback.

    Source: §1 · pp. 2–3

  • Results

    For non-monotone DR-submodular functions, the algorithms achieve the best (in some cases the first) sublinear α-regret bounds across all feedback models and feasible region geometries considered.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Because projection-free methods rely on linear optimization rather than potentially expensive projections, their bounds may be practically relevant when per-round computational resources are limited.

    Source: §1 · p. 2

    The smoothing trick limits gradient estimation to a smaller domain than the full feasible set.

    Source: §4 · p. 8

Abstract

from arXiv · show

This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $\alpha$-regret bounds or have better $\alpha$-regret bounds than the state of the art, where $\alpha$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $\alpha$-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area.

1 INTRODUCTION

Adversarial continuous DR-submodular optimization spans varied functions, constraints, feedback, and oracle types, while prior research has focused mainly on monotone objectives and/or full-information stochastic-gradient feedback. The paper develops unified projection-free Frank-Wolfe algorithms and improves α-regret guarantees across the considered settings.

1 INTRODUCTION

  • Projection-free methods use linear optimization rather than potentially costly projections, making their regret bounds relevant when per-round computational resources are limited.The paper cites matrix completion, routing, graph problems, and matroid polytopes as settings where linear optimization can be efficient while projections are expensive.Source: §1 · p. 2
  • The unified Frank-Wolfe framework covers monotone and non-monotone objectives, varied convex feasible sets, and full-information, semi-bandit, or bandit feedback with gradient or value queries.It provides the first projection-free algorithm for monotone maximization over general convex sets for any feedback and oracle type.Source: §1 · pp. 2–3
  • For non-monotone functions, the algorithms attain the best, and sometimes the first, sublinear α-regret bounds across all settings considered, improving prior bounds in nearly every combination.The reported exception is general convex sets with full-information feedback of T^1/2 gradients, where the regret bounds match.Source: §1 · pp. 2–3
  • Among projection-free methods for monotone functions, the algorithms achieve state-of-the-art α-regret bounds in 7 of 8 cases and match the remaining result.Across all algorithms, they achieve state-of-the-art bounds in 4 of 8 cases; they also obtain first sublinear regret for two general-convex-set settings.Source: §1 · pp. 2–3
  • Technical novelties include combining meta-actions with random permutations for full information and handling stochastic feedback without variance reduction such as momentum.The paper also describes a unified approach that specializes to multiple scenarios.Source: §1 · p. 3

2 BACKGROUND AND NOTATION

The section establishes notation for continuous DR-submodular optimization and formulates adversarial online optimization with several feedback models. It also states regularity assumptions and frames the objective as minimizing α-regret relative to offline approximation guarantees.

2 BACKGROUND AND NOTATION

  • The feasible region is a bounded convex set K ⊆ [0, 1]^d; downward-closed sets are assumed to contain the origin unless stated otherwise.The section also defines the diameter of K and vector-order notation.Source: §2 · p. 4

2.1 PROBLEM SETUP

  • The adversary chooses the reward-function sequence before the optimizer acts, and α-regret is the objective, with α denoting an offline approximation ratio.The setup assumes an oblivious adversary and notes that offline DR-submodular maximization is NP-hard.Source: §2.1 · pp. 4–5
  • The objective functions are assumed to be differentiable, nonnegative, bounded, Lipschitz, smooth, and DR-submodular, with bounded value or gradient oracles.The algorithms need not know the regularity and oracle-bound constants in advance, though those constants appear in regret bounds.Source: §2.1 · p. 5
  • Feedback ranges from full-information stochastic gradient or value queries to semi-bandit gradient samples and noisy bandit value samples.Full-information queries may be made at multiple points; semi-bandit and bandit feedback reveal information at the chosen action.Source: §2.1 · p. 5

3 PROPOSED ALGORITHMS

The proposed algorithms are organized around four problem divisions and several feedback scenarios. The full-information section identifies four main ideas used by Algorithm 1 to obtain the desired regret bounds.

3 PROPOSED ALGORITHMS

  • The algorithm framework divides the problem into four cases, with different approximation ratios and corresponding changes to algorithm steps and proofs.The listed cases include non-monotone functions on downward-closed sets, monotone functions on general convex sets, and non-monotone functions on general convex sets.Source: §3 · p. 6
  • The proposed algorithms are described across different feedback scenarios.The passage identifies feedback scenarios as an organizing axis for the algorithm subsections.Source: §3 · pp. 5–6

3.1 FULL INFORMATION

  • Algorithm 1 uses four main ideas to obtain the desired regret bounds.The supplied passage does not specify those ideas.Source: §3.1 · p. 6

1. Offline bounds

The offline-bound argument relates approximation loss after Frank-Wolfe updates to a known term and accumulated linear-oracle discrepancies. The section also links the argument to prior methods and describes random permutations within blocks.

1. Offline bounds

  • For any comparator x* in K, αF(x*) − F(x(K+1)) is bounded above by a known term plus accumulated linear combinations of oracle-advantage inner products.The inequality is stated for a sequence of vectors in K and points generated by repeated updates.Source: §1 · p. 6
  • The algorithm partitions the horizon into blocks and uses a random permutation of the rounds within each block.The supplied algorithm fragment specifies block size L, horizon T, and Q = T/L blocks.Source: §1 · p. 6
  • The lemma is described as a reformulation of ideas from earlier DR-submodular maximization work.The passage names Bian et al., Zhang et al., Du, Mualem and Feldman, and Pedramfar et al.Source: §1 · p. 6

2. Meta actions

The meta-actions approach runs online linear optimization instances to mimic iterations of an offline Frank-Wolfe algorithm. Each instance receives a linear reward after the function is revealed, while its guarantee is expressed through a regret function.

2. Meta actions

  • The algorithm runs K online linear optimization instances, with K matching the number of offline Frank-Wolfe iterations it aims to mimic.After the function is revealed, each instance is given a linear reward based on the corresponding linear maximization oracle.Source: §2 · p. 7
  • The method repeats the reward-feeding process for each subsequent function in the online sequence.The passage states that this process, combined with Idea 1, yields the desired α-regret bounds.Source: §2 · p. 7
  • Each online linear optimization oracle is assumed to select a vector before receiving an adversarial vector chosen independently of that selection, and to satisfy a regret guarantee.Follow-the-Perturbed-Leader is given as one possible oracle choice.Source: §2 · p. 7

3. Random permutations

The method groups the function sequence into blocks and uses a random permutation within each block to support gradient estimation with fewer queries. It applies meta-actions to the sequence of block-average functions.

3. Random permutations

  • The horizon is divided into Q = T/L blocks, each of length L, and the method uses K ≤ L exploration steps per block.The section describes online linear maximization oracles on the shrunken set for the blocks.Source: §3 · p. 7
  • A uniformly random permutation of each block makes every function's expected value equal to that block's average, enabling gradient estimates from within-block observations.The meta-action idea is applied to the sequence of block-average functions.Source: §3 · p. 7
  • For each time step, the algorithm identifies the corresponding exploration index in the permutation and queries the associated function before playing the block action.The pseudocode includes value-oracle sampling and querying the corresponding linear maximization oracle.Source: §3 · p. 7

4. Smoothing trick

The smoothing trick supports value-oracle optimization by smoothing the objective and restricting optimization to a shrunken feasible set. In semi-bandit feedback, the algorithm uses exploration steps to gather information and exploits the best action so far in remaining steps.

4. Smoothing trick

  • Because the smoothed function's domain is smaller than the original domain, gradient estimation is limited to a smaller region of the feasible set.The paper introduces a shrunken constraint set to address this concern.Source: §4 · p. 8
  • Value-oracle optimization restricts the problem to a shrunken constraint set and maximizes the smoothed objective there using a one-point gradient estimator.The smoothed function averages values over a sliced ball of radius δ; the smoothing is described as a good approximation with a simple one-point estimator.Source: §4 · p. 8

3.2 (SEMI-)BANDIT FEEDBACK

  • In each semi-bandit block, K exploration steps provide information, while the remaining L − K steps exploit the best action found so far.The exploration actions support analysis similar to the full-information setting.Source: §3.2 · p. 8
  • Figure 2 plots time-averaged regret at T = 500 and cumulative regret across horizons, with solid lines for the methods and dashed or dotted lines for baselines.The caption reports that the methods use fewer queries and computation than baselines with similar regret bounds, or achieve better regret at similar resource use.Source: Figure 2 · p. 9
  • With gradient queries, expected α-regret is O(T^3/4 log(T)^2) in Case (C) and O(T^3/4) otherwise; with value queries, it is O(T^5/6 log(T)^2) in Case (C) and O(T^5/6) otherwise.The stated query complexities are Q = T^1/2 for gradient queries and Q = T^2/3 for value queries.Source: §3.2 · p. 9

5 EXPERIMENTS

The experiments evaluate non-monotone quadratic maximization over randomly generated downward-closed feasible regions. GMFW(β = 1/2) performs best overall while using fewer gradient queries and less computation than the Meta baselines.

5 EXPERIMENTS

  • The experiments test non-monotone quadratic maximization over randomly generated downward-closed feasible regions for three dimension and constraint pairs: (25, 15), (40, 20), and (50, 50).The evaluation includes full-information and semi-bandit gradient feedback.Source: §5 · p. 9
  • The comparisons include ODC, Mono, Meta(β), GMFW(β), and SBFW, with query parameters varied for the full-information methods.Figure 1 depicts regret-bound and query-complexity trade-offs for full-information methods; run-time differences are related in part to the number of linear maximization oracles and per-round queries.Source: §5 · pp. 9–10
  • GMFW(β = 1/2) performs best overall despite using fewer gradient queries and less computation than the Meta algorithms, while GMFW(β = 0) beats Mono at the same feedback level.Figure 2 reports regret across time, averaged over 10 independent runs.Source: §5 · pp. 9–10

REPRODUCIBILITY STATEMENT

The appendix reviews offline and online DR-submodular optimization results and compares online stochastic methods under bandit and semi-bandit feedback. The reproducibility statement identifies available code, assumptions, and proofs.

REPRODUCIBILITY STATEMENT

A.1 OFFLINE DR-SUBMODULAR MAXIMIZATION

  • The paper excludes non-monotone maximization over boxes because discretization methods have not been successfully applied to more general convex sets.Source: §A.1 · p. 14

A.2 ONLINE DR-SUBMODULAR MAXIMIZATION

  • The authors identify moving from deterministic to stochastic oracles as a challenge and report a refined analysis retaining the same order of regret bounds with stochastic feedback.They also report considering noisy semi-bandit feedback for adversarial DR-submodular maximization for the first time.Source: §A.2 · p. 15
  • For the nonadversarial special case, the unified algorithm matches the state of the art among projection-free methods and matches it in 7 of 8 cases when projection-based methods are included.Source: §A.2 · p. 15

B COMPARISON FOR ONLINE STOCHASTIC DR-SUBMODULAR

  • In online stochastic DR-submodular optimization with bandit and semi-bandit feedback, the algorithm matches the state of the art in all cases when compared with projection-free algorithms.The comparison reports a match in 7 of 8 cases overall.Source: B COMPARISON FOR ONLINE STOCHASTIC… · p. 16

C COMMENTS ON PREVIOUS RESULTS IN LITERATURE

The discussion clarifies how oracle-access assumptions and feasible-set geometry affect comparisons with prior work, then develops offline lemmas for the settings considered. It also identifies noisy bandit feedback as a new setting for adversarial DR-submodular maximization.

C COMMENTS ON PREVIOUS RESULTS IN LITERATURE

  • Prior results are qualified or adapted according to feasible-set geometry, including extensions from downward-closed sets to convex sets containing the origin.The discussion also notes a proposed, rather than established, extension for lower-dimensional convex sets.Source: C COMMENTS ON PREVIOUS RESULTS IN… · pp. 16–17
  • Restricting oracle queries to the feasible set makes maximizing over K distinct from maximizing over conv(K ∪ {0}), despite equal optima without that restriction.The passage reports different known approximation coefficients for these two query settings: 1/2 and 1 − 1/e, respectively.Source: C COMMENTS ON PREVIOUS RESULTS IN… · p. 17
  • This is the first work to consider adversarial DR-submodular maximization with noisy bandit feedback; the authors also identify bounded-oracle assumptions behind some prior guarantees.For several prior works, the discussion says their results hold with a constant multiplicative factor if stochastic gradient oracles are bounded.Source: C COMMENTS ON PREVIOUS RESULTS IN… · p. 17

D USEFUL LEMMAS

  • The cited lemma toolkit includes smoothing results that preserve DR-submodularity and, for monotone functions, monotonicity.The section introduces these and other literature lemmas for use in the analysis.Source: D USEFUL LEMMAS · p. 18

E OFFLINE

  • The offline analysis separates monotone and non-monotone objectives across downward-closed and general convex feasible sets.These four cases are named as categories (A′)–(D′) for the offline lemma.Source: E OFFLINE · p. 19
  • For a monotone objective over a set with a minimum point, the proof uses monotonicity and concavity along non-negative directions to compare iterates with the optimum.The case assumes the minimum point u lies in K and is below every point in K.Source: E OFFLINE · pp. 19–20
  • For non-monotone objectives over downward-closed sets, the adjusted update remains feasible because it lies between the minimum point and the oracle point.The iterates are convex combinations of feasible points in this case.Source: E OFFLINE · pp. 19, 21

F PROOF OF THEOREM 1

The proof analyzes functions in blocks using their average as a representative, then uses oracle properties and offline guarantees to bound regret. It treats stochastic gradient and value queries through their respective unbiasedness properties.

F PROOF OF THEOREM 1

  • A block’s average function represents its constituent functions because summing block averages recovers the total reward sum divided by block size.The proof uses this relation to analyze regret computed from the sum of reward functions.Source: F PROOF OF THEOREM 1 · p. 25
  • Randomly permuting functions within each block makes the sampled function and its smoothed version unbiased estimates of their block averages.The proof also states the corresponding expectation identity for gradients.Source: F PROOF OF THEOREM 1 · p. 26
  • For stochastic gradient or value queries, the proof invokes oracle unbiasedness to establish the expected estimator relation used in the regret bound.It then applies the offline lemma to the averaged smoothed functions.Source: F PROOF OF THEOREM 1 · p. 27

G PROOF OF THEOREM 2

Theorem 2’s proof reuses the update rule from Algorithm 1 and carries over key arguments from Theorem 1 without modification.

G PROOF OF THEOREM 2

  • Algorithm 2 uses the same update rule for x_q as Algorithm 1.This allows the proof to reuse the earlier argument for bounding the relevant expected term.Source: G PROOF OF THEOREM 2 · p. 29
  • The proof says the corresponding Theorem 1 arguments apply directly, without modification, to this bound.The passage specifically notes that the update rules are the same in both algorithms.Source: G PROOF OF THEOREM 2 · p. 29
  • Because both algorithms have the same update rules, the proof of Equation 11 applies verbatim.Source: G PROOF OF THEOREM 2 · p. 29

H.1 EXPERIMENT SETUP

The experiments test online maximization on non-monotone objectives with downward-closed constraints and full-information or semi-bandit gradient feedback. GMFW(β = 1/2) performs best overall in the reported experiments, while the results also compare query and runtime trade-offs.

H.1 EXPERIMENT SETUP

  • The experiments use randomly generated non-monotone quadratic objectives and downward-closed feasible regions, testing three dimension-and-constraint pairs.The horizons range from T = 20 to T = 500; regret is measured against a near-optimal solution obtained using a 1/e-approximation algorithm.Source: §H.1 · pp. 29–30

H.2 RESULTS AND DISCUSSION

  • GMFW(β = 1/2) performs best across the tested dimensions and constraints, and at T = 100, n = 50, m = 50 runs in under 10 seconds versus over 14 minutes for Meta(β = 3/2).For larger horizons, it also performs better than Meta(β = 3/2), despite using fewer gradient queries and less computation.Source: §H.2 · p. 30
  • GMFW(β = 0) uses one full-information gradient query per round and has a regret bound of ˜O(T^2/3).It performs significantly better than the single-query Mono baseline across dimensions and horizons, reaching one seventh of Mono’s regret in some experiments.Source: §H.2 · pp. 30–31
  • Semi-bandit SMFW uses one gradient query at the played action, has a ˜O(T^3/4) regret bound, and has among the highest empirical regrets.Its regret is similar to Mono and, at large horizons, significantly better than ODC; it also takes about 0.3 seconds versus almost a minute for ODC at T = 100 and n = 50.Source: §H.2 · p. 31

Related papers

Loading 2403.10063v2…