Carina Moreira Costa, Maria Eduarda Pinheiro, Martin Schmidt
原文摘要
We study data poisoning attacks on logistic regression with $\ell_2$-regularization, where an attacker chooses the features of a fixed number of injected observations with prescribed labels to maximize the logistic loss on the clean training data. Strong convexity of the defender's problem yields an exact reformulation through its first-order optimality conditions. Using convex conjugacy of the softplus function, we replace the sigmoid relations by a single convex optimality-gap inequality and express the attacker's objective as a concave function. A change of variables makes the stationarity condition affine, leaving bounded bilinear equalities as the only nonconvex constraints. We derive finite bounds on all variables involved in these equalities, including a global bound on the coefficient norm and tighter bounds obtained by preprocessing based on convex optimization. Experiments on eight binary classification datasets evaluate attack effectiveness and compare the two reformulations when solved with \textsf{SCIP}. Attacks obtained by local optimization degrade predictive performance on most datasets, while the convex-analytic formulation produces substantially stronger reported dual bounds within a fixed time limit.
Aloïs Duguet, Tobias Harks, Martin Schmidt, Julian Schwarz
原文摘要
We consider combinatorial multi-item markets and propose the notion of a $Δ$-regret Walrasian equilibrium, consisting of an allocation and item prices such that prices clear the market, the allocation is capacity-feasible, and the players' strategies lead to a total regret of at most $Δ$. Regret is the sum of the players' utility gaps relative to optimal bundles at the given prices. We derive a complete characterization for the existence of $Δ$-regret equilibria by introducing the concept of a parameterized social welfare problem, where only the capacity constraints binding at a prescribed allocation are retained. Our characterization then relates the achievable regret value to the associated duality/integrality gap of the parameterized social welfare problem at that allocation. For the special case of monotone valuations and upwards-closed strategy spaces this translates to regret bounds recovering the duality/integrality gap of the original social welfare problem. We also characterize weighted buyer and seller regret by configuration-LP gaps and establish a finite exact penalty enforcing market clearing. We further derive a slack-dependent price-adjustment bound whose uniform version is sharp for prescribed allocations. Finally, these structural results translate approximation algorithms for social welfare with guarantees relative to the configuration LP into algorithms computing low-regret Walrasian equilibria. We also derive lower bounds from integrality and duality gaps and computational complexity.