We consider the problem of jointly learning a one-dimensional projection and a univariate function in high-dimensional Gaussian models. Specifically, we study predictors of the form $f(x)=\varphi^\star(\langle w^\star, x \rangle)$, where both the direction $w^\star \in \mathcal{S}_{d-1}$, the sphere of $\mathbb{R}^d$, and the function $\varphi^\star: \mathbb{R} \to \mathbb{R}$ are learned from Gaussian data. This setting captures a fundamental non-convex problem at the intersection of representation learning and nonlinear regression. We analyze the gradient flow dynamics of a natural alternating scheme and prove convergence, with a rate controlled by the information exponent reflecting the *Gaussian regularity* of the function $\varphi^\star$. Strikingly, our analysis shows that convergence still occurs even when the initial direction is negatively correlated with the target. On the practical side, we demonstrate that such joint learning can be effectively implemented using a Reproducing Kernel Hilbert Space (RKHS) adapted to the structure of the problem, enabling efficient and flexible estimation of the univariate function. Our results offer both theoretical insight and practical methodology for learning low-dimensional structure in high-dimensional settings.
论文检索
输入标题、作者或关键词，从 1,712 篇学术成果中精准定位
Optimization · Non-Convex
Sign-based optimization methods, such as SignSGD and Signum, have become essential for modern Deep Learning due to their 1) high performance 2) low memory footprint and 3) communication efficiency. Despite their success, these methods suffer from distinct limitations in the terminal phase of training: they decouple update mechanisms from gradient magnitudes and fail to account for parameter heterogeneity, often leading to oscillation rather than convergence. While switching to SGD represents a potential remedy, a naive "hard" switch is poorly useful due to learning rate mismatches, momentum buffer suboptimality, and the assumption of uniform parameter dynamics. In this work, we propose SoftSignum, a novel optimization method that implements a principled, smooth transition mechanism from sign-based updates to SGD, which adapts to individual parameter sensitivities. We provide a generalized theoretical framework guaranteeing convergence in stochastic non-convex settings relevant to Deep Learning and demonstrate empirically that SoftSignum effectively handles parameter heterogeneity, yielding superior convergence across diverse tasks, including LLM pretraining, compared to standard sign-based baselines.
Normative theories allow one to elicit key parts of a ML algorithm from first principles, which is crucial at a time of championed scrutiny for ML work. Direct Preference Optimization (DPO) cleverly bypasses reward modeling by making an explicit link with a specific normative model of human choice. Our paper elevates this connection to the full generality of DPO's normative framework. Getting there requires reworking social choice theory's textbook path for a better RLHF/ML fit. It elevates the connection to a remarkably broad viewpoint on preference optimization, considering the current panorama of DPO follow-ups. It also unveils unexpected riches for ML, chief among which the support for *non-convex* losses, the fact that *any* compliant ML analytical choice can be embedded with *any* human choice model, and a normative framework's umbrella wide enough to safeguard DPO's *extensions* (margins, length correction, ...). A *toy* experiment ``far away'' from the DPO crowd is given.
Deep Learning · Theory
Weak-to-strong generalization (W2SG) is the phenomenon in which a powerful student model, trained on labels produced by a weaker teacher, ultimately outperforms the teacher on the target task. In this work, we theoretically investigate how W2SG can arise via a generalized bias–variance decomposition under Bregman divergence. We show that the expected population risk gap between the student and the teacher is characterized by the expected misfit between the two models. Unlike earlier misfit-based analyses, our theory removes several restrictive assumptions, e.g., it does not require the student hypothesis class to be convex. Our results indicate that W2SG is more likely when the student effectively approximates the teacher's posterior mean. Specializing to squared loss, we provide a sufficient condition (illustrated through a concrete example) under which the student converges to its posterior mean teacher; in particular, increasing the student model size can ensure this convergence. For cross-entropy loss, our analysis further suggests that lowering the entropy of the student's predictive distribution can promote W2SG. We also find that the reverse cross-entropy, unlike the standard forward cross-entropy, is less sensitive to the teacher's predictive uncertainty. Finally, we verify these theoretical insights empirically and demonstrate that incorporating reverse cross-entropy consistently improves student performance.
Deep Learning · Generative Models and Autoencoders
Generative modeling within constrained sets is essential for scientific and engineering applications involving physical, geometric, or safety requirements (e.g., molecular generation, robotics). We present a unified framework for constrained diffusion models on generic nonconvex feasible sets $\Sigma$ that simultaneously enforces equality and inequality constraints throughout the diffusion process. Our framework incorporates both overdamped and underdamped dynamics for forward and backward sampling. A key algorithmic innovation is a computationally efficient landing mechanism that replaces costly and often ill-defined projections onto $\Sigma$, ensuring feasibility without iterative Newton solves or projection failures. By leveraging underdamped dynamics, we accelerate mixing toward the prior distribution, effectively alleviating the high simulation costs typically associated with constrained diffusion. Empirically, this approach reduces function evaluations and memory usage during both training and inference while preserving sample quality. On benchmarks featuring equality and mixed constraints, our method achieves comparable sample quality to state-of-the-art baselines while significantly reducing computational cost, providing a practical and scalable solution for diffusion on nonconvex feasible sets.
General Machine Learning · Representation Learning
Auto-regressive models have emerged as powerful tools for sequential data, from language to video. Understanding how and why these models learn latent representations remains an open theoretical question. In this work, we demonstrate that when trained by empirical risk minimization on data from partially observed linear dynamical systems, two-layer linear auto-regressive models naturally learn to approximate Kalman filtering. In particular, we show that the learned hidden representation coincides, up to a similarity transformation, with the state estimates produced by the optimal (Kalman) filter, even though the model has no explicit knowledge of the underlying dynamics or state. The result follows from three main insights. First, we establish that the Kalman filter is well approximated by an auto-regressive model with bounded truncation error. Second, we show that despite non-convexity, the two-layer optimization landscape is benign, i.e., all stationary points are either strictly saddle or global minima. Finally, as our main contributions, we provide finite-sample guarantees on prediction error, parameter estimation error, and latent state recovery. Numerical simulations support the theoretical results and demonstrate that auto-regressive models automatically represent latent state estimates.
General Machine Learning · Everything Else
The Tensor Nuclear Norm (TNN), derived from the tensor singular value decomposition, is a widely used low-rank modeling tool that enforces element-wise sparsity on frequency-domain singular values. However, as a direct extension of the matrix nuclear norm, TNN fundamentally assumes single-level spectral sparsity, which is misaligned with the multi-level spectral structures prevalent in real-world data, where low-rankness within frequency components coexists with sparsity across them. To overcome this limitation, we propose the tensor $\ell_p$-Schatten-$q$ quasi-norm ($p,q\in(0,1]$), which enables explicit control of dual spectral sparsity by jointly regularizing inter-frequency sparsity and intra-frequency low-rankness. This formulation strictly generalizes TNN and subsumes several existing tensor regularizers by coupling global frequency sparsity with local spectral low-rankness, leading to a fundamentally different modeling principle. We establish the first minimax error bounds under this model and develop an efficient reweighted optimization algorithm for the resulting nonconvex problem. Numerical experiments on noisy and Poisson tensor completion as well as image clustering demonstrate the effectiveness and robustness of our method across reconstruction and representation learning tasks involving complex multi-way data.
Probabilistic Methods · Monte Carlo and Sampling Methods
Approximation of a target probability distribution using a finite set of points is a problem of fundamental importance in numerical integration. Several authors have proposed to select points by minimising a maximum mean discrepancy (MMD), but the non-convexity of this objective typically precludes global minimisation. Instead, we consider the concept of \emph{stationary points of the MMD} which, in contrast to points globally minimising the MMD, can be accurately computed. Our main contributions are two-fold and theoretical in nature. We first prove the (perhaps surprising) result that, for integrands in the associated reproducing kernel Hilbert space, the numerical integration error of stationary MMD points vanishes \emph{faster} than the MMD. Motivated by this \emph{super-convergence} property, we consider MMD gradient flows as a practical strategy for computing stationary points of the MMD. We then prove that MMD gradient flow can indeed compute stationary MMD points, based on a refined convergence analysis that establishes a novel non-asymptotic finite-particle error bound.
General Machine Learning · Evaluation
Conditional generative models have recently achieved remarkable success in various applications. However, a suitable metric for evaluating the reliability of these models, which takes into account their inherent uncertainty, is still lacking. Existing metrics, which typically assess a single output, may fail to capture the variability or potential risks in generation. In this paper, we propose a novel evaluation metric called \emph{reliability score} based on conformal prediction, which measures the worst-case performance within the prediction set at a pre-specified confidence level. However, computing this score is challenging due to the high-dimensional nature of the output space and the nonconvexity of both the metric function and the prediction set. To efficiently compute this score, we introduce Conformal ReLiability (CReL), a framework that can \textbf{(i)} construct the prediction set with desired coverage; and \textbf{(ii)} accurately optimize the reliability score within the constructed prediction set. We provide theoretical results on coverage and demonstrate empirically that our method produces more informative prediction sets than existing approaches. Experiments on synthetic data and the image-to-text and text-to-image tasks further demonstrate the interpretability of our new metric, and the validity and effectiveness of our computational framework.
Deep Learning · Graph Neural Networks
We present a differentiable optimization framework for multi-agent coordination. An input is decomposed into overlapping local views, each processed by an agent that solves a convex subproblem parametrized by a neural encoder. Agents coordinate through the Alternating Direction Method of Multipliers (ADMM) with inter-agent constraints specified by a cellular sheaf. The sheaf specifies which aspects of neighboring solutions must agree. Backpropagating through the unrolled optimization jointly trains encoders, decoders, and sheaf structure. We evaluate on maze pathfinding, image classification, and Sudoku, where agents with individually insufficient local views coordinate to produce correct global outputs. We show that this locality also yields improved robustness to distribution shifts (padding, missing patches, and noise) when evaluated against a standard CNN on MNIST, while exposing interpretable primal/consensus/dual variables that make the coordination dynamics directly inspectable.
Optimization · Non-Convex
Estimating statistical parameters from quantized data has received significant attention in recent years, as recovering information from quantized measurements has numerous applications across signal processing, communications, and data analysis. In this work, we focus on maximum likelihood (ML) estimation of statistical parameters from quantized samples. Directly solving the ML problem is challenging, as the likelihood function involves multiple integrals that are difficult to evaluate. To address this challenge, we propose an expectation-conditional-maximization (ECM) algorithm under a general distributional framework. Our approach generalizes the quantization model to multi-bit settings and allows the underlying signal to follow any distribution within the normal mean-variance mixture family. By designing suitable surrogate functions, the ECM algorithm ensures that all model parameters can be updated in closed form at each iteration. Leveraging the ECM framework, we provide convergence guarantees, and under specific distributional assumptions, we further derive bounds on the convergence rate and the statistical error. Extensive experiments demonstrate the effectiveness of our method in recovering statistical parameters from quantized data.
Optimization · Large Scale, Parallel and Distributed
This paper considers decentralized optimization of convex functions with mixed affine equality constraints involving both local and global variables. Constraints on global variables may vary across different nodes in the network, while local variables are subject to coupled and node-specific constraints. Such problem formulations arise in machine learning applications, including federated learning and multi-task learning, as well as in resource allocation and distributed control. We analyze this problem under smooth and non-smooth assumptions, considering both strongly convex and general convex objective functions. Our main contribution is an optimal algorithm for the smooth, strongly convex regime, whose convergence rate matches established lower complexity bounds. We further provide near-optimal methods for the remaining cases.
Reinforcement Learning · Batch/Offline
Offline reinforcement learning (RL) aims to optimize policies from pre-collected datasets. A bottleneck of this paradigm is managing epistemic uncertainty, which arises from limited data coverage (sample-level) and the ambiguity in identifying transition dynamics from finite data (model-level). To provide a unified quantification of these uncertainties, Bayesian RL has been proposed by treating the dynamics model as a random variable and maintaining a corresponding belief. Despite its theoretical appeal, policy optimization in Bayesian RL remains computationally challenging as it requires solving composite objectives with expectations. Prior methods either employ search-based techniques with poor computational scalability or impose restrictive posterior assumptions that sacrifice the adaptability of Bayesian RL. To address these limitations, we propose Posterior Hybrid Bayesian Belief (PhyB), which reformulates the expectation as a convex combination over a subset of dynamics models. Theoretical analysis demonstrates that the objective discrepancy induced by this approximation remains bounded. Based on PhyB, we develop an iterative regularized policy optimization algorithm that provides metric-agnostic guarantees for monotonic improvement until convergence. Empirical results demonstrate that PhyB achieves state-of-the-art performance on various benchmarks.
Deep Learning · Large Language Models
Convexity recognition plays a central role in many optimization, control, and learning problems. However, the ability of Large Language Models (LLMs) to identify this property in symbolic expressions remains unexamined. We introduce \cb, a scalable and mechanically verifiable benchmark for testing whether LLMs can determine the convexity of a symbolic objective under deep functional composition. Experiments on frontier LLMs reveal a sharp \textit{compositional reasoning gap}: performance degrades rapidly with increasing depth, dropping from an F1-score of $1.0$ at depth $2$ to approximately $0.2$ at depth $100$. Inspection of models' reasoning traces indicates two failure modes: \textit{parsing failure} and \textit{lazy reasoning}. To address these limitations, we propose an agentic divide-and-conquer framework that (i) offloads parsing to an external tool to construct an abstract syntax tree (AST) and (ii) enforces recursive reasoning over each intermediate sub-expression with focused context. This framework reliably mitigates deep-composition failures, achieving substantial performance improvement at large depths (e.g., F1-Score $= 1.0$ at depth $100$).
Deep Learning · Theory
Kolmogorov--Arnold Networks (KANs) have recently emerged as a structured alternative to standard MLPs, yet a principled theory for their training dynamics, generalization, and privacy properties remains limited. In this paper, we analyze gradient descent (GD) for training two-layer KANs and derive general bounds that characterize their training dynamics, generalization, and utility under differential privacy (DP). As a concrete instantiation, we specialize our analysis to logistic loss under an NTK-separable assumption, where we show that polylogarithmic network width suffices for GD to achieve an optimization rate of order $1/T$ and a generalization rate of order $1/n$, with $T$ denoting the number of GD iterations and $n$ the sample size. In the private setting, we characterize the noise required for $(\epsilon,\delta)$-DP and obtain a utility bound of order $\sqrt{d}/(n\epsilon)$ (with $d$ the input dimension), matching the classical lower bound for general convex Lipschitz problems. Our results imply that polylogarithmic width is not only sufficient but also necessary under differential privacy, revealing a qualitative gap between non-private (sufficiency only) and private (necessity also emerges) training regimes. Experiments further illustrate how these theoretical insights can guide practical choices, including network width selection and early stopping.
Social Aspects · Privacy
In machine unlearning, $(\varepsilon,\delta)-$unlearning is a popular framework that provides formal guarantees on the effectiveness of the removal of a subset of training data, the \emph{forget set}, from a trained model. For strongly convex objectives, existing first-order methods achieve $(\varepsilon,\delta)-$unlearning, but they only use the forget set to calibrate injected noise, never as a direct optimization signal. In contrast, efficient empirical heuristics often exploit the forget samples (e.g., via gradient ascent) but come with no formal unlearning guarantees. We bridge this gap by presenting the Variance-Reduced Unlearning (*VRU*) algorithm. To the best of our knowledge, *VRU* is the first first-order algorithm that directly includes forget set gradients in its update rule, while provably satisfying $(\varepsilon,\delta)-$unlearning. We establish the convergence of *VRU* and show that incorporating the forget set yields strictly improved rates, *i.e.*, a better dependence on the achieved error compared to existing first-order $(\varepsilon,\delta)-$unlearning methods. Moreover, we prove that, in a low-error regime *VRU* asymptotically outperforms any first-order methods that ignores the forget set. Experiments corroborate our theory, showing consistent gains over both state-of-the-art certified unlearning methods and over empirical baselines that explicitly leverage the forget set.
Optimization · Stochastic
Stochastic Frank-Wolfe is a classical optimization method for solving constrained optimization problems. On the other hand, recent optimizers such as Lion and Muon have gained quite significant popularity in deep learning. In this work, building on recent initiatives, we provide a unifying perspective by interpreting these seemingly disparate methods through the lens of Stochastic Frank-Wolfe. Specifically, we show that Lion and Muon with weight decay can be viewed as special instances of a Stochastic Frank-Wolfe, and we establish their convergence guarantees in terms of the Frank-Wolfe gap, a standard stationarity measure in non-convex optimization for Frank-Wolfe methods. We further find that convergence to this gap implies convergence to a KKT point of the original problem under a norm constraint for Lion and Muon. Moreover, motivated by recent empirical findings that stochastic gradients in modern machine learning tasks often exhibit heavy-tailed distributions, we extend Stochastic Frank-Wolfe to settings with heavy-tailed noise by developing two robust variants with strong theoretical guarantees that hold for general compact convex sets without the need for a large batch size, filling the gap in the literature on Stochastic Frank-Wolfe for non-convex optimization. Our contributions in the later part of this work, in turn, yield new variants of Lion and Muon, that better accommodate heavy-tailed gradient noise, thereby enhancing their practical scope.
Optimization · Large Scale, Parallel and Distributed
Federated learning~(FL) across multiple HPC facilities faces stochastic \emph{admission delays} from batch schedulers that dominate wall-clock time. Synchronous FL suffers from severe stragglers, while asynchronous FL accumulates stale updates when queues spike. We propose \fedqueue{}, a queue-aware FL protocol that incorporates scheduler delays directly into training and aggregation, which (i) predicts per-facility queue delays online to budget local work, (ii) applies cutoff-based admission that buffers late arrivals to bound staleness, and (iii) performs staleness-aware aggregation to stabilize heterogeneous local workloads. We prove the convergence for non-convex objectives at rate $\mathcal{O}(1/\sqrt{R})$ under bounded staleness, and show that the admission controls yield bounded staleness with high probability under queue-prediction error. Real-world cross-facility deployment of \fedqueue{} shows 20.5\% improvement over baseline algorithms. Controlled queue simulations demonstrate robust improvement over the baselines; in particular, about 34\% reduction in time to reach a target accuracy level under high queue variance and non-IID partitions.
Optimization · Non-Convex
Recent developments in deep learning optimization have brought about radically new algorithms based on the Linear Minimization Oracle (LMO) framework, such as Muon and Scion. After over a decade of Adam's dominance, these LMO-based methods are emerging as viable replacements, offering several practical advantages such as improved memory efficiency, better hyperparameter transferability, and most importantly, superior empirical performance on large-scale tasks, including LLM training. However, a significant gap remains between their practical use and our current theoretical understanding: prior analyses (1) overlook the layer-wise LMO application of these optimizers in practice, and (2) rely on an unrealistic smoothness assumption, leading to impractically small stepsizes. To address both, we propose a new LMO-based framework called Gluon, capturing prior theoretically analyzed methods as special cases, and introduce a new refined generalized smoothness model that captures the layer-wise geometry of neural networks, matches the layer-wise practical implementation of Muon and Scion, and leads to state-of-the-art convergence guarantees. Our experiments with NanoGPT and CNN confirm that our assumption holds along the optimization trajectory, ultimately closing the gap between theory and practice.
Optimization · Non-Convex
MARS has recently emerged as a state-of-the-art optimizer, consistently outperforming AdamW in large language model (LLM) training. It modifies the momentum-based variance reduction (MVR) update by introducing a multiplicative coefficient $\gamma$, which scales the momentum correction term. However, the existing theory of Yuan et al. (2025) does not explain why this modification improves the convergence of MARS over MVR. In this paper, we provide a rigorous theoretical explanation for the superiority of MARS over MVR. We introduce the novel similarity condition, called **$\gamma$-similarity**, which generalizes standard similarity and smoothness assumptions for analyzing stochastic algorithms. Under this condition, we derive gradient complexity guarantees for MARS, which explicitly depend on $\gamma$ and a $\gamma$-similarity constant $\delta_\gamma$. We prove that by appropriately tuning $\gamma \in [0,1]$, MARS achieves strictly lower complexity than MVR. Finally, experiments on GPT pretraining corroborate our theoretical findings, demonstrating that MARS with an optimal choice of $\gamma$ improves token efficiency over MVR, and yields substantial gains compared to AdamW.