论文检索

Theory · Reinforcement Learning and Planning

Federico Corso, Marco Mussi, Alberto Maria Metelli

Stability is a property of fundamental importance in real-world systems. Although it has been widely studied and well understood in *control theory* (CT) for deterministic systems, it is largely overlooked in stochastic systems such as *Markov decision processes* (MDPs). In this paper, we aim to translate the steady-state control problem, well established in CT, where the goal is to synthesize a controller with prescribed asymptotic stability properties, into the MDP framework. To this end, we propose the novel *fast-mixing steady-state* (FMSS) problem. Given an ergodic MDP and a target steady-state distribution, the objective is to synthesize a Markovian policy that induces this distribution with the fastest possible convergence rate. Addressing this problem requires controlling the spectral properties of the induced *Markov chain* (MC) transition matrix, which generally leads to non-convex programs. Thus, we derive a tractable surrogate objective that leads to a convex program, whose properties we study in terms of approximation quality, feasibility, and computational complexity. We then move to the learning setting and propose an "offline" sample-based algorithm for FMSS (FMSS-SV), designed for tabular MDPs, in which the environment’s transition model is estimated from data. We quantify the impact of transition model estimation errors on both the objective value and the learned policy, and provide a finite-sample complexity analysis.

Social Aspects · Privacy

Hengliang Wu, Jiale Yang, Youming Tao, Shuzhen Chen, Di Wang, Dongxiao Yu

Decentralized Unlearning (DU) aims to remove the influence of specific clients from a collaboratively trained global model. However, existing methods suffer from strong reliance on static, problem-specific hyperparameters or restrictive convexity assumptions, limiting their general applicability. To overcome these limitations, we propose **TRA**jectory-aware **CE**rtified **D**ecentralized **U**nlearning (**TRACE-DU**), a generic unlearning framework for decentralized training. **TRACE-DU** introduces a fine-grained sensitivity analysis that leverages local SGD updates and decentralized training dynamics, thereby eliminating the need for convexity assumptions and reducing dependence on manually tuned parameters. By integrating strategic checkpoint selection with calibrated noise perturbation, the proposed framework enables efficient certified unlearning. Moreover, we exploit historical model trajectories to extend this framework, enabling it to naturally support sequential unlearning requests from an arbitrary number of clients. We provide theoretical guarantees for certified unlearning and derive sensitivity bounds under both convex and non-convex loss functions. Experimental results demonstrate that our framework outperforms state-of-the-art baselines across diverse metrics.

Optimization · Stochastic

Yuan Zhou, Yidan Ou, Xinli Shi

Federated Multi-Objective Learning (FMOL) enables collaborative training of conflicting objectives but faces a compounded challenge: the recursive coupling between intra-task client drift and inter-task aggregation bias. We propose DREAM, a unified framework that jointly corrects these two coupled error sources through drift-aware control variates and momentum-smoothed local updates. On the server side, DREAM formulates multi-objective aggregation as a regularized quadratic program parameterized by a task correction matrix, which provides a generalized formulation that can flexibly adapt to scalarization, prioritization, and gradient manipulation strategies. Theoretically, we establish a linear speedup convergence rate of $\mathcal{O}(1/\sqrt{NT})$ for non-convex objectives. We further provide theoretical guarantees for the conflict-avoidant descent direction. In the strongly convex setting, DREAM achieves convergence in weighted sub-optimality and admits a unified Lyapunov analysis showing linear convergence to a regularization-dependent neighborhood. Numerical experiments validate the superior performance and effectiveness of DREAM in practice.

Optimization · Stochastic

Vassilis Apidopoulos, Iosif Lytras, Panayotis Mertikopoulos

Many optimization problems in machine learning and data science—from deep neural networks to Bayesian inference and beyond—fall outside the standard Lipschitz smoothness framework that underpins the convergence theory of stochastic gradient descent (SGD). Motivated by this theory-practice disconnect, we examine the almost sure convergence of the trajectories of SGD in non-convex landscapes under a generalized $(L_0,L)1)$-smoothness condition which allows for gradients with superlinear growth (even exponential). We begin by proposing a taming scheme for SGD that achieves almost sure convergence under a generalized ABC-type condition on the gradient noise. Subsequently, to relax this requirement, we introduce a more flexible, dissipative taming scheme which converges almost surely under less restrictive moment bound conditions for the stochastic gradients entering the process. For both taming schemes, we show that the generated trajectories avoid strict saddle points (and/or manifolds thereof) with probability 1 so, generically, both methods only converge to local minimizers.

Optimization · Non-Convex

Siqiao Mu, Diego Klabjan

The low-rank adaptation (LoRA) algorithm for fine-tuning large models has grown popular in recent years due to its remarkable performance and low computational requirements. LoRA trains two "adapter" matrices that form a low-rank representation of the model parameters, thereby massively reducing the number of parameters that need to be updated at every step. Although LoRA is simple, its convergence is poorly understood due to the lack of Lipschitz smoothness, a key condition for classic convergence analyses. As a result, current theoretical results only consider asymptotic behavior or assume strong boundedness conditions which artificially enforce Lipschitz smoothness. In this work, we provide for the first time a non-asymptotic convergence analysis of the *original LoRA gradient descent* algorithm, which reflects widespread practice, without such assumptions. Our work relies on three key steps: i) reformulating the problem in terms of the outer product of the stacked adapter matrices, ii) a modified descent lemma for the "Lipschitz-like" reparametrized function, and iii) controlling the step size. With this approach, we prove that LoRA gradient descent converges to a stationary point at rate $O(\frac{1}{\log T})$, where $T$ is the number of iterations. We conduct numerical experiments to validate our theoretical findings.

General Machine Learning · Methodology

Junhyoung Chung, Euijong Song, Won Hwa Kim, Gunwoong Park

We introduce Convex Distance Operator Transport (CDOT), the first convex optimal transport framework that aligns distributions across heterogeneous domains by jointly preserving feature correspondence and intrinsic geometric structure. Specifically, CDOT employs an operator-based regularization that aligns aggregated distance structures by introducing distance and conditional expectation operators. Consequently, the proposed regularization improves the robustness to local geometric variations. We further prove that the resulting CDOT discrepancy is a valid pseudometric on the space of attributed compact metric-measure spaces. In addition, we characterize the relationship between CDOT and Gromov--Wasserstien (GW) through a new notion of dispersion gap, formally elucidating the geometric source of non-convexity in GW compared to the convexity of CDOT. In the finite-sample regime, we derive a non-asymptotic risk bound decomposed into optimization and statistical errors, establishing risk consistency under a globally convergent Frank--Wolfe algorithm. Experiments on synthetic point clouds, brain connectomes, and graph classification benchmarks demonstrate better performance over existing methods, with stable and reliable behavior in practice.

Theory · Optimization

Jinyi Huang, Jinlong Lei, Guodong Shi

Distributionally Robust Optimization (DRO) is widely used to improve model robustness, with existing methods addressing either geometric perturbations (e.g., input shifts) or statistical contamination (e.g., heavy-tailed noise and outliers) effectively. However, these uncertainty sources often co-exist. Coupling them through a single divergence or optimal transport constraint conflates geometric displacement with loss-based outlierness, which often leads to the discarding of informative high-leverage samples. We introduce nested DRO, a bilevel formulation that combines optimal transport with an outer $\\phi$-divergence constraint to decouple geometric smoothing from statistical robustness. We prove that this structure naturally induces a geometry-invariant, loss-based reweighting mechanism that separates outlier suppression from transport-induced regularization. We derive a tractable strong dual for the resulting non-convex problem and show its equivalence to variance-regularized risk minimization, providing a rigorous theoretical justification for reweighting gains as a natural consequence of dualization. Empirical results on synthetic and real datasets demonstrate that nested DRO consistently outperforms geometry-coupled DRO baselines, particularly under heavy-tailed contamination where preserving high-leverage structure is crucial.

Theory · Online Learning and Bandits

Yan-Feng Xie, Yu-Jie Zhang, Peng Zhao, Zhi-Hua Zhou

We study dynamic regret minimization in non-stationary online learning, with a primary focus on follow-the-regularized-leader (FTRL) methods. FTRL is important for curved losses and for understanding adaptive algorithms, yet existing dynamic regret analyses are less explored for FTRL. To address this, we build on the discounted-to-dynamic reduction and present a modular way to obtain dynamic regret bounds. The reduction simplifies prior proofs for online linear regression, recovers optimal rates, and provides new guarantees for online logistic regression, covering two representative curved losses. Beyond online convex optimization, we apply the reduction to analyze the Adam optimizers, obtaining optimal convergence rates in stochastic, non-convex, and non-smooth settings. The reduction also enables a more detailed treatment of Adam with two discount parameters $(\beta_1,\beta_2)$, leading to new results for both clipped and clip-free variants.

Probabilistic Methods · Monte Carlo and Sampling Methods

Mehmet Berk Sahin, Behzad Sharif, Abolfazl Hashemi

Sampling from high-dimensional, non-log-concave distributions with unnormalized densities constitutes a fundamental challenge in machine learning, particularly when gradient information is inaccessible or computationally prohibitive. While Langevin dynamics provides a robust mechanism for gradient-based sampling, its extension to the derivative-free setting is frequently compromised by high variance and a lack of rigorous convergence guarantees in non-convex landscapes. In this work, we propose a principled variance-reduced zeroth-order Langevin dynamics framework that addresses these limitations for both general non-log-concave black-box sampling and inverse problems utilizing pre-trained score-based generative priors. We introduce a novel gradient estimator that significantly mitigates the variance inherent in traditional zeroth-order methods, enabling stable navigation of complex, multimodal posterior distributions. Theoretically, we establish the first non-asymptotic complexity bounds for this class of algorithms, proving convergence to the target distribution in terms of $\varepsilon$-relative Fisher information, and, under a Poincare inequality, squared total variation distance, specifically for non-log-concave densities. We empirically validate our framework, demonstrating superior mixing and sampling accuracy on standard black-box benchmarks and establishing state-of-the-art performance for derivative-free linear and nonlinear inverse problems.

Optimization · Non-Convex

Shutong Ding, Yimiao Zhou, Ke Hu, Xi Yao, Junchi Yan, Xiaoying Tang, Ye Shi

Recent advances in diffusion models show promising potential to accelerate nonconvex problem solving by leveraging their multimodality. However, most existing diffusion-based optimization approaches rely on supervised learning and lack a mechanism to enforce constraint satisfaction, which is required in real-world applications. In that case, we investigate and theoretically analyze the inherent problem of supervised diffusion solvers and identify the distributional misalignment problem, i.e., the generated solution distribution often exhibits low probability mass on the feasible region. To resolve this issue, we propose DiOpt, a new diffusion-based learning framework for constrained nonconvex optimization, which effectively learns the mapping from noise to the constraint region. Specifically, this framework operates in two distinct phases: an initial warm-start phase, implemented via supervised learning, followed by a bootstrapping training phase. This dual-phase architecture is designed to iteratively refine solutions, thereby improving the objective function with high constraint satisfaction. Finally, we also employ a solution selection technique in inference for better optimality. Notably, DiOpt is the first successful integration of the diffusion solver in constrained nonconvex optimization. Evaluations on diverse nonconvex tasks demonstrate the superiority of DiOpt in both optimality and constraint satisfaction.

Optimization · Non-Convex

John Hood, Aaron Schein

Despite the ubiquity of multiway data across scientific domains, there are few user-friendly tools that fit tailored nonnegative tensor factorizations. Researchers may use gradient-based automatic differentiation (which often struggles in nonnegative settings), choose between a limited set of methods with mature implementations, or implement their own model from scratch. As an alternative, we introduce NNEinFact, an einsum-based multiplicative update algorithm that fits any nonnegative tensor factorization expressible as a tensor contraction by minimizing one of many user-specified loss functions (including the $(\alpha,\beta)$-divergence). To use NNEinFact, the researcher simply specifies their model with a string. NNEinFact converges to a local minimum of the loss, supports missing data, and fits to tensors with hundreds of millions of entries in seconds. Empirically, NNEinFact fits custom models which outperform standard ones in heldout prediction tasks on real-world tensor data by over 37% and attains less than half the test loss of gradient-based methods while converging up to 90 times faster.

Social Aspects · Privacy

Shuli Jiang, Walid Krichene, Nicolas Mayoraz

We study differentially private (DP) regression in settings where each data sample includes public, non-sensitive features—common in applications like recommendation or advertising systems. While such label DP or DP with semi-sensitive features settings have been primarily explored in the context of classification, effective approaches for regression remain underexplored. We introduce $\textsf{Cond-DP}$, a conditioned variant of $\textsf{DPSGD}$ that leverages the structure of public feature matrices to improve optimization under privacy constraints. Motivated by the observation that these public features often exhibit rapidly decaying spectra, $\textsf{Cond-DP}$ incorporates a data-driven conditioning matrix to reshape the optimization landscape and accelerate convergence. We provide convergence guarantees for convex, strongly convex and non-convex settings, and recover standard $\textsf{DPSGD}$ as a special case when the conditioning matrix is the identity. We show how to construct an effective conditioning matrix for $\textsf{Cond-DP}$ directly from public features, enabling faster convergence than $\textsf{DPSGD}$ in private linear regression, without incurring additional privacy cost. Empirically, $\textsf{Cond-DP}$ with this conditioning matrix consistently outperforms state-of-the-art baselines across a wide range of datasets and model architectures under label DP, demonstrating strong and robust performance in practice.

Optimization · Non-Convex

Haocheng Luo, Zehang Deng, Thanh-Toan Do, Mehrtash Harandi, Dinh Phung, Trung Le

Direct Preference Optimization (DPO) has emerged as a popular algorithm for aligning pretrained large language models with human preferences, owing to its simplicity and training stability. However, DPO suffers from the recently identified *squeezing effect* (also known as *likelihood displacement*), where the probability of preferred responses decreases unintentionally during training. To understand and mitigate this phenomenon, we develop a theoretical framework that models the coordinate-wise dynamics in logit space. Our analysis reveals that negative-gradient updates cause residuals to expand rapidly along high-curvature directions, which underlies the squeezing effect, whereas Sharpness-Aware Minimization (SAM) can suppress this behavior through its curvature-regularization effect. Building on this insight, we investigate *logits-SAM*, a computationally efficient variant that perturbs only the output layer with negligible overhead. Extensive experiments on Pythia-2.8B, Mistral-7B, and Gemma-2B-IT across multiple datasets and benchmarks demonstrate that logits-SAM consistently improves the effectiveness of DPO and integrates seamlessly with other DPO variants. Code is available at .

Optimization · Learning for Optimization

Panagiotis D. Grontas, Antonio Terpin, Efe Balta, Raffaello D'Andrea, John Lygeros

We introduce an output layer for neural networks that ensures satisfaction of convex constraints. Our approach, $\Pi$net, leverages operator splitting for rapid and reliable projections in the forward pass, and the implicit function theorem for backpropagation. We deploy $\Pi$net as a feasible-by-design optimization proxy for parametric constrained optimization problems and obtain modest-accuracy solutions faster than traditional solvers when solving a single problem, and significantly faster for a batch of problems. We surpass state-of-the-art learning approaches by orders of magnitude in terms of training time, solution quality, and robustness to hyperparameter tuning, while maintaining similar inference times. Finally, we tackle multi-vehicle motion planning with non-convex trajectory preferences and provide $\Pi$net as a GPU-ready package implemented in JAX.

Optimization · Large Scale, Parallel and Distributed

Xiaowen Jiang, Anton Rodomanov, Sebastian Stich

Different federated optimization algorithms typically employ distinct client-selection strategies: some methods communicate only with a randomly sampled subset of clients at each round, while others need to periodically communicate with all clients or use a hybrid scheme that combines both strategies. However, existing metrics for comparing optimization methods typically do not distinguish between these strategies, which often incur different communication costs in practice. To address this disparity, we introduce a simple and natural model of federated optimization that quantifies communication and local computation complexities. This new model allows for several commonly used client-selection strategies and explicitly associates each with a distinct cost. Within this setting, we propose a new algorithm that achieves the best-known communication and local complexities among existing federated optimization methods for non-convex optimization. This algorithm is based on the inexact composite gradient method with a carefully constructed gradient estimator and a special procedure for solving the auxiliary subproblem at each iteration. The gradient estimator is based on SAGA, a popular variance-reduced gradient estimator. We first derive a new variance bound for it, showing that SAGA can exploit functional similarity. We then introduce the Recursive-Gradient technique as a general way to potentially improve the error bound of a given conditionally unbiased gradient estimator, including both SAGA and SVRG. By applying this technique to SAGA, we obtain a new estimator, RG-SAGA, which has an improved error bound compared to the original one.

Optimization · Non-Convex

Yudong Wei, Liang Zhang, Bingcong Li, Niao He

While normalization techniques are widely used in deep learning, their theoretical understanding remains relatively limited. In this work, we establish the benefits of (generalized) weight normalization (WN) applied to the overparameterized matrix sensing problem. We prove that WN with Riemannian optimization achieves linear convergence, yielding an $\textit{exponential}$ speedup over standard methods that do not use WN. Our analysis further demonstrates that both iteration and sample complexity improve polynomially as the level of overparameterization increases. To the best of our knowledge, this work provides the first characterization of how WN leverages overparameterization for faster convergence in matrix sensing.

Optimization · Non-Convex

Jiawei Xu, Yi Zheng, Chenghe Sun, Taiyu Zhou, Zuqi Zhang, Jie Li, Lirong Zheng, Zhuo Zou

Efficient deployment of deep neural networks increasingly relies on Post-Training Quantization (PTQ). Logarithmic PTQ, in particular, promises multiplier-free hardware efficiency, but its performance is often limited by the nonlinear and symmetric quantization grid and standard rounding-to-nearest (RTN) approach. While learnable rounding has significantly advanced linear PTQ, its application to the non-linear and often discrete nature of logarithmic domain remains unexplored. This paper introduces learnable Logarithmic Adaptive Rounding Techniques (LogART) that pioneer task-aware learnable rounding specifically for the logarithmic domain. LogART further extends the learnable rounding strategy to flexibly support outlier-aware, asymmetric, and hardware-friendly dynamic logarithmic bases, determined in a distribution-aware manner using an efficient search strategy. Extensive experiments demonstrate that LogART achieves state-of-the-art accuracy while maintaining efficiency in quantizing models across various architectures and ultra-low bitwidths, outperforming existing logarithmic PTQ methods and paving the way for more effective hardware deployment. The code is available at https://github.com/logart-lab/logart.

Optimization · Non-Convex

Francisco Patitucci, Ruichen Jiang, Aryan Mokhtari

A recent breakthrough in nonconvex optimization is the online-to-nonconvex conversion framework of Cutkosky et al. (2023), which reformulates the task of finding an $\varepsilon$-first-order stationary point as an online learning problem. When both the gradient and the Hessian are Lipschitz continuous, instantiating this framework with two different online learners achieves a complexity of $ \mathcal{O}(\varepsilon^{-1.75}\log(1/\varepsilon)) $ in the deterministic case and a complexity of $ \mathcal{O}(\varepsilon^{-3.5}) $ in the stochastic case. However, this approach suffers from several limitations: (i) the deterministic method relies on a complex double-loop scheme that solves a fixed-point equation to construct hint vectors for an optimistic online learner, introducing an extra logarithmic factor; (ii) the stochastic method assumes a bounded second-order moment of the stochastic gradient, which is stronger than standard variance bounds; and (iii) different online learning algorithms are used in the two settings. In this paper, we address these issues by introducing an online optimistic gradient method based on a novel **doubly optimistic hint function**. Specifically, we use the gradient at an extrapolated point as the hint, motivated by two optimistic assumptions: that the difference between the hint and the target gradient remains near constant, and that consecutive update directions change slowly due to smoothness. Our method eliminates the need for a double loop and removes the logarithmic factor. Furthermore, by simply replacing full gradients with stochastic gradients and under the standard assumption that their variance is bounded by $\sigma^2$, we obtain a unified algorithm with complexity $\mathcal{O}(\varepsilon^{-1.75} + \sigma^2 \varepsilon^{-3.5})$, smoothly interpolating between the best-known deterministic rate and the optimal stochastic rate.

Optimization · Non-Convex

Yuman Wu, Xiaochuan Gong, Jie Hao, Mingrui Liu

Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-Łojasiewicz (PL) conditions for the lower-level function to establish non-asymptotic convergence to a solution with a small hypergradient. However, these assumptions may not hold in practice, and recent work (Chen et al. 2024) has shown that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients. In this paper, we identify a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via lower-level uniform convexity. For uniformly convex lower-level functions with exponent $p\geq 2$, we establish a novel implicit differentiation theorem characterizing the hyperobjective's smoothness property. Building on this, we design a new stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on an oracle that provides stochastic gradient and Hessian-vector product information for the bilevel problems. Our algorithm achieves $\widetilde{O}(\epsilon^{-5p+6})$ oracle complexity bound for finding $\epsilon$-stationary points. Notably, our complexity bounds match the optimal rates in terms of the $\epsilon$ dependency for strongly convex lower-level functions ($p=2$), up to logarithmic factors. Our theoretical findings are validated through experiments on synthetic tasks and data hyper-cleaning, demonstrating the effectiveness of our proposed algorithm.

General Machine Learning · Causality

Taiyu Ban, Changxin Rong, Xiangyu Wang, Lyuzhou Chen, Yanze Gao, Xin Wang, Huanhuan Chen

Learning instantaneous and time-lagged causal relationships from time-series data is essential for uncovering fine-grained, temporally-aware interactions. Although this problem has been formulated as a continuous optimization task amenable to modern machine learning methods, existing approaches largely neglect the use of coarse-grained, lag-agnostic causal priors, an important form of prior knowledge that is often available in practice. To address this gap, we propose a novel framework for structure learning from time series to integrate lag-agnostic priors, enabling the discovery of lag-specific causal links without requiring precise temporal annotations. We introduce formulations to precisely characterize the lag-agnostic prior, and demonstrate their consequential and process-equivalence to priors, maintaining consistency with the intended semantics of the priors throughout optimization. We further analyze the challenge for optimization due to the increased non-convexity by lag-agnostic prior constraints, and introduce a data-driven initialization to mitigate this issue. Experiments on both synthetic and real-world datasets show that our method effectively incorporates lag-agnostic prior knowledge to enhance the recovery of fine-grained, lag-aware structures.