论文检索

Optimization · Non-Convex

Ying Chen, Aoxi Li, Javad Lavaei

Sharpness-Aware Minimization (SAM) empirically boosts generalization by seeking parameters that minimize the worst-case loss in a small neighborhood, yet existing theory explains its behavior under either strong convexity or small perturbation radius. We revisit SAM through the bilevel minimax problem $\min_{\theta}\max_{\|\Delta\|\le\rho}l(\theta+\Delta)$ and derive a $(\theta,\Delta)$ gradient flow ODE whose equilibria coincide with the problem’s optimality conditions. A Lyapunov argument—free of convexity assumptions—quantifies how the optimality gap depends on the radius~$\rho$ and local curvature. Discretizing the flow yields a \emph{Multi-step SAM} algorithm that recovers classical SAM as $\rho\!\to\!0$. {Moreover, our analysis and the resulting algorithm remain valid even for large $\rho$, providing principled guidance for aggressive neighborhood exploration.} Experiments on synthetic objectives and CIFAR-10 validate the predicted gains from multiple inner updates, bridging the gap between SAM’s minimax intuition and its practical implementation.

Optimization · Convex

Nicholas Di, Eric Chi, Samy Wu Fung

Operator splitting algorithms are a cornerstone of modern first-order optimization, decomposing complex problems into simpler subproblems solved via proximal operators. However, most functions lack closed-form proximal operators, which has long restricted these methods to a narrow set of problems. Hamilton-Jacobi-based proximal operator (HJ-Prox) is a recent derivative-free Monte Carlo technique based on Hamilton-Jacobi PDE theory, that approximates proximal operators numerically. In this work, we introduce a unified framework for operator splitting via HJ-Prox, which allows for deployment of operator splitting even when functions are not proximable. We prove that replacing exact proximal steps with HJ-Prox in algorithms such as proximal point, proximal gradient descent, Douglas–Rachford splitting, Davis–Yin splitting, and primal–dual hybrid gradient preserves convergence guarantees under mild assumptions. Numerical experiments demonstrate HJ-Prox is competitive and effective on a wide variety of statistical learning tasks.

Optimization · Stochastic

Egor Gladin, Alexey Kroshnin, Jia-Jie Zhu, Pavel Dvurechenskii

The LogSumExp function, dual to the Kullback-Leibler (KL) divergence, plays a central role in many important optimization problems, including entropy-regularized optimal transport (OT) and distributionally robust optimization (DRO). In practice, when the number of exponential terms inside the logarithm is large or infinite, optimization becomes challenging since computing the gradient requires differentiating every term. We propose a novel convexity- and smoothness-preserving approximation to LogSumExp that can be efficiently optimized using stochastic gradient methods. This approximation is rooted in a sound modification of the KL divergence in the dual, resulting in a new $f$-divergence called the *safe KL divergence*. Our experiments and theoretical analysis of the LogSumExp-based stochastic optimization, arising in DRO and continuous OT, demonstrate the advantages of our approach over existing baselines.

Theory · Optimization

Zusen Xu, Jia-Jie Zhu

We propose a mathematically principled PDE gradient flow framework for distributionally robust optimization (DRO). Exploiting the recent advances in the intersection of Monte Carlo sampling and statistical optimal transport, we show that our theoretical framework can be implemented as practical algorithms for sampling from worst-case distributions and, consequently, DRO. While numerous previous works have relied on dual reformulation techniques, we contribute a sound and complete gradient flow view based on SDEs or PDEs that can be used to construct new algorithms for general, potentially non-convex, losses. Without loss of generality, we solve a class of Wasserstein and entropy-regularized DRO problems using the recently-discovered Wasserstein Fisher-Rao and Stein variational gradient flows. Notably, we also show some simple reductions of our framework recover exactly previously proposed popular DRO methods, and provide new insights into their theoretical limits and optimization dynamics of DRO. Numerical studies based on stochastic gradient descent on machine learning tasks provide empirical backing for our theoretical findings.

Theory · Optimization

Anming Gu, Juno Kim

The mean-field Langevin dynamics (MFLD) minimizes an entropy-regularized nonlinear convex functional on the Wasserstein space over $\mathbb{R}^d$, and has gained attention recently as a model for the gradient descent dynamics of interacting particle systems such as infinite-width two-layer neural networks. However, many problems of interest have constrained domains, which are not solved by existing mean-field algorithms due to the global diffusion term. We study the optimization of probability measures constrained to a convex subset of $\mathbb{R}^d$ by proposing the \emph{mirror mean-field Langevin dynamics} (MMFLD), an extension of MFLD to the mirror Langevin framework. We obtain linear convergence guarantees for the continuous MMFLD via a uniform log-Sobolev inequality, and uniform-in-time propagation of chaos results for its time- and particle-discretized counterpart.

Jake Cunningham, Nicola Muca Cirone

Analyzing attention weights has become a standard approach for interpreting the information flow of Large Language Models (LLMs). However, this approach has significant limitations as it neglects the geometric properties of the value vectors being aggregated. To address this gap, we introduce \emph{Contribution Weights}, a projection-based metric that quantifies a token's influence by accounting for it's attention weight, value magnitude, and directional alignment with the layer output. We demonstrate that contribution weights provide a more faithful measure of token importance, consistently outperforming attention-based metrics in identifying semantically critical tokens across different models, tasks, and datasets. Further, our metric enables novel mechanistic analysis of \emph{attention sinks}. While previous work has characterized sinks as passive repositories for excess attention, we reveal they serve an active functional role, suppressing information through a convex relationship between sink rate and output norm, stabilizing representations by opposing the semantic drift of low-confidence tokens.

Jiachen Liu

Spectral clustering, a widely-used technique for graph-based data partitioning, faces a severe computational bottleneck due to its $O(n^{3})$ time complexity. While anchor-based approximations reduce the complexity to $O(nm^{2})$ ($m \ll n$), they often yield degenerate solutions in the absence of explicit cluster-size control. To address this limitation, we propose \textbf{SC-FAGC (Size-Constrained Fast Anchor Graph Clustering)}, a unified formulation that integrates entropy regularization and bilateral cardinality constraints within an anchor-based spectral clustering framework. Our model simultaneously promotes cohesive clusters and enforces soft lower and upper bounds on cluster sizes, thus avoiding trivial or highly unbalanced partitions. To solve the resulting non-convex optimization problem efficiently, we develop an \textbf{Iteratively Re-weighted (IRW)} optimization scheme, which sequentially linearizes the objective and solves each subproblem via a \textbf{Double-Bounded Optimal Transport (DB-OT)} solver based on the \textbf{Sinkhorn--Knopp} algorithm. This approach guarantees convergence while maintaining scalability. Extensive experiments on benchmark datasets demonstrate that SC-FAGC consistently achieves state-of-the-art performance in terms of accuracy, purity, and recall, while strictly satisfying the prescribed cluster-size constraints. Thus the proposed method offers a principled and scalable solution for large-scale graph clustering with controllable partition structure.

General Machine Learning · Supervised Learning

Mohamed Chiheb Yaakoubi, Cosme Louart, Malik TIOMOKO, Zhenyu Liao

We study high-dimensional convex empirical risk minimization (ERM) under general non-Gaussian data designs. By heuristically extending the Convex Gaussian Min–Max Theorem (CGMT) to non-Gaussian settings, we derive an asymptotic min–max characterization of key statistics, enabling approximation of the mean $\mu_{\hat{\theta}}$ and covariance $C_{\hat{\theta}}$ of the ERM estimator $\hat{\theta}$. Specifically, under a concentration assumption on the data matrix and standard regularity conditions on the loss and regularizer, we show that for a test covariate $x$ independent of the training data, the projection $\hat{\theta}^\top x$ approximately follows the convolution of the (generally non-Gaussian) distribution of $\mu_{\hat{\theta}}^\top x$ with an independent centered Gaussian variable of variance $\mathrm{tr}\!\big(C_{\hat{\theta}}\,\mathbb{E}[xx^\top]\big)$. This result clarifies the scope and limits of Gaussian universality for ERMs. Additionally, we prove that any $\mathcal{C}^2$ regularizer is asymptotically equivalent to a quadratic form determined solely by its Hessian at zero and gradient at $\mu_{\hat{\theta}}$. Numerical simulations across diverse losses and models are provided to validate our theoretical predictions and qualitative insights.

Optimization · Stochastic

Haeun Jeon, Seunghoon Choi, Hyunglip Bae, Yongjae Lee, Woo Chang Kim

Sparse tangent portfolio optimization aims to learn an interpretable, low-cardinality portfolio in the tangency direction of the mean–variance frontier, yet the associated cardinality-constrained formulation is NP-hard and standard predict-then-optimize pipelines often misalign forecasting accuracy with downstream portfolio quality. We propose an end-to-end decision-focused learning framework that reformulates Sharpe-ratio maximization as a Disciplined Parametrized Programming (DPP)-compliant convex programming layer and replaces discrete selection with a smooth top-k operator enforcing an exact sum-to-k sparsity budget. This enables gradient flow through prediction, asset selection, and re-optimization, allowing the predictive model to directly optimize the portfolio performance. Across five major equity markets, our method consistently delivers higher out-of-sample Sharpe ratios than historical and prediction-focused baselines while producing meaningful sparse selections.

Theory · Everything Else

Takuya Koriyama, Pratik Patil, Jin-Hong Du, Kai Tan, Pierre C Bellec

We characterize the squared prediction risk of ensemble estimators obtained through subagging (subsample bootstrap aggregating) regularized M-estimators and construct a consistent estimator for the risk. Specifically, we consider a heterogeneous collection of M?1 regularized M-estimators, each trained with (possibly different) subsample sizes, convex differentiable losses, and convex regularizers. We operate under the proportional asymptotics regime, where the sample size n, feature size p, and subsample sizes km for m?[M] all diverge with fixed limiting ratios n/p and km/n. Key to our analysis is a new result on the joint asymptotic behavior of correlations between the estimator and residual errors on overlapping subsamples, governed through a (provably) contractive nonlinear system of equations. Of independent interest, we also establish convergence of trace functionals related to degrees of freedom in the non-ensemble setting (with M=1) along the way, extending previously known cases for squared loss with ridge and lasso regularizers. When specialized to homogeneous ensembles trained with a common loss, regularizer, and subsample size, the risk characterization sheds some light on the implicit regularization effect due to the ensemble and subsample sizes (M,k). For any ensemble size M, optimally tuning subsample size yields sample-wise monotonic risk. For the full-ensemble estimator (when M??), the optimal subsample size k? tends to be in the overparameterized regime (k??min{n,p}), when explicit regularization is vanishing. Finally, joint optimization of subsample size, ensemble size, and regularization can significantly outperform regularizer optimization alone on the full data (without any subagging).

Theory · Optimization

Sharan Sahu, Cameron Hogan, Martin Wells

In this paper, we provide a comprehensive theoretical analysis of Stochastic Gradient Descent (SGD) and its momentum variants (Polyak Heavy-Ball and Nesterov) for tracking time-varying optima under strong convexity and smoothness. Our finite-time bounds reveal a sharp decomposition of tracking error into transient, noise-induced, and drift-induced components. This decomposition exposes a fundamental trade-off: while momentum is often used as a gradient-smoothing heuristic, under distribution shift it incurs an explicit drift-amplification penalty that diverges as the momentum parameter $\beta$ approaches 1, yielding systematic tracking lag. We complement these upper bounds with minimax lower bounds under gradient-variation constraints, proving this momentum-induced tracking penalty is not an analytical artifact but an information-theoretic barrier: in drift-dominated regimes, momentum is unavoidably worse because stale-gradient averaging forces systematic lag. Our results provide theoretical grounding for the empirical instability of momentum in dynamic settings and precisely delineate regime boundaries where vanilla SGD provably outperforms its accelerated counterparts.

Deep Learning · Large Language Models

Yuan Li, Bo Wang, Yufei Gao, Yuqian Yao, Xinyuan Wang, Zhangyue Yin, Xipeng Qiu

Proximal constraints are fundamental to the stability of the Large Language Model reinforcement learning. While the canonical clipping mechanism in PPO serves as an efficient surrogate for trust regions, we identify a critical bottleneck: fixed bounds strictly constrain the upward update margin of low-probability actions, disproportionately suppressing high-advantage tail strategies and inducing rapid entropy collapse. To address this, we introduce **Band-constrained Policy Optimization** (BandPO). BandPO replaces canonical clipping with **Band**, a unified theoretical operator that projects trust regions defined by $f$-divergences into dynamic, probability-aware clipping intervals. Theoretical analysis confirms that Band effectively resolves this exploration bottleneck. We formulate this mapping as a convex optimization problem, guaranteeing a globally optimal numerical solution while deriving closed-form solutions for specific divergences. Extensive experiments across diverse models and datasets demonstrate that BandPO consistently outperforms canonical clipping and Clip-Higher, while robustly mitigating entropy collapse.

Applications · Robotics

Zixuan Hu, Xuantuo Huang, Yancheng Li, Yichun Hu, Shengyong Xu, LINGYU DUAN

Navigating under non-stationary environment shifts poses a critical challenge for a Vision-and-Language Navigation (VLN) agent deployed in the wild. Yet, existing Test-Time Adaptation (TTA) methods for VLN largely treat online adaptation as transient, isolated updates, leading to catastrophic forgetting and negative transfer. To overcome these issues, we propose **I**nter-**D**omain Bridg**E** with Historical **A**ssets (**IDEA**), a novel TTA framework that transforms adaptation into the accumulation and composition of assets. Specifically, IDEA introduces soft prompts optimized via a Fisher-guided weighting scheme to capture the transferable knowledge. These optimized prompts are then augmented with domain coordinates to form a dynamic asset library. Leveraging this library, IDEA constructs a cross-domain bridge by projecting the target domain onto the convex hull of historical knowledge. These designs form a complementary loop: the evolving library underpins bridge construction, while the bridge provides superior initialization to accelerate asset optimization. Extensive experiments across REVERIE, R2R, and R2R-CE benchmarks demonstrate the consistent superiority of IDEA over existing methods, showcasing its ability to enable training-free adaptation via asset sharing. The code will be publicly available.

General Machine Learning · Clustering

Yao Fu, Dong Hu, Zhi Wang

Multiview subspace clustering (MvSC) has shown remarkable potential in exploring underlying structures of high-dimensional data. However, existing MvSC methods still suffer from two shortcomings: (1) the commonly use of convex low-rank approximations inadequately capture high-order correlations across views, while sensitivity to noise and outliers degrades clustering performance, and (2) they lack the ability to preserve global correlations and local geometric patterns simultaneously. To address these issues, we propose a novel nonconvex regularized MvSC model with deep prior, which not only accurately characterizes the intrinsic low-rank structure and suppresses the effect of outliers, but also preserves local structural properties through deep networks. By mathematically analyzing the optimal solution of the optimization problem in our proposed model, we develop an efficient ADMM-based algorithm with provable convergence guarantees to solve it. Extensive experiments on various datasets demonstrate the superiority of the proposed model.

Social Aspects · Everything Else

Jiangwei Chen, Xinyuan Niu, Rachael Hwee Ling Sim, Zhengyuan Liu, Nancy Chen, Bryan Kian Hsiang Low

Machine unlearning aims to remove the influence of specific training samples due to privacy, copyright or bias concerns. Multi-objective unlearning seeks to ensure the effective forgetting of such samples while preserving the utility of the unlearned model. Existing multi-objective unlearning methods typically optimize a weighted combination of the objectives. They provide no guarantee that any of the objectives can achieve a required performance and do not consider the similarity between the forget data and the remaining retain data. In this work, we quantify how hard it is to reconcile the conflicting objectives arising from overlapping data and provide conditions under which collateral forgetting is unavoidable, that is, when improving forget quality forces retain utility degradation. Utilizing this hardness measure, we propose a hardness-aware multi-objective unlearning algorithm (HAMU) that adapts the unlearning updates based on the per-iteration hardness. Our algorithm is applicable to non-convex models and is easily parallelizable, making it readily deployable in real-world scenarios. We empirically demonstrate HAMU's superior performance over baselines on both image and text datasets using large-scale models.

Optimization · Everything Else

Shenyang Deng, Zhuoli Ouyang, Ruochen Jin, Tianyu Pang, Zihang Liu, Shuhua Yu, Yaoqing Yang

Preconditioned adaptive methods have gained significant attention for training deep neural networks, as they capture rich curvature information. The central challenge in this field lies in balancing preconditioning effectiveness with computational efficiency of implementing the preconditioner. Among recent advances, \textsc{MUON} stands out by using Newton-Schulz iteration to obtain preconditioned updates without explicitly constructing the preconditioning matrix. In this paper, we introduce \textsc{RMNP} (Row Momentum Normalized Preconditioning), an optimizer that replaces Newton-Schulz iteration with a simple row-wise $\ell_2$ normalization operation, motivated by the empirically observed diagonal block structure of the Transformer layerwise Hessian. This substitution reduces the per-iteration complexity from $\mathcal{O}(mn\cdot\min(m,n))$ to $\mathcal{O}(mn)$ for an $m\times n$ weight matrix while maintaining comparable optimization performance. Theoretically, we establish convergence guarantees for \textsc{RMNP} in the non-convex setting that match recent results for \textsc{Muon} optimizers, achieving the information-theoretic minimax optimal complexity. Extensive experiments on large language model pretraining show that \textsc{RMNP} delivers competitive optimization performance compared with \textsc{Muon} while substantially reducing preconditioning process wall-clock time. Our code is available at \href{https://anonymous.4open.science/r/RMNP-317C/}{link}.

Optimization · Non-Convex

Qiujing Lu, Tonmoy Monsoor, Ehsan Ebrahimzadeh, Kartik Sharma, Vwani Roychowdhury

Nonnegative matrix factorization (NMF) seeks a low-rank approximation $X \approx UV^T$ with nonnegative factors and is commonly solved using *interior* methods that enforce feasibility throughout optimization. We show that such constraint-driven approaches can impede progress in the nonconvex landscape, leading to slow convergence or convergence to suboptimal stationary points. We propose an *exterior* framework for NMF (eNMF) that separates low-rank approximation from nonnegativity enforcement. Our method initializes from the optimal unconstrained factorization and introduces a rotation procedure that maps unconstrained factors to an exterior point closest to the nonnegative orthant. This viewpoint yields an algorithmic framework in which simple iterative updates converge to KKT-satisfying stationary points on the boundary of the positive orthant. The exterior formulation also enables a geometric interpretation of NMF solutions, clarifying equivalence classes of factorizations under permutation and orthogonal transformations. An intriguing numerical result, involving 400 NMF experiments across both real and synthetic datasets, show that in 99\% of the cases, different algorithms tend to converge towards equivalent factor matrices. We benchmark eNMF against 9 state-of-the-art NMF algorithms with 9 initialization schemes across 3 real-world and 2 synthetic datasets. eNMF consistently outperforms all 81 competitors, achieving up to 30\% lower reconstruction error under equal-time settings and up to 150\% speedup under equal-error settings. The downstream experiments further demonstrate substantial performance gains in audio processing and recommendation tasks, corroborating the practical benefits of the proposed exterior optimization framework. Anonymized code is available at https://anonymous.4open.science/r/eNMF-6240/README.md

Optimization · Zero-order and Black-box Optimization

Helin Wang, Chenyi Zhang, Xiwen Tao, Yexin Zhang, Tongyang Li

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that outputs an $\epsilon$-stationary point using $\widetilde O(n^2/\epsilon^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $\delta$ using $\widetilde O(n^2\log(1/\delta))$ queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $\epsilon$-stationary point, which takes $\widetilde O(n/\epsilon^{1.5})$ queries.

Probabilistic Methods · Graphical Models

Leander Kurscheidt, Gabriele Masina, Roberto Sebastiani, Antonio Vergari

In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction in an efficient and reliable way extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our structure aware approach outperforms constraint-agnostic baselines.

Optimization · Non-Convex

Alexander Tyurin

Even for the gradient descent (GD) method applied to neural network training, understanding its optimization dynamics, including convergence rate, iterate trajectories, function value oscillations, and especially its implicit acceleration, remains a challenging problem. We analyze nonlinear models with the logistic loss and show that the steps of GD reduce to those of generalized perceptron algorithms (Rosenblatt, 1958), providing a new perspective on the dynamics. This reduction yields significantly simpler algorithmic steps, which we analyze using classical linear algebra tools. Using these tools, we demonstrate on a minimalistic example that the nonlinearity in a two-layer model can provably yield a faster iteration complexity $\tilde{\mathcal{O}}(\sqrt{d})$ compared to $\Omega(d)$ achieved by linear models, where $d$ is the number of features. This helps explain the optimization dynamics and the implicit acceleration phenomenon observed in neural networks. The theoretical results are supported by extensive numerical experiments. We believe that this alternative view will further advance research on the optimization of neural networks.