Recent results [arXiv:2602.04378, arXiv:2602.22608] establish lower bounds for optimization over strongly convex sets, covering specified Frank-Wolfe updates and unrestricted deterministic first-order linear minimization oracle (LMO) methods, respectively. Neither establishes a lower bound for unrestricted randomized methods. We close this gap by proving an $Ω(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound after $T$ oracle calls for randomized first-order LMO methods over strongly convex sets, with final outputs required to be feasible on every instance and seed. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We also show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound. Our construction uses the same curvature-diameter coupling as [arXiv:2602.22608]. Comparisons with the upper bound [arXiv:1406.1305] must account for this coupling. Separately, we show that prescribed slow exact-line-search Frank-Wolfe trajectories can locally amplify sufficiently small initialization errors, corresponding to roughly one extra bit of initialization accuracy per iteration, and that initializations satisfying a particular eventual slow envelope have planar measure zero.
Takeshi Koshizuka, Denis Blessing, Max Zimmer, Sebastian Pokutta, Lorenz Richter
原文摘要
We study the numerical approximation of Schrödinger Bridges in the setting where samples from the target distribution are unavailable and only an unnormalized target density is given. In this regime, the widely used iterative proportional fitting (IPF) procedure (and its variants) often exhibits severe numerical instabilities, stemming from ill-conditioned underlying control problems and from the fact that the optimal solution may lie far from the initialization. To address these issues, we propose a trust region variant of IPF that constrains successive updates to remain at a fixed Kullback-Leibler divergence from the current iterate. This restriction significantly improves numerical stability. Moreover, we show that the resulting method admits an interpretation as a mirror descent scheme with an adaptively chosen step size. We demonstrate the effectiveness of our approach on several challenging sampling tasks.
Nataša Djurdjevac Conrad, Sebastian Pokutta, Christof Schütte
原文摘要
Large language model (LLM) agents are increasingly used as synthetic participants in opinion-dynamics experiments, often assuming that an agent's behaviour is fully determined by its prompt. We test this assumption with a framework in which LLM agents discuss a contested policy issue over repeated rounds while their stance is quantified by a fixed psychometric instrument independent of any dynamics model. Across six LLMs, committed personas are intrinsically stable: in each of the five models tested without peer input, every agent keeps its assigned side for 20 rounds. The observed loss of alignment under discussion is therefore interaction-induced, we call it alignment drift, and model-specific: gpt-4.1 keeps opinion clusters apart, claude-sonnet-5 holds them partially, and gpt-5.6-sol and claude-opus-5 abandon them. Under selective attention, one LLM maintains separated opinion clusters under stance-homophilous attention. Qualitative profiles persist at doubled population and horizon and on a second issue. Such heterogeneity makes the LLM choice a first-class validity variable for social simulation.
Fault-tolerant quantum computation requires substantial resources for non-Clifford gates. Their count also enters exponentially into the runtime of several classical simulation methods. We present algebraic methods for minimizing the non-Clifford CCZ (Toffoli) count in {CNOT,CCZ} phase circuits using tensor decomposition over $\mathbb{F}_2$. On standard cubic benchmarks, these methods match or improve prior automated Toffoli counts, with most instances optimized in under a minute on a single CPU. With additional computation, the decompositions provide effective initializations for existing T-count methods, improving T counts on several circuits. We also present algebraic methods for CNOT-count optimization at fixed Toffoli count. This gives competitive ancilla-free finite-field multiplication circuits and reduces the CNOT count of XOR AES S-box circuits.