论文检索

Theory · Deep Learning

Bodie Rubacher

Softmax attention is increasingly treated as a reusable inference primitive in transformers. Much prior theory covers Gaussian/linear models or assumes one shared quadratic query--key metric, which can fail for non-Gaussian exponential-family likelihoods with varying curvature. This risks overreading learned similarities as a global metric or as proof of Bayes-optimality. For discrete latent symbols with exponential-family observations, we show a single head can implement Bayes posteriors (and posterior means) by setting logits to log prior plus log likelihood, and we characterize single-head posteriors as exactly the log-linear (exponential-family) class. Using convex duality, we rewrite log-likelihoods as negative Bregman divergences on mean/sufficient-statistic space, making Bayes rule a soft nearest-neighbor computation; this yields a sharp boundary for globally shared quadratic metrics and a multi-head curvature-atlas approximation with head-count scaling, and we extend these guarantees to in-context estimation with consistency and finite-sample stability bounds. In synthetic Gaussian and Bernoulli in-context estimation, trained minimal attention models validate these predictions: performance approaches a Bayes-oracle baseline as prompt length grows; learned metrics align with noise precision in the Gaussian case, while Bernoulli retains a gap consistent with curvature variation. Together, these results explain when Fisher geometry should emerge, when a single metric is justified, and when multiple heads are necessary for Bayes-like in-context estimators beyond Gaussians.

Optimization · Large Scale, Parallel and Distributed

Yihan Zhang, Xinwen Zhang, My T. Thai, Jie Wu, Hongchang Gao

Decentralized stochastic bi-level optimization has been actively studied in recent years. However, existing studies assume that the lower-level loss function is strongly convex, which limits their applicability to many machine learning models. To address this limitation, in this paper, we propose a novel decentralized stochastic first-order optimization algorithm, which does not require second-order Hessian or Jacobian matrices, for the setting where the lower-level loss function is nonconvex but satisfies the Polyak–Łojasiewicz (PL) condition. Additionally, unlike existing single-agent methods that introduce a regularization term to the lower-level loss function to artificially enforce strong convexity, our algorithm does not require such modification. Moreover, our algorithm employs a constant single-timescale learning rate for updating variables, which is different from the time-dependent and two-timescale learning rate schedules used in prior work. To establish the convergence rate, we develop a new convergence analysis framework for the pure PL condition, rather than relying on the artificial strong convexity introduced through regularization in existing single-agent methods. To the best of our knowledge, this is the first algorithm for nonconvex decentralized bi-level optimization that offers theoretical convergence guarantees under mild conditions. Finally, our extensive experimental results on hyperparameter optimization and model pruning applications validate the efficacy of the proposed algorithm.

Optimization · Stochastic

Tianxi Zhu, Yi Xu, Qi Wang, Xiangyang Ji

Recently, many empirical work has shown that, in machine learning, the noise distribution of stochastic gradients often exhibits heavy tails when stochastic optimization methods are employed. Most existing theoretical analyses of heavy-tailed stochastic methods rely on various convexity and smoothness assumptions and our knowledge of how heavy-tailed stochastic methods behave in the setting of weakly convex optimization is still limited. In the weakly convex setting, this paper derives new upper bounds on the convergence of the stochastic gradient method (SGD) under heavy-tailed noises. In particular, for vanilla SGD, we establish an in-expectation convergence guarantee on the bounded constrained domain under the assumption of bounded $p$-th central moment ($p$-BCM) of the gradient noise, and a high-probability guarantee on the unbounded domain when the noise follows a heavy-tailed sub-Weibull distribution. By equipping SGD with the gradient clipping (Clip-SGD), we demonstrate that it achieves high-probability convergence in the unbounded domain under the $p$-BCM gradient noise. All of our high-probability convergence bounds depend on the failure probability only through polynomial-logarithmic factors. Finally, we present numerical experiments to validate our theoretical findings.

Lin Wang, Zhichao Wang, Ye Shi, Sai Praneeth Reddy Karimireddy, Xiaoying Tang

Federated Learning (FL) often suffers from a trade-off between global model performance and client-level fairness due to data heterogeneity, which often leads to inconsistent performance of the globally trained models, resulting in unfair outcomes among users. Existing fair FL algorithms face a trade-off: they either sacrifice global model performance to promote fairness or fall short of achieving optimal fairness. In this paper, we propose a novel framework that bridge this trade-off by integrating information-theoretic principles with model alignment. Specifically, we leverage the Maximum Entropy Principle to derive an analytic, closed-form solution for fair aggregation weights, ensuring significant fairness enhancements with minimal computational overhead. To maintain the global model performance, we further employ a step-wise model alignment strategy that synchronizes gradient directions across heterogeneous clients, effectively mitigating the drift induced by local updates. Theoretical analysis proves that our method guarantees convergence even in non-convex settings. Importantly, we push the theoretical frontier of federated fairness by extending performance variance analysis to generalized regression, providing broader guarantees. Extensive experiments on five datasets demonstrate that our approach consistently outperforms state-of-the-art methods, achieving superior fairness without sacrificing global accuracy.

Optimization · Non-Convex

Haosong Zhang, Shenxi Wu, Xingjian Ma, Shirui Bian, Yichi Zhang, Xi Chen, Wei Lin

Deeper modern architectures are costly to train, making hyperparameter transfer preferable to expensive repeated tuning. Maximal Update Parametrization ($\mu$P) helps explain why many hyperparameters transfer across width. Yet depth scaling is less understood for modern architectures, whose computation graphs contain multiple parallel paths and residual aggregation. To unify various non-recurrent multi-path neural networks such as CNNs, ResNets, and Transformers, we introduce a graph-based notion of effective depth. Under stabilizing initializations and a maximal-update criterion, we show that the optimal learning rate decays with effective depth following a universal -3/2 power law. Here, the maximal-update criterion maximizes the typical one-step representation change at initialization without causing instability, and effective depth is the minimal path length from input to output, counting layers and residual additions. Experiments across diverse architectures confirm the predicted slope and enable reliable zero-shot transfer of learning rates across depths and widths, turning depth scaling into a predictable hyperparameter-transfer problem.

Social Aspects · Alignment

Natalie Collina, Surbhi Goel, Aaron Roth, Emily Ryu, Mirah Shi

Aligning AI systems with human values remains a fundamental challenge, but does our inability to create perfectly aligned models preclude obtaining the benefits of alignment? We study a strategic setting where a human user interacts with multiple differently misaligned AI agents, none of which are individually well-aligned. Our key insight is that when the user’s utility lies approximately within the convex hull of the agents’ utilities, a condition that becomes easier to satisfy as model diversity increases, strategic competition can yield outcomes comparable to interacting with a perfectly aligned model. We model this as a multi-leader Stackelberg game, extending Bayesian persuasion to multi-round conversations between differently informed parties, and prove three results: (1) when perfect alignment would allow the user to learn her Bayes-optimal action, she can also do so in all equilibria under the convex hull condition; (2) under weaker assumptions requiring only approximate utility learning, a non-strategic user employing quantal response achieves near-optimal utility in all equilibria; and (3) when the user selects the best single AI after an evaluation period, equilibrium guarantees remain near-optimal without further distributional assumptions. We complement the theory with two forms of empirical evidence: First, we perform simulations of the best-AI selection game using best response dynamics, which show that competition among individually misaligned agents reliably improves user utility when the approximate convex hull assumption is satisfied, but does not always when it fails. Second, we show that synthetically generated AI utility functions (produced via perturbations of the same prompt to evaluate instances on a movie recommendation (MovieLens) and ethical judgement (ETHICS) dataset) quickly produce a convex hull that contains a good approximation of a given utility function even when none of the individual LLM utility functions is well aligned. We show that this phenomenon extends to human and LLM responses on real-world polling data (OpinionQA): a convex hull of LLM opinions can approximate human opinions more accurately than any individual LLM across a wide range of survey questions.

General Machine Learning · Transfer, Multitask and Meta-learning

Longtao Xu, Jian Li

Real-world federated systems seldom operate on static data: input distributions drift while privacy rules forbid raw data sharing. We study Federated Domain-Incremental Learning (FDIL), where (i) clients are heterogeneous, (ii) tasks arrive sequentially with shifting domains, and (iii) the label space remains fixed. Two theoretical pillars remain missing for FDIL under partial participation: a guarantee of backward knowledge transfer (BKT) and a convergence rate that holds *uniformly across the task sequence*. We introduce SPECIAL (Server-Proximal Efficient Continual Aggregation for Learning), a simple, memory-free FDIL algorithm that adds a single server-side ``anchor'' to FedAvg: in each round, the server aggregates updates from a uniformly sampled subset of clients and then blends the result with the previous global model via a lightweight proximal step. This anchor curbs cumulative drift without replay buffers, synthetic data, or task-specific heads, leaving communication cost and model size unchanged. Our theory shows that SPECIAL (i) *preserves earlier tasks*: a BKT bound caps any increase in earlier-task loss by a drift-controlled term that shrinks with more rounds, local epochs, and participating clients; and (ii) *achieves task-uniform, communication-efficient convergence* for non-convex FDIL with partial participation: $\mathcal{O}\!\big(\sqrt{E/(NT)}\big)$ in expected gradient norm, with $E$ local epochs, $T$ rounds, and $N$ participating clients, while explicitly separating optimization variance from inter-task drift. Experiments on standard FDIL benchmarks corroborate the theory.

Philip Jordan, Maryam Kamgarpour

We study the existence and computation of Nash equilibria in concave games where the players' admissible strategies are subject to shared coupling constraints. Under playerwise concavity of constraints, we prove existence of Nash equilibria. Our proof leverages topological fixed point theory and novel structural insights into the contractibility of feasible sets, and relaxes strong assumptions for existence in prior work. Having established existence, we address the question of whether in the presence of coupling constraints, playerwise independent learning dynamics have convergence guarantees. We address this positively for the class of potential games by designing a convergent algorithm. To account for the possibly nonconvex feasible region, we employ a log barrier regularized gradient ascent with adaptive stepsizes. Starting from an initial feasible strategy profile and under exact gradient feedback, the proposed method converges to an $\epsilon$-approximate constrained Nash equilibrium within $\mathcal{O}(\epsilon^{-3})$ iterations.

Deep Learning · Everything Else

Ozan Candogan, Ayoub Foussoul

We introduce Deep Flow Networks (DFNs), a new class of discrete function approximators. DFNs are inspired by and generalize minimum-cost flow value functions that map node imbalances on a subset of nodes to the optimal flow cost. Such functions are known to be M-convex (Murota2003) and admit efficient optimization. On the theoretical side, we prove that DFNs are universal approximators for discrete functions on $\mathbb{Z}^d$ that admit convex extensions to $\mathbb{R}^d$, and characterize their optimization complexity in terms of their deviation from the M-convex regime. Guided by these results, we develop a practical DFN implementation for learning from data. Finally, we evaluate our implementation empirically on data from different ground-truth functions, showing that DFNs achieve strong approximation accuracy while being substantially faster to optimize than benchmark approaches.

Theory · Learning Theory

SANTANU DAS, Sagnik Chatterjee, jatin batra

In this paper, we tackle a fundamental problem in high-dimensional statistics, namely, learning Single Index Models (SIMs) robustly in the presence of heavy-tailed noise and an adversary that can corrupt a constant fraction of both covariates and responses. Prior research on efficient robust recovery only focuses on monotonic link functions or only limit themselves to Phase Retrieval. Provable efficient robust recovery guarantees for generic nonlinear link functions have remained elusive. In this paper, we obtain the first near-linear time, optimal-sample-complexity robust recovery algorithm for a wide class of nonlinear non-monotonic link functions. Critical to our result is an improved understanding of the squared-loss landscape: we identify a sufficient condition under which a broad class of non linear link functions admit a dimension-independent constant-radius convex basin around the ground truth, establishing statistical identifiability beyond previously known cases. We also leverage second-order Stein's identities to identify a structural condition, that we term Expected Squared Convexity (ESC), that acts as a sufficient condition for spectral initialization techniques to obtain an estimator within the convex basin with error $O(\epsilon^{1/4})$, even under heavy-tailed noise and strong adversarial contamination. This robust initialization technique can be combined with a robust gradient descent phase to break the spectral error barrier, achieving an improved estimation error of $O(\sigma\sqrt{\epsilon})$. Our non-convex optimization framework gives the first efficient sample and time complexity robust recovery results for activation functions such as GeLU and Swish that act as building blocks of modern deep-learning architectures.

General Machine Learning · Clustering

Henri Schmidt, Peter Halmos, Benjamin Raphael

Optimal transport (OT) finds a least cost transport plan between two probability distributions using a cost matrix defined on pairs of points. Unlike standard OT, which infers unstructured pointwise mappings, low-rank optimal transport explicitly constrains the rank of the transport plan to infer latent structure. This improves statistical stability and robustness, yields sharper parametric rates for estimating Wasserstein distances adaptive to the intrinsic rank, and generalizes $K$-means to co-clustering. These advantages, however, come at the cost of a non-convex and NP-hard optimization problem. We introduce transport clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a clustering problem on correspondences obtained from a full-rank *transport registration* step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a $(1+\gamma)$ approximation for negative-type metrics and a $(1+\gamma+\sqrt{2\gamma})$ approximation for kernel costs, where $\gamma \in [0,1]$ denotes the approximation ratio of the optimal full-rank solution relative to the low-rank optimal. Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.

Theory · Game Theory

Philip Jordan, Maryam Kamgarpour

We study the existence and computation of Nash equilibria in concave games where the players' admissible strategies are subject to shared coupling constraints. Under playerwise concavity of constraints, we prove existence of Nash equilibria. Our proof leverages topological fixed point theory and novel structural insights into the contractibility of feasible sets, and relaxes strong assumptions for existence in prior work. Having established existence, we address the question of whether in the presence of coupling constraints, playerwise independent learning dynamics have convergence guarantees. We address this positively for the class of potential games by designing a convergent algorithm. To account for the possibly nonconvex feasible region, we employ a log barrier regularized gradient ascent with adaptive stepsizes. Starting from an initial feasible strategy profile and under exact gradient feedback, the proposed method converges to an $\epsilon$-approximate constrained Nash equilibrium within $\mathcal{O}(\epsilon^{-3})$ iterations.

Theory · Online Learning and Bandits

Dhruv Sarkar, Abhishek Sinha

We propose an anytime online algorithm for learning a sequence of convex cost functions while approximately satisfying a sequence of convex constraints, without prior knowledge of the time horizon. Both the cost and constraint functions may be chosen adversarially over time. While this problem has recently been resolved in the setting where the time horizon is known, extending these guarantees to the anytime setting, without resorting to inefficient doubling tricks, has remained technically challenging. Our main contribution is the introduction of a time-varying yet horizon-oblivious Lyapunov function to track constraint violations. The use of such a time-varying Lyapunov function introduces new technical difficulties, as a key monotonicity property underlying prior analyses no longer holds. By developing a novel analytical technique, we show that our algorithm achieves $O(\sqrt{t})$ \regret~ and $\tilde{O}(\sqrt{t})$ cumulative constraint violation (\CCV) for all $t \geq 1$. We further extend our framework to the dynamic regret setting, obtaining bounds that adapt to the unknown path length of the comparator sequence. Finally, we present an adaptive algorithm for the optimistic setting, whose performance scales gracefully with the cumulative prediction error. We validate the practical effectiveness of our approach through numerical experiments on the online shortest path problem.

Optimization · Convex

Ji Qi, Mingxiao Liu, VIET THUC, Yuzhe Li, Zhuoshi Pan, Gene Cheung, Hong Zhao

To forecast traffic with both spatial and temporal dimensions, we unroll a mixed-graph-based optimization algorithm into a lightweight and interpretable transformer-like neural net. Specifically, we construct two graphs: an undirected graph $\mathcal{G}^u$ capturing spatial correlations across geography, and a directed graph $\mathcal{G}^d$ capturing sequential relationships over time. We formulate a prediction problem for the future samples of signal $\mathbf{x}$, assuming it is ``smooth'' with respect to both $\mathcal{G}^u$ and $\mathbf{G}^d$, where we design new $\ell_2$ and $\ell_1$-norm variational terms to quantify and promote signal smoothness (low-frequency reconstruction) on a directed graph. We construct an iterative algorithm based on alternating direction method of multipliers (ADMM), and unroll it into a feed-forward network for data-driven parameter learning. We periodically insert graph learning modules for $\mathcal{G}^u$ and $\mathcal{G}^d$, which are akin to the self-attention mechanism in classical transformers. Experiments show that our unrolled networks achieve competitive traffic forecast performance as state-of-the-art prediction schemes, while reducing parameter counts drastically.

Deep Learning · Large Language Models

Chenyi Li, Yanchen Nie, Zhenyu Ming, Gong Zhang, Kun Yuan, Zaiwen Wen

Recent advances in formal theorem proving have focused on Olympiad-level mathematics, leaving undergraduate domains largely unexplored. Optimization, fundamental to machine learning, operations research, and scientific computing, remains underserved by existing provers. Its reliance on domain-specific formalisms (convexity, optimality conditions, and algorithmic analysis) creates significant distribution shift, making naive domain transfer ineffective. We present OptProver, a trained model that achieves robust transfer from Olympiad to undergraduate optimization. Starting from a strong Olympiad-level prover, our pipeline mitigates distribution shift through two key innovations. First, we employ large-scale optimization-focused data curation via expert iteration. Second, we introduce a specialized preference learning objective that integrates perplexity-weighted optimization with a mechanism to penalize valid but non-progressing proof steps. This not only addresses distribution shifts but also guides the search toward efficient trajectories. To enable rigorous evaluation, we construct a novel benchmark in Lean 4 focused on optimization. On this benchmark, OptProver achieves state-of-the-art Pass@1 and Pass@32 among comparably sized models while maintaining competitive performance on general theorem-proving tasks, demonstrating effective domain transfer without catastrophic forgetting.

Probabilistic Methods · Monte Carlo and Sampling Methods

Yunbum Kook, Shunshi Zhang

We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when $π$ satisfies a Poincaré inequality and the chain possesses a spectral gap, we can achieve similar sample complexity using MCMC as compared to an estimator constructed using i.i.d. samples, with potentially much better query complexity. As an application of our methods, we show improvements for the query complexity in both constrained and unconstrained settings for concrete instances of MCMC. In particular, we provide guarantees regarding isotropic rounding procedures for sampling uniformly on convex bodies.

Theory · Optimization

Zijian Liu

Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular $\mathtt{Adam}$ and $\mathtt{AdamW}$, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case, $\mathtt{AdaGrad}$, the origin of adaptive gradient methods. We provide the first provable convergence rate for $\mathtt{AdaGrad}$ in non-convex optimization when the tail index $p$ satisfies $\frac{4}{3}<p\leq2$. Notably, this result is achieved without requiring any prior knowledge of $p$ and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by $\mathtt{AdaGrad}$. Lastly, we consider $\mathtt{AdaGrad}\text{-}\mathtt{Norm}$, a popular variant of $\mathtt{AdaGrad}$ in theoretical studies, and show an improved rate that holds for any $1<p\leq2$ under an extra mild assumption.

Theory · Learning Theory

Yufeng Xie, Yunwen Lei

Asynchronous stochastic gradient descent (ASGD) is widely adopted in distributed and federated learning. In this paper, we develop a sharp generalization analysis for ASGD by leveraging the concept of on-average model stability. For convex and smooth objectives, we establish stability and excess risk bounds under minimal assumptions, removing Lipschitz continuity, bounded noise, bounded parameter or data domains, while allowing randomly partitioned data and arbitrary delays. Our bounds are optimistic and explicitly characterize the impact of worker participation, recovering the minimax-optimal rate $O(1/\sqrt{mn})$ in balanced regimes where $mn$ denotes the sample size and implying fast rates under low-noise conditions. We further extend the analysis to non-smooth objectives with Hölder-continuous gradients and to heterogeneous data settings via random ASGD, obtaining non-vacuous excess risk guarantees in both settings. Experimental results support our theoretical findings.

Optimization · Stochastic

Yuheng Zhao, Yu-Hu Yan, Amit Attia, Tomer Koren, Lijun Zhang, Peng Zhao

Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with optimally tuned methods. While some parameter-free methods do not require the specific values of the problem parameters, they still rely on prior knowledge, such as the lower or upper bounds of them. We refer to such methods as "partially parameter-free". In this work, we target achieving "*fully* parameter-free" methods, i.e., the algorithmic inputs do not need to satisfy any *unverifiable* condition related to the true problem parameters. We propose a general and powerful *grid search* framework, named GRASP, with a novel *self-bounding* analysis technique that effectively determines the parameter search ranges, in contrast to previous work. Our method demonstrates generality in: (i) the non-convex case, where we propose a fully parameter-free method that achieves near-optimal convergence rate, up to logarithmic factors; (ii) the convex case, where our parameter-free methods are competitive with strong performance in terms of acceleration and universality. Finally, we contribute a sharper guarantee for the model ensemble, a final step of the grid search framework, under interpolated variance characterization.

Optimization · Non-Convex

Haolin Pan, Lianghong Huang, Dong Jinyuan, Mingjie Xing, Yanjun Wu

Compiler auto-tuning faces a dichotomy between traditional black-box search methods, which lack semantic guidance, and recent Large Language Model (LLM) approaches, which often suffer from superficial pattern matching and causal opacity. In this paper, we introduce ECCO, a framework that bridges interpretable reasoning with combinatorial search. We first propose a reverse engineering methodology to construct a Chain-of-Thought dataset, explicitly mapping static code features to verifiable performance evidence. This enables the model to learn the causal logic governing optimization decisions rather than merely imitating sequences. Leveraging this interpretable prior, we design a collaborative inference mechanism where the LLM functions as a strategist, defining optimization intents that dynamically guide the mutation operations of a genetic algorithm. Experimental results on seven datasets demonstrate that ECCO outperforms the LLVM opt -O3 baseline, achieving an average 24.44% reduction in cycles. Our code is available at https://anonymous.4open.science/r/ECCO-Evidence-Driven-Causal-Reasoning-for-Compiler-Optimization-3AD2.