PaperlayerView exact revision on arXiv

Source-linked AI summary

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization

Mohammad Pedramfar, Vaneet Aggarwal

arXiv:2405.00065v4math.OCcs.CCcs.LGstat.ML

TL;DR

Adversarial up-concave optimization spans many function classes and feedback settings, while prior work has treated many special cases. The paper introduces upper-quadratizable functions and meta-algorithms that connect their optimization to linear or quadratic maximization. Its applications improve regret guarantees across online and offline cases and provide the first dynamic and adaptive regret guarantees for online DR-submodular maximization.

  • Problem

    Adversarial up-concave optimization has been studied in many special cases despite applications including revenue maximization, mean-field inference, and recommendation systems.

    Source: §1 · pp. 1–2

  • Method

    The paper defines upper-quadratizable functions and uses meta-algorithms to convert linear or quadratic optimization algorithms into methods for these functions and multiple feedback settings.

    Source: §1 · pp. 2–4

  • Results

    Across nine offline cases, results improve prior projection-free guarantees except for deterministic first-order feedback, and improve 6 and match 3 against algorithms that are not projection-free; online results provide the first dynamic and adaptive regret guarantees for DR-submodular maximization.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Extending the framework to another function class requires proving it is quadratizable and providing an unbiased estimator of g.

    Source: §1 · p. 3

    Applications of FOTZO, STB, and FOTZO-2P require a differentiable Lipschitz extension that is up-concave with respect to its own gradient; an unrelated up-super-gradient field alone is insufficient.

    Source: §5 · p. 10

Abstract

from arXiv · show

This paper introduces the notion of upper-linearizable/quadratizable functions, a class that extends concavity and DR-submodularity in various settings, including monotone and non-monotone cases. A general meta-algorithm is devised to convert algorithms for linear/quadratic maximization into ones that optimize upper-linearizable/quadratizable functions, offering a unified approach to tackling concave and DR-submodular optimization problems. The paper extends these results to multiple feedback settings, facilitating conversions between semi-bandit/first-order feedback and bandit/zeroth-order feedback, as well as between first/zeroth-order feedback and semi-bandit/bandit feedback. Leveraging this framework, new algorithms are derived using existing results as base algorithms for convex optimization, improving upon state-of-the-art results in various cases. Dynamic and adaptive regret guarantees are obtained for DR-submodular maximization, marking the first algorithms to achieve such guarantees in these settings. Notably, the paper achieves these advancements with fewer assumptions compared to existing state-of-the-art results, underscoring its broad applicability and theoretical contributions to non-convex optimization.

1 Introduction

The paper develops upper-linearizable and upper-quadratizable function classes and meta-algorithms that connect their optimization to linear or quadratic maximization. It applies this framework across function classes and feedback settings, deriving improved regret guarantees and the first dynamic and adaptive regret guarantees for online DR-submodular maximization.

1 Introduction

  • Across 18 online cases, the framework improves prior projection-free guarantees in all cases and improves 12 and matches 5 when non-projection-free algorithms are included.The table compares static regret results for online up-concave maximization.Source: Table 1 · p. 2, §1 · pp. 2, 4
  • Applications use SO-OGD for projection-free adaptive regret results and Improved Ader for projection-based dynamic regret results.The framework applies these base algorithms to three up-concave optimization scenarios.Source: §1 · p. 3
  • Upper-quadratizable functions generalize strong concavity, concavity, and DR-submodularity in settings including monotone functions over convex sets and non-monotone functions over general convex sets.A meta-algorithm converts linear or quadratic maximization algorithms into algorithms for upper-quadratizable functions.Source: §1 · p. 3
  • Four meta-algorithms relate first-order or semi-bandit feedback to zeroth-order or bandit feedback, and full-information feedback to semi-bandit or bandit feedback.Together, these methods cover five feedback settings.Source: §1 · pp. 3–4
  • Across nine offline cases, results improve prior projection-free guarantees except for deterministic first-order feedback, and improve 6 and match 3 against algorithms that are not projection-free.Source: §1 · p. 4
  • The framework yields the first adaptive and dynamic regret guarantees for online DR-submodular maximization.The adaptive guarantees cover all cases in Table 3; the dynamic guarantees cover nine feedback/function-class cases.Source: §1 · p. 4
  • For monotone γ-weakly functions with bounded curvature over general convex sets, the paper improves the approximation ratio.Source: §1 · p. 4
  • In all considered cases with an existing result, the paper reports using fewer assumptions than the existing state of the art.Source: §1 · p. 4

2 Problem Setup and Definitions

The paper models online optimization as a repeated game on a convex domain, with adversaries that may be oblivious, weakly adaptive, or fully adaptive. It defines regret notions for different time intervals and comparator sets, and states assumptions and scope boundaries for the results.

Function classes

  • The setup includes γ-weakly up-concave functions and relates γ-weakly continuous DR-submodularity to up-concavity.The section also defines strong up-concavity with respect to a specified up-super-gradient field; when γ = 1 under the stated conditions, it recovers strong concavity.Source: §2 · pp. 4–5

Oracle complexity and assumptions

  • The stated complexity comparison covers oracle calls within the constraint set and notes that prior results generally require differentiability, DR-submodularity, Lipschitzness, and smoothness.The paper’s stated requirements vary by result: its results require non-negative Lipschitz functions, while zeroth-order results require differentiable Lipschitz extensions to the cube.Source: §2 · p. 5

Online setting

  • Each round, the agent chooses an action, then receives oracle feedback for an adversarially selected function; adversaries may be oblivious, weakly adaptive, or fully adaptive.The feasible set is compact and convex, with positive diameter and affine dimension at least one.Source: §2 · pp. 4–5

Regret definitions

  • Static, dynamic, and adaptive regret differ by the comparator set or interval over which performance is evaluated.Static regret uses the full horizon and all constant actions; dynamic regret compares against a single sequence, while adaptive regret takes the maximum over intervals.Source: §2 · p. 5

Non-stationary results

  • For non-stationary up-concave maximization, adaptive-regret results are projection-free, whereas dynamic-regret results use convex projection.The passage also states that deterministic full-information algorithms require two function queries, while stochastic-feedback algorithms require one at the cost of higher regret.Source: §2 · p. 6, Table 3 · p. 6

3 Formulation of Upper-Quadratizable Functions and Regret Relation to that of Quadratic Functions

The section defines upper-quadratizable function classes through maps and parameters that relate function optimization to quadratic optimization. Its meta-algorithm wraps an online semi-bandit algorithm and query procedure, transferring regret guarantees to the target class.

Definition and regret relation

  • A function class is upper-quadratizable when maps and parameters satisfy the class’s defining upper-quadratic relation; the case μ = 0 is called upper-linearizable.The associated comparison functions are linear or quadratic forms built from the map’s output and a displacement from the current point.Source: §3 · p. 6
  • OMBQ runs a semi-bandit algorithm on transformed actions and returns query-algorithm outputs as its feedback.When the action map is the identity and the query algorithm is trivial, the wrapper reduces to the original algorithm.Source: §3 · pp. 6–7
  • Theorem 1 transfers the base algorithm’s regret bound to upper-quadratizable functions, with a corresponding relation for unbiased bounded estimates.The exact-query case compares against a transformed quadratic-function class; the estimated-query case uses a bounded-output class.Source: §3 · p. 7
  • For concave functions, choosing the identity action map and a super-gradient recovers the concave version of earlier meta-algorithm results.This special case uses α = β = 1.Source: §3 · p. 7

4 Up-concave function optimization is upper-quadratizable function optimization

The section shows that several up-concave function settings are upper-quadratizable, enabling meta-algorithms to transfer guarantees from quadratic optimization. It treats monotone functions on general convex sets, monotone functions when the set contains the origin, and non-monotone functions on general convex sets.

4.1 Monotone up-concave optimization over general convex sets

  • For monotone strongly γ-weakly up-concave functions on general convex sets, a semi-bandit algorithm’s guarantees transfer under curvature and non-negative extension assumptions.The first-order result permits a specified up-super-gradient field; the passage notes that the zeroth-order application requires a differentiable extension up-concave with respect to its own gradient.Source: §4.1 · p. 7

4.2 Monotone up-concave optimization over convex sets containing the origin

  • When the convex set contains the origin, the section gives a BQM0-based transfer result for monotone γ-weakly up-concave functions.The function class is assumed differentiable and Lipschitz, and each function is the restriction of a non-negative monotone function on the cube.Source: §4.2 · p. 8

4.3 Non-monotone up-concave optimization over general convex sets

  • For non-monotone up-concave functions on general convex sets, Theorem 4 transfers the base guarantee with a factor of 3/8.The result assumes differentiable, Lipschitz functions that are restrictions of non-negative up-concave functions on the cube, and uses a fixed reference point in its action map.Source: §4.3 · p. 9

5 Meta algorithms for other feedback cases

The section develops meta-algorithms for converting between feedback settings and from online to offline optimization. Smoothing supports first-order-to-zeroth-order conversions, subject to assumptions on the function class and up-concavity.

Smoothing

  • Smoothing averages function values over a sliced ball and maps the result back to K; it preserves the stated up-concavity, nonnegativity, applicable monotonicity, curvature, and Lipschitz bounds.The strong up-concavity parameter becomes s^2μ, and the Lipschitz bound becomes sM1.Source: §5 · pp. 9–10

First-order/semi-bandit to zeroth-order/bandit feedback

  • First-order algorithms can be converted to zeroth-order or bandit feedback while retaining the stated regret bounds under Theorems 5 and 6 assumptions.FOTZO converts first-order feedback, while FOTZO-2P handles semi-bandit feedback; the conversion uses a smoothed function class.Source: §5 · pp. 9–10

Smoothing assumptions

  • These applications require a differentiable Lipschitz extension with the specified properties and up-concavity with respect to its own gradient, not merely an unrelated up-super-gradient field.The simulated first-order oracles estimate the smoothed function’s gradient or its projection onto the feasible affine hull.Source: §5 · p. 10

Full information to trivial query

  • SFTT converts full-information algorithms to trivial-query algorithms: first-order feedback becomes semi-bandit feedback, and zeroth-order feedback becomes bandit feedback.The stated theorem assumes a fixed number of queries per round, independent of current-round observations, and a function class closed under convex combinations.Source: §5 · p. 10

Online to Offline

  • Online-to-batch conversion samples one of the online algorithm’s actions uniformly, and the theorem gives a sample-complexity bound from an online α-regret bound.The stated result assumes an oblivious adversary and at most K = T^θ queries per time-step.Source: §5 · p. 11

6 Applications

Figure 1 organizes applications as directed paths through meta-algorithm conversions. The path’s starting node, edge color, and permitted components determine the resulting algorithm and feedback setting.

Figure 1

  • A valid application path starts at one of the three left-hand nodes, has at least one same-color edge, and excludes SFTT and OTB when the base algorithm is IA.The figure summarizes applications described in Tables 1–3; exact statements are in Corollaries 7 and 8.Source: §6 · p. 11
  • A path from SO-OGA through OMBQ, FOTZO, and SFTT yields a projection-free bandit algorithm for monotone up-concave functions over convex sets containing the origin.The cited example gives adaptive regret of order O(T^4/5).Source: §6 · pp. 11–12
  • Red edges indicate that G is a trivial-query algorithm, so OMBQ’s output has semi-bandit feedback.The path example’s SFTT conversion leads to bandit feedback.Source: §6 · pp. 11–12

7 Conclusions

The conclusion presents upper-quadratizable functions as a framework covering concave and DR-submodular optimization across settings and feedback types. The accompanying material reviews related methods, formalizes the online problem, and sketches a proof strategy for Theorem 1.

7 Conclusions

  • The framework treats upper-quadratizable functions as a generalized class and derives algorithms with improved static, dynamic, and adaptive regret guarantees; exploring more applicable subclasses remains future work.The conclusion states that the framework covers concave and DR-submodular functions across various settings and feedback types.Source: §7 · p. 12

A Related works

  • Related work distinguishes Frank-Wolfe and boosting approaches to DR-submodular maximization and describes quadratization as extending convex-optimization meta-algorithms to broader function classes.The review also situates online up-concave maximization and projection-free optimization among prior work.Source: A Related works · pp. 16–17

B Problem Setup in Detail

  • The setup models online optimization as a repeated game on a convex domain, with feedback determined by the query oracle and query policy, and regret defined over selected comparator sets and intervals.It distinguishes oblivious, weakly adaptive, and fully adaptive adversaries.Source: B Problem Setup in Detail · pp. 17–19

C Proof of Theorem 1

  • Theorem 1’s proof fixes the query-oracle randomness to form a deterministic comparison, then uses the up-quadratizability inequality and Jensen’s inequality in the stochastic analysis.The proof notes that fixing the randomness need not preserve the oracle’s unbiasedness condition.Source: C Proof of Theorem 1 · pp. 19–20

D Proof of Lemma 1

The proof uses a lattice identity and the stated curvature and up-concavity inequalities to establish its claim.

D Proof of Lemma 1

  • The identity x ∨ y + x ∧ y = x + y supplies the algebraic relation used in the proof.The proof invokes it while applying the definition of curvature.Source: D Proof of Lemma 1 · p. 21
  • Nonnegativity of f is used to derive an intermediate bound from the curvature relation.The passage states that nonnegativity implies the next inequality.Source: D Proof of Lemma 1 · p. 21
  • Applying the up-concavity inequalities with respect to the specified field, then using the intermediate inequality and f(x ∧ y) ≥ 0, yields the claim after multiplying by γ^2.The proof also uses the lattice identity in its final equality.Source: D Proof of Lemma 1 · p. 21

E Proof of Lemma 2

The proof bounds the defining integrand to establish that F is well-defined, then uses monotonicity and up-concavity in its analysis.

E Proof of Lemma 2

  • The integrand is bounded, so F is well-defined on [0, 1]^d.The proof first notes F(0) = 0 and bounds the integrand for nonzero x.Source: E Proof of Lemma 2 · pp. 21–22
  • The proof states that F is differentiable everywhere.The displayed gradient-related expression is incomplete in the supplied passage.Source: E Proof of Lemma 2 · p. 22
  • The remaining argument invokes monotonicity and up-concavity of f.The supplied excerpt does not include the resulting inequality.Source: E Proof of Lemma 2 · p. 22

F Proof of Lemma 3

The proof of Lemma 3 uses a result for nonnegative up-concave functions and establishes properties of F; it also states a relaxation for the gradient identity.

F Proof of Lemma 3

  • Lemma 4 applies to any two vectors and any continuously differentiable, nonnegative up-concave function.The excerpt introduces the lemma as an extension of earlier results for DR-submodular functions to up-concave functions.Source: F Proof of Lemma 3 · p. 22
  • For the gradient identity, everywhere differentiability can be relaxed to Lipschitz continuity and differentiability at the anchor, with full gradients almost everywhere along relevant segments.The relaxation applies only to the gradient identity; the lemma's other assumptions remain unchanged.Source: F Proof of Lemma 3 · pp. 22–23
  • In the Lemma 4 proof, the argument uses z = x ∨ y − y and concavity along a line segment within the cube.The proof also invokes non-negativity of f to obtain the lemma's conclusion.Source: F Proof of Lemma 3 · p. 23
  • The proof bounds the integrand to show that F is well-defined on [0, 1]^d.It then states that F is differentiable everywhere.Source: F Proof of Lemma 3 · p. 23

G Proof of Theorem 5

Theorem 5 is proved using wrappers that convert feedback settings while running a base algorithm on the same convex set. Smoothing and rescaling yield a regret guarantee under the stated base-algorithm conditions.

G Proof of Theorem 5

  • FOTZO converts first-order feedback to zeroth-order feedback, while STB converts semi-bandit feedback to bandit feedback.The wrappers use smoothing and rescaling; the base algorithm runs on the same convex set.Source: G Proof of Theorem 5 · pp. 25–26
  • The proof uses a ball-smoothing identity to construct simulated first-order feedback; the two-point wrapper uses a deterministic value oracle.The queried points are kept in K, and smoothing and rescaling bound the reward difference.Source: G Proof of Theorem 5 · p. 26
  • The regret transfer combines comparator and reward estimates, with separate action-error bounds for full-information wrappers and STB.The proof then takes the supremum over the adversary to establish the theorems.Source: G Proof of Theorem 5 · pp. 26–27
  • For fixed geometry and dimension, M1 = O(B0) gives the FOTZO wrapper rate O(B0 T^((1+η)/2)).The corollary chooses δ = min{r/2, T^((η−1)/2)} for FOTZO, or STB when the base algorithm is semi-bandit.Source: G Proof of Theorem 5 · p. 27

H Proof of Theorem 7

Theorem 7’s proof groups rounds into blocks and simulates the base algorithm using block-mixture oracle responses. Its interval-regret analysis accounts for incomplete boundary blocks and action deviations.

H Proof of Theorem 7

  • Block mixtures produce unbiased oracle observations for the base algorithm, with the simulated interaction having the same law as the original one.The construction uses a random permutation of queries within each block; queries do not depend on other responses in that block.Source: H Proof of Theorem 7 · p. 27
  • At most 2(L − 1) interval rounds lie outside complete blocks, costing at most 2M1D(L − 1) in regret.Within complete blocks, the played action differs from the base action on at most K rounds per block.Source: H Proof of Theorem 7 · p. 27
  • The block argument also applies to other oracle classes closed under block mixtures; if L does not divide T, the leftover rounds add at most M1D(L − 1) to interval regret.The boundedness of oracle outputs is used only to ensure the block oracle belongs to the stated adversary class.Source: H Proof of Theorem 7 · p. 28
  • When K = O(1), the stated exponent is 1/(2 − η); when M1D = O(B), the coefficient simplifies to O(B).The corollary selects block length L = Θ(T^((1+θ−η)/(2−η))) with L > K and handles the final incomplete block separately.Source: H Proof of Theorem 7 · p. 28

I Proof of Theorem 8

The section establishes query and regret guarantees for projection-free adaptive and dynamic optimization. Its corollaries cover multiple feedback settings under stated extension and boundedness assumptions.

I Proof of Theorem 8

  • Theorem 8's proof counts T^(1+θ) queries when the base algorithm uses T^θ queries per time step, and relates expected error to regret divided by time.It states ε = O(T^(η−1)) after T^(1+θ) queries.Source: I Proof of Theorem 8 · p. 28

J Projection-free adaptive regret

  • O(M1T^1/2) bounds the adaptive regret for the stated linear-function class in Theorem 9.The theorem assumes ∥l∥ ≤ M1 for all l in L.Source: J Projection-free adaptive regret · p. 29
  • The projection-free adaptive-regret corollary distinguishes zeroth-order differentiable Lipschitz extensions from first-order extensions that need not be differentiable.Its hidden constants may depend on fixed geometric parameters of K.Source: J Projection-free adaptive regret · p. 30

K Dynamic regret

  • For dynamic regret, the authors do not use SFTT because Theorem 7 applies only when the comparator is K_T* and does not convert dynamic-regret bounds..Source: K Dynamic regret · p. 32
  • O((B0 + M1)T^3/4(1 + P_T(u))^1/2) bounds the stated dynamic-regret result under Theorem 4's assumptions.The corollary also assumes F is bounded by M0 and B0 ≥ M0.Source: K Dynamic regret · p. 32
Loading 2405.00065v4…