In this thesis, we investigate online dimensionality reduction methods, wherethe algorithms learn by sequentially acquiring data. We focus on two specificalgorithm design problems in (i) recommender systems and (ii) heterogeneousclustering from binary user feedback. (i) For recommender systems, we consider a system consisting of m users and n items. In each round, a user,selected uniformly at random, arrives to the system and requests a recommendation. The algorithm observes the user id and recommends an itemfrom the item set. A notable restriction here is that the same item cannotbe recommended to the same user more than once, a constraint referred toas a no-repetition constraint. We study this problem as a variant of themulti-armed bandit problem and analyze regret with the various structurespertaining to items and users. We devise fundamental limits of regret andalgorithms that can achieve the limits order-wise. The analysis explicitlyhighlights the importance of each component of regret. For example, we candistinguish the regret due to the no-repetition constraint, that generated tolearn the statistics of user’s preference for an item, and that generated tolearn the low-dimensional space of the users and items were shown. (ii) Inthe clustering with binary feedback problem, the objective is to classify itemssolely based on limited user feedback. More precisely, users are just askedsimple questions with binary answers. A notable difficulty stems from theheterogeneity in the difficulty in classifying the various items (some itemsrequire more feedback to be classified than others). For this problem, wederive fundamental limits of the cluster recovery rates for both offline andonline algorithms. For the offline setting, we devise a simple algorithm thatachieves the limit order-wise. For the online setting, we propose an algorithm inspired by the lower bound. For both of the problems, we evaluatethe proposed algorithms by inspecting their theoretical guarantees and usingnumerical experiments performed on the synthetic and non-synthetic dataset.

Denna avhandling studerar algoritmer för datareduktion som lär sig från sekventiellt inhämtad data. Vi fokuserar speciellt på frågeställningar som uppkommer i utvecklingen av rekommendationssystem och i identifieringen av heterogena grupper av användare från data. För rekommendationssystem betraktar vi ett system med m användare och n objekt. I varje runda observerar algoritmen en slumpmässigt vald användare och rekommenderar ett objekt. En viktig begränsning i vår problemformuleringar att rekommendationer inte får upprepas: samma objekt inte kan rekommenderas till samma användartermer än en gång. Vi betraktar problemet som en variant av det flerarmadebanditproblemet och analyserar systemprestanda i termer av "ånger” under olika antaganden.Vi härleder fundamentala gränser för ånger och föreslår algoritmer som är (ordningsmässigt) optimala. En intressant komponent av vår analys är att vi lyckas att karaktärisera hur vart och ett av våra antaganden påverkar systemprestandan. T.ex. kan vi kvantifiera prestandaförlusten i ånger på grund av att rekommendationer inte får upprepas, på grund avatt vi måste lära oss statistiken för vilka objekt en användare är intresserade av, och för kostnaden för att lära sig den lågdimensionella rymden för användare och objekt. För problemet med hur man bäst identifierar grupper av användare härleder vi fundamentala gränser för hur snabbt det går att identifiera kluster. Vi gör detta för algoritmer som har samtidig tillgång till all data och för algoritmer som måste lära sig genom sekventiell inhämtning av data. Med tillgång till all data kan vår algoritm uppnå den optimala prestandan ordningsmässigt. När data måste inhämtas sekventiellt föreslår vi en algoritm som är inspirerad av den nedre gränsen på vad som kan uppnås. För båda problemen utvärderar vi de föreslagna algoritmerna numeriskt och jämför den praktiska prestandan med de teoretiska garantierna.

This thesis contributes to the field of stochastic online learning problems, with a collection of six papers each addressing unique aspects of online learning and inference problems under specific structures. The first four papers focus on exploration and inference problems, uncovering fundamental information-theoretic limits and efficient algorithms under various structures. The last two papers focus on maximizing rewards by efficiently leveraging these structures.

The first paper addresses the complex problem of learning to cluster items based on binary user feedback for multiple questions. It establishes information-theoretical error lower bounds for both uniform and adaptive selection strategies under a fixed budget of rounds or users, and proposes an adaptive algorithm that efficiently allocates the budget.The second paper tackles the challenge of uncovering hidden communities in the Labeled Stochastic Block Model using single-shot observations of labels. It introduces a computationally efficient algorithm, Instance-Adaptive Clustering, which is the first to match instance-specific lower bounds on the expected number of misclassified items.The third paper delves into the best-arm identification or simple regret minimization problem within a Bayesian setting. It takes into consideration a prior distribution for the bandit problem and the expectation of simple regret with respect to that distribution, defining it as Bayesian simple regret.It characterizes the rate of Bayesian simple regret assuming certain continuity conditions on the prior, revealing that the leading term of Bayesian simple regret stems from parameters where the gap between optimal and suboptimal actions is less than . The fourth paper contributes to the fixed budget best-arm identification problem for two-arm bandits with Bernoulli rewards. It demonstrates the optimality of uniform sampling, which evenly samples the arms.It proves that no algorithm can outperform uniform sampling while being at least as good as uniform sampling for some bandit instances.The fifth paper revisits the regret minimization problem in sparse stochastic contextual linear bandits. It introduces a new algorithm, the Thresholded Lasso Bandit, which estimates the linear reward function and its sparse support, and then selects an arm based on these estimations. The algorithm achieves superior regret upper bounds compared to previous algorithms and numerically outperforms them.The sixth and final paper provides a theoretical analysis of recommendation systems in an online setting under unknown user-item preference probabilities and some structures. It derives regret lower bounds based on various structural assumptions and designs optimal algorithms that achieve these bounds. The analysis reveals the relative weights of the different components of regret, providing valuable insights into the efficient algorithms for online recommendation systems.

This thesis addresses the technical challenge of structured stochastic online learning problems, providing new insights into the power and limitations of adaptivity in these problems.

Denna avhandling bidrar till området för stokastiska online inlärningsproblem, med en samling av sex papper som var och en behandlar unika aspekter av online inlärning och inferensproblem under specifika strukturer. De första fyra pappren fokuserar på utforskning och inferensproblem, avslöjar grundläggande informationsteoretiska gränser och effektiva algoritmer under olika strukturer. De två sista pappren fokuserar på att maximera belöningar genom att effektivt utnyttja dessa strukturer.

Det första pappret behandlar det komplexa problemet att lära sig att klustra objekt baserat på binär användarfeedback för flera frågor. Det fastställer informationsteoretiska fel nedre gränser för både uniform och adaptiv urvalsstrategier under en fast budget av rundor eller användare, och föreslår en adaptiv algoritm som effektivt allokerar budgeten.Det andra pappret tar sig an utmaningen att avslöja dolda samhällen i den märkta stokastiska blockmodellen med enstaka observationer av etiketter. Det introducerar en beräkningsmässigt effektiv algoritm, Instance-Adaptive Clustering, som är den första att matcha instansspecifika nedre gränser för det förväntade antalet felklassificerade objekt.Det tredje pappret gräver djupt i problemet med bästa armidentifiering eller enkel ångerminimering inom en Bayesiansk miljö. Det tar hänsyn till en fördelning för banditproblemet och förväntan om enkel ånger med avseende på den fördelningen, vilket definierar det som Bayesiansk enkel ånger. Det karakteriserar hastigheten för Bayesiansk enkel ånger under antagande av vissa kontinuitetsvillkor på det tidigare, vilket avslöjar att den ledande termen för Bayesiansk enkel ånger kommer från parametrar där gapet mellan optimala och suboptimala handlingar är mindre än . Det fjärde pappret bidrar till det fasta budget bästa arm identifieringsproblemet för två-arm banditer med Bernoulli belöningar. Det demonstrerar optimaliteten av uniform provtagning, som jämnt provtar armarna. Det bevisar att ingen algoritm kan överträffa uniform provtagning samtidigt som den är minst lika bra som uniform provtagning för vissa banditinstanser.Det femte pappret återbesöker ångerminimeringsproblemet i glesa stokastiska kontextuella linjära banditer. Det introducerar en ny algoritm, Thresholded Lasso Bandit, som uppskattar den linjära belöningsfunktionen och dess glesa stöd, och sedan väljer en arm baserat på dessa uppskattningar. Algoritmen uppnår överlägsna ånger övre gränser jämfört med tidigare algoritmer och överträffar dem numeriskt.Det sjätte och sista pappret ger en teoretisk analys av rekommendationssystem i en online miljö under okända användarobjekt preferens sannolikheter och vissa strukturer. Det härleder ånger nedre gränser baserat på olika strukturella antaganden och utformar optimala algoritmer som uppnår dessa gränser. Analysen avslöjar de relativa vikterna av de olika komponenterna i ånger, vilket ger värdefulla insikter i effektiva algoritmer för online rekommendationssystem.

Denna avhandling behandlar den tekniska utmaningen med strukturerade stokastiska onlineinlärningsproblem, och ger nya insikter i kraften och begränsningarna av anpassningsförmåga i dessa problem.