Papers for

optimization algorithm developers

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.

Neural network size estimates improved by counting parameter symmetries

Sharp Covering-Number Bounds for Feedforward ReLU Networks via Parameter Symmetries

Abstract: In neural networks, distinct parameter configurations often realize the same input--output mapping, indicating that nominal parameter counts can overstate functional complexity. In this paper, we characterize the parameter-space symmetries of ReLU and Leaky ReLU networks across fully connected, convolutional, and residual architectures. We prove that every quasianalytic parameter map preserving the network function is a composition of positive channel scaling and channel permutation. By quotienting out both symmetries, we derive uniform covering-number upper bounds in which positive scaling reduces the complexity exponent from the total parameter count $S$ to $S-H$ (with $H$ denoting the number of scalable channels) and permutation symmetry divides the bound by the factorial count $G$ of channel permutations. We establish matching lower bounds showing that the exponent $S-H$ is sharp in general and that the divisor $G$ is attained for one-hidden-layer and generically identifiable networks. We further extend these results to general continuous piecewise-linear activated networks. Finally, we apply our covering-number bounds to derive statistical risk guarantees for empirical risk minimization and capacity control beyond i.i.d.\ settings, and show how the underlying symmetries help explain weight rebalancing in function approximation and flat directions in empirical risk optimization.

Wed 11 NovMachine Learning
The gist
Neural networks often have many different ways to adjust their settings that end up producing the same results. The authors studied these overlaps to better understand how complex a network really is. They found exact ways to count how much simpler a network’s true complexity is when accounting for these duplicate parameter settings. Their findings help explain why certain changes in neural network training don’t affect the output, potentially improving the way networks are designed and analyzed.
Open → 2611.15300v1

Dual-space preconditioning improves solving variational inequalities and roots

Dual-Space Preconditioning for Variational Inequalities and Root-Finding Problems

Abstract: This paper develops a dual-space preconditioning framework for variational inequalities and root-finding problems beyond classical cocoercivity and Lipschitz continuity assumptions. To this end, we introduce both a novel cocoercivity-type condition and a relaxed Lipschitz continuity condition, and derive convergence of deterministic and stochastic methods under these generalized conditions. For isotropic preconditioners, the resulting algorithms can be interpreted as variable-stepsize variants of classical methods, extending recent analyses based on $(L_0, L_1)$-type growth conditions while allowing simpler proofs and larger stepsize ranges. We also show that the framework naturally handles variational inequalities through weak Minty-type arguments. Finally, we study the associated continuous-time dynamics and derive a variational and optimal control interpretation of the preconditioned flow. Overall, the results show that dual-space preconditioning provides a flexible mechanism for designing and analyzing operator methods beyond the standard Euclidean Lipschitz setting.

Tue 10 NovMachine Learning
The gist
Finding solutions to certain math problems, like where a function equals zero or satisfies some inequality, often uses assumptions that limit how those problems behave. The authors introduce a new way to relax these assumptions, making algorithms work under broader conditions. They show that their methods converge reliably and can be seen as improved versions of known approaches with adaptable step sizes. Additionally, they link these methods to continuous processes and control theory to better understand their behavior.
Open → 2611.13916v1

Finite spectral depth changes early neural net training paths

Finite Spectral Depth Controls Gaussian Entrance Rank and Avoidance of the First Gradient-Flow Saddle

Abstract: Matrix factorization provides a simple model for studying the training dynamics of neural networks. Recent studies of gradient flow under small initialization have analyzed how trajectories escape from a neighborhood of the origin and approach their first nonzero stationary point. In this paper, we study continuous-time dynamics that applies a finite number of Newton-Schulz iterations to the normalized matrix gradient (Muon). We show that the number of Newton-Schulz steps can change the rank selected during the early stages of training and allow the resulting trajectory to bypass the first nonzero stationary point approached by gradient flow. Under an additional residual-inertia condition, we prove that bypass occurs for all sufficiently large finite Newton-Schulz depths and provide an explicit sufficient threshold. We also construct an example in which the bypass threshold is four.

Tue 3 NovMachine Learning
The gist
Training neural networks often involves slowly changing matrices from simple starting points. This paper studies a method that adjusts these changes using a set number of mathematical steps called Newton-Schulz iterations. The authors found that by changing how many steps are used early on, you can steer the training process to skip certain sticking points and select simpler structures in the matrix. They also proved conditions under which these skips happen and gave an example where just four steps are enough to bypass the usual training pause.
Open → 2611.05022v1

New equations better capture real gradient descent learning dynamics

Stochastic learning flow: moment equations for stochastic gradient descent at finite step size

Abstract: Analytical theories of learning in deep networks often assume gradient flow, discarding the finite step size and batch noise of stochastic gradient descent (SGD). Starting from the discrete update, we derive continuous-time equations for the mean and covariance of the parameter distribution under a Gaussian closure for a general stochastic learning, to first order in the learning rate $η$. Applying these stochastic learning flow (SLF) equations to SGD, we show that the mean descends an effective loss regularized by the covariance and loss curvature, while the covariance, unlike in stochastic differential equation approximations, becomes unstable at curvature $2/η$. In SGD ensembles of linear and nonlinear networks, SLF predicts learning curves and mean trajectories more accurately than gradient flow and captures the covariance dynamics, failing where the parameter distribution becomes strongly non-Gaussian. In the full-batch limit, the edge of stability corresponds to a stationary point of the coupled sharpness-covariance dynamics, recovering self-stabilization and central flow, and batch-to-batch curvature fluctuations lower this threshold under SGD.

Fri 30 OctMachine Learning
The gist
Deep learning often assumes smooth changes in model training, ignoring the effects of step sizes and randomness in updates. The authors derived new equations that model how parameters and their variations evolve during stochastic gradient descent more accurately. These equations reveal when learning becomes unstable and explain why real training behaves differently than idealized continuous models. Their work helps predict learning progress and instability better than previous simpler models.
Open → 2611.00473v1

Improved newton boosting method with better convergence and adaptivity

Affine-invariant Cubic Newton with Weak Learners

Abstract: Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global $\mathcal{O}(1/γ^{12}k^2)$ rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy $γ^{12}$ dependence on a worst-case `weak gradient edge' $γ$. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values $\overlineΘ_k$ along the optimization path and directional improvements $δ_k$ in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by $δ_k$. Under semi-strong self-concordance, we establish a global $\mathcal{O}(1/\overlineΘ_k^4 k^2)$ rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.

Sat 24 OctMachine Learning
The gist
Boosting methods in machine learning often use Newton's method but sometimes fail to guarantee steady progress. The authors develop a new mathematical approach that improves how these methods converge to good solutions by considering geometric factors more carefully. Their method adapts its steps automatically and works better with less ideal 'weak learners'. They also show their approach includes other optimization techniques as special cases.
Open → 2610.33516v1

Stochastic gradient descent converges in deep linear neural networks

Convergence of stochastic gradient descent for learning linear neural networks

Abstract: Stochastic gradient descent (SGD) is the cornerstone of modern deep learning, yet its theoretical convergence properties remain poorly understood in non-convex settings. To address this gap, we study SGD dynamics in deep linear neural networks - simplified models that retain key non-convex characteristics while remaining analytically tractable. Building on recent results for gradient descent, we extend convergence guarantees to SGD under regularized squared loss. We establish almost sure boundedness of SGD iterates. Using the framework of asymptotic pseudotrajectories from stochastic approximation theory, our analysis establishes then, for both deterministic and adaptive step-size choices, convergence of SGD to the set of critical points under mild conditions (without relying on Lipschitz properties or whitened data). To our knowledge, this is the first work providing almost sure convergence guarantees for SGD in deep linear networks, bridging the gap between theoretical optimization and practical stochastic training.

Tue 20 OctMachine Learning
The gist
Stochastic gradient descent (SGD) is widely used to train deep learning models, but it’s hard to understand exactly how and why it works, especially with complicated models. The authors studied a simpler type of neural network called deep linear networks, which are easier to analyze but still share some real challenges. They proved that when using SGD with certain conditions, the process will reliably get closer to stable points where learning doesn’t improve anymore. This work helps bridge the gap between theoretical math and practical training of neural networks.
Open → 2610.28561v1

Deterministic optimization costs scale poorly under low curvature trace

Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

Abstract: Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding $\varepsilon$-stationary points of $L$-smooth nonconvex functions on $\mathbb{R}^d$ from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most $LE$; this is the effective rank condition used to explain zeroth-order fine-tuning. When $ET\le d$, the Gaussian two-point method that such fine-tuning uses needs only $O(ET)$ calls if it rejects steps that raise $f$, where $T=LΔ/\varepsilon^2$ is the iteration count of gradient descent from initial gap $Δ$, and we prove that every randomized method needs $Ω(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetildeΩ(d\min\{T,\sqrt{ET}\})$ calls, and adaptive subspace search attains $O(d\min\{T,\sqrt{ET}\})$: a deterministic method pays about $d$ calls per discovered direction, and the trace budget allows about $\sqrt{ET}$ directions. Determinism thus multiplies the cost by a factor of order $d/(E+\sqrt{ET})$ up to logarithmic factors, which grows linearly with $d$ for fixed $E$ and $T$; once $E$ exceeds $T$ by a logarithmic factor, deterministic methods need $Ω(dT)$ calls, as without any trace budget. Our lower bounds hold for $C^\infty$ functions with the matrix bound on all of $\mathbb{R}^d$, even when each call also returns gradient projections priced by rank.

Tue 20 OctMachine Learning
The gist
Finding points where smooth but complex functions don't change much (called stationary points) can be done using random guesses more efficiently than using fixed, predictable steps. The authors show that when the function has a special low-rank structure, randomized methods can find these points much faster, while deterministic methods require many more function calls. This means that if you want to avoid randomness, you’ll have to spend a lot more effort, especially in high dimensions. Their work proves that this large difference in cost is unavoidable.
Open → 2610.27550v1

Two hidden layers suffice to compute maximum of many inputs

Two hidden layer suffice: the caterpillar net

Abstract: Every continuous piecewise linear (CPWL) function is a finite signed sum of maxima of affine functions, making maximum representation a central problem in the study of the expressiveness of ReLU networks. A now-disproved conjecture predicted logarithmic depth for maxima. Inspired by the proof by Brunck et al. (2026) that two hidden layers suffice for general CPWL functions, we give the Caterpillar Net, a nonrecursive construction for the maximum of $N$ inputs with two hidden layers of widths $O(N^2)$ and $2^{O(N\log N)}$. The construction has a direct geometric interpretation.

Mon 19 OctMachine Learning
The gist
Figuring out the maximum value from many inputs is important in understanding certain neural networks. The authors present a new design, called the Caterpillar Net, that calculates this maximum using only two layers of neurons. Their method uses a specific construction and has a clear geometric meaning. This confirms earlier work showing two layers are enough, but this approach is simpler and nonrecursive.
Open → 2610.26795v1

Deep network training converges better with noise and wider layers

Global Convergence in Deep Networks via the Second Law of Thermodynamics

Abstract: Existing convergence analyses of finite-width overparameterized deep neural networks under standard parameterization often rely on parameters remaining close to their initialization and typically neglect the role of noise, despite empirical evidence that stochasticity can improve optimization and generalization. To bridge this gap, we study $L_2$-regularized continuous-time Langevin dynamics (CLD) with isotropic noise, for training feedforward networks with smooth activations. We introduce a change-of-measure inequality, inspired by the second law of thermodynamics, that enables control of key properties of the training dynamics under the time-evolving parameter distribution. Leveraging a sharpened lower bound on the minimum eigenvalue of the Neural Tangent Kernel (NTK) at initialization, we show that injected noise helps preserve NTK stability with high probability without confining the weights to a small neighborhood of their initialization. As a result, we derive a non-asymptotic upper bound on the expected training loss. Our analysis yields explicit conditions on width and noise temperature that guarantee convergence to a finite loss floor. Finally, we experimentally show the network Jacobian can change from initialization, departing the commonly analyzed lazy regime.

Sat 17 OctMachine Learning
The gist
Training very large deep neural networks usually assumes the parameters don’t move far from where they start, but in reality, noise during training helps improve performance. The authors studied a training process that adds controlled noise to the network parameters and found that this noise helps keep key features stable even as the parameters change significantly. This stability allows the network to learn better without being stuck close to its starting state. Their math shows how wide the network needs to be and how much noise to add for training to reliably improve.
Open → 2610.24775v1

Zeroth-order nonconvex optimization lower bounds match theory limits

On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

Abstract: Recent work has sought to transfer first-order nonconvex optimization guarantees to zeroth-order methods through gradient estimators, typically incurring a factor linear in $d$. \citet{kornowski2024} obtained an $\mathcal{O}(dδ^{-1}ε^{-3})$ oracle complexity for nonsmooth nonconvex optimization and asked whether its dependence on all three parameters is jointly optimal. Although the dimension dependence and the first-order dependence on $(δ,ε)$ are separately known to be unavoidable, a matching zeroth-order lower bound has remained open. We answer this question in the unrestricted full-space setting. For smooth stochastic nonconvex optimization, we establish a scalar-oracle lower bound of $Ω\!\left(dL_0^2\min\{ΔH,L_0^2\}/ε^4\right)$ assuming a smooth, globally lower-bounded population objective and a second-moment bound on sample Lipschitz constants. A smooth reduction then yields a lower bound for Goldstein stationarity, proving the joint minimax optimality of the dependence on $(d,δ,ε)$ under explicit high-dimensional and small-accuracy conditions. Crucially, our results allow algorithms to query arbitrary points in $\mathbb{R}^d$, adaptively select sample-function labels, reuse the same sampled function at any number of locations, and output points without spatial restrictions. Thus, unlike lower bounds based on bounded query regions or fresh evaluation noise, our guarantees apply to a fully adaptive, reusable-sample scalar oracle. We also establish a separate noiseless exact-value lower bound against randomized algorithms, and hence also against deterministic methods. Our proof combines a globally defined sequential nonconvex construction with an exact Gaussian scalar channel, multistage random-field estimates, and an antithetic finite-sample realization that preserves information hardness under adaptive reuse.

Wed 14 OctMachine Learning
The gist
Optimizing complex functions without knowing their gradients is harder and often slower. The authors show the best possible lower bounds on how many function evaluations are needed for such problems when using zeroth-order methods, which rely only on function values. They prove that this difficulty grows linearly with the number of dimensions, and depends tightly on the desired accuracy and smoothness. Their results apply even in flexible settings where algorithms can adapt and reuse samples, settling an open question about the fundamental limits of these methods.
Open → 2610.19652v1

Randomized methods have provable limits in convex set optimization

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

Abstract: Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $Ω(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. 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 further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.

Fri 9 OctMachine Learning
The gist
Optimizing complex problems with linear minimization oracles (LMOs) is important in machine learning and other fields. Previous work showed worst-case performance limits for certain LMO methods but didn’t fully account for randomized algorithms. The authors prove that even randomized first-order LMO methods face fundamental lower bounds on how fast they can optimize over strongly convex sets. Their findings clarify the best possible performance achievable and close gaps left by earlier results.
Open → 2610.13590v1

Comb inequality violation detection proven computationally hard

Separating comb inequalities is NP-hard

Abstract: Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in polyhedral combinatorics. We present a reduction from 3-SAT proving that deciding whether a comb inequality is violated is NP-complete and that the corresponding separation problem is NP-hard. This result holds even when the input vector belongs to the subtour elimination polytope, every edge value is zero, one half or one and the support graph is nonplanar with maximum degree four. The reduction constructs a graph in which six-vertex ladder gadgets encode Boolean relations and cubic graphs enforce consistency among occurrences of each logical variable. For a propositional logic formula with $v$ variables and $m$ clauses, the constructed graph has $40v+70m+30$ vertices and a linear number of positive edges. The reduction also proves hardness when every permitted tooth has two or four vertices with half of the tooth in the handle. We discuss consequences for approximating the maximum comb violation, optimization over the comb relaxation and explain why hardness of separation does not automatically transfer to larger inequality families.

Tue 6 OctComputational Complexity
The gist
Figuring out if certain mathematical rules, called comb inequalities, are broken in travel route problems is very difficult. The authors show that this problem is as hard as solving some of the toughest logic puzzles known. They build special graphs that mimic logic rules to prove their point. This means computers cannot quickly guarantee finding these rule violations in all cases. The result helps explain why some ways to improve route planning are challenging to automate.
Open → 2610.09065v1

Undercomplete linear autoencoders favor large decoder weights in training

Broken scale symmetries in undercomplete linear autoencoders

Abstract: Neural network loss landscapes have many symmetries, which are preserved by gradient flow but broken by finite-stepsize stochastic gradient descent (SGD). A canonical example of such a symmetry is scale in homogeneous networks: one can scale up the parameters in one layer and down in the next without changing the network output. Previous work has documented cases in which SGD breaks this symmetry in favor of balancing gradient noise or minimizing fluctuations. Here, we show that the solution geometry of undercomplete linear autoencoders instead selects a preferred sign for scale drift: on the PCA solution manifold, SGD favors large decoder weights. This directed scale drift occurs on a slow timescale, and its dynamics admit an analytically-tractable effective description. However, it cannot continue indefinitely: increasing scale eventually drives the dynamics towards a finite-stepsize stability boundary. The resulting solutions are sharper than a balanced baseline in the sense of the maximum eigenvalue of the loss Hessian, but different sharpness measures can move in opposing directions. Thus, undercomplete autoencoders give a concrete illustration of how loss geometry can convert residual gradient noise into directed motion along a manifold of functionally-equivalent solutions.

Fri 2 OctMachine Learning
The gist
Training certain neural networks called undercomplete linear autoencoders involves a kind of symmetry where changing scales of weights in connected layers doesn't change the output. This paper finds that the usual training method, stochastic gradient descent (SGD), tends to break this symmetry by pushing scale values in one direction, favoring larger weights in the decoder part. This change happens slowly and can be described with a clear mathematical model. However, this scaling can't increase indefinitely because of stability limits in training. The resulting solutions differ in certain technical measures of how sensitive they are to changes, showing how small randomness during training can cause steady changes in the network’s parameters without changing its function.
Open → 2610.03640v1

Decoded quantum interferometry breaks topological barriers in sampling

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

Abstract: We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $β_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when $D=αk$ with fixed $α>1$, both Prange's algorithm and DQI can sample at any inverse temperature $β< \tanh^{-1}(1/α)$ for sufficiently large $k$, well beyond the dynamical threshold $β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

Wed 30 SeptComputational ComplexityData Structures and Algorithms
The gist
Sampling from complex systems, like certain magnetic models, is hard because some barriers stop usual algorithms from working well. The authors show that a method called decoded quantum interferometry (DQI) can overcome these barriers where other stable algorithms fail. They connect the problem of sampling to a quantum decoding challenge and prove that DQI can work at lower temperatures where typical methods get stuck. This work highlights how quantum techniques can help solve problems that are difficult for classical algorithms.
Open → 2609.40345v1

Weak proximal oracles trade speed for complexity in convex optimization

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

Abstract: We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

Mon 21 SeptMachine Learning
The gist
The paper studies a special way to solve certain math problems that involve finding the best solution with some smooth or rough features. It focuses on methods that use a 'weak proximal oracle,' which is easier to run but less precise than the usual method. The authors found that while these easier oracles can speed up each step, they cannot fully match the fastest possible overall solving methods. They also provide a new approach that nearly matches traditional methods for nonsmooth problems using these weaker oracles.
Open → 2609.24423v1

Connections between quadratic transform and schur complement revealed

Connections Between Quadratic Transform for Fractional Programming and Schur Complement

Abstract: This paper shows that there are intimate connections between the quadratic transform technique for solving fractional programming (FP) problems and the Schur-complement technique in matrix analysis. We demonstrate that the quadratic transform technique is related to two aspects of the Schur complement: (i) the linear matrix inequality (LMI) condition for positive semidefiniteness and (ii) the matrix determinant formula. Specifically, we establish that the quadratic transform and the Schur-complement LMI condition imply each other. This connection allows us to provide new interpretations of the auxiliary variable in the quadratic transform, and it allows us to rederive the Schur-complement determinant formula. Furthermore, this connection leads to generalizations of the quadratic transform in FP and the Schur-complement LMI that can accommodate generalized matrix inverse. As an application in information theory, we apply the generalized FP framework to the least-favorable-noise minimax formulation of the Gaussian vector broadcast channel sum capacity problem. When the least-favorable noise covariance is singular, matrix-inverse-based Karush-Kuhn-Tucker (KKT) analysis would require a careful analysis of the input and output spaces of the channel. We show using generalized FP that an auxiliary-variable representation of the singular matrix fraction directly yields the reciprocal multiple-access channel and recovers the uplink-downlink duality relation for sum capacity.

Fri 18 SeptInformation Theory
The gist
This paper reveals a deep link between two mathematical techniques used in optimization and matrix analysis: the quadratic transform and the Schur complement. The authors show these methods are closely related, providing new ways to understand and generalize both. They apply this insight to a problem in information theory involving noisy communication channels, especially when certain matrices are singular and traditional methods struggle. This work offers a fresh perspective that simplifies complex calculations in such cases.
Open → 2609.21730v1