Showing 1–28 of 28 results for author: Fallah, A

Response Time Enhances Alignment with Heterogeneous Preferences

Authors: Federico Echenique, Alireza Fallah, Baihe Huang, Michael I. Jordan

Abstract: Aligning large language models (LLMs) to human preferences typically relies on aggregating pooled feedback into a single reward model. However, this standard approach assumes that all labelers share the same underlying preferences, ignoring the fact that real-world labelers are highly heterogeneous and usually anonymous. Consequently, relying solely on binary choice data fundamentally distorts the… ▽ More Aligning large language models (LLMs) to human preferences typically relies on aggregating pooled feedback into a single reward model. However, this standard approach assumes that all labelers share the same underlying preferences, ignoring the fact that real-world labelers are highly heterogeneous and usually anonymous. Consequently, relying solely on binary choice data fundamentally distorts the learned policy, making the true population-average preference unidentifiable. To overcome this critical limitation, we demonstrate that augmenting preference datasets with a simple, secondary signal -- the user's response time -- can restore the identifiability of the population's average preference. By modeling each decision as a Drift-Diffusion Model (DDM), we introduce a novel, consistent estimator of heterogeneous preferences that successfully corrects the distortions of standard choice-only labels. We prove that our estimator asymptotically converges to the true average preference even in extreme cases where each anonymous labeler contributes only a single choice. Empirically, across both synthetic and real-world datasets, our method consistently outperforms standard baselines that otherwise fail and plateau at a bias floor. Because response times are essentially free to record and require zero user tracking or identification, our results bring promises and open up new opportunities for future data-collection pipelines to improve the social benefit without requiring user-level identifiers or repeated elicitations. △ Less

Submitted 7 May, 2026; originally announced May 2026.

Signaling in Data Markets via Free Samples

Authors: Nivasini Ananthakrishnan, Alireza Fallah, Michael I. Jordan

Abstract: We study a setting in which a data buyer seeks to estimate an unknown parameter by purchasing samples from one of K data sellers. Each seller has privately known data quality (e.g., high vs. low variance) and a private per-sample cost. We consider a multi-stage game in which the first stage is a free-trial stage in which the sellers have the option of signaling data quality by offering a few sampl… ▽ More We study a setting in which a data buyer seeks to estimate an unknown parameter by purchasing samples from one of K data sellers. Each seller has privately known data quality (e.g., high vs. low variance) and a private per-sample cost. We consider a multi-stage game in which the first stage is a free-trial stage in which the sellers have the option of signaling data quality by offering a few samples of data for free. Buyers update their beliefs based on the sample variance of the free data and then run a procurement auction to buy data in a second stage. For the auction stage, we characterize an approximately optimal Bayesian incentive compatible mechanism: the buyer selects a single seller by minimizing a belief-adjusted virtual cost and chooses the purchased sample size as a function of posterior quality and virtual cost. For the free-trial stage, we characterize the equilibrium, taking the above mechanism as the continuation game. Free trials may fail to emerge: for some parameters, all sellers reveal zero samples. However, under sufficiently strong competition (large K), there is an equilibrium in which sellers reveal the maximum allowable number of samples; in fact, it is the unique equilibrium. △ Less

Submitted 18 February, 2026; originally announced February 2026.

Quantization-aware Photonic Homodyne computing for Accelerated Artificial Intelligence and Scientific Simulation

Authors: Lian Zhou, Kaiwen Xue, Amirhossein Fallah, Lijin Liu, Chun-Ho Lee, Kiwon Kwon, Clayton Cheung, Yuan Li, Yue Yu, Yun-Jhu Lee, Songlin Zhao, Ryan Hamerly, Edo Waks, Dirk Englund, Constantine Sideris, Mengjie Yu, Zaijun Chen

Abstract: Modern problems in high-performance computing, ranging from training and inferencing deep learning models in computer vision and language models to simulating complex physical systems with nonlinearly-coupled equations, require exponential growth of computational resources. Photonic analog systems are emerging with solutions of intrinsic parallelism, high bandwidth, and low propagation loss. Howev… ▽ More Modern problems in high-performance computing, ranging from training and inferencing deep learning models in computer vision and language models to simulating complex physical systems with nonlinearly-coupled equations, require exponential growth of computational resources. Photonic analog systems are emerging with solutions of intrinsic parallelism, high bandwidth, and low propagation loss. However, their application has been hindered by the low analog accuracy due to the electro-optic distortion, material nonlinearities, and signal-to-noise ratios. Here we overcome this barrier with a quantization-aware digital-photonic mixed-precision framework across chiplets for accelerated AI processing and physical simulation. Using Lithium Niobate photonics with channel equalization techniques, we demonstrate linear multiplication (9-bit amplitude-phase decoupling) in homodyne optical logics with 6-bit precision at the clock rate of 128 giga-symbol-per-second (128 GS/s), enabling AI processing with 6 ns latency. Codesign hardware-algorithms, including iterative solvers, sparse-dense quantization, and bit-sliced matrix multiplication, explore photonic amplitude and phase coherence for complex-valued, physics-inspired computation. In electromagnetic problems, our approach yields 12-bit solutions for partial differential equations (PDEs) in scattering problems that would conventionally require up to 32-bit and often even 64-bit precision. These results preserve digital-level fidelity while leveraging the high-speed low-energy photonic hardware, establishing a pathway toward general-purpose optical acceleration for generative artificial intelligence, real-time robotics, and accurate simulation for climate challenges and biological discoveries. △ Less

Submitted 9 February, 2026; originally announced February 2026.

High-Probability Bounds For Heterogeneous Local Differential Privacy

Authors: Maryam Aliakbarpour, Alireza Fallah, Swaha Roy, Ria Stevens

Abstract: We study statistical estimation under local differential privacy (LDP) when users may hold heterogeneous privacy levels and accuracy must be guaranteed with high probability. Departing from the common in-expectation analyses, and for one-dimensional and multi-dimensional mean estimation problems, we develop finite sample upper bounds in $\ell_2$-norm that hold with probability at least $1-β$. We c… ▽ More We study statistical estimation under local differential privacy (LDP) when users may hold heterogeneous privacy levels and accuracy must be guaranteed with high probability. Departing from the common in-expectation analyses, and for one-dimensional and multi-dimensional mean estimation problems, we develop finite sample upper bounds in $\ell_2$-norm that hold with probability at least $1-β$. We complement these results with matching minimax lower bounds, establishing the optimality (up to constants) of our guarantees in the heterogeneous LDP regime. We further study distribution learning in $\ell_\infty$-distance, designing an algorithm with high-probability guarantees under heterogeneous privacy demands. Our techniques offer principled guidance for designing mechanisms in settings with user-specific privacy levels. △ Less

Submitted 13 October, 2025; originally announced October 2025.

The Statistical Fairness-Accuracy Frontier

Authors: Alireza Fallah, Michael I. Jordan, Annie Ulichney

Abstract: We study fairness-accuracy tradeoffs when a single predictive model must serve multiple demographic groups. A useful tool for understanding this tradeoff is the fairness-accuracy (FA) Pareto frontier, which characterizes the set of models that cannot be improved in either fairness or accuracy without worsening the other. While characterizing the FA frontier requires full knowledge of the data dist… ▽ More We study fairness-accuracy tradeoffs when a single predictive model must serve multiple demographic groups. A useful tool for understanding this tradeoff is the fairness-accuracy (FA) Pareto frontier, which characterizes the set of models that cannot be improved in either fairness or accuracy without worsening the other. While characterizing the FA frontier requires full knowledge of the data distribution, we focus on the finite-sample regime, quantifying how well a designer can approximate any point on the frontier from limited data and bounding the worst-case gap. In particular, we derive worst-case-optimal estimators that depend on the designer's knowledge of the covariate distribution. For each estimator, we characterize how finite-sample effects asymmetrically impact each group's welfare and identify optimal sample allocation strategies. Finally, we provide uniform finite-sample bounds for the entire FA frontier, yielding confidence bands that quantify the reliability of welfare comparisons across alternative fairness-accuracy tradeoffs. △ Less

Submitted 16 February, 2026; v1 submitted 24 August, 2025; originally announced August 2025.

A General Framework for Estimating Preferences Using Response Time Data

Authors: Federico Echenique, Alireza Fallah, Michael I. Jordan

Abstract: We propose a general methodology for recovering preference parameters from data on choices and response times. Our methods yield estimates with fast ($1/n$ for $n$ data points) convergence rates when specialized to the popular Drift Diffusion Model (DDM), but are broadly applicable to generalizations of the DDM as well as to alternative models of decision making that make use of response time data… ▽ More We propose a general methodology for recovering preference parameters from data on choices and response times. Our methods yield estimates with fast ($1/n$ for $n$ data points) convergence rates when specialized to the popular Drift Diffusion Model (DDM), but are broadly applicable to generalizations of the DDM as well as to alternative models of decision making that make use of response time data. The paper develops an empirical application to an experiment on intertemporal choice, showing that the use of response times delivers predictive accuracy and matters for the estimation of economically relevant parameters. △ Less

Submitted 31 July, 2025; v1 submitted 27 July, 2025; originally announced July 2025.

Vessel Length Estimation from Magnetic Wake Signature: A Physics-Informed Residual Neural Network Approach

Authors: Mohammad Amir Fallah, Mehdi Monemi, Matti Latva-aho

Abstract: Marine remote sensing enhances maritime surveillance, environmental monitoring, and naval operations. Vessel length estimation, a key component of this technology, supports effective maritime surveillance by empowering features such as vessel classification. Departing from traditional methods relying on two-dimensional hydrodynamic wakes or computationally intensive satellite imagery, this paper i… ▽ More Marine remote sensing enhances maritime surveillance, environmental monitoring, and naval operations. Vessel length estimation, a key component of this technology, supports effective maritime surveillance by empowering features such as vessel classification. Departing from traditional methods relying on two-dimensional hydrodynamic wakes or computationally intensive satellite imagery, this paper introduces an innovative approach for vessel length estimation that leverages the subtle magnetic wake signatures of vessels, captured through a low-complexity one-dimensional profile from a single airborne magnetic sensor scan. The proposed method centers around our characterized nonlinear integral equations that connect the magnetic wake to the vessel length within a realistic finite-depth marine environment. To solve the derived equations, we initially leverage a deep residual neural network (DRNN). The proposed DRNN-based solution framework is shown to be unable to exactly learn the intricate relationships between parameters when constrained by a limited training-dataset. To overcome this issue, we introduce an innovative approach leveraging a physics-informed residual neural network (PIRNN). This model integrates physical formulations directly into the loss function, leading to improved performance in terms of both accuracy and convergence speed. Considering a sensor scan angle of less than $15^\circ$, which maintains a reasonable margin below Kelvin's limit angle of $19.5^\circ$, we explore the impact of various parameters on the accuracy of the vessel length estimation, including sensor scan angle, vessel speed, and sea depth. Numerical simulations demonstrate the superiority of the proposed PIRNN method, achieving mean length estimation errors consistently below 5\% for vessels longer than 100m. For shorter vessels, the errors generally remain under 10\%. △ Less

Submitted 27 April, 2025; originally announced April 2025.

Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy

Authors: Maryam Aliakbarpour, Syomantak Chaudhuri, Thomas A. Courtade, Alireza Fallah, Michael I. Jordan

Abstract: Local Differential Privacy (LDP) offers strong privacy guarantees without requiring users to trust external parties. However, LDP applies uniform protection to all data features, including less sensitive ones, which degrades performance of downstream tasks. To overcome this limitation, we propose a Bayesian framework, Bayesian Coordinate Differential Privacy (BCDP), that enables feature-specific p… ▽ More Local Differential Privacy (LDP) offers strong privacy guarantees without requiring users to trust external parties. However, LDP applies uniform protection to all data features, including less sensitive ones, which degrades performance of downstream tasks. To overcome this limitation, we propose a Bayesian framework, Bayesian Coordinate Differential Privacy (BCDP), that enables feature-specific privacy quantification. This more nuanced approach complements LDP by adjusting privacy protection according to the sensitivity of each feature, enabling improved performance of downstream tasks without compromising privacy. We characterize the properties of BCDP and articulate its connections with standard non-Bayesian privacy frameworks. We further apply our BCDP framework to the problems of private mean estimation and ordinary least-squares regression. The BCDP-based approach obtains improved accuracy compared to a purely LDP-based approach, without compromising on privacy. △ Less

Submitted 23 October, 2024; originally announced October 2024.

Fair Allocation in Dynamic Mechanism Design

Authors: Alireza Fallah, Michael I. Jordan, Annie Ulichney

Abstract: We consider a dynamic mechanism design problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group. We begin by studying the static case ($T=1$) and establish that the optimal me… ▽ More We consider a dynamic mechanism design problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group. We begin by studying the static case ($T=1$) and establish that the optimal mechanism involves two types of subsidization: one that increases the overall probability of allocation to all buyers, and another that favors the groups which otherwise have a lower probability of winning the item. We then extend our results to the dynamic case by characterizing a set of recursive functions that determine the optimal allocation and payments in each round. Notably, our results establish that in the dynamic case, the seller, on the one hand, commits to a participation bonus to incentivize truth-telling, and on the other hand, charges an entry fee for every round. Moreover, the optimal allocation once more involves subsidization, which its extent depends on the difference in future utilities for both the seller and buyers when allocating the item to one group versus the others. Finally, we present an approximation scheme to solve the recursive equations and determine an approximately optimal and fair allocation efficiently. △ Less

Submitted 3 October, 2024; v1 submitted 31 May, 2024; originally announced June 2024.

Comments: A shorter conference version has been accepted at the Advances in Neural Information Processing Systems (NeurIPS) 2024

Near-Field Spot Beamfocusing: A Correlation-Aware Transfer Learning Approach

Authors: Mohammad Amir Fallah, Mehdi Monemi, Mehdi Rasti, Matti Latva-Aho

Abstract: Three-dimensional (3D) spot beamfocusing (SBF), in contrast to conventional angular-domain beamforming, concentrates radiating power within a very small volume in both radial and angular domains in the near-field zone. Recently the implementation of channel-state-information (CSI)-independent machine learning (ML)-based approaches have been developed for effective SBF using extremely large-scale p… ▽ More Three-dimensional (3D) spot beamfocusing (SBF), in contrast to conventional angular-domain beamforming, concentrates radiating power within a very small volume in both radial and angular domains in the near-field zone. Recently the implementation of channel-state-information (CSI)-independent machine learning (ML)-based approaches have been developed for effective SBF using extremely large-scale programmable metasurface (ELPMs). These methods involve dividing the ELPMs into subarrays and independently training them with Deep Reinforcement Learning to jointly focus the beam at the desired focal point (DFP). This paper explores near-field SBF using ELPMs, addressing challenges associated with lengthy training times resulting from independent training of subarrays. To achieve a faster CSI-independent solution, inspired by the correlation between the beamfocusing matrices of the subarrays, we leverage transfer learning techniques. First, we introduce a novel similarity criterion based on the phase distribution image (PDI) of subarray apertures. Then we devise a subarray policy propagation scheme that transfers the knowledge from trained to untrained subarrays. We further enhance learning by introducing quasi-liquid layers as a revised version of the adaptive policy reuse technique. We show through simulations that the proposed scheme improves the training speed about 5 times. Furthermore, for dynamic DFP management, we devised a DFP policy blending process, which augments the convergence rate up to 8-fold. △ Less

Submitted 16 December, 2024; v1 submitted 21 May, 2024; originally announced May 2024.

On Three-Layer Data Markets

Authors: Alireza Fallah, Michael I. Jordan, Ali Makhdoumi, Azarakhsh Malekian

Abstract: We study a three-layer data market comprising users (data owners), platforms, and a data buyer. Each user benefits from platform services in exchange for data, incurring privacy loss when their data, albeit noisily, is shared with the buyer. The user chooses platforms to share data with, while platforms decide on data noise levels and pricing before selling to the buyer. The buyer selects platform… ▽ More We study a three-layer data market comprising users (data owners), platforms, and a data buyer. Each user benefits from platform services in exchange for data, incurring privacy loss when their data, albeit noisily, is shared with the buyer. The user chooses platforms to share data with, while platforms decide on data noise levels and pricing before selling to the buyer. The buyer selects platforms to purchase data from. We model these interactions via a multi-stage game, focusing on the subgame Nash equilibrium. We find that when the buyer places a high value on user data (and platforms can command high prices), all platforms offer services to the user who joins and shares data with every platform. Conversely, when the buyer's valuation of user data is low, only large platforms with low service costs can afford to serve users. In this scenario, users exclusively join and share data with these low-cost platforms. Interestingly, increased competition benefits the buyer, not the user: as the number of platforms increases, the user utility does not necessarily improve while the buyer utility improves. However, increasing the competition improves the overall utilitarian welfare. Building on our analysis, we then study regulations to improve the user utility. We discover that banning data sharing maximizes user utility only when all platforms are low-cost. In mixed markets of high- and low-cost platforms, users prefer a minimum noise mandate over a sharing ban. Imposing this mandate on high-cost platforms and banning data sharing for low-cost ones further enhances user utility. △ Less

Submitted 17 November, 2025; v1 submitted 14 February, 2024; originally announced February 2024.

The Limits of Price Discrimination Under Privacy Constraints

Authors: Alireza Fallah, Michael I. Jordan, Ali Makhdoumi, Azarakhsh Malekian

Abstract: We study a producer's problem of selling a product to a continuum of privacy-conscious consumers, where the producer can implement third-degree price discrimination, offering different prices to different market segments. We consider a privacy mechanism that provides a degree of protection by probabilistically masking each market segment. We establish that the resultant set of all consumer-produce… ▽ More We study a producer's problem of selling a product to a continuum of privacy-conscious consumers, where the producer can implement third-degree price discrimination, offering different prices to different market segments. We consider a privacy mechanism that provides a degree of protection by probabilistically masking each market segment. We establish that the resultant set of all consumer-producer utilities forms a convex polygon, characterized explicitly as a linear mapping of a certain high-dimensional convex polytope into $\mathbb{R}^2$. This characterization enables us to investigate the impact of the privacy mechanism on both producer and consumer utilities. In particular, we establish that the privacy constraint always hurts the producer by reducing both the maximum and minimum utility achievable. From the consumer's perspective, although the privacy mechanism ensures an increase in the minimum utility compared to the non-private scenario, interestingly, it may reduce the maximum utility. Finally, we demonstrate that increasing the privacy level does not necessarily intensify these effects. For instance, the maximum utility for the producer or the minimum utility for the consumer may exhibit nonmonotonic behavior in response to an increase of the privacy level. △ Less

Submitted 16 June, 2024; v1 submitted 13 February, 2024; originally announced February 2024.

Towards Near-Field 3D Spot Beamfocusing: Possibilities, Challenges, and Use-cases

Authors: Mehdi Monemi, Mohammad Amir Fallah, Mehdi Rasti, Matti Latva-Aho, Merouane Debbah

Abstract: Spot beamfocusing (SBF) is the process of focusing the signal power in a small spot-like region in the 3D space, which can be either hard-tuned (HT) using traditional tools like lenses and mirrors or electronically reconfigured (ER) using modern large-scale intelligent surface phased arrays. ER-SBF can be a key enabling technology (KET) for the next-generation 6G wireless networks offering benefit… ▽ More Spot beamfocusing (SBF) is the process of focusing the signal power in a small spot-like region in the 3D space, which can be either hard-tuned (HT) using traditional tools like lenses and mirrors or electronically reconfigured (ER) using modern large-scale intelligent surface phased arrays. ER-SBF can be a key enabling technology (KET) for the next-generation 6G wireless networks offering benefits to many future wireless application areas such as wireless communication and security, mid-range high-power and safe wireless chargers, medical and health, physics, etc. Although near-field HT-SBF and ER-beamfocusing have been studied in the literature and applied in the industry, there is no comprehensive study of different aspects of ER-SBF and its future applications, especially for nonoptical (mmWave, sub-THz, and THz) electromagnetic waves in the next generation wireless technology, which is the aim of this paper. The theoretical concepts behind ER-SBF, different antenna technologies for implementing ER-SBF, employing machine learning (ML)-based schemes for enabling channel-state-information (CSI)-independent ER-SBF, and different practical application areas that can benefit from ER-SBF will be explored. △ Less

Submitted 19 August, 2024; v1 submitted 24 December, 2023; originally announced January 2024.

Contract Design With Safety Inspections

Authors: Alireza Fallah, Michael I. Jordan

Abstract: We study the role of regulatory inspections in a contract design problem in which a principal interacts separately with multiple agents. Each agent's hidden action includes a dimension that determines whether they undertake an extra costly step to adhere to safety protocols. The principal's objective is to use payments combined with a limited budget for random inspections to incentivize agents tow… ▽ More We study the role of regulatory inspections in a contract design problem in which a principal interacts separately with multiple agents. Each agent's hidden action includes a dimension that determines whether they undertake an extra costly step to adhere to safety protocols. The principal's objective is to use payments combined with a limited budget for random inspections to incentivize agents towards safety-compliant actions that maximize the principal's utility. We first focus on the single-agent setting with linear contracts and present an efficient algorithm that characterizes the optimal linear contract, which includes both payment and random inspection. We further investigate how the optimal contract changes as the inspection cost or the cost of adhering to safety protocols vary. Notably, we demonstrate that the agent's compensation increases if either of these costs escalates. However, while the probability of inspection decreases with rising inspection costs, it demonstrates nonmonotonic behavior as a function of the safety action costs. Lastly, we explore the multi-agent setting, where the principal's challenge is to determine the best distribution of inspection budgets among all agents. We propose an efficient approach based on dynamic programming to find an approximately optimal allocation of inspection budget across contracts. We also design a random sequential scheme to determine the inspector's assignments, ensuring each agent is inspected at most once and at the desired probability. Finally, we present a case study illustrating that a mere difference in the cost of inspection across various agents can drive the principal's decision to forego inspecting a significant fraction of them, concentrating its entire budget on those that are less costly to inspect. △ Less

Submitted 4 November, 2023; originally announced November 2023.

Prediction Based Decision Making for Autonomous Highway Driving

Authors: Mustafa Yildirim, Sajjad Mozaffari, Luc McCutcheon, Mehrdad Dianati, Alireza Tamaddoni-Nezhad Saber Fallah

Abstract: Autonomous driving decision-making is a challenging task due to the inherent complexity and uncertainty in traffic. For example, adjacent vehicles may change their lane or overtake at any time to pass a slow vehicle or to help traffic flow. Anticipating the intention of surrounding vehicles, estimating their future states and integrating them into the decision-making process of an automated vehicl… ▽ More Autonomous driving decision-making is a challenging task due to the inherent complexity and uncertainty in traffic. For example, adjacent vehicles may change their lane or overtake at any time to pass a slow vehicle or to help traffic flow. Anticipating the intention of surrounding vehicles, estimating their future states and integrating them into the decision-making process of an automated vehicle can enhance the reliability of autonomous driving in complex driving scenarios. This paper proposes a Prediction-based Deep Reinforcement Learning (PDRL) decision-making model that considers the manoeuvre intentions of surrounding vehicles in the decision-making process for highway driving. The model is trained using real traffic data and tested in various traffic conditions through a simulation platform. The results show that the proposed PDRL model improves the decision-making performance compared to a Deep Reinforcement Learning (DRL) model by decreasing collision numbers, resulting in safer driving. △ Less

Submitted 5 September, 2022; originally announced September 2022.

Comments: Published at ITSC 2022

Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms

Authors: Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, Asuman Ozdaglar

Abstract: We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy cost which we quantify using diffe… ▽ More We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy cost which we quantify using differential privacy. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. In both settings, we establish minimax lower bounds for the estimation error and derive (near) optimal estimators for given heterogeneous privacy loss levels for users. Building on this characterization, we pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities. Under a regularity condition on the distribution of privacy sensitivities we develop efficient algorithmic mechanisms to solve this problem in both privacy settings. Our mechanism in the central setting can be implemented in time $\mathcal{O}(n \log n)$ where $n$ is the number of users and our mechanism in the local setting admits a Polynomial Time Approximation Scheme (PTAS). △ Less

Submitted 5 September, 2023; v1 submitted 9 January, 2022; originally announced January 2022.

Comments: To appear in the Operations Research journal. The abstract appeared in the Proceedings of the 23rd ACM Conference on Economics and Computation (EC 2022)

Private Adaptive Gradient Methods for Convex Optimization

Authors: Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, Kunal Talwar

Abstract: We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm with adaptive stepsizes, as well as the AdaGrad algorithm. We provide upper bounds on the regret of both algorithms and show that the bounds are (worst-case) optimal. As a consequence of our development, we show that our… ▽ More We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm with adaptive stepsizes, as well as the AdaGrad algorithm. We provide upper bounds on the regret of both algorithms and show that the bounds are (worst-case) optimal. As a consequence of our development, we show that our private versions of AdaGrad outperform adaptive SGD, which in turn outperforms traditional SGD in scenarios with non-isotropic gradients where (non-private) Adagrad provably outperforms SGD. The major challenge is that the isotropic noise typically added for privacy dominates the signal in gradient geometry for high-dimensional problems; approaches to this that effectively optimize over lower-dimensional subspaces simply ignore the actual problems that varying gradient geometries introduce. In contrast, we study non-isotropic clipping and noise addition, developing a principled theoretical approach; the consequent procedures also enjoy significantly stronger empirical performance than prior approaches. △ Less

Submitted 25 June, 2021; originally announced June 2021.

Comments: To appear in 38th International Conference on Machine Learning (ICML 2021)

A Wasserstein Minimax Framework for Mixed Linear Regression

Authors: Theo Diamandis, Yonina C. Eldar, Alireza Fallah, Farzan Farnia, Asuman Ozdaglar

Abstract: Multi-modal distributions are commonly used to model clustered data in statistical learning tasks. In this paper, we consider the Mixed Linear Regression (MLR) problem. We propose an optimal transport-based framework for MLR problems, Wasserstein Mixed Linear Regression (WMLR), which minimizes the Wasserstein distance between the learned and target mixture regression models. Through a model-based… ▽ More Multi-modal distributions are commonly used to model clustered data in statistical learning tasks. In this paper, we consider the Mixed Linear Regression (MLR) problem. We propose an optimal transport-based framework for MLR problems, Wasserstein Mixed Linear Regression (WMLR), which minimizes the Wasserstein distance between the learned and target mixture regression models. Through a model-based duality analysis, WMLR reduces the underlying MLR task to a nonconvex-concave minimax optimization problem, which can be provably solved to find a minimax stationary point by the Gradient Descent Ascent (GDA) algorithm. In the special case of mixtures of two linear regression models, we show that WMLR enjoys global convergence and generalization guarantees. We prove that WMLR's sample complexity grows linearly with the dimension of data. Finally, we discuss the application of WMLR to the federated learning task where the training samples are collected by multiple agents in a network. Unlike the Expectation Maximization algorithm, WMLR directly extends to the distributed, federated learning setting. We support our theoretical results through several numerical experiments, which highlight our framework's ability to handle the federated learning setting with mixture models. △ Less

Submitted 16 June, 2021; v1 submitted 14 June, 2021; originally announced June 2021.

Comments: To appear in 38th International Conference on Machine Learning (ICML 2021)

Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks

Authors: Alireza Fallah, Aryan Mokhtari, Asuman Ozdaglar

Abstract: In this paper, we study the generalization properties of Model-Agnostic Meta-Learning (MAML) algorithms for supervised learning problems. We focus on the setting in which we train the MAML model over $m$ tasks, each with $n$ data points, and characterize its generalization error from two points of view: First, we assume the new task at test time is one of the training tasks, and we show that, for… ▽ More In this paper, we study the generalization properties of Model-Agnostic Meta-Learning (MAML) algorithms for supervised learning problems. We focus on the setting in which we train the MAML model over $m$ tasks, each with $n$ data points, and characterize its generalization error from two points of view: First, we assume the new task at test time is one of the training tasks, and we show that, for strongly convex objective functions, the expected excess population loss is bounded by ${\mathcal{O}}(1/mn)$. Second, we consider the MAML algorithm's generalization to an unseen task and show that the resulting generalization error depends on the total variation distance between the underlying distributions of the new task and the tasks observed during the training process. Our proof techniques rely on the connections between algorithmic stability and generalization bounds of algorithms. In particular, we propose a new definition of stability for meta-learning algorithms, which allows us to capture the role of both the number of tasks $m$ and number of samples per task $n$ on the generalization error of MAML. △ Less

Submitted 16 November, 2021; v1 submitted 7 February, 2021; originally announced February 2021.

Comments: 35th Conference on Neural Information Processing Systems (NeurIPS 2021)

Entropic Compressibility of Lévy Processes

Authors: Julien Fageot, Alireza Fallah, Thibaut Horel

Abstract: In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the self-similar Wiener process to piecewise-constant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari (2018), we characterize their compressibility by studying the entropy of their double discretization (both… ▽ More In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the self-similar Wiener process to piecewise-constant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari (2018), we characterize their compressibility by studying the entropy of their double discretization (both in time and amplitude) in the regime of vanishing discretization steps. For a Lévy process with absolutely continuous marginals, this reduces to understanding the asymptotics of the differential entropy of its marginals at small times, for which we obtain a new local central limit theorem. We generalize known results for stable processes to the non-stable case, with a special focus on Lévy processes that are locally self-similar, and conceptualize a new compressibility hierarchy of Lévy processes, captured by their Blumenthal-Getoor index. △ Less

Submitted 15 May, 2022; v1 submitted 22 September, 2020; originally announced September 2020.

Comments: 34 pages, 1 figure

MSC Class: 60E07; 94A17; 60G18

Journal ref: IEEE Transactions on Information Theory, 68 (8), 2022, pp. 4949-4963

Personalized Federated Learning: A Meta-Learning Approach

Authors: Alireza Fallah, Aryan Mokhtari, Asuman Ozdaglar

Abstract: In Federated Learning, we aim to train models across multiple computing units (users), while users can only communicate with a common central server, without exchanging their data samples. This mechanism exploits the computational power of all users and allows users to obtain a richer model as their models are trained over a larger set of data points. However, this scheme only develops a common ou… ▽ More In Federated Learning, we aim to train models across multiple computing units (users), while users can only communicate with a common central server, without exchanging their data samples. This mechanism exploits the computational power of all users and allows users to obtain a richer model as their models are trained over a larger set of data points. However, this scheme only develops a common output for all the users, and, therefore, it does not adapt the model to each user. This is an important missing feature, especially given the heterogeneity of the underlying data distribution for various users. In this paper, we study a personalized variant of the federated learning in which our goal is to find an initial shared model that current or new users can easily adapt to their local dataset by performing one or a few steps of gradient descent with respect to their own data. This approach keeps all the benefits of the federated learning architecture, and, by structure, leads to a more personalized model for each user. We show this problem can be studied within the Model-Agnostic Meta-Learning (MAML) framework. Inspired by this connection, we study a personalized variant of the well-known Federated Averaging algorithm and evaluate its performance in terms of gradient norm for non-convex loss functions. Further, we characterize how this performance is affected by the closeness of underlying distributions of user data, measured in terms of distribution distances such as Total Variation and 1-Wasserstein metric. △ Less

Submitted 22 October, 2020; v1 submitted 18 February, 2020; originally announced February 2020.

Comments: To appear in 34th Conference on Neural Information Processing Systems (NeurIPS 2020)

An Optimal Multistage Stochastic Gradient Method for Minimax Problems

Authors: Alireza Fallah, Asuman Ozdaglar, Sarath Pattathil

Abstract: In this paper, we study the minimax optimization problem in the smooth and strongly convex-strongly concave setting when we have access to noisy estimates of gradients. In particular, we first analyze the stochastic Gradient Descent Ascent (GDA) method with constant stepsize, and show that it converges to a neighborhood of the solution of the minimax problem. We further provide tight bounds on the… ▽ More In this paper, we study the minimax optimization problem in the smooth and strongly convex-strongly concave setting when we have access to noisy estimates of gradients. In particular, we first analyze the stochastic Gradient Descent Ascent (GDA) method with constant stepsize, and show that it converges to a neighborhood of the solution of the minimax problem. We further provide tight bounds on the convergence rate and the size of this neighborhood. Next, we propose a multistage variant of stochastic GDA (M-GDA) that runs in multiple stages with a particular learning rate decay schedule and converges to the exact solution of the minimax problem. We show M-GDA achieves the lower bounds in terms of noise dependence without any assumptions on the knowledge of noise characteristics. We also show that M-GDA obtains a linear decay rate with respect to the error's dependence on the initial error, although the dependence on condition number is suboptimal. In order to improve this dependence, we apply the multistage machinery to the stochastic Optimistic Gradient Descent Ascent (OGDA) algorithm and propose the M-OGDA algorithm which also achieves the optimal linear decay rate with respect to the initial error. To the best of our knowledge, this method is the first to simultaneously achieve the best dependence on noise characteristic as well as the initial error and condition number. △ Less

Submitted 13 February, 2020; originally announced February 2020.

On the Convergence Theory of Debiased Model-Agnostic Meta-Reinforcement Learning

Authors: Alireza Fallah, Kristian Georgiev, Aryan Mokhtari, Asuman Ozdaglar

Abstract: We consider Model-Agnostic Meta-Learning (MAML) methods for Reinforcement Learning (RL) problems, where the goal is to find a policy using data from several tasks represented by Markov Decision Processes (MDPs) that can be updated by one step of stochastic policy gradient for the realized MDP. In particular, using stochastic gradients in MAML update steps is crucial for RL problems since computati… ▽ More We consider Model-Agnostic Meta-Learning (MAML) methods for Reinforcement Learning (RL) problems, where the goal is to find a policy using data from several tasks represented by Markov Decision Processes (MDPs) that can be updated by one step of stochastic policy gradient for the realized MDP. In particular, using stochastic gradients in MAML update steps is crucial for RL problems since computation of exact gradients requires access to a large number of possible trajectories. For this formulation, we propose a variant of the MAML method, named Stochastic Gradient Meta-Reinforcement Learning (SG-MRL), and study its convergence properties. We derive the iteration and sample complexity of SG-MRL to find an $ε$-first-order stationary point, which, to the best of our knowledge, provides the first convergence guarantee for model-agnostic meta-reinforcement learning algorithms. We further show how our results extend to the case where more than one step of stochastic policy gradient method is used at test time. Finally, we empirically compare SG-MRL and MAML in several deep RL environments. △ Less

Submitted 16 November, 2021; v1 submitted 12 February, 2020; originally announced February 2020.

Comments: 35th Conference on Neural Information Processing Systems (NeurIPS 2021)

Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks

Authors: Alireza Fallah, Mert Gurbuzbalaban, Asuman Ozdaglar, Umut Simsekli, Lingjiong Zhu

Abstract: We study distributed stochastic gradient (D-SG) method and its accelerated variant (D-ASG) for solving decentralized strongly convex stochastic optimization problems where the objective function is distributed over several computational units, lying on a fixed but arbitrary connected communication graph, subject to local communication constraints where noisy estimates of the gradients are availabl… ▽ More We study distributed stochastic gradient (D-SG) method and its accelerated variant (D-ASG) for solving decentralized strongly convex stochastic optimization problems where the objective function is distributed over several computational units, lying on a fixed but arbitrary connected communication graph, subject to local communication constraints where noisy estimates of the gradients are available. We develop a framework which allows to choose the stepsize and the momentum parameters of these algorithms in a way to optimize performance by systematically trading off the bias, variance, robustness to gradient noise and dependence to network effects. When gradients do not contain noise, we also prove that distributed accelerated methods can \emph{achieve acceleration}, requiring $\mathcal{O}(κ\log(1/\varepsilon))$ gradient evaluations and $\mathcal{O}(κ\log(1/\varepsilon))$ communications to converge to the same fixed point with the non-accelerated variant where $κ$ is the condition number and $\varepsilon$ is the target accuracy. To our knowledge, this is the first acceleration result where the iteration complexity scales with the square root of the condition number in the context of \emph{primal} distributed inexact first-order methods. For quadratic functions, we also provide finer performance bounds that are tight with respect to bias and variance terms. Finally, we study a multistage version of D-ASG with parameters carefully varied over stages to ensure exact $\mathcal{O}(-k/\sqrtκ)$ linear decay in the bias term as well as optimal $\mathcal{O}(σ^2/k)$ in the variance term. We illustrate through numerical experiments that our approach results in practical algorithms that are robust to gradient noise and that can outperform existing methods. △ Less

Submitted 4 October, 2021; v1 submitted 19 October, 2019; originally announced October 2019.

On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms

Authors: Alireza Fallah, Aryan Mokhtari, Asuman Ozdaglar

Abstract: We study the convergence of a class of gradient-based Model-Agnostic Meta-Learning (MAML) methods and characterize their overall complexity as well as their best achievable accuracy in terms of gradient norm for nonconvex loss functions. We start with the MAML method and its first-order approximation (FO-MAML) and highlight the challenges that emerge in their analysis. By overcoming these challeng… ▽ More We study the convergence of a class of gradient-based Model-Agnostic Meta-Learning (MAML) methods and characterize their overall complexity as well as their best achievable accuracy in terms of gradient norm for nonconvex loss functions. We start with the MAML method and its first-order approximation (FO-MAML) and highlight the challenges that emerge in their analysis. By overcoming these challenges not only we provide the first theoretical guarantees for MAML and FO-MAML in nonconvex settings, but also we answer some of the unanswered questions for the implementation of these algorithms including how to choose their learning rate and the batch size for both tasks and datasets corresponding to tasks. In particular, we show that MAML can find an $ε$-first-order stationary point ($ε$-FOSP) for any positive $ε$ after at most $\mathcal{O}(1/ε^2)$ iterations at the expense of requiring second-order information. We also show that FO-MAML which ignores the second-order information required in the update of MAML cannot achieve any small desired level of accuracy, i.e., FO-MAML cannot find an $ε$-FOSP for any $ε>0$. We further propose a new variant of the MAML algorithm called Hessian-free MAML which preserves all theoretical guarantees of MAML, without requiring access to second-order information. △ Less

Submitted 15 May, 2020; v1 submitted 27 August, 2019; originally announced August 2019.

Comments: To appear in the proceedings of the $23^{rd}$ International Conference on Artificial Intelligence and Statistics (AISTATS) 2020

A Universally Optimal Multistage Accelerated Stochastic Gradient Method

Authors: Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, Asuman Ozdaglar

Abstract: We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is universally optimal in the sense that it achieves the optimal rate both in the deterministic and stochastic case and operates without knowledge of noise characteristics. The algorithm consists of stages that use a stochastic… ▽ More We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is universally optimal in the sense that it achieves the optimal rate both in the deterministic and stochastic case and operates without knowledge of noise characteristics. The algorithm consists of stages that use a stochastic version of Nesterov's method with a specific restart and parameters selected to achieve the fastest reduction in the bias-variance terms in the convergence rate bounds. △ Less

Submitted 27 October, 2019; v1 submitted 23 January, 2019; originally announced January 2019.

Comments: 33rd Conference on Neural Information Processing Systems (NeurIPS 2019)

Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions

Authors: Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, Asuman Ozdaglar

Abstract: We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent (GD) and accelerated gradient (AG) methods for minimizing strongly convex functions when the gradient has random errors in the form of additive white noise. With gradient errors, the function values of the iterates need not converge to the optimal va… ▽ More We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent (GD) and accelerated gradient (AG) methods for minimizing strongly convex functions when the gradient has random errors in the form of additive white noise. With gradient errors, the function values of the iterates need not converge to the optimal value; hence, we define the robustness of an algorithm to noise as the asymptotic expected suboptimality of the iterate sequence to input noise power. For this robustness measure, we provide exact expressions for the quadratic case using tools from robust control theory and tight upper bounds for the smooth strongly convex case using Lyapunov functions certified through matrix inequalities. We use these characterizations within an optimization problem which selects parameters of each algorithm to achieve a particular trade-off between rate and robustness. Our results show that AG can achieve acceleration while being more robust to random gradient errors. This behavior is quite different than previously reported in the deterministic gradient noise setting. We also establish some connections between the robustness of an algorithm and how quickly it can converge back to the optimal solution if it is perturbed from the optimal point with deterministic noise. Our framework also leads to practical algorithms that can perform better than other state-of-the-art methods in the presence of random gradient noise. △ Less

Submitted 5 November, 2019; v1 submitted 27 May, 2018; originally announced May 2018.

Comments: To appear in SIAM Journal on Optimization (SIOPT)

Sampling and Distortion Tradeoffs for Indirect Source Retrieval

Authors: Elaheh Mohammadi, Alireza Fallah, Farokh Marvasti

Abstract: Consider a continuous signal that cannot be observed directly. Instead, one has access to multiple corrupted versions of the signal. The available corrupted signals are correlated because they carry information about the common remote signal. The goal is to reconstruct the original signal from the data collected from its corrupted versions. The information theoretic formulation of the remote recon… ▽ More Consider a continuous signal that cannot be observed directly. Instead, one has access to multiple corrupted versions of the signal. The available corrupted signals are correlated because they carry information about the common remote signal. The goal is to reconstruct the original signal from the data collected from its corrupted versions. The information theoretic formulation of the remote reconstruction problem assumes that the corrupted signals are uniformly sampled and the focus is on optimal compression of the samples. In this paper we revisit this problem from a sampling perspective. We look at the problem of finding the best sampling locations for each signal to minimize the total reconstruction distortion of the remote signal. In finding the sampling locations, one can take advantage of the correlation among the corrupted signals. Our main contribution is a fundamental lower bound on the reconstruction distortion for any arbitrary nonuniform sampling strategy. This lower bound is valid for any sampling rate. Furthermore, it is tight and matches the optimal reconstruction distortion in low and high sampling rates. Moreover, it is shown that in the low sampling rate region, it is optimal to use a certain nonuniform sampling scheme on all the signals. On the other hand, in the high sampling rate region, it is optimal to uniformly sample all the signals. We also consider the problem of finding the optimal sampling locations to recover the set of corrupted signals, rather than the remote signal. Unlike the information theoretic formulation of the problem in which these two problems were equivalent, we show that they are not equivalent in our setting. △ Less

Submitted 5 December, 2016; v1 submitted 17 June, 2016; originally announced June 2016.

Comments: Under review