Papers for

optimization algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Upper bound found for edges in Gomory corner polyhedron geometry

An upper bound on the number of edges of a Gomory corner polyhedron

Abstract: We establish the first nontrivial upper bound on the number of edges of a Gomory corner polyhedron, resolving a long-standing open question. For an $n$-dimensional corner polyhedron associated with an integer lattice of determinant $δ$, the number of edges is at most $$ O\left(n6^n \cdot \bigl(1+\log_2(2δ)\bigr)^{2n-3}\right). $$ This improves the standard bound obtained by counting pairs of vertices, reducing the logarithmic exponent from $(2n-2)$ to $(2n-3)$.

Thu 12 NovComputational GeometryDiscrete Mathematics
The gist
Counting the edges in a special kind of geometric shape called a Gomory corner polyhedron has been a challenging problem for many years. The paper shows a new way to put an upper limit on how many edges these shapes can have, depending on their dimension and other properties. This new bound is tighter than previously known results. The authors thus resolved a question that people in math and computer science had been stuck on for some time.
Open → 2611.16839v1

Wolfe's minimum norm point method linked to simplex method shows exponential behavior

Wolfe's Minimum-Norm-Point Method Generalizes the Simplex Method

Abstract: Wolfe's method computes the point of minimum Euclidean norm in the convex hull of finitely many points. The method is parameterized by an insertion rule and it has been an open problem whether Wolfe's original rule guarantees a polynomial number of iterations (De Loera, Haddock, and Rademacher; STOC'18). We resolve this question by proving an exponential lower bound. In fact, we establish a tight connection to the simplex method for linear programming that allows us to transfer many lower bounds for simplex pivot rules to corresponding insertion rules of Wolfe's method. These include not only Wolfe's linopt rule via Dantzig's pivot rule, but also many other classical, randomized and history-based rules. As a corollary, we obtain the first exponential example for the Lawson-Hanson algorithm for nonnegative least squares, as well as PSPACE-hardness of deciding whether the linopt rule ever uses a given point.

Mon 9 NovData Structures and Algorithms
The gist
This paper studies a mathematical method called Wolfe's method, used to find the closest point within a shape formed by other points. The authors answer a long-standing question about whether this method always finishes quickly by showing that, in some cases, it can take an extremely long time to finish. They closely connect Wolfe's method to another well-known approach in optimization called the simplex method and use this link to prove new limits on how fast Wolfe's method can work. The results also reveal the complexity of deciding some behaviors of the method, impacting related algorithms in data fitting.
Open → 2611.12680v1

Algorithms face sharp limits on solving logic puzzles efficiently

Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF

Abstract: We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.

Fri 6 NovData Structures and Algorithms
The gist
Many computer algorithms try to solve logic puzzles called 3-CNF formulas by flipping variables or resampling groups of variables. The authors found that these algorithms work quickly when each variable appears only a few times, but suddenly slow down drastically when variables appear more often. Surprisingly, this slowdown happens before the problem becomes truly hard to solve. They also show that the two popular algorithms can behave very differently on the same puzzle, with one solving it quickly while the other takes exponentially longer, and vice versa.
Open → 2611.09335v1

Bayesian methods link functional inequalities to estimation limits

Functional inequalities from the fundamental limits of Bayesian estimation

Abstract: We develop a Bayesian information-theoretic framework for proving functional inequalities for log-concave measures. Motivated by Klartag and Ordentlich, we establish a unified equivalence between $Φ$-Sobolev inequalities and Bayesian estimation lower bounds: for a large class of smooth convex $Φ$, a log-concave measure $μ$ satisfies a $Φ$-Sobolev inequality with constant $C>0$ if and only if for $X\simμ$, any $t>0$, and any real-valued measurable $f$, the Bayes risk of estimating $f(X)$ under the $Φ$-Bregman loss from the Gaussian additive observation $Y_t=\sqrt tX+G, G\sim N(0,I_n)$ is at least a $1/(1+Ct)$-fraction of that of the trivial estimator. Combining it with direct information-theoretic arguments, such as testing-to-estimation reductions, we obtain old and new functional inequalities: - For the Poincaré inequality, corresponding to $Φ(x)=(x-1)^2$, we give a simple static information-theoretic proof that the Poincaré constant of an isotropic log-concave measure on $\mathbb{R}^n$ is $O(n^{1/2})$, first proven via stochastic localization in the seminal work of Lee and Vempala. - For the log-Sobolev inequality, corresponding to $Φ(x)=x\log x$, we prove that all smooth $K$-subgaussian log-concave measures $μ$ satisfy $C_{\mathrm{LS}}(μ)\lesssim K^2n^{1/4}$, surpassing the recent state-of-the-art bound of $O(K^2n^{1/2})$ by Bizeul. In parallel and independent work, OpenAI claimed the optimal bound $O(K^2)$ in their October 6, 2026 release of 722 papers. - Finally, we give a Bayesian reformulation of the common structure of the three recent proofs of the Kannan--Lovász--Simonovits conjecture, a dimension-free Poincaré bound for isotropic log-concave measures [BK26; BKL26; SZ26]. Tools from the study of the "low-degree MMSE" in computational complexity of statistical inference motivate and recast key steps and quantities of these proofs.

Wed 4 NovInformation Theory
The gist
Some mathematical inequalities help describe how certain shapes in space behave. This paper shows that these inequalities are connected to how well one can guess hidden information using noisy signals. By using ideas from Bayesian statistics and information theory, the authors find new ways to prove these inequalities and improve previous results, especially for shapes called log-concave measures. They also relate their findings to some big open problems in mathematics and statistics.
Open → 2611.05831v1

Tight lower bounds for optimizing smooth convex functions with matching orders

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity

Abstract: In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose $p^{th}$-order derivatives are Hölder continuous with degree $ν$ and parameter $H$, and that are uniformly convex with degree $q$ and parameter $σ$. When these orders match, namely, $q = p + ν$, we show that any deterministic algorithm with access to derivatives up to order $p$ requires $Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right)$ oracle calls to reduce an initial optimality gap of $Δ_0$ to $ε$. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.

Tue 3 NovMachine Learning
The gist
Finding the best solution quickly in math often depends on how smooth and curved the function you're working with is. This paper shows the exact minimum number of steps any method needs to find a good answer when certain smoothness and curvature conditions match. The authors developed a new, careful approach to prove this limit, improving over previous methods. Their result completes the picture for this specific situation where previous knowledge was incomplete.
Open → 2611.05527v1

New limits found for monotone arithmetic proofs of logical formulas

Nonnegative Rank Bounds for the Algebraic Monotone Calculus

Abstract: In Hrubes' Algebraic Monotone Calculus a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $χ(A)-εχ(1)$ for some $ε>0$, where the coefficient of $χ(A)$ at $x^σ$ counts the terms of $A$ satisfied by $σ$, and $χ(1)=\prod_i(x_i^0+x_i^1)$. Proof size is circuit size, and $ε$ is existentially quantified, so lower bounds must hold at arbitrarily small $ε$. We prove lower bounds for bounded-depth fragments by two nonnegative rank measures of the target: monotone tensor rank and the nonnegative rank of a flattening. At depth three a proof is a nonnegative tensor decomposition. Restricting its terms to subcube indicators gives conical juntas, a system polynomially equivalent to Sherali-Adams in twin variables. For arbitrary terms we adapt Rothvoss' hyperplane separation to monotone tensor rank: Tseitin formulas on constant-degree expanders of large girth need proofs of size $2^{Ω(εn)}$ whenever $ε=ω(\log n/n)$. This cannot reach every $ε$: at shift $2^{-Θ(n\log n)}$ Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every $ε\geq2^{-Ω(n)}$, converting a Sherali-Adams degree bound into a size bound. Depth three is essential: Tseitin has monotone proofs of size $O(n^3)$ and depth $O(\log n)$ at every $ε$. Beyond depth three we bound the nonnegative rank of a flattening by $L^{2^t}$ for a monotone formula with $L$ leaves and mixed-product depth $t$: the largest number of product gates on a root-to-leaf path whose two inputs each meet both sides of the bipartition. Approximate extension complexity then bounds perfect matching and odd factor instances, and planted CSP integrality gaps give an explicit family of planted Tseitin DNFs hard at inverse-polynomial shift.

Sat 31 OctComputational Complexity
The gist
Understanding how complex logical statements can be proven using certain arithmetic circuits is important for fields like computer science and math. This paper studies a special kind of proof method, called the Algebraic Monotone Calculus, which uses circuits to handle monotone expressions. The authors find that for some difficult formulas, these proofs need to be very large, especially when the proofs are shallow (have small depth). They also show how allowing deeper circuits drastically reduces proof size, revealing key trade-offs in proof complexity. These insights help explain why some problems are hard to prove efficiently with these methods.
Open → 2611.01055v1

Proof confirms limit for space partitions and removes computer aid

On the Propeller Conjecture

Abstract: We simplify and improve OpenAI's proof of the propeller conjecture of Khot and Naor from 2008: the sum of the squared lengths of the Gaussian moments of any partition of Euclidean space is at most $9/(8π)$. We show equality only occurs for three 120 degree sectors in the plane (up to symmetries, measure zero changes, and taking orthogonal cross products with Euclidean space). We also remove computer assistance from the three-dimensional case of the conjecture, which previously used an epsilon net traversal.

Fri 23 OctComputational Complexity
The gist
This work deals with a math problem about dividing space into parts and measuring certain properties of those parts. The authors improved a previous proof by simplifying it and removing the need for computer help in one case. They showed the best possible way to divide the plane into three equal parts at 120-degree angles. This confirms that their result holds true in higher dimensions without relying on computers.
Open → 2610.32158v1

Finite angular motion of learning paths for definable functions

On the gradient conjecture at infinity: Finite spherical length for gradient trajectories of definable potentials

Abstract: We prove that for every open $ U \subseteq \mathbb R^n $ the spherical projection of every gradient trajectory $θ(t)$, $t \geq 0$, of a definable $C^1$-potential $F \colon U \to \mathbb R$ has finite length and, in particular, converges (directional convergence). In other words, every gradient trajectory of a definable $C^1$-potential has finite total angular motion. Here, definable means definable in an arbitrary o-minimal structure expanding the real field. Notably, the gradient trajectory in this result is an arbitrary solution of the gradient flow differential equation (whose solutions may not be unique) with no further assumptions: The gradient trajectory may be unbounded and diverge to infinity or it may be convergent. The established theorem therefore provides affirmative answers to both the gradient conjecture at infinity for definable potentials and the definable Thom gradient conjecture. We apply our theorem to the training of deep neural networks (DNNs) to conclude that, in the case of definable and continuously differentiable activation and loss functions, the spherical projection of the DNN training flow must always converge (directional convergence).

Wed 21 OctMachine Learning
The gist
The paper shows that when using smooth and nicely describable functions, paths that follow the steepest uphill or downhill directions cannot spin around endlessly. Instead, their direction settles down over time, even if the path itself goes off to infinity. This is important because it confirms a long-standing mathematical idea about how these paths behave in complicated spaces. The authors also connect this idea to how deep learning models learn, implying that under certain conditions, the way these models update their settings will eventually point in a consistent direction.
Open → 2610.29211v1

Parameter gradient flows close only under specific model rank conditions

When Parameter Gradient Flows Close in Representation Space

Abstract: The represented gradient flow of a parameterized model depends on a mobility that can retain hidden parameter information. We study when one entire represented mobility map works for every autonomous loss from one fixed initialization. For two-factor matrix representations wider than both output dimensions, with individually full-row-rank factors, we classify all admissible joint ranks: closure occurs precisely at effective scalar-balanced minimal joint rank or a two-value signed spectral family at full joint rank. All intermediate ranks are excluded; positive represented flows belong to known square-root families. For general representations with constant ambient representation and gradient-Lie ranks, ordinary closure is equivalent to a local invariant-level metric in the analytic case and specified smooth regimes. An endpoint section forces the initially unrestricted mobility map to admit a locally smooth representative on the represented image. We also separate testing families: linear losses locally admit closure at every submersion, whereas one fixed translated strongly convex quadratic family fails it on a delayed-bracket example. A fixed output readout gives an ordinary squared-loss witness. These supporting results do not characterize quadratic-only closure in general. We retain the unresolved smooth output-rank-two case with Lie rank at least four. A frozen deterministic experiment checks a separate engineered-loss construction; it is distinguished from the squared-loss proof, universal theorems and empirical learning performance.

Tue 20 OctMachine Learning
The gist
Gradient flows describe how machine learning models change their parameters to improve performance. This paper studies when these flows behave predictably based on the model's internal structure, focusing on matrix factorization models. The authors find that only certain rank conditions of these factors ensure stable behavior called closure, while others are excluded. They also provide insight into when specific loss functions cause or fail this closure, improving understanding of model training dynamics.
Open → 2610.27474v1

Heavy-ball method does not speed up solving 1D smooth convex problems

Non-Acceleration of the Heavy-Ball Method in 1D

Abstract: Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.

Sun 18 OctMachine Learning
The gist
Finding the fastest way to solve optimization problems is important for many fields. The heavy-ball method is a way to speed up solving such problems, especially when dealing with multi-dimensional quadratic functions. The authors show that in one-dimensional smooth, strongly convex problems, this method does not actually speed up the solution process. They use mathematical analysis to prove this and also explore more complex cycling behaviors of the method in higher dimensions.
Open → 2610.25104v1

Muon polar update optimal only under specific radial conditions

When Is Muon Optimal? Radial Fragility and Minimax Geometry

Abstract: Muon replaces a matrix gradient by an approximate polar factor and has shown strong empirical performance in neural-network training. The Isotropic Curvature Model (ICM) provides a curvature-based explanation for this update by asking when gradient orthogonalization minimizes a one-step local-loss surrogate. We investigate the stability of this explanation when the fixed input radius of the ICM is replaced by a general radial law. We introduce the Random-Radius Isotropic Curvature Model (RR-ICM) and the Polar-Factor Admissibility Set, which encodes exact scaled-polar optimality as a geometric condition on the positive polar factor of the gradient. We derive an exact characterization of this set for arbitrary radial laws and show that all nonscalar admissible responses arise from radial atoms aligned with curvature kinks. Consequently, every atomless radial law exhibits zero-capacity rigidity: exact scaled-polar optimality is possible only when the gradient is already a scaled column isometry. To connect the curvature-based framework with the established spectral geometry of Muon, we introduce the Minimax RR-ICM by replacing directional averaging with worst-case optimization over probability laws on the sphere. We prove that every nonzero global minimizer lies on the polar ray of the gradient, while its scale is determined by a one-dimensional convex problem. The corresponding admissibility geometry is a positive-semidefinite trace slab, in sharp contrast to the spherical-zonoid geometry of the RR-ICM. Together, these results expose the radial fragility of average-curvature explanations and provide a new minimax variational characterization of Muon's polar direction.

Thu 15 OctArtificial IntelligenceMachine Learning
The gist
Training neural networks involves adjusting models to improve accuracy. The authors study Muon, a method that changes these adjustments to use an approximation called the polar factor. They find that Muon's effectiveness depends heavily on assumptions about how input data distances are distributed. When these assumptions change, the method only works optimally under very strict conditions. Their work introduces new ways to understand when Muon’s approach is best and reveals limitations of previous explanations.
Open → 2610.21549v1

Constant-step momentum improves stability in stochastic gradient descent

A Nonlinear Time-Series Theory for Constant-step SGD with Momentum

Abstract: Constant-step stochastic gradient descent with momentum (SGDM) augments the parameter recursion with a momentum state that carries geometrically decaying memory of past stochastic gradients. We study this coupled recursion as a nonlinear time series and develop a framework for its stationary behavior and distributional limits. The joint parameter-momentum process forgets its initialization geometrically under a finite $p$th moment for $p > 1$, yielding a unique stationary causal solution. Under a second-moment condition, this contraction leads to an invariance principle and quenched Gaussian limit for averaged SGDM, while a small-learning-rate analysis gives a Gaussian limit for the last iterate. In a stochastic-curvature quadratic model, we further study how the rate of initialization forgetting relates to stationary variance and averaged fluctuations.

Mon 12 OctMachine Learning
The gist
Stochastic gradient descent with momentum is a common method for training machine learning models by updating parameters while remembering past updates. The authors analyze this method as a kind of nonlinear time series to better understand its long-term behavior and stability. They show the method steadily forgets initial starting points under certain conditions, leading to predictable, stable behavior that resembles a Gaussian process when averaged or in the limit of small learning steps. This gives new insights into why momentum helps training and how it affects variability in the updates.
Open → 2610.16034v1

Virtual extension complexity can vastly outperform classic extension complexity

Two Linear Programs are Better than One

Abstract: The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

Sun 11 OctComputational ComplexityDiscrete MathematicsMachine Learning
The gist
When trying to represent shapes called polytopes, it's important to measure how complicated that representation is. The authors study a new measure called virtual extension complexity, which looks at how combining two simpler shapes can represent a complex one more easily. They show that using two shapes instead of one can make this complexity much smaller, sometimes exponentially so. They also find examples where this simplification isn't enough and explore how complicated polygons behave under this measure.
Open → 2610.15909v1

Simulated annealing achieves precise sampling for spin glass models

Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model

Abstract: We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.

Wed 7 OctData Structures and Algorithms
The gist
Sampling from complex probability models like the Sherrington-Kirkpatrick spin glass is important but very challenging. The authors present a simulated annealing method that efficiently produces samples very close to the true model distribution with polynomial-time guarantees. Their approach relies on sophisticated mathematical inequalities and new techniques to control errors that arise when approximating these complex systems. This work advances the understanding of how to accurately analyze and approximate difficult random systems using computational methods.
Open → 2610.09882v1

Stochastic gradient methods fall short on certain nonconvex games

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

Abstract: How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For $\ell$-smooth games with an inner $μ$-PL inequality, we prove a complexity lower bound $Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})$, where $κ=\ell/μ$ is the condition number, $σ^2$ is the gradient variance, and $\varepsilon$ measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as $o(κ^2)$. Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.

Tue 6 OctComputer Science and Game TheoryMachine Learning
The gist
This paper studies a popular approach called stochastic gradient descent ascent (SGDA) used to solve problems where two players compete with complex strategies. The authors found that SGDA has fundamental limits in solving a class of these problems, meaning it can be inefficient or even fail. They proved precise mathematical bounds showing how hard the problem is for SGDA and showed that other methods can be better. This helps explain when and why simple tuning of SGDA won’t solve these problems well.
Open → 2610.07814v1

Optimal risk descent speed follows a cycloid shape for fastest arrival

Least-time Gradient Flow

Abstract: Prescribing the speed of gradient flow on the risk itself, by the dynamics $\dot w=-u(E(w))\nabla E(w)/\abs{\nabla E(w)}^{2}$, makes the risk $e(t)=E(w(t))$ obey $\dot e=-u(e)$ exactly, whatever the landscape~$E$; the time needed to reach zero risk from $e_0$ is $\int_0^{e_0}\dd e/u(e)$. Minimizing this time alone is ill posed, and we study the regularized problem $\inf\{\int_0^{e_0}(\tfrac\lambda2\abs{u'}^{2}+1/u)\,\dd e:\ u\in H^{1}(0,e_0),\ u\ge0,\ u(0)=0\}$, $λ>0$. We prove that the minimizer exists, is unique, and is a linearly scaled cycloid, and we show that the optimal rate behaves like $u^{*}(e)\sim(9/(2λ))^{1/3}e^{2/3}$ near zero risk: the exponent $2/3$ is the one found in \cite{betti2026holder} by a power-law ansatz, and it lies in the Hölder window $(\tfrac12,1)$ where the arrival is in finite time with vanishing weight speed. The proof follows the classical route: existence by the direct method, uniqueness by strict convexity, positivity of the minimizer away from the origin, and the explicit integration of the Euler-Lagrange equation.

Thu 1 OctMachine Learning
The gist
When trying to improve something step-by-step by following its steepest downhill path, the authors study how to choose the speed at which to move. They find a special way to set this speed so that the overall error decreases at a precise rate, no matter the problem's complexity. To do this best, the speed follows a certain curved path called a cycloid, which they describe exactly. This result helps understand how to reach the goal in the least possible time with smooth speed changes.
Open → 2610.01426v1

Limitations found in robust approximation for constraints with many variables

Robust Approximation and the Arity Barrier at Width Two

Abstract: Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint languages, Barto and Kozik proved that robust approximability is characterized by bounded width. We ask whether arity-independent robustness persists beyond width one and show that it fails already at width two. For Majority-closed Boolean linear constraints of maximum arity $k \ge 2$, we give a randomized polynomial-time algorithm that, without knowing $\varepsilon$, violates an expected $O(\sqrt{\varepsilon \log k})$ fraction of the constraint weight on $(1-\varepsilon)$-satisfiable instances. Under the Unique Games Conjecture (UGC), a matching NP-hardness lower bound of $Ω(\sqrt{\varepsilon \log k})$ holds in an explicit parameter regime. Under this assumption, the bounded-width characterization therefore does not extend uniformly to constraints of unbounded arity. The algorithm rounds a degree-eight Sum-of-Squares (SoS) relaxation with a single Gaussian threshold. Since polynomial size alone does not make SoS solvable in polynomial bit complexity, we construct complete truncated Groebner bases for the soft Majority ideal and show that, at every fixed degree $2d$, the relaxation can be optimized to any rational accuracy in polynomial time with exactly feasible solutions, and degree-$2d$ SoS proofs can be found after an additive perturbation at degree at most $4d+10$. The lower bound combines Raghavendra's gap-to-hardness theorem with an integrality gap on a Gaussian star, analyzed via the Isaksson-Mossel theorem that parallel halfspaces maximize the joint membership probability of exchangeable Gaussians.

Tue 29 SeptComputational Complexity
The gist
The paper studies how well certain mathematical problems with many conditions can be approximated when they are mostly but not completely possible to solve. It shows that while earlier work found good approximation methods that work regardless of how many variables the problem has, this no longer holds true when problems have a certain structural complexity called width two. The authors provide an algorithm that works well up to a certain error margin but prove that improving this significantly is impossible under a major theoretical assumption. They also develop new mathematical tools to solve these problems more reliably and precisely.
Open → 2609.37417v1

Preferent compression bounds proven exactly right for safety guarantees

Preferent Compression Bounds Are Tight

Abstract: The lack of rigorous safety and performance certificates remains a key bottleneck to the deployment of modern learning-based methods. Sample compression has recently emerged as a powerful tool for deriving such certificates, with particularly sharp bounds available for algorithms satisfying a so-called preference property -- also known as stability in the learning theory literature. These bounds find direct application across domains as different as the Scenario Approach, Pick-to-Learn, and Support Vector methods. However, whether they are tight has remained an open problem. In this paper we resolve this question affirmatively and show that the state-of-the-art bound for preferent compressions is provably tight. We establish this by exhibiting an explicit construction based on the uniform distribution and order statistics that attains the bound in the limit. Along the way, we also provide a considerably shorter and more accessible proof of this bound, requiring only elementary counting arguments and no infinite-dimensional duality.

Mon 28 SeptMachine Learning
The gist
Ensuring that machine learning methods are safe and reliable is hard because it’s tricky to prove how well they perform. One approach uses something called sample compression, which helps give safety certificates, especially when the algorithm follows a preference or stability rule. The authors show that the best-known mathematical limits for this kind of compression are exactly correct and cannot be improved. They also provide a simpler proof that doesn’t rely on complicated math, making the result easier to understand and verify.
Open → 2609.36030v1

Natural gradient step size estimation can be computationally hard

The cost of useful natural gradient updates

Abstract: What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction $\varepsilon$ of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is $Θ(\log(1/δ)/(p\varepsilon^2))$ for small $\varepsilon$, where $p$ scales rare-state probabilities and $δ$ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.

Sun 27 SeptMachine LearningInformation Theory
The gist
This paper looks at what is needed to make useful steps when updating models using the natural gradient method. The authors show that even when knowing the best direction to move, deciding how far to move can be very hard or costly, both in terms of computation and the number of samples needed. They support this with examples and complexity results, showing that sometimes finding a good step can be as difficult as solving tough problems in computer science. Their results highlight that knowing where to move in model space isn’t enough; how far to move carries the entire challenge.
Open → 2609.33499v1

Condition number limits efficiency in complex minimax problems

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

Abstract: We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $μ$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-envelope stationarity criterion and the same primal-dual initialization gap. Specifically, when $σ\ge\varepsilon$, the worst-case complexity of zero-respecting algorithms is $Θ(κLGσ^2\varepsilon^{-4})$ in the stated accuracy regime, where $κ=L/μ$, $G$ bounds the initial primal-dual gap, and $σ^2$ bounds the variance of a general unbiased first-order oracle. The lower bound is realized on a smooth problem class with a bounded dual box. Our construction routes each link of a nonconvex zero-chain through a dual gradient of magnitude proportional to $\varepsilon/\sqrtκ$, while an undiscovered primal coordinate prevents stationarity. It also yields the primal-gradient lower bound $Ω(LΔ(\sqrtκ\varepsilon^{-2}+κσ^2\varepsilon^{-4}))$ after combination with the known deterministic bound, where $Δ$ bounds the initial primal function gap.

Fri 25 SeptMachine Learning
The gist
This paper studies a mathematical challenge in certain optimization problems where two things compete, but one side behaves more predictably than the other. The authors show that a common measure affecting how quickly algorithms can solve these problems—the condition number—actually sets a fundamental speed limit. They prove that no algorithm following some natural rules can work faster than this limit under certain realistic conditions. This helps clarify when further improvements in algorithm efficiency might be possible and when they are not.
Open → 2609.30877v1

Stochastic contraction framework improves td learning convergence analysis

A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning

Abstract: Many iterative algorithms rely on bootstrapping. A variable is updated using a second, frozen copy as a target, which is periodically replaced with the updated variable. Majorize-minimize and inexact proximal-point methods share this structure, as does temporal-difference (TD) learning. However, existing convergence guarantees for scenarios that combine sampled updates with targets refreshed only every $K$ steps rely on the specific structure of the update, such as linear approximation or gradient-based inner steps, and on uniformly bounded sampling error. We instead model the sampled update as a stochastic operator on the parameter space, which reduces the analysis to a contraction argument that needs no gradient structure and allows the sampling error to grow with the iterates. Within this framework, we derive a finite-time bound for i.i.d. samples and any target-update period $K$. We show that the iterates converge geometrically in root mean square to a ball around the fixed point, provided the sensitivity to the frozen target is smaller than the contraction slack of the inner map. Existing deterministic frozen-target contraction and stochastic-gradient-type bounds follow as special cases of our framework, and simulations of TD learning reproduce the predicted contraction rate and scaling of the error floor with the step size.

Thu 24 SeptMachine Learning
The gist
Many methods that learn by updating estimates based on parts of themselves use a technique called bootstrapping, but analyzing how well this works when updates happen intermittently and with some randomness is hard. The authors model these updates as a kind of shrinking process called a stochastic contraction, which simplifies the analysis and allows for greater flexibility in errors growing with the learning steps. They prove the learning process converges steadily to near the correct answer under clear conditions. This general approach helps unify previous specific results and matches test simulations on temporal-difference learning.
Open → 2609.29961v1

Clipped SGD achieves faster and more accurate convergence bounds

Precise Convergence Speed of Clipped SGD

Abstract: We present a tightened convergence analysis of clipped gradient descent on $(L_0, L_1)$-smooth functions, with quantitative constants. Building on the ideas of Koloskova et al (2023), we refactor several case disjunctions to reveal the central role of a control of the bias derived from fundamental properties of $\ell_2$-projection, simplifying proofs. We also extend the domain of validity from $η\leq 1 / (9 β)$ to $η< 1 /β$ where $β= L_0 + c L_1$ for clipping constant $c$, which matches the more traditional analysis of smooth functions. We strengthen the convergence criterion from $\left( \min_{t < T} \mathbb{E}[\lVert \nabla f(x_t) \rVert_2] \right)$ to $\left( \frac{1}{T} \sum_{t < T} \mathbb{E}[\lVert \nabla f(x_t) \rVert_2] \right)$ with matching speed, and lower the final achievable loss from $\mathcal{O}(\min(σ^2/c, σ))$ to the more precise $6 \min(σ^2 /c, 3 σ)$.

Thu 24 SeptMachine Learning
The gist
When training machine learning models, a common technique is to adjust model settings gradually by following gradients. Sometimes these gradients are 'clipped' to avoid very large steps. This paper by the authors explains more precisely how this clipped gradient method converges towards a solution, improving on previous analyses. They provide clearer mathematical constants and conditions for stable training, and also improve the way we measure progress over many steps. This helps better understand and tune training to be both faster and more reliable.
Open → 2609.29458v1

Finding specific Nash equilibria in games is computationally hard

Finding a Positive Index Nash Equilibrium is PPADS-Complete

Abstract: Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].

Sun 20 SeptComputational ComplexityComputer Science and Game Theory
The gist
The paper shows that finding a special type of stable outcome called a Nash equilibrium with a positive index in certain two-player games is computationally difficult. Every such game has equilibria whose indices sum to one, but identifying exactly one with index +1 is proven to be hard. The authors’ result settles a previously open question by proving this problem is complete for a complexity class known as PPADS. This means that solving these games in this precise way is as hard as the hardest problems in that class.
Open → 2609.23879v1

Elementary proof shows balanced sign choices keep vectors small

An elementary proof of the Komlós conjecture

Abstract: We give an elementary proof of the Komlós conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ with $\|v_i\|_2\le1$ admit signs $\varepsilon_i\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i v_i\|_\infty\le36$. The proof uses only elementary combinatorial and probabilistic arguments and basic calculus.

Thu 17 SeptComputational Complexity
The gist
The paper solves a problem about balancing numbers attached to points in space so that when added up with plus or minus signs, their largest coordinate stays small. The authors provide an easier and more straightforward demonstration than before, showing that for any set of points within a unit size, it's always possible to pick plus or minus signs so their combined effect is limited by a specific number. The proof only uses basic math tools like elementary counting and probability, making it accessible and simpler.
Open → 2609.20979v1