1.3k citations · 3.8k across the 222 of their papers we have counts for
19 papers · 1 filter
On the Convergence of Encoder-only Shallow Transformers
Yongtao Wu, Fanghui Liu, Grigorios G Chrysos +1
In this paper, we aim to build the global convergence theory of encoder-only shallow Transformers under a realistic setting from the perspective of architectures, initialization, a…
Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks
Jiayuan Ye, Zhenyu Zhu, Fanghui Liu +2
We analytically investigate how over-parameterization of models in randomized machine learning algorithms impacts the information leakage about their training data. Specifically, w…
Maximum Independent Set: Self-Training through Dynamic Programming
Lorenzo Brusca, Lars C. P. M. Quaedvlieg, Stratis Skoulakis +2
This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph,…
Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling
Zhenyu Zhu, Francesco Locatello, Volkan Cevher
This paper provides statistical sample complexity bounds for score-matching and its applications in causal discovery. We demonstrate that accurate estimation of the score function…
Evaluating the Fairness of Discriminative Foundation Models in Computer Vision
Junaid Ali, Matthaeus Kleindessner, Florian Wenzel +3
We propose a novel taxonomy for bias evaluation of discriminative foundation models, such as Contrastive Language-Pretraining (CLIP), that are used for labeling tasks. We then syst…
Exponential Lower Bounds for Fictitious Play in Potential Games
Ioannis Panageas, Nikolas Patris, Stratis Skoulakis +1
Fictitious Play (FP) is a simple and natural dynamic for repeated play with many applications in game theory and multi-agent reinforcement learning. It was introduced by Brown (194…
Stable Nonconvex-Nonconcave Training via Linear Interpolation
Thomas Pethick, Wanyun Xie, Volkan Cevher
This paper presents a theoretical analysis of linear interpolation as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the…
Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
Artem Agafonov, Dmitry Kamzolov, Alexander Gasnikov +4
We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, which occurs typically in machine learning. We establish theore…
Distributed Extra-gradient with Optimal Complexity and Communication Guarantees
Ali Ramezani-Kebrya, Kimon Antonakopoulos, Igor Krawczuk +2
We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local stochastic dual vectors. This setting…
Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees
Ioannis Panageas, Stratis Skoulakis, Luca Viano +2
In this work, we introduce a new variant of online gradient descent, which provably converges to Nash Equilibria and simultaneously attains sublinear regret for the class of conges…
Federated Learning under Covariate Shifts with Generalization Guarantees
Ali Ramezani-Kebrya, Fanghui Liu, Thomas Pethick +2
This paper addresses intra-client and inter-client covariate shifts in federated learning (FL) with a focus on the overall generalization performance. To handle covariate shifts, w…
Adversarial Training Should Be Cast as a Non-Zero-Sum Game
Alexander Robey, Fabian Latorre, George J. Pappas +2
One prominent approach toward resolving the adversarial vulnerability of deep neural networks is the two-player zero-sum paradigm of adversarial training, in which predictors are t…
What can online reinforcement learning with function approximation benefit from general coverage conditions?
Fanghui Liu, Luca Viano, Volkan Cevher
In online reinforcement learning (RL), instead of employing standard structural assumptions on Markov decision processes (MDPs), using a certain coverage condition (original from o…
Benign Overfitting in Deep Neural Networks under Lazy Training
Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos +2
This paper focuses on over-parameterized deep neural networks (DNNs) with ReLU activation functions and proves that when the data distribution is well-separated, DNNs can achieve B…
Regularization of polynomial networks for image recognition
Grigorios G Chrysos, Bohan Wang, Jiankang Deng +1
Deep Neural Networks (DNNs) have obtained impressive performance across tasks, however they still remain as black boxes, e.g., hard to theoretically analyze. At the same time, Poly…
Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems
Thomas Pethick, Puya Latafat, Panagiotis Patrinos +2
This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax pr…
Solving stochastic weak Minty variational inequalities without increasing batch size
Thomas Pethick, Olivier Fercoq, Puya Latafat +2
This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI)…
Revisiting adversarial training for the worst-performing class
Thomas Pethick, Grigorios G. Chrysos, Volkan Cevher
Despite progress in adversarial training (AT), there is a substantial gap between the top-performing and worst-performing classes in many datasets. For example, on CIFAR10, the acc…
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps
Volkan Cevher, Georgios Piliouras, Ryann Sim +1
In this paper we present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems while requiring a simple and intuitive analysis. Simila…